Raft 协议学习笔记

1 前言

2 名词

3 什么是分布式一致性?

4 Raft选举

4.1 什么是leader选举

4.2 选举的实现

4.3 Term和Lease比较

4.4 选举图示

4.5 选举总结

5 Raft日志复制

5.1 什么是日志复制

5.2 日志复制的实现

5.3 脑裂时的日志复制

6 概念对比

7 共性探讨

7.1 PacificA&HBase&Kafka

7.2 Redis&Raft&ZAB&PoxOS

8 总结浓缩

8.1 三种角色

8.2 两种RPC

8.3 两个超时时间

9 参考

1 前言

常见的一致性协议主要有:PaxOS、Raft、ZAB、PacificA等。同PaxOS,Raft也不考虑拜占庭将军问题(Byzantine failures,注:比特币采用工作量证明PoW和股权证明PoS解决了拜占庭将军问题)。

2 名词

Distributed Consensus

分布式一致性

Distributed Consensus Algorithms

分布式一致性算法,PaxOS是分布式一致性算法的鼻祖,绝大多数的实现要么基于PaxOS,要么受PaxOS影响(如Zookeeper)。‍

PaxOS

就分布式系统中的某个值(在PaxOS中叫决议,即Proposer)达成一致的算法。PaxOS是分布式一致性协议的鼻祖,在Google的三大件未推出之前少为人知,1989年莱斯利·兰伯特提出。Leslie Lamport是大神的英文名,出生于1941年2月7日纽约。兰伯特目前就职于微软研究院,他也是排版系统LaTeX的作者,2008年获得冯诺依曼奖,2013年获得图灵奖,麻省理工学院学士和布兰戴斯大学博士。最早的实现为Google内部使用的Chubby。

Raft

木筏协议,一种共识算法,旨在替代PaxOS,相比容易理解许多。斯坦福大学的两个博士Diego Ongaro和John Ousterhout两个人以易懂为目标设计的一致性算法,2013以论文方式发布。由于易懂,不从论文发布到不到两年的时间,即出现大量的Raft开源实现。为简化PaxOS的晦涩,它采用分而治之的办法,将算法分为三个子问题:选举(Leader Election)、日志复制(Log Replication)、安全性(Safety)和集群成员动态变更(Cluster Membership Changes)。

ZAB

Zookeeper采用的一致性算法,全称“ZooKeeper Atomic Broadcast”,即Zookeeper原子广播协议,实为Zookeeper版本的PaxOS。

PacificA

微软2008年提出的日志复制协议,与PaxOS和Raft不同,PacificA并不提供Leader选举,因此需要结合PaxOS或Raft,分布式消息队列Kafka的ISR算法类似于PacificA。小米开源的KV系统Pegasus基于PacificA实现。

Viewstamped Replication

简称VR,最初被提出是作为数据库中的一部分工作,2012年作为单独的分布式共识算法再次发表。

Log Replication

日志复制

Leader Election

领导选举

Log

代表一个修改操作

Entry

(日志)条目(代表一个修改操作),Log在Raft中的实体,即一个Entry表示一条Log

Term

任期(可简单理解成租约,但稍有不同),是一个从0开始递增的整数值,每次发起选举时增一,最终所有节点的Term值是相同的。等同于ZAB协议中的zxid的高32位,即ZAB中的Epoch。

Index

和Term密切相关,Term针对的是选举,而Index针对的是一条Log,它的值也是从0开始递增。同样最终所有节点的Index也相同,如果两个节点的Term和Index均相同,则这两个节点的数据是完全一致的。等同于ZAB协议中的zxid的低32位。

Node

节点

Single Node

单节点

Multiple Nodes

多节点

Leader

领导(唯一接受修改操作的)

Follower

跟随者(投票参与者)

Candidate

候选人(唯一具有发起选举的)

Vote

投票

Heal

恢复,比如恢复网络分区(Heal the network partition)

Step Down

下台,当一个Leader发现有更大的Term时,自动降为Follower

Logic Clock

逻辑时钟,由Lampert提出,原因是分布式中无法使用精准的时钟维护事件的先后顺序,方法是为每个消息(或日志)加上一个逻辑时间戳。在ZAB协议中,每个消息均由唯一的zxid标识。zxid是一个64位无符号整数值,被分成两部分:高32位是Epoch,低32位是一个从0开始的递增值。类似于Raft的Term,每次选举新Leader,Epoch值增一,但同时zxid值清0。而Raft也类似,实际也是两部分组成,Term对应于Epoch,Index对应于zxid的低32位。

Quorum

法定人数

Brain Split

脑裂,同一个网络的节点被分成了两个或多个不互通的部分

3 什么是分布式一致性

多个节点(Multiple Nodes)的数据完全相同,即为分布式一致性。但因为多个节点通过网络互联,并不一定时刻可用,而服务不能因为某些节点(特别是少数节点)不可用时,导致整个系统不可用。

Raft将节点分成三种角色:Leader、Follower和Candidate,一个节点可为三种角色中的任意一种,但同一时刻只会为其中一种角色。正常情况下,只有Leader和Follower两种角色的节点,只有在选举时才会出现Candidate角色节点,而且可能多个节点同时处于Candidate角色同时竞争选举。

