Raft一致性算法整理【原理笔记】

目录

一、Raft概述
1.Raft定义
2.复制状态机
3.Raft一致性
4.Raft新的特性
二、Raft一致性算法
1.State（状态）
2.AppendEntries RPC（日志追加远程过程调用）
3.RequestVote RPC（投票请求RPC）
4.Rules for Serve（服务器需要遵守的规则）
5.三种角色
6.任期
7.选主
8.日志复制
9.安全性
四、客户端交互
五、学习资料

一、Raft概述

1.Raft定义

Raft是一种用来管理日志复制的一致性算法。一致性算法允许一组机器像一个整体一样工作，即使其中的一些机器出了错误也能正常工作。

2.复制状态机

复制状态机(State Machine Replication)：通过复制服务副本，并和副本一起来协调客户端的交互，来实现容错服务。Raft复制状态机是通过复制日志来实现的，每一台服务器保存着一份日志。

3.Raft一致性

Raft实现一致性是首先选择一个确定的leader，然后leader负责管理日志复制。leader接受来自客户端的请求并追加到本地日志，然后把日志复制到其它的机器并告诉其它机器什么时候可以安全的将日志应用到状态机。集群存在一个leader的好处可以简化日志复制的管理。例如：leader可以决定日志的追加，而不需要经其它机器的同意。整个集群的数据流向也是从leader流向其它机器。如果leader宕机或者网络断开，其它的机器可以重新选举一个新的leader。 Raft一致性问题分解为3个相对独立的子问题 Leader election：当一个leader宕机后，一个新的leader必须被选举。 Log replication：leader必须响应客户端的请求，并把日志复制到整个集群来保证其它机器的日志和自己的相同。 Safety：状态机的安全是Raft优先保证的。如果任意一台机器将一条特定的日志应用到自己的状态机，那么其他的机器就不能应用一条不同的日志到自己的状态机。解决这个问题的方案就是在选举是增加额外的规则约束。

4.Raft新的特性

强领导者（Strong Leader）：日志条目只从领导者发送向其他服务器。 领导选取（Leader Selection）：Raft使用了随机定时器来选择leader。 成员变化（Membership Change）：Raft使用了一种联合一致性的方法，使得集群中的机器发生变更的时候，整个集群也可以正常的工作。联合一致性配置是两个不同配置的大多数机器的重叠。

二、Raft一致性算法

1.State（状态）

所有机器需要持久化的状态（在RPC响应之前，需要更新稳定存储介质） currentTerm 服务器存储的最新任期号从0开始递增 votedFor 在当前任期内收到选票的候选人id如果没有就为null log[] 日志条目；每个条目包含状态机的要执行命令和从领导人处收到时的任期号 所有机器的可变状态 commitIndex 将被提交的日志记录的索引从0开始递增 lastApplied 已经被提交到状态机的最后一个日志的索引从0开始递增 leader的可变状态(每次选举后重新初始化) nextIndex[] 每台机器在数组占据一个元素，元素的值为下条发送到该机器的日志索引(初始值为 leader最新一条日志的索引+1) matchIndex[] 每台机器在数组中占据一个元素，元素的记录将要复制给该机器日志的索引的从0开始递增

2.AppendEntries RPC（日志追加远程过程调用）

被leader用来复制日志；同时也被用作心跳。 Arguments： term leader任期 leaderId 用来follower重定向到leader prevLogIndex 前继日志记录的索引 prevLogTerm 前继日志的任期 entries[] 存储日志记录 leaderCommit leader的commitIndex

Results： term 当前的任期号，用于领导人更新自己的任期号 success 如果follower包含索引为prevLogIndex和任期为prevLogItem的日志

