如果定时器完全相同，谁也赢不了

一句话总结

共识并不是决定“谁是对的”，而是决定“轮到谁发言”，而 Raft 只用任期（term）和过半数投票这两个机制来解决它。而且这场选举要想结束，计时器必须各不相同。

为什么需要它

假设在三台服务器上保存相同的值。如果客户端分别向三台服务器发送写入，由于网络延迟，到达的顺序会不同，三台服务器的记录就会出现分歧。所以实际工作中的答案始终是一样的——把接收写入的地方定为一个，其余的都跟随这一个。问题是“那一个”崩溃的时候。在没有任何人指定下一个轮到谁的状态下，剩下的服务器必须自己把它定下来。

自然会有人问：让人来介入不就行了吗？事实上，很长时间里就是这样做的，至今仍有很多数据库复制把晋升（promotion）交给人手动完成。但是人介入需要以分钟计的时间，这期间服务无法接收写入。更糟的是，人也会出错——如果原来的领导者其实还活着，只是网络断了，那么一旦晋升，接收写入的地方就成了两个。

Raft 论文（Diego Ongaro、John Ousterhout）的目标，是以可以理解的方式解决这个问题。官方网站把 Raft 介绍为“为易于理解而设计的共识算法，在容错性和性能上与 Paxos 相当” （raft.github.io）。论文的精简版在 2014 年的 USENIX ATC 上获得了最佳论文奖。

工作原理

Raft 的时间以任期流逝。任期是只增不减的整数，每个任期最多有一个领导者。没有领导者时，任期加一，并开启新的选举。每条消息里都带有发送方的任期，所以两个节点相遇时，规则就很简单——看到更大任期的一方，会把自己的任期提高到那个值，并退回追随者。对于更小任期的请求，则予以拒绝，但不会把我自己的任期降到对方的那个值。

选举三行就结束了。

1. 리더 소식이 타임아웃만큼 끊기면 → 임기 +1, 후보가 되어 자기에게 한 표
2. 나머지에게 투표를 요청 → 받는 쪽은 '한 임기에 한 표' 만 준다
3. 과반을 받으면 리더. 과반은 절반 이상이 아니라 절반 초과다

该代码块中的韩文注释依次说明：领导者的消息中断达到超时时间后，任期加 1，成为候选人并给自己投一票；向其余节点请求投票，接收方在一个任期内只投一票；获得过半数的票就成为领导者，过半数是超过一半，而不是达到一半以上。

过半数这个条件只做一件事——两个过半数必然有重叠。 无论怎样从 5 台中选出 3 台组成的两个集合，至少有一台会同时出现在两个集合中。那一台在一个任期内只投一票，所以同一个任期出现两个领导者的情况不可能发生。raft.github.io 把这一性质写作“只要服务器的任意过半数还活着，就能继续推进——例如，5 台的集群即使有 2 台挂掉，也能继续运行”。

剩下的就是计时器。如果三个节点的超时时间完全相同，三个就会在同一瞬间成为候选人，各自给自己投一票，而不给对方。没有任何一个能拿到过半数，只有任期在不断上升。所以 Raft 会在一定区间内随机选取超时时间。先醒来的那一个，如果在其余节点醒来之前收齐了票，选举一次就结束了。

在这里最好说清楚一点。选举并不是挑选“哪个节点更好”。不看性能，不看资源，也不看最近的负载。看的只有两样—— 是否先醒来，以及（有了日志之后）日志是否没有落后。正是这种简单，让算法变得可以理解，同时也让“为什么偏偏是那个节点成了领导者”这个问题的答案变得很扫兴。答案通常是“因为它的计时器先响了”。

领导者做的事也比想象中少。接收值，把它转发给其余节点，并持续发送表示自己还活着的信号。那个信号就是心跳（heartbeat），即使没有话要说也会一直发——因为区分沉默和死亡，只有这一个办法。追随者每次收到心跳，都会把计时器重置为起点。所以选举再次开启的条件不是“领导者死了”，而是 “心跳没有在超时时间内到达”，而这两者的差别，可以解释运维中的大部分事故。

在现场相遇的样子

在运维中，这个话题通常表现为“任期一直在上升”的告警。etcd 文档写道，即使领导者还活着，如果心跳没有按时到达，也会发生“无谓的选举（spurious election）”，并建议在延迟较大的环境中调整 heartbeat-interval 和 election-timeout（etcd FAQ）。磁盘变慢导致写入积压，或者 GC 停顿很久时，节点明明好好的，只是心跳变晚了，选举就会反复发生。在此期间，集群无法接收写入。

也有相反方向的事故。如果把超时设得过长，当领导者真的挂了，就会停摆那么久。选举超时是“能多快察觉”与“多频繁地白白受惊” 之间的旋钮，而两个方向都会表现为故障。

下一项实验要做什么

启动三个仅端口不同的进程，亲手实现选举。HTTP 服务器和计时器之类的接线已经为你准备好，你只需要编写任期比较、投票、过半数判定这类做判断的函数。最后一步，把三个节点的超时设成相同，观察 9 秒。你会亲眼看到，领导者选不出来，只有任期在上升。