raft协议浅析-ag真人游戏

什么是raft协议？

对于分布式系统而言，与单机系统相比优势之一就是有更好的容错性。比如当一台机器上的磁盘损坏，数据丢失，可以从另一台机器上的磁盘恢复（分布式系统会对数据做备份），集群中某些机器宕机，整个集群还可以对外提供服务。实现的方法很自然的想到的就是备份。
一个系统的工作模式：接受客户端的command，系统进行处理，将处理的结果返回给客户端。由此可见，系统里的数据可能会因为command而变化。
实现备份的做法之一就是复制状态机（repilcated state machine，rsm），它有一个很重要的性质——确定性（deterministic）：如果两个相同的、确定性的状态从同一状态开始，并且以相同的顺序获得相同的输入，那么这两个状态机将会生成相同的输出，并且结束在相同的状态
　　也就是说，如果我们能按顺序将command作用于状态机，它就可以产生相同的状态和相同的输出。

　　那么，状态机该如何实现？见下图（来自raft协议）

　　上图中，每个rsm都有一个replicated log，存储的是来自客户端的commands。每个rsm中replicate log中commads的顺序都是相同的，状态机按顺序处理replicate log中的command,并将处理的结果返回给客户端。由于状态机具有确定性，因此每个状态机的输出和状态都是相同的。
consensus module模块的作用是：保证每个server上log的一致性！如果不做任何保障，直接将commad暴力写入，一旦服务器宕机或者出现什么其他故障，就会导致这个log丢失，并且无法恢复。而出现故障的可能性是很高的，这就导致系统不可用。

　　因此，raft就是consensus module的一个实现，是用来保障servers上副本一致性的一种算法，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。

consensus一致性

　　再了解raft协议之前，首先了解一下一致性这个概念。consensus一致性是指多个服务器在状态达成一致，但是在一个分布式系统中，因为各种意外可能，有的服务器可能会崩溃或变得不可靠，它就不能和其他服务器达成一致状态。这样就需要一种consensus协议，一致性协议是为了确保容错性，也就是即使系统中有一两个服务器当机，也不会影响其处理过程。

raft为了实现consensus一致性这个目标，过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。在raft中，任何时候一个服务器可以扮演下面角色之一：

leader: 处理所有客户端交互，日志复制等，一般一次只有一个leader.
follower: 类似选民，完全被动
candidate候选人: 类似proposer律师，可以被选为一个新的领导人

　　通常情况下（无主备切换时），一个leader其他是follower。follower处于被动的状态，它不能发起任何请求，只能回应leader和candidate的请求。leader处理客户端的请求，如果客户端请求发到了follower，follower负责将请求重定向到leader。candidate是选主过程中用于选出新主。

term

　　raft将时间划分为term。term可以是任意长度的时间段。term有一个连续递增的id。每个term以选主开始，选主过程中，若干candidate尝试成为leader。选主过程成功之后进度normal operation的阶段，leader开始服务。选主可能因为选票分裂而失败，此时当前term没有leader，在下一个term继续选主。

　　term是需要持久化保存的。因为是分布式环境，所以不同的机器维护的term可能不一样，term是一个逻辑时钟（参见分布式系统下的时间时钟事件序论文解读），因此，当一台机器在与其他机器通信时发现自己的term比较小，应该推进本地的term。如果一台机器发现请求方的term比较小，则要拒绝请求。如果一个candidate发现自己的term落后了，就要退回到follower。

　　机器之间使用rpc通信，raft中只有两种rpc：requstvote和appendentries。requstvote rpc用于candidate在选主期间拉票。appendentries rpc用于leader复制日志到follower，同时也作为主备之间的心跳rpc。rpc请求收不到任何结果时，要定时重试。为了优化性能，rpc可以并发发起。

raft协议原理：

election safty ：每一个任期内只能有一个领导人
leader append-only：leader只能追加日志条目，不能重写或者删除日志条目
log maching：如果两个日志条目的index和term都相同，则两个如果日志中，两个条目及它们之前的日志条目也完全相同
leader completeness：如果一条日志被commited过，那么大于该日志条目任期的日志都应该包含这个点，也就是说当一个新的leader产生时它一定包含着前一个leader所处理过的commited点。
state machine safety ：如果一个server将某个特定index的日志条目交由状态机处理了，那么对于其他server，交由状态及处理的log中相同index的日志条目应该相同

如何保证election safty

　　raft中，只要candidate获得多数投票，就可以成为领导人。follower在投票的时候遵循两个条件：

