摘要：Raft算法是一种分布式一致性算法，由Diego Ongaro和John Ousterhout在2013年提出。它主要用于分布式系统中，保证系统中的数据在多个节点间保持一致性。
分享概要
一、前言
二、核心概念
1. 日志复制状态机
2. Leader、Follower、Candidate
三、Why Elixir
四、选主实现
1. 任期（Term）
2. 选举计时（Election timer）
3. 消息类型
4. 状态机框架
5. 选举计时
6. 拉票
7. 处理拉票消息
8. 计票
五、Leader的工作
六、日志复制
1. 从客户端行为开始
2. 数据结构
3. 日志仓库
4. 日志复制分步实现
5. 日志复制安全性讨论
6. Rethink集群选主
7. Leader提交过往任期的日志讨论
七、用户状态机
1. 什么是用户状态机？
2. 定义状态机行为
3. 应用状态机与Raft日志的交互
八、编写一个分布式KVDB
1. 状态机实现
2. 完整的Raft-base KVDB
3. 验证
九、总结
一、前言
Raft算法是一种分布式一致性算法，由Diego Ongaro和John Ousterhout在2013年提出。它主要用于分布式系统中，保证系统中的数据在多个节点间保持一致性。
Raft算法被广泛应用于众多分布式系统中，尤其是在需要强一致性保证的场景中，例如：
分布式存储系统：如ETCD、Consul等键值存储系统，它们利用Raft算法来保证数据的强一致性和高可用性。分布式数据库：一些分布式数据库管理系统（DBMS），如CockroachDB等。分布式锁服务：例如Google的Chubby以及微软的Azure Service Bus等。得物的多个内部中间件也是使用Raft算法作为多分片一致性的保证。
长期以来，大部分开发者都是将Raft作为一个黑盒使用，只知道它能保证多分片的一致性，对其运行原理也停留在纸面。当面临Raft性能调优或者奇怪的Raft问题排障的时候则束手无策。
费曼说过：“What I cannot create, I do not understand。” 我们中国先贤也强调“知行合一，以致良知”。如果我们不能亲手编写一次Raft算法，对这个东西就不能算作理解。
二、核心概念
在着手开始写之前，我们先介绍几个Raft算法中的核心概念。
1、日志复制状态机
如果说什么是分布式系统理论的基石，那一定“日志”。此处的日志与我们平时在应用中打印的给人阅读的信息不同，它是最简单的存储抽象，是按时间排序的append-only的、有序的记录序列。
“日志”揭示了系统当下正在发生的事实。
关于日志的更深入理解，可以参考博客The Log: What every software engineer should know about real-time data's unifying abstraction，非常全面深刻。
当进入分布式的领域，日志就需要“状态机”的辅助：
如果两个相同的确定性过程以相同的状态开始并以相同的顺序获得相同的输入，它们将产生相同的输出并以相同的状态结束。确定性意味着处理不依赖于时间，并且不会让任何其他输入影响其结果。例如，一个程序的输出受到线程特定执行顺序或调用gettimeofday或其他一些不可重复的东西的影响，通常最好被认为是非确定性的。
进程的状态是在处理结束时保留在机器上的任何数据，无论是在内存中还是在磁盘上。
关于以相同的顺序获得相同的输入的一点应该会引起人们的注意——这就是日志的用武之地。这是一个非常直观的概念：如果你将两段确定性代码提供给相同的输入日志，它们将产生相同的输出。
所以Raft最重要的任务就是解决如何在分布式系统中使多个副本的日志数据达成一致的问题。
2、Leader、Follower、Candidate
为了实现上述目标，Raft使用强领导模型，即要求集群中的一个副本充当Leader，其他副本充当Follower。
Leader负责根据客户端请求采取行动生成命令，将命令复制给Follower，并将响应返回给客户端。
多个副本根据选举算法推选合法的Leader。
这个方案解决了分布式系统中的以下问题：
容错性（Fault Tolerance）：分布式系统中可能会出现节点故障，包括宕机、网络分区等问题。通过这些角色的分工和协作，系统可以在一定数量的节点出现故障时仍然正常运行。领导者选举（Leader Election）：在分布式系统中，通常需要一个节点（Leader）来协调其他节点（Followers）的工作，以确保一致性和效率。Leader负责管理日志复制、决策提议等任务。当Leader失效时，系统需要能够选举出新的Leader。
一致性（Consensus）：为了保证系统状态的一致性，需要所有节点就某个值或状态达成共识。这通常通过一系列的投票和通信过程来实现，其中Candidate角色在选举过程中起到关键作用。
去中心化（Decentralization）：在去中心化的系统中，没有中央权威来决定系统状态。这些角色的引入有助于在没有中心节点的情况下实现一致性和决策。
这种模型有其优点和缺点：
显著的优点是简单。数据总是从领导者流向Leader，只有Leader响应客户端请求(工程实践中有例外)。这使得Raft集群更容易分析、测试和调试。缺点是性能——因为集群中只有一台服务器与客户端通信，这在客户端活动激增的情况下可能成为瓶颈。当然这个可以通过一些工程手段在一致性和吞吐性能中做出平衡，例如我们可以放弃强一致的要求，从Follower中读取数据，减轻Leader的负担，关于一致性的部分，可以参考文章《共识、线性一致性、顺序一致性、最终一致性、强一致性概念区分》。
三、Why Elixir
本系列中介绍的Raft实现是用Elixir编写的。在笔者看来，Elixir具有三个优势，使其成为本系列和网络服务的有前途的实现语言：
Raft框架需要大量的网络编程，而Elixir基于Erlang在网络编程方面体验一骑绝尘，甚至自带RPC实现；Elixir自带一个功能强大的Shell，开发调试的难度大大降低；Raft这类算法需要大量的并发编程，而并发编程在Elixir中就像呼吸一样简单；Erlang语言的OTP框架大大降低的服务器编程的心智负担，常见的服务端编程场景都有合适的解决方案。这个项目的开发中，笔者借鉴了这个生产级别的开源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、网络分区等。
为了实现选主的逻辑，我们要引入一些概念：
1、任期（Term）
论文中的解释：任期（Term）是分布式系统中共识算法中的一个关键概念，尤其是在领导者选举（Leader Election）和共识达成过程中。任期是时间上的一个划分，用于组织和同步分布式系统中的事件，确保系统中的所有节点能够在一个明确的时间段内就某个领导者或一系列决策达成一致。
简单来说，任期标明了Leader的服役阶段。
任期这个概念有以下特性：
任期越大，话语权越大：本地任期较小的总是服从任期更高的消息来源。每次选举，任期都会+1：确保不会多个选举过程计票混乱。一山不容二虎：同个任期内最多只有一个Leader被选出。2、选举计时（Election Timer）
每个Follower都会在本地维持一个选举计时器，在选举计时器到期前，如果没有收到Leader的日志或者心跳，Follower就会认为Leader出了意外，那么就会开始发起选举。这里有几个常见问题：
Q：会不会有多个Follower同时成为候选人？
A：会的，为了避免这种情况出现，我们给选举计时器添加一些随机区间，这是Raft简单的原因之一。Raft使用这种随机化来降低多个Follower同时进行选举的机会。但是即使他们同时成为候选人，任何给定任期内也只有一个人会被选为领导人。在极少数情况下，如果选票分裂，没有候选人能获胜，将进行新的选举。
Q：如果Follower与集群断开连接（分区）怎么办？
A：这就是网络分区的隐蔽性，因为Follower无法区分谁被分区了。这种情况Follower会开始选举。但这种情况下Follower不会得到任何选票。这个节点可能会在候选状态中持续自旋（每隔一段时间重新启动一个新的选举），直到重新连接到集群。
3、消息类型
Raft中两个节点的通信类型多种多样，不过涉及到选主的部分较为简单，只有下图添加注释这4种消息类型：
4、状态机框架
从上述介绍中可以看出，选主这个过程涉及多个状态的轮转，每个状态下对不同消息做不同的反应，所以非常自然我们选择状态机的方式实现。
而Erlang OTP有个自带的状态机实现框架：gen_statem，有了这个利器，可以写出很清晰的状态机逻辑：
5、选举计时
我们这里的计时方式也是借鉴了“龙舟”的风格，即维护一个单位时间很小（1s）的本地时钟，其他超时事件全部用该时钟的整数倍来计算，这种方式配置和编码起来较为简单。
我们在代码中需要判断localTick的次数超出了electionTimeout，即可将自身状态转变为Candidate开启选主。
6、拉票
开启投票前Candidate需要做这几件事：
将自身的Term+1；投自己一票。完成这些后，就将携带新Term的消息发给所有其他的节点。
需要注意的是在这个Raft实现中，消息发送全部采用单向流，消息的发送和处理是隔离开的。
具体实现中则是使用了Erlang自带的RPC，简化了自己开发通信协议的成本。
7、处理拉票消息
由于Raft中任期概念的设计，其他角色在接收到拉票消息时需要考虑以下几种情况：
request_vote消息携带的Term大于本地Term这种情况较为简单，做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算法中规定，如下情况可以投赞成票：
这个任期中当前节点谁都没投过，这个消息来源第一个来拉票的，那就投给消息来源节点；
这个任期中当前节点投过了，而且我投的就是同个节点，那就不介意再投一次。
8、计票
Candidate在散出request_vote的消息后，会开始等待其他节点的回执，这时候有3种情况：
收到了更高Term的心跳或者其他消息这种情况说明集群中已经存在一个更高任期的节点，那也不需要继续选举了，直接默认该消息来源节点为Leader。这里和上文中处理更高Term的request_vote消息类似。
收到了半数以上的同意选票大部分节点同意了当前的选举要求，那该节点就成为这个任期的合法Leader：
Raft算法不会给Candidate无限的计票窗口，如果一直没有收到足够的选票，就清零计票，重置Term+1，再次发起选举，重复上述的过程，直到有个合法的Leader诞生。
接着上面网络分区的场景讨论，相信许多Raft系统的维护人员会发现，如果某个离群的节点在重新回归后会立即成为Leader，就是这个原因，离群的节点在不停的自旋选举过程中将自己的Term抬高了很多，一但回到集群就会因为Term优势成为Leader。为了解决这个问题，Raft有个prevote的补丁，这里暂不展开讨论。
来源：dbaplus社群一点号