Raft算法是一种分布式一致性算法，由Diego Ongaro和John Ousterhout在2013年提出。它主要用于分布式系统中，保证系统中的数据在多个节点间保持一致性。

Raft算法被广泛应用于众多分布式系统中，尤其是在需要强一致性保证的场景中，例如：

得物的多个内部中间件也是使用Raft算法作为多分片一致性的保证。

长期以来，大部分开发者都是将Raft作为一个黑盒使用，只知道它能保证多分片的一致性，对其运行原理也停留在纸面。当面临Raft性能调优或者奇怪的Raft问题排障的时候则束手无策。

费曼说过：“What I cannot create, I do not understand。” 我们中国先贤也强调“知行合一，以致良知”。如果我们不能亲手编写一次Raft算法，对这个东西就不能算作理解。

在着手开始写之前，我们先介绍几个Raft算法中的核心概念。

如果说什么是分布式系统理论的基石，那一定“日志”。此处的日志与我们平时在应用中打印的给人阅读的信息不同，它是最简单的存储抽象，是按时间排序的append-only的、有序的记录序列。

“日志”揭示了系统当下正在发生的事实。

关于日志的更深入理解，可以参考博客The Log: What every software engineer should know about real-time data's unifying abstraction，非常全面深刻。

当进入分布式的领域，日志就需要“状态机”的辅助：

关于以相同的顺序获得相同的输入的一点应该会引起人们的注意——这就是日志的用武之地。这是一个非常直观的概念：如果你将两段确定性代码提供给相同的输入日志，它们将产生相同的输出。

所以Raft最重要的任务就是解决如何在分布式系统中使多个副本的日志数据达成一致的问题。

为了实现上述目标，Raft使用强领导模型，即要求集群中的一个副本充当Leader，其他副本充当Follower。

Leader负责根据客户端请求采取行动生成命令，将命令复制给Follower，并将响应返回给客户端。

多个副本根据选举算法推选合法的Leader。

这个方案解决了分布式系统中的以下问题：

这种模型有其优点和缺点：

本系列中介绍的Raft实现是用Elixir编写的。在笔者看来，Elixir具有三个优势，使其成为本系列和网络服务的有前途的实现语言：

这个项目的开发中，笔者借鉴了这个生产级别的开源Raft库——龙舟的实现细节，如果对生产级的Raft实现感兴趣，可以阅读龙舟的代码。

我们的实现大致代码结构如下：

├── README.md                                ├── Taskfile.yaml                                  ├── lib        │   └── ex_raft │       ├── config.ex │       ├── core               # 各个状态下的处理逻辑  │       │   ├── candidate.ex  │       │   ├── common.ex     │       │   ├── follower.ex │       │   ├── free.ex       │       │   ├── leader.ex│       │   └── prevote.ex            │       ├── debug.ex │       ├── exception.ex│       ├── guards.ex│       ├── log_store        # 日志存储，本节暂时不用│       │   ├── cub.ex               │       │   └── inmem.ex │       ├── log_store.ex              │       ├── message_handlers      # 各个状态下的消息处理│       │   ├── candidate.ex                                     │       │   ├── follower.ex                              │       │   ├── leader.ex│       │   └── prevote.ex                         │       ├── mock              # 日志复制状态机，本节暂时不用  │       │   └── statemachine.ex                                   │       ├── models              # 几个分片常用的数据结构      │       │   ├── replica.ex                             │       │   └── replica_state.ex                                         │       ├── pb                      # 消息的数据结构│       │   ├── ex_raft.pb.ex                                │       │   ├── ex_raft.proto                                      │       │   └── gen.sh                    │       ├── remote                 # 节点间通信客户端 │       │   ├── client.ex                       │       │   └── erlang.ex                       │       ├── remote.ex│       ├── replica.ex            # 分片进程                    │       ├── serialize.ex│       ├── server.ex             # 节点间以及和客户端通信的服务端│       ├── statemachine.ex     │       ├── typespecs.ex │       └── utils                     # 工具集          │           ├── buffer.ex│           └── uvaint.ex             ├── mix.exs             ├── mix.lock                                                                                    ├── test                                                                                          │   ├── ex_raft_test.exs                                                                    │   ├── log_store.exs                                                                       │   └── test_helper.exs                                                                     └── tmp

