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- 

长按二维码关注公众号

这么长都看完了 点个在看吧↓