4 Raft选举

4.1 什么是leader选举

Raft协议中,一个节点有三个状态:Leader、Follower和Candidate,但同一时刻只能处于其中一种状态。Raft选举实际是指选举Leader,选举是由候选者(Candidate)主动发起,而不是由其它第三者。

并且约束只有Leader才能接受写和读请求,只有Candidate才能发起选举。如果一个Follower和它的Leader失联(失联时长超过一个Term),则它自动转为Candidate,并发起选举。

发起选举的目的是Candidate请求(Request)其它所有节点投票给自己,如果Candidate获得多数节点(a majority of nodes)的投票(Votes),则自动成为Leader,这个过程即叫Leader选举。

在Raft协议中,正常情况下Leader会周期性(不能大于Term)的向所有节点发送AppendEntries RPC,以维持它的Leader地位。

相应的,如果一个Follower在一个Term内没有接收到Leader发来的AppendEntries RPC,则它在延迟随机时间(150ms~300ms)后,即向所有其它节点发起选举。

采取随机时间的目的是避免多个Followers同时发起选举,而同时发起选举容易导致所有Candidates都未能获得多数Followers的投票(脑裂,比如各获得了一半的投票,谁也不占多数,导致选举无效需重选),因而延迟随机时间可以提高一次选举的成功性。

4.2 选举的实现

Raft中,和选举有关的超时值有两个:

选举超时(Election Timeout)

Follower等待成为Candidate的时间,为随机时间,随机范围为150ms~250ms。如果在超时之前收到了其它的AppendEntries,则重置选举超时重新计时,否则在选举超时后,Follower成为Candidate,投票给自己(Votes for itself)并发起新的选举任期(Term),发送RequestVote给所有其它节点,以请求投票给自己。如果在这个Term时间内仍然没有获得投票,则重置选举超时,以准备重新发起选举。而一旦获得多数节点的投票,则成为Leader。成为Leader后,定期性的发送AppendEntries给所有Followers,以维持Leader地位。发送AppendEntries的间隔叫作心跳超时。

心跳超时(Heartbeat Timeout)

Follower会应答每一个AppendEntries,一个选举任期(Election Term)会一直存在,直到有新的Follower成为Candidate。Leader节点通过定期发送AppendEntries维护自己的Leader地位,定期的间隔时长即为心跳超时时长。在Raft中,心跳方向是:Leader -> Follower。

如果一个Follower在一个Term时间内没有收到AppendEntries(并非要求是来自Leader的AppendEntries,其它Candidates也一样有效),则它成为Candidate,并在等待选举超时(Election Timeout)后发起选举。

要求获得多数节点的投票,可以保证每个任期(Term)内只有一个Leader。如果两个Candidates同时发起选举,则会分割投票,这样需要再重新发起选举。Raft设计“选举超时”,可以降低两个或多个Candidates同时发起选举的概率,减少连续重选举。

Redis的选举有个借鉴意义,在Redis集群中,不同节点可有不同权重,权重大的优先获得发起选举几率。在Redis中,权重是指复制节点数据的新旧程度,而对Raft来说可考虑机架机房等作为权重。

4.3 Term与Lease比较

Raft中的Term可以简单看成Lease(租约),但概念上仍然是有区别的。Lease通常是一个节点向一个中心化节点请求,而Term是无中心化的。

如果没有发生选举超时,则Term的值不会发生变化,否则至少增一。

4.4 选举图示

每个节点的Term值初始化为1(圆圈中的数字),每个节点选举超时时间为一个150ms~300ms的随机值(实际实现可以调整,但这个值是发明者测试得到的优值,详情请参见两位斯坦福大学教授的论文):

节点S2最先发起选举成为Leader,在发起选举之前,它需要先自增自己的Term值,因此Term值由1变成2,同时其它节点的Term值也需要更新为比自己大的Term值(如果一个Leader遇到一个更大的Term,它需要主动降为Follower):

人工将节点S1和S2停掉,这时两者不可用。这会导致其它正常的节点S3、节点S4和节点S5在选举超时时间内收不到来自Leader的心跳(实为AppendEntry),因此会触发节点S3、节点S4和节点S5发起选举(究竟哪个节点发起选举,视哪个节点最先达到选举超时):

因为节点S2的数据处于未提交状态,因为它的已提交Index值要小于S3和S5,它没有最新的数据,不可能成为新的Leader。新的Leader必然在S3和S5中产生。先强制重置S2的选举超时时长,以让出优先发起选举:

虽然S3和S5均有最新的数据,但因为S3的Term小于S5的Term,因此只有S5才能成为Leader,这样最新的Term值将为5+1为6:

这个时候恢复节点S1,Term值是否会改变?

一个Leader节点,如果遇到比自有更大的Term值,则主动放弃Leader身份,并使用原Term替代自己的Term,然后转变为Candidate重新开始选举。

非Leader节点也是一样的,只要遇到比自己大的Term,都会使用更大的Term替代自己的Term。这样能保证节点均能正常通信时,Leader节点总是持有最大的Term。