这一节中，我们暂时不考虑日志复制的细节，专注实现选主逻辑。

从论文In Search of an Understandable Consensus Algorithm（《寻找一种易于理解的一致性算法（扩展版）》，以下称为“论文”）中，可以得知：“选主”这个过程本身也是个状态机（注意区分此处的状态机和日志复制状态机不是一回事）：

在典型的稳态场景中，集群中的一台服务器是Leader，而所有其他服务器都是Follower。

虽然我们希望事情永远这样保持下去，但Raft的目标是容错，所以我们会讨论一些故障场景：例如其中一些服务器crash、网络分区等。

为了实现选主的逻辑，我们要引入一些概念：

论文中的解释：任期（Term）是分布式系统中共识算法中的一个关键概念，尤其是在领导者选举（Leader Election）和共识达成过程中。任期是时间上的一个划分，用于组织和同步分布式系统中的事件，确保系统中的所有节点能够在一个明确的时间段内就某个领导者或一系列决策达成一致。

简单来说，任期标明了Leader的服役阶段。

任期这个概念有以下特性：

每个Follower都会在本地维持一个选举计时器，在选举计时器到期前，如果没有收到Leader的日志或者心跳，Follower就会认为Leader出了意外，那么就会开始发起选举。这里有几个常见问题：

Q：会不会有多个Follower同时成为候选人？

A：会的，为了避免这种情况出现，我们给选举计时器添加一些随机区间，这是Raft简单的原因之一。Raft使用这种随机化来降低多个Follower同时进行选举的机会。但是即使他们同时成为候选人，任何给定任期内也只有一个人会被选为领导人。在极少数情况下，如果选票分裂，没有候选人能获胜，将进行新的选举。

Q：如果Follower与集群断开连接（分区）怎么办？

A：这就是网络分区的隐蔽性，因为Follower无法区分谁被分区了。这种情况Follower会开始选举。但这种情况下Follower不会得到任何选票。这个节点可能会在候选状态中持续自旋（每隔一段时间重新启动一个新的选举），直到重新连接到集群。

Raft中两个节点的通信类型多种多样，不过涉及到选主的部分较为简单，只有下图添加注释这4种消息类型：

从上述介绍中可以看出，选主这个过程涉及多个状态的轮转，每个状态下对不同消息做不同的反应，所以非常自然我们选择状态机的方式实现。

而Erlang OTP有个自带的状态机实现框架：gen_statem，有了这个利器，可以写出很清晰的状态机逻辑：

我们这里的计时方式也是借鉴了“龙舟”的风格，即维护一个单位时间很小（1s）的本地时钟，其他超时事件全部用该时钟的整数倍来计算，这种方式配置和编码起来较为简单。

我们在代码中需要判断localTick的次数超出了electionTimeout，即可将自身状态转变为Candidate开启选主。

开启投票前Candidate需要做这几件事：

完成这些后，就将携带新Term的消息发给所有其他的节点。

需要注意的是在这个Raft实现中，消息发送全部采用单向流，消息的发送和处理是隔离开的。

具体实现中则是使用了Erlang自带的RPC，简化了自己开发通信协议的成本。

由于Raft中任期概念的设计，其他角色在接收到拉票消息时需要考虑以下几种情况：

这种情况较为简单，做Follower即可。

需要注意的是，在遇到较大Term而转换自身状态的情况下，不用重置选举计时器，原因在注释中写明了：

Not to reset the electionTick value to avoid the risk of having the local node not being to campaign at all. if the local node generates the tick much slower than other nodes (e.g. bad config, hardware clock issue, bad scheduling, overloaded etc), it may lose the chance to ever start a campaign unless we keep its electionTick value here.

简而言之就是防止某个节点一直处于Follower角色，失去选举的机会。

代码中cast_pipein这个函数是指在变更状态为Follower后，继续处理这个request_vote消息。

这种情况，直接丢掉消息就行，任期小的消息在Raft算法中是不用处理掉的。

这种情况就是在情况1转变本地Term的后续，当任期一致时，投不投票也有讲究。

