用“隐喻”的方式带你建立对 Raft 的直觉
本文来自我和 roseduan 合作的《从零实现分布式 KV》的课程。该课程会手把手教你如何弄懂一个共识协议，以及基于共识协议的分布式 KV 的方方面面、各种细节；也会教你如何组织和写出漂亮的工程代码。分布式系统是当今主流互联网系统的基础架构，而共识协议又是其中的典型代表和基石中的基石。学习本课程，能让你对分布式系统所面临的问题、所使用的技能有一个全面和深入的认识。
相比 Paxos，Raft 的一大特色就是算法拆成了相对正交的几个部分——领导者选举、日志同步、状态持久化、日志压缩和配置变更。你如果对课程照目录看下就能看出来，除却最后一部分，这些模块就是我们课程 PartA ~ PartD 要分别实现的内容。将算法正交化拆分的好处是，让每个模块相对内聚，使得整体更易理解和实现——这也是 Raft 算法设计的初衷。
下面我不打算采用精确的方式来讲解每个模块——那是论文正文和代码实现要做的事情。相反，本章我将带领大家在感性上建立一个对 Raft 基本概念（任期、选举）和两大流程（领导选举、日志同步）的认识。带着这个感性认识，大家可以再去仔细研读论文[1]，想必能事半功倍地梳理出 Raft 算法中海量的细节。
任期
任期（term）在任何共识协议中都很重要。Raft 中所有关键事件的展开，都是基于任期的，任期最直观的理解就是领导者任期，如“总统任期”。
但其本质上是一种关于时间隐喻，可以理解为“纪元”——如桃花源中的村民“不知有汉，无论魏晋”的那种朝代纪元。与桃花源村民相似，在 Raft 中，如果出现网络分区，某些 Peer 被隔绝，也很容易不知道其他 Peer 到了哪个 Term。一段时间后，被隔绝分区中的 Peer 与其他 Peer 重新建立通信（武陵人发现了他们）时，首先要做的就是对齐 Term，这是之后一切沟通展开的基础。
从另外一个角度讲，任期还是一种优先级或者权力的隐喻：
- 低任期的 Peer 收到高任期的 Peer 任何信息后，会自动“跟上”（Follow）任期变成跟随者（Follower）。
- 高任期的 Peer 收到低任期 Peer 的任何请求时，会直接拒绝。
在所有 Peer 进行“交流”（RPC 通信）时，任期都是第一优先级的，只有对齐了任期，才有谈其他的基础。
领导选举
Raft 使用的是“强人模式”，即只要 Leader 当选，他就对其任期内日志长啥样有说一不二的权力。Raft 中也采取“一山不容二虎”策略——一个任期内最多有一个 Leader（也可以没有选出）。但在同一时刻，可能会存在多个 Leader，但，他们一定处于不同任期中。
由于采用强人策略，则在选举时就要慎之又慎——以期能选出能“顾全大局”的人（具备所有已提交日志的候选者）。为此，每个 Peer 在投票时，都要比比谁的日志“更新更全”。一旦跟随者投出其票，就表示对该候选者心悦诚服——“承诺”一段时间内不会再发起选举（重置选举时钟）。
Leader 在当选后，要做的第一件事就是“昭告天下”（心跳）以“压制”其他“试图挑战权威”的人——“迫使”每个 Follower 承诺一段时间内不得再发起选举。Follower 在收到心跳后，只要任期不比人家大，就要乖乖给出“承诺”（重置选举时钟）。
之后，Leader 便会周期性的发送“政令”，直到收到来自高“任期”的消息，便要乖乖“交权”，让出领导权。从这里也可以看出，任期是第一优先级，这是“时间法则”的攻击，Leader 也不能免疫。当然，还有一种优化，就是 Leader 发现自己成为“孤家寡人”（发现大部分人不应答“政令”了，通常出现在 Leader 与多数 Follower 发生了网络隔离时）后，也自动交权。
日志同步
Leader 在接收到“甲方”（客户端）的“请求”后，会将其包装为“政令”（日志），然后“附带”到周期性的广播（心跳）上，将“政令灌输”给每个 Follower。最简单粗暴的方式，就是将本地所有日志一股脑的附带到心跳上，Follower 收到后，直接替换本地日志即可。但如果 Leader 日志量很大，通信代价将会非常高。因此 Leader 采用一种“乐观+回撤”的方式进行同步：
- 乐观：一开始心跳不附带任何日志，只带一些“暗号”过去。假如 Follower 的通过“暗号”发现自己日志跟 Leader 完全一致，就直接回：一致，之后的心跳不需附加任何日志。
- 回撤：如果 Follower 通过“暗号”发现自己和 Leader 日志并不一致，也会告诉 Leader——下次得附带日志。则 Leader 就附加一些末尾的日志，如果发现还是不一致，就要继续回撤，多向前附加一些日志，同时更新“暗号”，直到收到 Follower 肯定回复，则继续恢复不附加任何日志的心跳。
这个“暗号”，就是 Leader 所附带日志的的前一条日志信息的二元组：<下标，任期>。如果心跳没有附加任何日志，则暗号就是 Leader 最后一条日志的相关信息。为了保证 Leader 附带日志总有前一条日志，我们在对日志进行初始化的时候，会在开头放一条“空日志”，从而避免一些边界判断（这个做法类似带头结点的链表）。
那为什么只要“暗号”对的上，就能保证两方日志前缀一致呢？
简单来说，对“暗号”的过程，就是一个递推的过程。根据数学归纳法，每次附加新日志，都要对齐前序日志。而由任期单调递增、单任期最多一个 Leader，则同任期的日志前缀一定对得上。这样一来，同任期前缀对的上，跨任期同步前都会对齐前任日志，则“政令畅通”的情况下，所有日志最终都会收敛为 Leader 日志。
在“政令”（日志）同步到大多数节点后，Leader 就会宣布该政令“生效”（提交）。但论文特别强调了，Leader 不能直接宣布前任的“政令”生效，而要在本任期内发布“政令”后，通过“生效”本任期“政令”来间接“追认”前序任期的相关“政令”。这是为什么呢？（下图是 Raft 中大名鼎鼎的一张图“Figure 8”，很多实现 Raft 的同学应该都被该图虐过。）
这是由于我们选举时会通过比最后一条日志的“大小”来决定是否 Leader 当选，因此前任的日志，如果没有通过本任期“盖棺定论”，是有可能被其他在相同下标具有更新日志的 Peer 当选 Leader 后“冲掉的”，也就是上图 c、d、e 的情况——没有 4 日志的“压一道”， S5 是可以当选 Leader 的，之后 S1~S3 的 2 日志是有可能被 S5 的 3 的日志冲掉。
参考资料
[1] Raft 论文: https://raft.github.io/raft.pdf
