Raft算法的学习与理解

这篇文章小秦学习了下Raft算法,和PAXOS一样,也是个分布式算法。

算法的原理其实很简单,《In Search of an Understandable Consensus Algorithm》这个论文中写的比较详细,这里记录下算法的一些注意点,帮助大家更快的理解下这个算法。另外推荐大家看下:https://raftconsensus.github.io/#implementations

理解算法时候的注意点:
1.在leader出问题之前,可以保证大多数的server其term是相等的
2.在leader出问题后,leader如果还是leader,则其term不会变。剩余的server在选举leader的时候,大多数-1(减去leader的那台)的term是和leader挂的时候一样的,所以新选出的leader如果要获取大多数的vote,则其term必然大于老leader出问题的时候的term,所以之后如果老的leader活过来了那么也没关系,因为其小的term此时已经不能让其成为leader了。
3.某个一leader真正成为leader的时候,其只有唯一的term。因此一个term只可能有一个leader。也就是说如果同一时间存在两个term,那么就可能存在两个leader,但是其中的一个leader永远不可能成功的commit。另外,真正活着的leader是最大的term的那个。
4.当一个新的leader产生后,其会的将每个follower的next index设置为其自己next index,然后发送心跳包给各个follower。如果follower发现这两个index不一样,则拒绝。leader如果发现follower拒绝了,则发送其next index的前一个index作为next index,直到follower接受。这样的话要保证两个事情:
a.如果term和index一样,那么内容一样
b.如果term和index一样,那么之前的日志内容一样
对于a,只要leader是唯一的,那么就能保证(因为一个唯一的leader对应唯一的term,同时其自身可以保证index的唯一)。对于b,每次发送AppendEntries的时候提供前一个日志的term和id,follower保证其和当前的term、index一致才接受,通过数学归纳可以知道这是可以保证b的。
在a、b的前提下,如果leader落后太多,那么其可能会清理follower上已经commit的日志。因此还需要额外的条件:在选举leader的时候,一个candidate如果其自己的term、id比另一个candidate发来的请求要新,那么就拒绝。
5.在leader宕了的情况下,集群里至少有大多数-1的主机是拥有所有commit日志的。
6.对于figure 8的问题,要注意的是对于c图,term为4的leader是不会去commit老的term为2的日志的,对于index为2的日志,一种情况是和d一样被overwrite了(此时term 2的日志从来就没有被commit过),另一个情况是和e一样,由S1在Log Matching Property的前提下被commit(收到term 4的AppendEntries的时候,发现S1已经提交到了term 4的日志,所以其follower也提交到这一步)。这里的关键在于,commit指的是重做事物日志,当leader广播的日志内容到了大多数服务器的时候,这些服务器(包括leader自己)都可能只是有这个日志,但是没有commit过。老的日志如果要被commit,前提是follower收到AppendEntries的时候,其包含的leader的最新提交term+index大于这个老的日志的term+index,此时才会被commit。
7.follower收到candidate的请求,且candidate的term大于follower的term的时候,此时follower会立刻认新的leader。

理解集群配置替换时候的注意点:
1.在集群配置变化的时候(主要是添加和减少主机),要避免的是新老两种配置同时生效(如果存在这种情况,按照figure 10可以看到可能存在同一个term中有两个leader的情况),换句话说就是要保证leader挂了的时候不会选出两个leader。为了解决这种问题,raft中采用配置同样依靠leader广播,且增加一种old-new的配置来解决这个问题。具体操作和原理如下(新加入的主机启动的时候对于集群的其他服务器信息一点配置都没有,因此其就是在等):
a.leader收到一个新的集群配置
b.leader广播一个old-new配置信息,这个信息被commit的前提是新集群和老集群中的多数follower都收到了这个信息
c.如果此时leader挂了,且b中的信息还没有被commit,此时集群中只有两种新的配置,一种是Cold,一种是Cold-new。Cold能正常commit或选举的前提是老集群中大多数服务器ok,Cold-new能正常commit或选举的前提是老集群中其大部分服务器ok,且新集群中其大部分服务器ok。如果说Cold-new中的某个服务器要成为leader,根据前提条件其需要老集群中的大部分服务器投票给他,这就保证了老集群中处于Cold的大部分服务器不会成为leader。如果老集群中的一个Cold服务器想成为leader,则Cold-new就没法投票成功(因为其得到不老集群中的多数投票)。当Cold中的一个服务器成为leader后,其再次发起投票即可(这次投票会的将得到上一轮Cold-new的日志overwrite掉)。
如果leader挂了的时候b中的信息已经被commit了,那么新的leader肯定是Cold-new的,这样就比较简单了。
d.当Cold-new已经被commit后,此时的leader就会发起包含新配置的Cnew信息。这个其实就是上面过程的翻转(Cold变成Cnew),成功的前提是老集群中的大部分和新集群的大部分都收到了Cnew消息。
2.总的来说,集群配置替换由于Cold-new的引入,保证了同一时刻Cold和Cnew不可能同时生效(因为Cold-new其实潜在要求了只有Cnew生效,Cold不生效。而c中另一种情况就是Cold,因此Cnew和Cold不能同时生效。),当Cnew和Cold不同时生效的时候,可能会处于中间的Cold-new或Cold或Cnew状态,其中处于Cold或Cold-new的时候,按照规定步骤继续向着Cnew前进即可。
3.在上面第一步的c中,如果Cold成了leader,其需要发起一次Cnew-old的广播,否则可能会由于收到新集群主机的选举信息而变成follower,并再次发起选举
4.Cold-new的比较简单的理解是,Ca-b要求a中的大多数、b中的大多数都投赞成票才算成功

理解快照时候的注意点:
1.快照最简单的理解就是按照figure 12的那样,把commit的当前内容及一些基本信息记录下。
2.在follower新加入集群的时候,由于其什么日志都没有,因此leader获取到期next index是一个已经由于快照而删除了的值。此时leader既要发送快照给这个follower。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*