接受者的实现 1.如果leader的任期小于自己的任期返回false。 2.如果自己不存在索引、任期和 prevLogIndex、prevLogItem匹配的日志返回false。 3.如果存在一条日志索引和prevLogIndex相等，但是任期和prevLogItem不相同的日志，需要删除这条日志及所有后继日志。 4.如果leader复制的日志本地没有，则直接追加存储。 5.如果leaderCommit>commitIndex，设置本地commitIndex为leaderCommit和最新日志索引中较小的一个。

3.RequestVote RPC（投票请求RPC）

被候选者用来收集选票 Arguments： term 候选者的任期 candidateId 候选者编号 lastLogIndex 候选者最后一条日志记录的索引 lastLogTerm 候选者最后一条日志记录的索引的任期

Results： term 当前任期，候选者用来更新自己 voteGranted 如果候选者当选则为true

接受者的实现： 1.如果leader的任期小于自己的任期返回false 2.如果本地voteFor为空，候选者日志和本地日志相同，则投票给该候选者

4.Rules for Serve（服务器需要遵守的规则）

所有机器 1.如果commitIndex > lastApplied：增加lastApplied，并将日志log[lastApplied]应用到状态机 2.如果RPC的请求或者响应中包含一个term T大于currentTerm，则currentTerm赋值为T，并切换状态为追随者（Follower） 追随者/参与者（followers） 1.响应来自候选者或者leader的请求 2.如果在超过选取领导人时间之前没有收到来自当前领导人的AppendEntries RPC或者没有收到候选人的投票请求，则自己转换状态为候选人

候选人（candidate） 1.一旦变为候选者，则开始启动选举 1.1 currentTerm自增 1.2 选举自己 1.3 重置选举定时器 1.4 并行发送选举请求到其他所有机器 2.如果收到集群大多数机器的选票，则称为新的leader 3.如果收到了来自新领导人的AppendEntries RPC（heartbeat）转换为追随者 4.如果选举超时开始新一轮的选举

领导者（leaders）： 1.一旦成为领导人：向其他所有服务器发送空的AppendEntries RPC（heartbeat）; 在空闲时间重复发送以防止选举超时 2.如果接受到来自客户端的请求，追加日志记录到本地日志，如果成功应用日志记录到状态机则回应客户端。 3.如果某个参与者的最新日志索引大于等于本地存储该参与者的最新日志索引：给该参与者发送包含从 nextIndex开始的日志追加请求。 3.1 如果成功，更新该参与者的 nextIndex和matchIndex。 3.2 如果由于日志不一致而失败，减少nextIndex并重试。 4.如果存在N > commitIndex（本地待提交日志的索引），majority(matchIndex[i]>= N)（如果参与者大多数的最新日志的索引大于 N），并且这些参与者索引为N的日志的任期也等于leader的当前任期：commitIndex=N（leader的待提交的日志索引设置为N）

Raft 一致性算法的总结 选举安全原则（Election Safety） 在一个给定的任期最多只可以选举出一个leader。 领导人只增加原则（Leader Append-Only）对于一个leader它永远不会重写和删除日志中的日志记录，它只会追加日志记录。 日志匹配原则（Log Matching） 如果两个日志文件中存在相同索引和任期的日志记录那么两个日志文件所有的日志记录在给定索引情况下是相同的。 领导人完全原则（Leader Completeness) 如果一条日志在一个给定的任期已经提交，那么这条日志将会出现在所有任期大于给定任期的leader的日志中。 状态机安全原则（State Machine Safety）如果一个server已经将给定索引的日志应用到状态机，别的server将不能应用一个相同索引但内容不同的日志记录到自己的状态机。

5.三种角色

任意时刻，一台server会处在三种状态中的一种：leader、follower和candidate。 正常情况下，集群中包含一个leader和参与者。集群中的参与者是被动的，它们不会主动解决问题而是被动的响应leader或者参与者的请求。集群中leader负责处理所有的客户端请求，如果一个客户端的请求连接到了参与者，这个参与者会将请求重定向到leader。候选者是在选举中可能成为leader的状态。

6.任期