Raft算法中规定，如下情况可以投赞成票：

这个任期中当前节点谁都没投过，这个消息来源第一个来拉票的，那就投给消息来源节点；

这个任期中当前节点投过了，而且我投的就是同个节点，那就不介意再投一次。

Candidate在散出request_vote的消息后，会开始等待其他节点的回执，这时候有3种情况：

这种情况说明集群中已经存在一个更高任期的节点，那也不需要继续选举了，直接默认该消息来源节点为Leader。这里和上文中处理更高Term的request_vote消息类似。

大部分节点同意了当前的选举要求，那该节点就成为这个任期的合法Leader：

Raft算法不会给Candidate无限的计票窗口，如果一直没有收到足够的选票，就清零计票，重置Term+1，再次发起选举，重复上述的过程，直到有个合法的Leader诞生。

接着上面网络分区的场景讨论，相信许多Raft系统的维护人员会发现，如果某个离群的节点在重新回归后会立即成为Leader，就是这个原因，离群的节点在不停的自旋选举过程中将自己的Term抬高了很多，一但回到集群就会因为Term优势成为Leader。为了解决这个问题，Raft有个prevote的补丁，这里暂不展开讨论。

当Candidate成功成为Leader后，就需要承担Leader的责任。在Raft算法中，Leader需要持续的向Follower发送心跳消息表明自己的存在。

Follower收到心跳后，就可以重置自己的选举计时，起码在这个选举周期内，集群中有个Leader了，不用开启选举。

Leader收到心跳回执后，需要标记下Follower的状态，这个状态在集群可用性处理和后续的日志复制中有大用。

上面的概念介绍中我们已经阐述过，Raft本质就是多个副本的日志数据达成一致的解决方案。我们已经实现了选主能力，但是尚未涉及到日志的部分。

接下来，我们将为选主集群添加日志复制能力。为了实现这个目标，我们需要一些新的数据结构和接口协议，同时也会对选主部分逻辑做增强的安全检查处理。

Raft集群的客户端会和集群产生交互，而交互的具体内容则是一个个具体的指令（Command）。例如一个Raft架构的KVDB，客户端会向集群发送类似PUT foo bar的写请求或者是GET foo的读请求，这里的请求都可以算作指令的范畴。

Raft集群在接收到客户端的指令后，根据论文第5.3节，会做如下的动作：

这里是论文中提供的日志复制的简单例子：

按照论文的论述，这种日志复制的机制有2个特点：

简单来说，如果2个节点中某个日志Entry的index和Term一样，那么从集群启动到日志记录的当下，集群中所有节点的状态是完全一致的。

这2个特点在论文中被定义为“日志匹配特性”，由这个特性保证了“集群状态可预测性”。

为了实现日志复制功能，我们需要扩展一下数据结构。

1）Entry

Entry即一个个日志块，每个Entry会携带一个Command，为了让Command可以在集群中传播，Command会序列化为一个binary。

这里的日志类型中本篇会新增用到以下两个，其余的暂时用不上：

2）Message

Message结构中，我们扩展了如下字段：

其他字段暂时用不到。

为了实现日志复制，每个节点都需要维护一个自己的日志仓库用于存储Raft的Entry，我们为日志仓库抽象了如下的API：

这里同样采取API和实现分离的设计方式，具体的实现是可拔插的。（按照Elixir的编程习惯，这里用Protocol的方式来定义更优雅）

在我们这个版本的实现中，我们采用了Cubdb作为日志仓库的实现基础。(Cubdb是一个以B+树文件存储为基础的嵌入式KVDB)。具体的实现方式可以参考代码。使用这个存储主要是为了简单考虑，如果考虑性能的话可以模仿龙舟的方式使用wal和memcache结合的方式，大大提升日志存储的吞吐性能。

1）发起提案

这里提案（Propose）即客户端对Raft集群发起的指令（Raft中读指令要比写指令复杂的多，读指令涉及到一致性相关讨论，感兴趣的可以搜索Raft中read_index的内容）。

接下来就是根据当前节点的不同角色来判断：

2）leader复制提案

Leader在接收到propose后做如下动作：

• 从propose中提取需要复制的Entries；

