自几年前偶然得知 Raft 之后，便粗略了解了 Raft, Paxos, 共识（一致性）这些概念。当时的想法是：这些算法听起来就挺装逼的，赶紧去看看咋回事。等到认真一看 Raft 论文，20页，太多了还是算了吧。 等到过了几天，又发现了 Raft 官网有个动画，还挺易懂的，又简单看了看，明白了，可以出去装逼了。 再过几天一回忆，好像啥也没记住呢？虽然张无忌学太极拳也啥也没记住，但至少人家打出来了，咱也得找机会练练。这会儿又找到了 MIT 6.824, 正好赶上新学期开课了，跟着学吧。 没等学两天，一到 lab 就懒得做，Go 看不懂啊，又学了几天 Go。学完了感觉啥都会了，但是又啥也不会。还是先去找实习吧。

前年快写毕业论文的时候，附带个翻译英文文献的任务，又到了装逼的时候了，我就直接在 arXiv 上找了篇 Raft 和 Paxos 对比 的论文翻译了下，由于当时懒得排版，等到去年年底才扔到博客上。

论文翻译完，又感觉啥也没记住。但是快要去上班了，又没时间研究了，上了一年班之后又找来了 Martin Kleppmann 的公开课来看，没几天就看完了，当时看完觉得啥都懂了，现在回忆起来只记住了拜占庭那些东西，又联想到凯撒、庞贝…又联想远了…

从去年7月入职以来，搞了本影印的 DDIA 来看。看书么，必须得英文原文，不然咋装逼啊是不。按照每天一页的进度终于把这书看完了（其实一周200页，然后歇半年）。看到后面又提到共识机制，觉得有必要再重新捡起来 Raft 论文再读一下了。

手中的 Raft 这篇论文实际上时几个月之前在公司的打印机上打印的，并且当时详细地做了注解，但随后没有好好整理。这次又根据上次遗留的问题来作笔记，最后写下了这篇文章表达一下自己的见解。

前提

Raft 据说是性能相当于 Paxos, 效果相当于 Multi-Paxos 的一个一致性算法，但它更容易理解。

一致性算法（共识算法）的作用是什么呢？是为了维护一个集群中的节点的数据一致性，但这个数据一致性不要求每个时刻所有节点上的数据都是一样的，而是整个集群对外看起来像是一样的。这就又让人迷惑了，既然你每个节点的数据都有可能不一样，那怎么能看起来是一样的呢？Raft 就采用了一个特别民主的方式，让大家去投票，只要超过半数的节点的数据/状态是一样的，那么这个集群的状态就是这样的。这种 Majority 的思想在很多算法/系统中都被采用。

既然要超过半数的节点达成一致，那么也就是说至少它们之间要互相交流，不然怎么能达成一致呢？设计过稍微复杂点的系统的人都知道，这个命题一听就很难，n 个节点每两个交流就得 n 的阶乘次了，这题还是让别人做吧。开玩笑，咱是那怂人吗？说上咱就上 (指 Raft)。Raft 简化了达成共识的条件，它描述了一个单 leader 的集群，leader 来决定是否更新到某个状态。这可比多 leader 或者无 leader 的容易理解多了，谁是领导听谁的呗，Majority + leader，在我们这叫民主集中制。

在 Raft 论文中描述，它将问题简化成了 leader election 和 log replication. leader election 上面提过了，就是选举投票呗。那 log replication 是啥呢？

懂的都懂，集群的目标一是为了横向扩展增强任务处理能力，二是为了 HA. 这里的 log replication 的主要目的就是为了做高可用，防止 leader 挂掉之后集群的数据丢失。当 leader 下线（主观或者客观）后，就会下一任 leader 取代它来发号施令，整个系统继续稳步前进。

据 Raft 说，它还有一些 novel features:
Strong leader
所有的日志都是由 leader 向 follwer 同步的。这样减少了很多复杂性，这个算法就更好理解了。

Leader elections
这个上面已经讲过了，而且我觉得一点也不 novel

Membership changes
这个我不打算着这里详细讲解，因为它实际上不算是 Raft 的核心内容