Raft将时间分为任意长度的间隔，每个间隔是一个任期。每个任期会由一个连续的整数进行表示。每个任期都是从选举开始的，在这个阶段会有一个或者多个候选者参与竞选。一旦某个候选者在选举中胜出，这个任期剩下的时间将有这个候选者作为leader。 一些特殊的情况下，一次选举可能出现选举分裂的情况。选举分裂的情况下，当前任期将不会选举出leader。紧接着一个新的任期将会启动重新进行选举。Raft通过上面的过程保证每个任期只会选举出至多一个leader。 当servers进行通讯的时候，也会交换当前的任期。如果一个 server 存储的任期小于其他机器存储的任期，那么它将更新自己的任期到其它机器存储的最大任期。如果是一个候选者或者leader发现自己的任期已经过期，它们会转变到参与者的状态。如果一个server接受到一个请求，这个请求中的任期是过时的，它将直接拒绝该请求。

7.选主

Raft使用心跳机制来触发选主的过程。当servers启动的时候，都是作为参与者。如果一个参与者收到来自leader或者候选者的合法请求，它将保持在参与者的状态。leader会发送心跳到其它的server来授权延长自己的任期。如果一个参与者的选举定时器超时的时候还没有收到任何请求，它可以假设整个集群没有可用的leader或者候选者，然后发起新的选举。 一次选举开始时，参与者增加自己本地存储的当前任期然后转变为候选者状态。这个候选者先选举自己，并行的给集群中的其它机器发送 RequestVote RPCs。 候选者将会一直保持候选状态直到下面三件事情中的任意一件发生：（a）：候选者本次选举胜出（b）：另外一台机器确认自己是leader（c）：僵持一段时候没有人胜出。 一个候选者如果接受到集群中大多数机器在同一个任期的选票，么它将胜出成为leader。每台机器在一个任期只能投票给一个候选者，按照先到先服务的原则。大多数投票胜出规则可以保证在一个特定的任期至多选出一个leader。一旦一个候选者胜出将成为集群的leader，它将会并行的给集群的其它机器发送心跳来宣示自己胜出，并阻止进行新的选举。 在等待选票的过程中，一个候选者可能接受到来自其它server的请求，该请求声明自己已经成为 leader。如果请求中的leader的任期大于候选者本地存储的任期，那么当前候选者认为这个leader 是合法的并转变为参与者状态。如果请求中leader的任期小于当前候选者本地存储的任期，那么候选将拒绝这个请求并保持在候选者状态。 第三种可能是是整个集群的所有候选者都没有胜出。如果集群中所有的参与者同一时刻转变为候选者， 由于每个机器只能投票给一个候选者，这种情况新会很容易发生选举分裂即没有一个候选者获得半数以上选票。当这种情况发生，所有的候选者的选举定时器将会超时，它们增加自己本地存储的任期并启动新一轮的选举。从上面可以看出如果没有额外的规则约束，选举分裂的情况将极易发生。 Raft通过随机选举定时器来阻止选举分裂的发生，即使选举分裂发生也可以很快的被解决。选举超时将在 [150,300]ms之间随机生成，这样就大概率保证集群中会有一个机器会先超时，而避免所有机器同时超时从而降低选举分裂情况发生的概率。如果首先超时的机器将会首先转变为候选者，它将会大概率的选举胜出成为leader，然后发送心跳续阻止其它机器定时器超时。

8.日志复制