• 将Entries添加至本地日志仓库；

• 维护本地的日志水位；

• 如果日志复制前后日志水位发生变化，说明有新日志，就会开启日志复制广播。

3）Leader广播日志复制消息

这一过程比较简单，不过需要注意的是Leader会维护每个Follower的复制水位，这个水位是通过日志复制和心跳共同维护的。

日志复制会从每个Follower的复制水位开始，直到Leader的最新日志或者最大复制体积。

发送的日志复制请求会携带Leader记录的复制水位index和水位对应的Term，这俩数据是非常重要的，Follower会根据这两个标定来检查日志是否安全。

4）Follower处理日志复制请求

Follower在接到日志复制消息后有如下情形：

这种情形说明Leader的复制水位已经落后太多，没必要做更多的动作，只需要回复Leader最新的commit水位即可。

这种情况说明Leader发来的日志可能与Follower的日志有部分重叠，这个时候要非常谨慎，需要仔细对比Leader的日志和本地日志是否匹配。

这里的日志匹配的过程分为这么几步：

为何需要在日志复制时做这么严格的任期检查呢？这个问题先保留，后面再细致讨论。

这种情况就比较简单了，日志都跳号了，肯定不能接受，直接回绝即可。

5)Leader处理复制回执

Leader在接收了Follower的日志复制回执后会有如下情形：

这种为正常情况，Leader会更新Follower的水位，并且发起一次commit的尝试。

commit的请求按照论文，必须选择至少半数复制成功的安全水位。

这里取安全水位的做法参考了龙舟的技巧，每次收到回执后将所有节点的match水位排序后取中位数即为半数同意的安全水位，非常巧妙。

值得注意的是，在commit之前我们还特地做了一次Term的检查工作，这里是Raft的安全性检查，后文中会详细讨论。

异常情况下，按照论文的描述，Leader不用做日志回滚，只需要调整复制的起点水位即可。复制的起点水位取本地记录的match水位和Follower返回的合理水位中的较小值（重复了没有问题，不连续才是大问题）。

如果这个过程中Follower的日志已经脏了，这个安全水位开始的日志可以覆盖纠正Follower的日志。

在上节的分步实现中，我们多次做了日志的任期检查：

为什么Raft需要不厌其烦地做Term和index的检查呢？

在Raft论文中有如下论述：

下图展示了Follower的日志可能和新Leader不同。Follower可能会丢失一些在新的Leader中存在的日志块，也可能拥有一些新Leader没有的日志块，或者两者都发生。丢失或者多出日志块可能会持续多个任期。

在Raft算法中，Leader是通过强制Follower直接复制自己的日志来处理不一致问题的。这意味着在Follower中的冲突的日志块会被Leader的日志覆盖。

要使得Follower的日志进入和自身一致的状态，Leader必须找到最后两者达成一致的地方，然后删除Follower从那个点之后的所有日志块（水位重置），并发送自己在水位之后的日志给Follower。

所有的这些操作都在进行日志复制RPC的一致性检查时完成。Leader针对每一个Follower维护了一个nextIndex，这表示下一个需要发送给Follower的日志块的索引。当一个Leader刚刚被选出的时候，它初始化所有的nextIndex值为自己的最后一条日志的index加1（图中的11）。

如果一个Follower的日志和Leader不一致，那么在下一次的日志复制RPC时的一致性检查就会失败。在被Follower拒绝之后，Leader就会减小nextIndex值并进行重试。最终nextIndex会在某个位置使得Leader和Follower的日志达成一致。当这种情况发生，日志复制RPC就会成功，这时就会把Follower冲突的日志块全部删除并且加上Leader的日志。一旦附加日志RPC成功，那么Follower的日志就会和Leader保持一致，并且在接下来的任期里一直继续保持。

通过这种机制，Leader在获得权力的时候就不需要任何特殊的操作来恢复一致性。他只需要进行正常的操作，然后日志就能在日志复制RPC——日志复制回复处理这一过程中自动趋于一致。Leader从来不会覆盖或者删除自己的日志。

在上面的篇幅中，我们讨论过集群选主的过程，一个节点只要拿到集群半数以上的request_vote的成功回执即可成为Leader，而且投票的原则非常简单，只要这个任期我没投过票或者我投过相同的节点即可赞成投票。