4.5 选举总结

能成为Leader的条件:

1) 有最大的Term;

2) 如果Term相同,则有最大的Index;

3) 如果Term相同,Index也相同,就看谁最先发起;

4) 最先发起者也不一定成为Leader,还得看谁最先获得多数选票。

一个Leader主动放弃Leader条件:

1) 遇到比自己更大的Term,这个时候会转为Follower。

5 Raft日志复制

5.1 什么是日志复制

Leader收到一个修改请求后,先将该请求记录到本地日志,这条日志在Raft中叫作Enry,此时处于未提交状态(Uncommitted),然后复制Entry给所有的Followers。当多数Followers节点确认已完成该Entry的写入后,Leader本地提交该Entry,响应客户端成功,这个过程叫日志复制(Log Replication)。如果一个Entry不能复制到多数节点,则该Entry状态一直为未提交,如果发生Leader转换,有可能被覆盖。

5.2 日志复制的实现

正常的复制不需要理解,主要看异常时的复制处理。让节点S5成为Leader,然后停掉节点S2、S3和S4,然后客户端再请求写操作,但此时由于写操作不能得到多数节点的确认,所以无法提交(不能应用到状态机中):

先停掉节点S1和S5,再恢复节点S2、S3和S4,并让节点S3成为Leader,然后客户端发起一笔写操作。让写操作在三个节点S2、S3和S4中得到确认,这样该笔写操作为已提交状态(Committed),可以看到变成如下状态了。显然节点S1和节点S5上存在了两笔脏数据:

恢复节点S1:

停止节点S3,构造条件让S1成为新的Leader:

5.3 脑裂时的复制

网络分裂时,出现两个Leader:

具有多数节点的一方仍然能够继续,但少数一方已不可用,这个时候从节点B读不到最新的数据:

当网络恢复后,节点B发现更大的Term,自动从Leader将为Follower,同时回滚未提交的Entries,集群又重新实现一致。

6 概念对比

Raft

PaxOS

ZAB‍

PacificA

Viewstamped Replication

获得多数同一

获得多数同一

获得多数同一

需所有都同意

获得多数同一

强Leader(领导),总是包含了最全最新的日志,日志无空洞,随机化简化Leader选举(Redis也采用了这个方法,并且加了节点权重)。

Proposer(提议者),允许有多个Proposer,并且不一定最包含了最全最新的日志,日志可存在空洞

强Leader(领导)‍

Primary(主)

Primary

Follower(跟随者)‍

Acceptor(接受者)

Follower(跟随者,参与投票)

Secondary(副),接收Primary的心跳,一个Primary对多个Secondary‍

Backup‍

Candidate(候选者)

Learner(学习者)

Looking(竞选状态)

Observing(观察者,不参与投票,只同步状态)

Entry

达到一致的叫Value(即决议),达到一致前叫提议

类似PaxOS

Term(任期)

Ballot(选票)

Epoch(纪元),为txid的高32位(注:Redis中也叫Epoch,作用类似)

View

Index(序号)

Proposal Number

txid的低32位

Serial Number

7 共性探讨

所有的并不是完全孤立的,而是存在很多共性。

7.1 PacificA&HBase&Kafka

PacificA和HBase均依赖于PaxOS这样的设施,HBase依赖于Zookeeper,PacificA同样依赖于类似的配置管理服务。

如同HBase依赖Zookeeper来发现Keys的位置信息,PacificA依赖配置管理服务发现分片的位置。

Kafka其实也类似,早期Kafka直接将位置信息存储在了Zookeeper中,遭遇了Zookeeper吞吐瓶颈,于是采取和HBase类似的做法,将位置信息作为一个特殊的Partition。

7.2 Redis&Raft&ZAB&PaxOS

Redis同Raft、ZAB和PaxOS并不是一类东西,但核心均有Quorum的朴素思想,即服从多数(多数人理解的即为真理),而且均依赖于一个递增的值来达到一致性状态,这个递增的值在Redis和ZAB中叫Epoch,Raft中叫Term。

8 总结浓缩

8.1 三种角色

1) Leader(领导者)

2) Follower(跟随者)

3) Candidate(候选人)

8.2 两种RPC

1) AppendEntry(心跳和写操作)

2) RequestVote(请求投票

8.3 两个超时时间

中文名

英文名‍

主要问题

小技巧

选举超时

Election Timeout

选票分裂造成活锁

随机时间(Redis非强一致,另加了权重)

心跳超时

Heartbeat Timeout

不能小于选举超时时长

9 参考

1) https://translate.google.cn

2) https://raft.github.io/raft.pdf

3) https://raft.github.io/

4) http://thesecretlivesofdata.com/raft/

5) PacificA:微软设计的分布式存储框架

6) 分布式共识(Consensus):Viewstamped Replication、Raft以及Paxos

7) https://static.googleusercontent.com/media/research.google.com/en//archive/paxos_made_live.pdf

- END-

原文发布于微信公众号 - 大数据手稿笔记(gh_fe6a620edd40)

原文发表时间:2019-06-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券