一旦一个候选者成为leader，它将开始处理客户端的请求。客户端的每个请求包含了一条需要执行到状态机的命令。leader将命令追加到自己的日志记录，同时并发AppendEntries RPCs请求来进行日志复制。当日志安全的复制之后，leader 将日志应用到自己的状态机并将结果返回给客户端。如果集群中有参与者宕机、处理速度慢、网络丢包等情况发生，leader将重试AppendEntries RPCs请求直到日志被安全的复制。 leader来决定将一条日志应用到状态机的安全时机。这样的一条日志被称为committed。Raft来保证日志的持久化并且所有已提交的日志将会都会被应用到状态机。一旦leader将一条日志成功的复制到集群的大多数机器，那么这条日志就是已提交状态。如果当前日志记录已提交，那么由前任leader或者当前leader创建的前继日志记录都会被提交。leader维护了即将被提交的日志记录的索引，并把这个索引放在未来的AppendEntries RPCs请求中。当参与者从请求获知已提交的索引，它会将本地该索引的日志应用到状态机。

Log Matching Property

如果两个日志的两条日志记录有相同的索引和任期，那么这两条日志记录中的命令必然也是相同的。 如果两个日志的两条日志记录有相同的索引和任期，那么这两个日志中的前继日志记录也是相同的。 在一个给定的任期，leader创建的日志索引是递增不重复的，一旦日志某条日志创建后是不会改变它在日志中位置。上面的事实保证了第一个性质的成立。每次当leader发送AppendEntries RPCs请求的时候，请求中会包含当前正在复制的日志记录的直接前继的任期和索引，如果参与者在自己的日志中没有发现有相同任期和索引的日志记录，它将直接拒绝请求。上面描述的一致性检测保证第二个性质的成立。一致性检测的步骤如下：初始化时候是满足Log Matching Property的；当有追加日志的时候进行一次一致性检测来保护Log Matching Property。这样当leader接受到返回成功的 AppendEntries RPCs请求时，说明了参与者与自己的日志是相同的。 正常情况下，leader 和参与者的日志都是相同的，日志一致性检测也不失败。当leader崩溃的时候就会导致日志的不一致，例如旧的leader没有将自己的日志记录安全的复制到其它机器。这些不一致可能聚合多个leader和参与者的崩溃。一个参与者可能缺失了leader有的日志记录，它也可能多出了leader没有的日志，或者上面的两种情况同时发生。缺失或多余的日志可能存在在多个任期。 Raft 是通过强制参与者只能复制leader的日志来解决不一致。这就意味者参与者的日志和leader的日志发生冲突的时候，参与者的日志将会重写或者删除。在额外附加的约束下上面的过程是安全的。 如果一致性检测失败后，为了保证参与者和自己的日志一致，leader需要先确认参与者和自己一致的最后一条日志记录。然后通知参与者删除这条日志记录后面的日志，并将这条日志记录之后的日志复制给参与者。leader为每个参与者维护了nextIndex，这个索引记录了leader将复制给该参与者的日志索引。当一个leader选举生效后，它将初始化nextIndex为它自己日志记录中最后一条日志记录的索引。如果leader的日志和参与者的日志不一致那么下一轮的AppendEntries RPCs进行AppendEntries一致性检测的时候就会发现。如果检测发生不一致，leader将会减少nextIndex并重试。经过多次重试leader就会确定参与者和自己一致的日志索引，然后通知参与者删除后面不一致的日志，然后复制自己的日志给参与者。经过上面的过程leader和参与者的一致就可以恢复一致。 上面过程中每次nextIndex减少1进行重试效率是存在问题的，但是也是可以优化的。一旦参与者进行日志一致性检测发现不一致之后，在响应leader请求中包含自己在这个任期存储的第一条日志。这样 leader接受到响应后，就可以直接跳过所有冲突的日志（其中可能包含了一致的日志）。这样就可以减少寻找一致点的过程。但是在实际中我们怀疑这种优化的必要性，因为失败发生的概率本来就很低，也不会同时存在大量不一致的日志记录。 使用上面的机制，一个leader生效的时候就不需要进行额外的操作来恢复日志的一致性。它只需按照正常的流程，日志的不一致经过多次AppendEntries RPCs一致性检测后会自动收敛。leader也不需要重写和删除本地日志。 Raft可以在集群只有半数以上存活的情况下接受、复制和应用新的日志记录；正常情况下只需要一轮 RPCs可以将日志记录复制到集群的大多数；单个速度慢的参与者不会影响整个集群的性能。