不过在添加日志复制后这里会出现一个小问题，例如在下图中：

如果f节点发起选举并得到了大多数成员认可，那么集群大部分节点就会面临日志回退，已经“安全”的日志都变得不再安全，这不符合Raft的设计初衷，所以我们需要在投票时添加一个机制防止类似f节点这类比较“旧”的节点当选为Leader。

论文中有如下论述：

简单来说就是：投票的时候如果拉票人的日志没我本地的新，那我就不能投票给你。

代码实现：

在日志复制的第5步中，Leader获取了半数以上的安全水位执行提交，不过提交前判断了是否与当前任期一致，如果出现跨任期的情况，就会暂缓这次提交，为什么需要这一步呢？

论文有如下论述：

下图8展示了一种情况，一条已经被存储到大多数节点上的老日志块，也依然有可能会被未来的Leader覆盖掉。

简单来说就是：过往任期的“安全”水位不一定是安全的，完全可能在Leader切换后被覆盖，只有当前任期的“安全”水位是安全的，因为其他日志不一致的节点没法在该任期内当选Leader只能被覆盖。

前面的篇幅中我们已经介绍了Raft的2个核心部分：

但是现在的Raft集群还没法集成任何业务，因为缺了和业务息息相关的一环——用户状态机。

接下来，我们将完成Raft拼图的最后一块，将业务能力集成，并尝试用这个完全体的Raft制作一个分布式的KVDB。

在Raft一致性算法中，业务状态机（也称为应用状态机或用户状态机）指的是实际执行业务逻辑的组件。当Raft处理完日志条目（通常是客户端发送的命令或操作请求）并通过选举和日志复制机制达成一致后，这些日志条目会被提交给状态机进行处理。

业务状态机是确定性的，这意味着对于任何给定的输入，它总是产生相同的结果，无论在哪个节点上运行。这个特性保证了，只要日志条目的顺序相同，所有节点上的状态机经过相同的序列化输入后会达到相同的状态。因此，即使集群中发生故障，只要有一个存活的节点，就可以通过复制其状态来恢复其他节点，从而保持整个系统的状态一致。

在Raft中，业务状态机的职责包括：

需要注意的是，Raft算法本身不关心业务状态机的具体实现细节，它只负责保证日志条目的顺序一致性和可用性。这使得Raft能够适用于各种不同的分布式系统和应用场景，例如数据库、缓存、配置管理系统等。

参照上面的概念定义，我们可以定义用户状态机的行为：

我们的状态机约定有如下API：

Raft中是这么定义“快照”的，后文有更加详细的解释：

应用状态机提供的各个API是和Raft的日志复制紧密相关的，我们分开讨论每个API的使用时机。

1）执行Raft日志中的业务命令

Raft的状态中保存了2个水位：

当commit_index>last_applied且commit_index任期与当前任期一致（原因见上篇文章Leader提交过往任期的日志讨论）时，即可将（last_applied, commit_index]这个范围的日志应用到应用状态（即调用update方法）。

而执行apply的时机就很有讲究了，各个Raft框架的实现各不相同，合理的apply时机和整个Raft框架的性能息息相关，开发者需要自己在框架的吞吐、提案的延迟中取一个合理的折中。我们这里的实现较为简单，定时apply到statemachine即可。

2）保存快照

快照（Snapshot）是一个重要的优化机制，用于处理日志文件不断增长所带来的存储和性能问题。随着系统的运行，Raft需要记录越来越多的状态转换指令，这些指令以日志条目的形式存储，以便在需要时能够重放这些指令来重建系统状态。

然而，随着日志的增长，以下问题逐渐显现：

为了解决这些问题，Raft引入了快照机制。快照是对系统当前状态的一个完整拷贝，它包含了从系统启动到快照生成时刻的所有状态信息。一旦快照创建完成，它所代表的那一刻之前的所有日志条目就可以被安全地删除，因为快照包含了那些日志条目所能提供的所有信息。

以下是快照在Raft中的一些关键作用：

快照的生成时机通常是根据预设的策略，比如日志条目达到一定数量或存储使用量超过阈值。