不好意思，上面又引入了新的概念，同步日志又是个啥？其实 Raft 为了保证节点达到一样的状态，利用了一个 replicated state machine. 一个 state machine 就好比一个函数，相同的输入总会得到相同的输出，这种情况我们叫做幂等。Raft 集群的节点的函数（状态机）肯定是一样的，那是不是只要保证输入是相同的，就总会得到相同的结果？所以 Raft 在各个节点上复制相同的日志作为输入，这样节点们就能达到相同的状态了。

那么怎么能让外部看起来整个集群是一致的状态呢，很简单，大多数节点都同步完了再返回。也就是集群内部先达成一致，然后再告诉外面一致的结果，这样看起来和只有一个状态机来处理是一样的。虽然效率低了点，但是稳得很。

Raft 有多稳呢？它保证了

• safety: 在非拜占庭情况下不返回错误的结果。翻译过来就是：只要没内鬼，结果一定不会是错的
• available: 大多数节点可用的情况下集群可用
• 不依赖物理时钟来保证日志一致性
• 大多数节点相应了就认为是一个 command 完成了

实现

上面那一堆简单来说，Raft 就是研究怎么去管理 replicated log 的。首先要有一个 leader，它来管理所有 log、接受请求…什么麻烦上都交给 leader. 所以 leader 选举至关重要。选完了 leader，在集群处理任务时如何复制日志也是 Raft 需要着重考虑的。此外还得保证一致性啥的…

Leader election

集群的所有对外的请求都是 leader 完成的，要是 follwer 收到了外部的请求，就把这个请求转发给 leader. 那么怎么选 leader 呢？

Raft 引入了一个随机长度的 term (一个逻辑时钟)，当需要选 leader 时会开启一个新的 term 来投票。每人只有一票，候选人（candidate）要求其它节点给它投票，当获得了大多数票 candidate 就变成了新的 leader. 只要没选出来 leader 就重新再选。

咋界定需要选 leader 呢？当一个节点很久没收到 leader 的消息（心跳）了，那么它就主观认为 leader 宕掉了，它就成为候选人参加选举；如果一个节点发现了一个 term 比当前 leader 大的新 leader，那么它也会客观认为这个 term 更大的 leader 是新的 leader。

此外，选举 leader 时候还有一些限制：候选者要求日志是最新的，不能只同步了一部分；follower 不能刚选完举就立马开启下一轮选举。这两点是为了简化 Raft 作出的一些优化设计。

Log replication

客户端向 leader 发请求的时候，leader 要先把这个 command log 到 entries 上，然后告诉其他的节点：我要 log 新 command 了，之后静静等待大多数节点同意。等到大多数节点都同意了（entries safely applied），leader 再将日志 apply 到状态机上，否则无限等待 follower 响应。

有的时候 follower 会丢失一些 log（它们作为少数时），那么它们在收到 leader 让它们同步 log 的请求时会拒绝写更新的 log，而是不断向前找到和 leader 相同的日志，然后慢慢追上来。

其实上面还有很多细节上的描述，但是总体思想大概就是上面这些，不明白的地方想想就能想出来，想不出来就再想想…

Cluster membership change

Raft 对集群切换给出了个方案，它不用整体服务停机。咋做的呢？

集群切换也是通过 log 实现的（joint consensus），提交一个新的配置（集群）的时候，旧的 leader 会把新旧集群的配置提交到所有节点上（这里的新旧集群的配置指的是这两个集群合并到一起的配置），这时候它们一起作为一个大集群，当旧集群和新集群各自同意了该配置，就认为该配置提交了。然后再提交新集群的配置，follwer 发现自己没在新的配置里面就自觉下线。

有几个需要注意的地方：

1. 新配置的节点可能跟不上旧的节点中的 log，那么它们就以只读状态同步一会儿日志
2. 旧的 leader 可能不再新的配置里面，那么它就不参与投票了，不算大多数中的一分子
3. 旧配置中的集群很可能发起选举（因为会有节点下线），这时候认为 leader 存活的节点要拒绝它

Log compaction 和 Client interaction 我就不介绍了，简单地很。

从整体上来看只要对一些计算机基础知识有所了解，那么 Raft 是很容易理解的（虎头蛇尾地结束了。