TiKV 的 Raft 逻辑梳理总结

作者： Lystorm 原文来源：https://tidb.net/blog/254a9186

Raft 是一种一致性算法，旨在在分布式系统中确保数据的一致性。TiKV 使用 Raft 来管理数据的复制和一致性。Raft 算法通过选举机制、日志复制和故障恢复等功能，确保系统在面对节点故障时仍能保持高可用性和一致性。

Raft 基本概念

节点角色：

• Leader：负责处理客户端请求，复制日志条目给 Follower，并管理集群的状态。

• Follower：被动地接受 Leader 的日志复制请求，不直接处理客户端请求。

• Candidate：在 Leader 失效时，Follower 可以成为 Candidate，发起选举以成为新的 Leader。

日志条目：每个日志条目包含一个唯一的索引和一个任期号，用于记录操作和其顺序。

任期（Term）：Raft 协议按任期划分时间段，每个任期开始于一次选举，可能有一个 Leader 也可能没有。

Raft 运行机制

选举

当一个 Follower 在一定时间内没有收到 Leader 的心跳消息时，它会成为 Candidate，并发起选举。选举过程如下：

1. 增加任期号：Candidate 增加自己的任期号。

2. 投票给自己：Candidate 投票给自己。

3. 请求选票：Candidate 向其他节点发送请求选票的消息。

4. 接收投票：其他节点收到请求选票的消息后，如果它们没有投票给其他候选人，并且 Candidate 的日志比自己的日志更新，则投票给 Candidate。

5. 赢得选举：如果 Candidate 获得多数票（超过半数），它就成为新的 Leader。

日志复制

Leader 负责将客户端的写请求转换为日志条目，并将其复制到 Follower。日志复制过程如下：

1. 接收写请求：Leader 接收客户端的写请求，将其作为新的日志条目添加到本地日志中。

2. 发送 AppendEntries 消息：Leader 将新的日志条目通过 AppendEntries RPC 发送给所有 Follower。

3. 接收确认：Follower 接收并持久化日志条目，并返回确认消息给 Leader。

4. 提交日志：当 Leader 收到多数 Follower 的确认后，提交日志条目，并将结果返回给客户端。

5. 应用日志：Leader 和 Follower 将已提交的日志条目应用到状态机中。

日志一致性

Raft 通过以下机制确保日志的一致性：

1. 日志匹配属性：如果两个日志在同一个索引位置有相同的任期号，那么它们之前的所有日志也必须相同。

2. 日志复制规则：Leader 只会提交自己当前任期的日志条目，并且只有在它已知该条目已被大多数节点复制时才会提交。

3. 日志修复：如果 Follower 的日志落后于 Leader，Leader 会通过发送缺失的日志条目来修复 Follower 的日志。

4. 故障恢复：Raft 能够处理各种故障情况，包括 Leader 故障和网络分区。

故障恢复机制如下：

1. Leader 故障：如果 Leader 发生故障，Follower 会在超时后发起选举，选出新的 Leader。

2. Follower 故障：如果某个 Follower 发生故障，Leader 继续正常工作，并在 Follower 恢复后重新同步日志。

3. 网络分区：当网络分区发生时，少数派无法选出新的 Leader，直到网络恢复后，少数派的节点会重新加入集群并同步数据。

具体实现

在 TiKV 中，Raft 的实现主要通过以下步骤进行：

1. 初始化 Raft Group：每个 Region 对应一个独立的 Raft Group，包含多个副本。

2. 处理客户端请求：Leader 节点接收客户端请求，生成日志条目并复制到 Follower。

3. 日志复制和提交：通过 AppendEntries RPC 进行日志复制，并确保日志一致性。

4. 选举和故障恢复：通过心跳机制和选举机制，确保集群在 Leader 故障时能够迅速恢复。

Raft 作为 TiKV 的核心一致性算法，通过选举、日志复制和故障恢复等机制，确保数据在分布式环境中的一致性和高可用性。TiKV 的 Raft 实现不仅保证了数据的一致性，还提供了高性能的读写操作，使其成为分布式存储系统的理想选择。