Raft 协议

Codebase（WIP）

引子

今年夏天在准备面试时，看了陈皓老师对于分布式锁的分享¹，随后查阅了一些关于分布式事务的资料，以及阅读《数据密集型应用系统设计》。再后来打算更深入了解下用于实现多数据节点间状态同步的分布式共识协议，详细看了下 Raft 协议的 paper²。写这篇文章来记录下自己的思考，也打算自己试着实现下这个协议。

分布式共识协议主要研究，在网络通信、机器运行状态等无法得到有效保证的情形下，由多个数据节点组成的分布式系统应如何尽可能保持数据状态的一致。如今分布式系统无处不在，如 Kafka、Redis、K8s、ElasticSearch 等常见的服务组件皆涉及分布式共识协议。

最早的分布式共识协议是 Paxos³，但 Paxos 难于理解且很难直接应用于实际环境，通常需要对协议进行改进以满足实际应用。在这个背景下，斯坦福大学团队希望构建一个更易理解及能够直接应用于实际环境的分布式共识协议，最终提出了 Raft 协议。

Raft 协议的工作机制

从编写代码以实现 Raft 协议的角度来看，我首先需要考虑，当启动一个运行 Raft 协议的服务后，这个服务将如何工作，可以分为两种情况：

当前环境不存在可加入的集群，此服务会创建一个新集群，成为 leader 节点，并等待其他节点加入；
当前环境存在可加入的集群，此服务试图加入这个集群。

对于情况 1，如果此服务的配置文件未指定其他节点，那么它将创建一个新集群，创建一个初始term（term = 0），并成为 leader 节点。

从一个新创建的数据节点出发。

为了易于理解，Raft 协议将共识协议分为几个独立模块：

Leader 选举
日志复制
安全性

需要搭建一个网络框架，用于数据节点间的互相通信
需要支持配置文件
每个请求需要有唯一的序列号，用于保证请求的幂等性
只有 leader 节点可以处理写请求
为保证返回最新的数据，只有 leader 节点可以处理读请求
需要实现一个定时任务框架，用于实现 leader 节点与数据节点间定时的心跳检测

当一个节点想要加入一个集群时，首先需要找到该集群的 leader 节点，该节点会向集群中的任意节点发起请求（RequestVote RPC），如果接收到请求的节点不是 leader 节点，那么此节点会拒绝这个请求，并返回其最近知晓的 leader 节点的信息（参考 paper 第 8 节）

分割成任意长度的 term，那节点之间需要保证 term 长度一致吗？

如果是第一个节点，

第二步数据节点需要追赶 leader 节点的数据状态。这个过程是通过 AppendEntries RPC 完成的，AppendEntries RPC 具有一致性检查功能。

leader 节点需要维护每个数据节点的nextIndex。

log entry 包含 term 与 log index。

Once a follower learns that a log entry is committed, it applies the entry to its local state machine (in log order).

Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index. §5.3

In Raft, the leader handles inconsistencies by forcing the followers’ logs to duplicate its own.

{
    "server_id": 1,
    "listen_address": "127.0.0.1:3456",
    "nodes": [
        "127.0.0.1:8081",
        "127.0.0.1:8082"
    ]
}

新 leader 会初始化所有节点的next_index，然后检查每个 follower 节点的日志记录，直至找到日志一致的最大索引。

选举时，follower 节点会通过检查 candidate 节点的term与index 以确定 candidate 的日志是否不比自己旧，如果比自己旧，则拒绝投票请求，优先比较term，term越大日志越新，如果term相同，则比较index，index越大日志越新。

某个节点一定包含其最新日志之前的所有日志。

新 leader 会提交之前 leader 未提交的日志。