在Raft中，快照的生成和传输过程需要谨慎设计，以确保数据一致性和系统的稳定性。

在我们这个玩具实现中，就不实现复杂的自动快照了，实现一个手动快照入口即可。

快照的构成包括2个部分：

Raft无法知道用户状态机想要持久化的数据，所以在保存快照时，携带snapshot_metadata调用用户状态机的快照API。这里我们设计了很简单的快照格式，用一个4字节的header保存snapshot_meta的长度，方便恢复的时候做长度切割。

我们的玩具实现中只是单纯的存在当前节点磁盘，生产中可以根据实际的业务需要将快照存储在三方存储（例如s3）中方便管理。

3）快照恢复

既然有快照保存，那就一定有快照恢复，快照恢复有以下几种情形：

第二种情形较为复杂，我们就先不讨论了，这里只实现第一种情况：

快照恢复的过程就是快照制作的反过程，我们从存储（磁盘）上读出快照数据，parse为业务快照和metadata，其中:

至此，我们已经介绍完了Raft中核心的概念，为了更直观的感受用Raft的功能，我们选择一个很简单的业务场景来验证——KVDB。

我们的玩具KVDB将支持以下能力：

为了实现这个KVDB，我们首先按照业务状态机的业务约定实现状态机接口。

这里的kv数据全部存储在内存map中，update和read方法即对该map的读写。

快照实现也非常简单，将所有的kv对dump为一个json，快照加载的时候读取这个json恢复所有kv即可。

有了这个状态机，我们就可以将我们编写的Raft框架和这个状态机联合起来，组成一个Raft-kv。

我们简单组织一下上层的API：

从代码可知，这里的写入和删除都是对Raft集群发起一个提案，而读则是采用的较为简单的“脏读”策略，直接读的本地内存（如果想要更为严格的一致性，需要实现Raft提供的一致性读API）。

接下来就是激动人心的时刻，我们将把从选主到状态机所有的代码串联起来，检验Raft是否能正常工作。

1）Raft集群组建

这里我们在本地启动3个Erlang进程，每个进程有个独立的node id和port，各个node通过Erlang虚拟机相互发现通信。

配置文件中，我们将这3个node组成一个Raft集群。

从图中的show命令执行结果可知，3个节点成功组成了稳态的Raft集群，节点1为Leader，2和3为Follower。

2）读写作业

由结果可知，我们的写入和删除提案都被3个节点复制执行成功。

3）快照落盘与恢复

由实验结果可知，我们的快照制作和快照恢复功能生效了，节点可以从磁盘中恢复状态和集群达到一致性。

本文深入探讨了Raft日志复制算法的核心概念和实现细节。从日志复制状态机的基础，到Leader、Follower、Candidate的角色定义，我们逐步揭开了Raft算法的神秘面纱。我们选择了Elixir作为实现语言，展示了其在构建高效、可扩展的分布式系统中的潜力。

通过分步实现日志复制，我们了解了如何发起提案、Leader如何复制提案以及Follower如何处理日志复制请求。安全性讨论让我们认识到了在分布式系统中保证数据一致性的重要性。此外，我们还探讨了Raft算法在集群选主和用户状态机中的常见问题和陷阱，以及如何通过定义状态机行为来执行业务命令。

在实践层面，我们学习了如何编写一个分布式KVDB，并验证了其正确性。这包括了Raft集群的组建、读写操作的执行、以及快照的落盘与恢复。这些实际操作不仅加深了我们对Raft算法的理解，也为我们提供了宝贵的实践经验。

本文仅浅尝辄止地了解了一下Raft的核心知识，制作了一个玩具的Raft实现，而生产级别的Raft框架需要考虑的问题更多了。感兴趣的开发者可以在本文的基础上进阶思考一下这些问题：

随着分布式理论的发展，业界也对Raft做了很多的扩展和升级，例如：

随着技术的不断进步，我们有理由相信Raft算法及其在分布式系统中的应用将会更加广泛。在未来，我们期待看到更多创新的实现和应用场景，以解决日益复杂的分布式计算问题。让我们拭目以待，共同见证分布式技术的未来发展。