先到先得
cadidate的term大于follower的term，或者两个term相等，但cadidate的index大于follower的index

对于选举结果来说：

如果票被瓜分，产生两个leader，这次选举失效，进行下一轮的选举
只有一个leader的情况是被允许的

　　这里重要的一点是：如何保证在有限的时间内确定出一个候选人，而不会总是出现票被瓜分的情况？*raft使用了一个比较优雅的实现方式，随机选举超时(randomize election timeouts)。*这就使得每个server的timeout不一样，发起新一轮选举的时候，有些server还不是投票者;或者一些符合条件的candidate还没有参加下一轮。这种做法使得单个leader会很快被选举出来。

如何保证log matching

　　leader在进行appendentry rpcs（添加消息）的时候，这个消息中会携带prelogindex和prelogterm这两个信息，follower收到消息的时候，首先判断它最新日志条目的index和term是否和rpc中的一样，如果一样，才会append。

　　这就保证了新加日志和其前一条日志一定是一样的。从第一条日志起就开始遵循这个原理，很自然地可以作出这样的推断。
　　
　　

如何保证leader completeness

　　假设leaderu是第一个没有包含leadert中committ点（t

raft协议中有一个约定，不能提交之前任期内log 记录作为commit点。

原因是如果在这一过程中，发生了网络分区或者网络通信故障，使得leader不能访问大多数follwers了，那么leader只能正常更新它能访问的那些follower服务器，而大多数的服务器follower因为没有了leader，他们重新选举一个候选者作为leader，然后这个leader作为代表于外界打交道，如果外界要求其添加新的日志，这个新的leader就按上述步骤通知大多数followers，如果这时网络故障修复了，那么原先的leader就变成follower，在失联阶段这个老leader的任何更新都不能算commit，都回滚，接受新的leader的新的更新。

选主过程

　　raft使用了心跳机制来触发选主。server刚启动时，状态处于follower，只要follewer一直收到leader或者candidate发来的rpc，就保持为follower。leader周期性地向follower发送心跳（用的是appendentries rpc，里面不带日志内容）来保持leader的权限。如果一个follower在election timeout时间内没有收到leader的心跳，follower就认为没有leader了，就会开始选主。

　　开始选主时，follower先递增本地term（要持久化），然后主机状态切换为candidate。然后主机向其他发送拉票请求，同时也给自己投票。candidate在这个状态等待，直到如下三种情况发生：
　　

该candidate赢得了选主
其他机器成为了leader
超时间内未能选主成功

　　一个candidate赢得选主的判定：在相同的term内，收到了多数派的投票。在给定的term内，每台机器都只能按照先来先服务的规则投一个candidate（要持久化）。收到多数派才可能成为leader，可以避免出现双主。选主成功之后，新主向其他主机发送心跳appendentries rpc，宣告自己当选了。
在选主时间内， candidate如果收到了其他主机宣告当选的心跳appendentries rpc且rpc中携带的term比本机维护的term更大或相等，本机就自动退为follower。
　　超时时间未能内选主成功，可能是发生了选票分裂。同时有若干参与者拉票，选票分流，没有candidate能够拉倒多数派的选票。选主失败时，所有candidate递增term开始下一轮。为了减少选票分裂出现的概率，选举超时时间使用随机化的方法避开多个candidate同时拉票。
　　
raft的选主方案的进化。一开始raft使用的是ranking system，每个candidate都分配一个唯一的rank，低rank的主机收到高rank的主机的拉票请求，就把自己转为follower，这样rank高的就能尽快被选出来（可能在下一轮选主中）。这个方案有些微妙的可用性问题：如果高rank的主机宕机了，低rank的主机还要等超时才有机会转为candidate。这个方案调整了几次，每次调整都引入新的corner case。最后才选择了这个随机化方案。
　　raft的选主方案还要加上一些约束，以支持log replication实现。

日志同步

　　leader被选出来之后，就开始服务客户端的请求。leader收到客户端请求之后，将命令记入日志并同步到follower。当这条日志被确认之后，就把日志对应的命令应用到状态机。如果某个follower没有收到appendentries rpc，leader会不停地重试，确保follower最终有全部的日志。
　日志组织发方式如下图所示：
　

每条日志都记录了term值，这个值是提交这条日志的leader当时的term值。这个term值可以用以检测不一致性。
当leader将日志复制到多数派的时候，这条日志就commit了。raft保证任何commit的日志最终都会被副本的状态机执行。
raft约束日志是连续commit的，leader维护最大已经commit的日志id，并将这个信息附加到appendentries告知follower，follower了解到之后即可将本机已有的且已经commit的日志应用到本地的状态机。
raft维护了更高级别的不同主机之间的日志的一致性，简化了系统的行为、使得系统行为更加可预测、更容易保证safety。