9.安全性

上面描述了Raft的选主和日志复制。但是目前所描述的机制还不能安全的保证日志是按照相同顺序被应用到状态机。例如：在leader提交了若干条日志后，某个参与者宕机并被选为新的leader。新的leader重写其它机器的日志，结果导致不同的状态机有不同的命令序。我们通过添加额外约束控制某些机器能被选举为leader来完善Raft算法。这个约束保证当选的leader包含了前任所有提交的日志。 通过约束我们可以精准的控制日志的提交。

选举约束:

Raft使用的方法是每个当选的leader必须之前所提交的所有日志，这种方法带来的好处是集群中数据的流向只能是从leader到参与者，leader永远仅需要追加即可。 Raft 使用选举过程来保证一个候选者必须包含有所有已提交的日志才能胜出。候选者为了胜出必须联系集群中的大多数机器，这就意味着每条日志至少出现在机群中的某一台机器上。如果候选者的日志如果比集群其它任意一台机器的日志更新（下面精确定义“更新”），那么它将包含所有已提交的日志。RequestVote RPCs来实现这个约束：请求中包含了 leader 的日志信息，如果投票者的日志比候选者的日志更新，那么它就拒绝投票。 两个日志文件谁的日志更新是通过比较日志中最后一条日志记录的任期和索引。如果两个日志文件的最后一条日志的任期不相同，谁的任期更大谁的的日志将更新。如果两条日志记录的任期相同，那么谁的索引越大，谁的日志将更新。

提交上一个任期的日志

如果当前任期的一条日志已经被复制到集群中的大多数，那么leader可以确定这条已经已经处于提交状态。如果上任leader在提交日志之前宕机，下一任leader将尝试完成日志的复制。然而，尽管上一任期的某条日志已经被复制到了大多数机器，但是新任leader还是不能准确断定这条日志是否是已提交。 Raft不能根据上一任期的日志是否被复制到大多数机器来决定是否提交日志。一旦当前任期看到一条日志被提交，由于Log Matching Property保证，那么这条日志之前的日志已自动被提交。

三、集群成员变更

在实际系统中，我们有时候可能需要变更配置，例如需要替换宕机的机器或者增加日志的副本数。为了保证安全，配置变更采用两阶段的方法。这里有很多方法可以实现两阶段，例如：有的系统在第一个阶段来停止旧配置，这样就不能响应客户端的请求；然后第二阶段切换到新配置。Raft集群第一阶段 会过渡到迁移配置（我们称之为联合一致性配置joint consensus）；一旦联合一致性被提交，系统将切换到新配置。joint consensus配置组合了老配置和新配置。

四、客户端交互

Raft的客户端将自己的请求发送到leader。当一个客户端首次启动，它会随机的选择集群的一台机器。如果客户端的首次选择不是leader，这台机器将拒绝客户端的请求，并会告知自己最近监听到的 leader。如果leader宕机，客户端的请求将会超时，客户端可以随机的选择机器进行重试。 Raft的目标是实现线性语义（每个操作都是立刻被执行的），然而，目前为止我们描述的 Raft可以重复多次的执行一条命令；例如，如果leader提交了日志但是还没有来得及响应客户端就宕机，那么客户端将会换一个leader重试之前的命令。解决方法就是客户端给每个命令一个唯一的编号，那么，状态机记录每个客户端处理的最新的编号。一旦接受到一条命令它的序列号已经被执行过，直接响应这个请求但是不重新执行这个请求。

五、学习资料

本文笔记整理自Raft论文译文，全文详见以下链接。 Raft论文译文 https://github.com/brandonwang001/raft_translation/blob/master/raft_translation.pdf Raft论文原文 https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf Raft动画 http://thesecretlivesofdata.com/raft/ Raft可视化操作 https://raft.github.io/