raft 算法学习

    本文介绍分布式一致性算法 Raft。 需要读者理解分布式一致性问题产生的原因。

    在分布式一致性算法上， 最著名的当然是 paxos。 同时， 这家伙也以难以理解而闻名。于是 raft  来了。本文对raft 依据（） 进行简单的说明， 帮助大家快速了解这个算法。 更多细节建议阅读原文。

    一个 raft 集群由多台 server 组成。比较典型的， 由 5 台 server 组成的集群， 可以抵抗 2 台服务器同时宕机（参阅拜占庭将军问题）。每一台服务器都是下面三种角色之一：leader， follower 或者 candidate。 一般情况下， 系统中只有一个leader， 其他都是follwers。 followers 本身不发出请求， 他们只是简单的回应 leader 和 candidates 的请求。我们把系统的功能简化为对一个变量 S 的更新， 写变量的时候是要先记录一条操作log， 然后再更新变量的值。 我们先看一个简单情况， 系统中有leader 记为L， followers 记为 F1， F2，F3，F4。客户端的请求总是发给L（ 如果客户端不知道谁是leader， 则可以向系统中任何一台服务器询问）。 对于写请求， L先在本地写更新log， 同时传播这条log到F1 － F4。 只有多数server接受了更新（算上L自己， 五台server里的三台为多数）这个更新才算作提交， 才可以应答客户写是ok的。 注意， 假设L和F1， F2， F3都已经接受了更新， 而F4因为某种原因暂时无应答，按照约定， 这个时候L可以应答客户写成功， 但是后台必须一直持续去更新F4. 一切看起来很简单美妙，其实这个简单描述隐藏了很多问题， 后面我们逐步讨论各种有问题的情况， 然后通过添加约束条件避免问题的发生。

leader的选举
    系统开始运行的时候， 所有的 server 都是 follower 身份。为了描述选举过程， 我们先引入term这个概念。 在Raft中， 整个系统的生命周期由一些列的term组成， 每个term都由一个唯一都整数（term number）表示， term 是单调递增的， 每个server都会在本地记录自己当前的term number。 当server之间互相通讯的时候， 当前term number会在server之间互相传播。 一个server发现自己的当前term number比其它的小， 则更新自己当前的term number到那个较大值。如果一个leader 或者 candidate 发现自己的term过时了， 它就立刻改成 follower 状态。如果一个server 收到一个带着过时term number的请求， 则server 拒绝这个请求。一个leader 通过发送心跳给其它server来保持自己的权威，同时阻止其它server成为leader， 一旦一个 follower 持续一段时间没有收到心跳， 它就可以认为系统中没有leader了， 它就转变自己为candidate， 开始竞争leader（虽然这个时候可能是这个follower跟其他server链接中断， 不过没关系， 那种情况下它也不可能赢得选举）。一个follower等待心跳的时间叫做 election timeout。 就是说， follower 等待了 election timeout 这么久没有收到心跳， 就可以认为系统中没有leader 从而开始选举过程。系统刚启动的时候， 所有的server都是follower， 所以经过一个 election timeout， 选举过程就开始了。
    选举过程开始后， 一个follower增加自己的term number， 然后转变到 candidate 状态。 它首先为自己投票， 然后和其它server通讯， 要求其他server为自己投票。每一个serve在一个term内， 只能投票给一个server， 采用先到先服务的原则， 总是投票给这个term最先发送请求的那个candidate。 一个candidate收到多数投票（本term的）则赢得选举。如果一个candidate在选举过程中收到一个自称leader的server的消息， 并且这个消息的term number不小于candidate的term number， 那么candidate承认这个leader， 自己转变成follower状态。如果经过一段时间无人胜出， 则重新开始选举过程， candidate 增加term number开始新的投票。
    我们看一个例子， 假如系统中有5台server。 s1-s5. 本来s3是leader， term number是7， 现在s3宕机（网络不可达）， 无心跳发出。 经过 election timeout， S1 和 S5 开始转变成candidate， 同时把当前的term number变为8。
    S1（8） S2（7） S3（7－网络不可达） S4（7） S5（8）；
    S1 和 S5 都投自己的票， 同时以term number 8 要求其它server投自己的票。S2先收到S1的请求， 于是在term number 8 上S2投票给S1， 后收到S5的请求， 这个时候因为在term 8，S2已经投过票了， 所以拒绝投票给S5. S4相反， 投票给了S5， 拒绝了S1. 现在S1 和 S5 都只有2票， 谁都没有达到多数， 大家都在等S3的投票结果， 因为S3网络阻塞， 一直没有回复。过了election timeout时间， 本轮投票结束， 无胜者， 再开始下一轮投票。
    大家发现如果一直这样循环下去，可能产生死循环， Raft解决这个问题的方法是每个server的 election timout时间是不一样的， 是个一定范围内的随机值。 所以我们假设S5先到达election timout， 于是它又开始一轮选举， S5的term number现在是9， 它开始要求其它server对它投票。现在是：
     S1（8） S2（8） S3（7 － 网络不可达） S4（8） S5（9）。
    大家注意， s2和s3 的term number是8 是因为上一轮投票时他们发现自己的term number过时， 更新成了投票消息中的最新值。因为S5 现在的term mumber是9， 我们假设， 某种原因， S1没收到这个消息， 但是 S2， S3，都很痛快的投票给S5. 这个时候，S5已经赢得了选举。
    现在的情况是 ：
    S1（8）  S2（9） S3（7 － 网络不可达） S4（9） S5（9） －－－S5是term 9的leader。
    好玩的来了， 下面
    S3的网络恢复了。 它发现自己收到了 S1， term8的投票要求， 而它自己的term是7， 所以它转变自己为follower， 然后投票给S1.
    S1现在赢得了term8 的leader， 因为它收到了S2， S3 和它自己的投票， 这个时候， 系统中有两个leader， 但是它们是不同term的。 这种情况是可能的， 不影响算法的正确性，因为当S1想要把任何更新传播到多数派的时候，它都会发现自己是过时的。
    在Raft中， 要保证任何一个 term 里只有一个 leader。 但是因为分布式系统没有全局时钟， 所以可能出现不同term同时存在的情况。我们也可以简单构造这种情况， 比如一个正常运行的集群发生了分区， 少数派中有老的leader， 多数派又选了一个leader出来， 并且进行了写操作。 这里特别把这一点提出来是提请注意， 如果写读算法， 一个自认为leader的server只读本地commit的数据， 可能不是强一致性了。
    在一个有leader的一致性算法里， leader需要最终存储所有的commited的数据。 有些算法允许信息不全的candidate成为leader 然后通过一定的机制来补全信息。但是Raft中为了简化和好理解， 要求一个leader总是包含这些信息而不必从其它角色处拉取。 所以在Raft中， 更新log只有一个流动方向， 就是leader到follower。leader 永远不覆写自己到log。为了达到这个要求， 被选为leader的candidate多了一个限制条件， 就是要包含所有已经提交的log。 因为一个server被选成leader 必须经过多数派的同意， 这就给了一个机会来检查一个candidate是否包含了所有已经提交的log（leader的log不应该比多数派中任何一个的log旧）。 
    leader的选举过程介绍完了， 休息一下。