　　正常运行时，主备之间通常都是一致的，appendentries rpc也一直成功。但是如果有leader宕机了，就会有不一致。例如如图。

最上面这个是新leader，a~f是follower，每个格子代表一条log entry，格子内的数字代表这个log entry是在哪个term上产生的。再上面的图中x<-1，y<-2这种写法代表每一次日志记录的内容。

　　主备不一致可能有如下几种情况：

少了一些日志（term可能相同或者少了）比如b；
多了一些未commit的日志（term可能多了也可能少了）比如d；
某些term多了一些日志且某些term少了一些日志，比如f。

raft中如何解决这些不一致呢？leader强制让follower的日志文件复制leader的日志文件，即follower上不一致的日志文件内容被覆写。新主上任之后，在和某个follower同步日志时，先确定和这个follower最后一条相同的日志，然后用leader上的内容覆盖之后不相同的部分。

　　leader确定与follower不一致点的方法：

leader维护一个log index，表示leader给各个follower发送的**下一条**log entry在log中的index。初始化为leader的最后一条log entry的下一个位置。
然后发送appendentries rpc到follower。follower在收到appendentries之后，检查rpc中携带的leader上被追加的这条日志的前面一条日志的term和log index(logindex-1)。
如果follower本地没有这条日志，就拒绝此次appendentries rpc，leader就能知道follower的同步点更靠前，逐渐就能知道同步点的位置。当然，实际实现时，会使用更有效率的方法。

以leader和b为例：

初始化，logindex为11，leader给b发送appendentriesrpc(6,10)，b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。
接着，leader将logindex减1，变成10，然后给b发送appendentriesrpc(6, 9)，b在自己log的9号槽位中同样没有找到term_id为6的log entry。
循环下去，直到leader发送了appendentriesrpc(4,4)，b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。
随后，leader就可以从槽位5开始给b推送日志了。

safety

election restriction(选主限制)-哪些follower有资格称为leader。

　　如果不对选主加约束，那么，可能一个落后的follower被选为主，落后的那些日志可能已经commit了，要保证提交的日志匹配，就必然要有从旧主或者其他不落后的follower上拉取这些已经提交的日志。
　　
raft使用的方案是：确保包含所有commit日志的candidate才能有机会被选为leader。因为一条日志commit，必然在任意一个多数派中，至少有一台主机包含了这条日志。选举时，candidate要和至少多数派的主机通信，通信时带上自己本地的日志信息（本地最后一条的term和log index），接收消息的主机发现发送消息的candidate的日志并不比我本地更新，就拒绝投票。也就是说，candidate至少是某个多数派中拥有最新日志的主机，才能被选为leader。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。

哪些日志记录被认为是commited?

leader正在复制当前term（即term 2）的日志记录给其它follower，一旦leader确认了这条log entry被大多数写盘了，这条log entry就被认为是committed。如图下雨，s1作为当前term即term2的leader，log index为2的日志被大多数写盘了，这条log entry被认为是commited。
leader正在replicate更早的term的log entry给其它follower。图b的状态是这么出来的：
- s1作为term2的leader，给s1和s2 replicate完log index=2的日志后宕机，当前状态为：
  
  s1 1 2 宕机
  
  s2 1 2
  
  s3 1
  
  s4 1
  
  s5 1
- s5被选为term3的leader(由于s5的最后一条log entry比s3，s4的最后一条log entry更新或一样新，接收到s3，s4，s5的投票)，自己产生了一条term3的日志，没有给任何人复制，就crash了，当前状态如下：
  
  s1 1 2
  
  s2 1 2
  
  s3 1
  
  s4 1
  
  s5 1 3 宕机
- 接着s1重启后，又被选为term4的leader(接收到s1，s2，s3的投票，文中没有指出s4？)，然后s1给s3复制了log index为2的log entry，当前状态如下：
  
  s1 1 2
  
  s2 1 2
  
  s3 1 2
  
  s4 1
  
  s5 1 3 宕机
- 这个时候s5重启，被选为了term5的主(接收了s2，s3，s4，s5的投票)，那么s5会把log index为2的日志3复制给其它server，那么日志2就被覆盖了。
所以虽然这里日志2被majority的server写盘了，但是并不代表它是commited的。

对commit加一个限制：主的当前term的至少一条log entry要被大多数写盘。如：c图中，就是主的当前term 4的一条log entry被majority写盘了，假设这个时候s1宕机了，s5是不可能变成主的。因为s2和s3的log entry的term为4，比s5的3大。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。raft采用对整个系统进快照行来处理，快照之前的日志都可以丢弃。

每个server独立的对自己的系统状态进行快照，并且只能对已经committed log entry(已经应用到了状态机)进行快照，快照有一些元数据，包括last_included_index，即快照覆盖的最后一条commited log entry的 log index，和last_included_term，即这条日志的termid。这两个值在快照之后的第一条log entry的appendentriesrpc的一致性检查的时候会被用上，之前讲过。一旦这个server做完了快照，就可以把这条记录的最后一条log index及其之前的所有的log entry都删掉。
snapshot的缺点就是不是增量的，即使内存中某个值没有变，下次做snapshot的时候同样会被转存到磁盘。

当leader需要发给某个follower的log entry被丢弃了(因为leader做了快照)，leader会将快照发给落后太多的follower。或者当新加进一台机器时，也会发送快照给它。

发送快照时使用新的rpc，installedsnapshot。

做snapshot有一些需要注意的性能点：

不要做太频繁，否则消耗磁盘带宽。
不要做的太不频繁，否则一旦server重启需要回放大量日志，影响availability。系统推荐当日志达到某个固定的大小做一次snapshot。
做一次snapshot可能耗时过长，会影响正常log entry的复制。这个可以通过使用写时复制的技术来避免快照过程影响正常log entry的复制。

集群拓补变化

集群拓扑变化的意思是在运行过程中多副本集群的结构性变化，如增加/减少副本数、节点替换等。raft协议定义时也考虑了这种情况，从而避免由于下线老集群上线新集群而引起的系统不可用。raft也是利用上面的log entry和一致性协议来实现该功能。假设在raft中，老集群配置用cold表示，新集群配置用cnew表示，整个集群拓扑变化的流程如下：

当集群成员配置改变时，leader收到人工发出的重配置命令从cold切成cnew；
leader副本在本地生成一个新的log entry，其内容是cold∪cnew，代表当前时刻新旧拓扑配置共存，写入本地日志，同时将该log entry推送至其他follower节点
follower副本收到log entry后更新本地日志，并且此时就以该配置作为自己了解的全局拓扑结构，
如果多数follower确认了cold u cnew这条日志的时候，leader就commit这条log entry；
接下来leader生成一条新的log entry，其内容是全新的配置cnew，同样将该log entry写入本地日志，同时推送到follower上；
follower收到新的配置日志cnew后，将其写入日志，并且从此刻起，就以该新的配置作为系统拓扑，并且如果发现自己不在cnew这个配置中会自动退出
leader收到多数follower的确认消息以后，给客户端发起命令执行成功的消息

异常分析

如果leader的cold u cnew尚未推送到follower，leader就挂了，此时选出的新的leader并不包含这条日志，此时新的leader依然使用cold作为全局拓扑配置
如果leader的cold u cnew推送到大部分的follower后就挂了，此时选出的新的leader可能是cold也可能是cnew中的某个follower；
如果leader在推送cnew配置的过程中挂了，那么和2一样，新选出来的leader可能是cold也可能是cnew中的某一个，那么此时客户端继续执行一次改变配置的命令即可
如果大多数的follower确认了cnew这个消息后，那么接下来即使leader挂了，新选出来的leader也肯定是位于cnew这个配置中的，因为有raft的协议保证。

问题分析

这里为什么要弄这样一个两阶段协议，而不能直接从cold切换至cnew？

这是因为，如果直接这么简单粗暴的来做的话，可能会产生多主。
- 假设cold为拓扑为(s1, s2, s3)，且s1为当前的leader。
- 假如此时变更了系统配置，将集群范围扩大为5个，新增了s4和s5两个服务节点，这个消息被分别推送至s2和s3，但是假如只有s3收到了消息并处理，s2尚未得到该消息。
- 这时在s2的眼里，拓扑依然是(s1, s2, s3)，而在s3的眼里拓扑则变成了(s1, s2, s3, s4, s5)。假如此时由于某种原因触发了一次新的选主，s2和s3分别发起选主的请求：
- 最终，候选者s2获得了s1和s2自己的赞成票，那么在它眼里，它就变成了leader，而s3获得了s4、s5和s3自己的赞成票，在它眼里s3也变成了leader，那么多leader的问题就产生了。而产生该问题的最根本原因是s2和s3的系统视图不一致。