Raft 是一种一致性算法，旨在在分布式系统中确保数据的一致性。TiKV 使用 Raft 来管理数据的复制和一致性。Raft 算法通过选举机制、日志复制和故障恢复等功能，确保系统在面对节点故障时仍能保持高可用性和一致性。
Raft 基本概念
节点角色：
- Leader：负责处理客户端请求，复制日志条目给 Follower，并管理集群的状态。
- Follower：被动地接受 Leader 的日志复制请求，不直接处理客户端请求。
- Candidate：在 Leader 失效时，Follower 可以成为 Candidate，发起选举以成为新的 Leader。
日志条目：每个日志条目包含一个唯一的索引和一个任期号，用于记录操作和其顺序。
任期（Term）：Raft 协议按任期划分时间段，每个任期开始于一次选举，可能有一个 Leader 也可能没有。
Raft 运行机制
选举
当一个 Follower 在一定时间内没有收到 Leader 的心跳消息时，它会成为 Candidate，并发起选举。选举过程如下：
- 增加任期号：Candidate 增加自己的任期号。
- 投票给自己：Candidate 投票给自己。
- 请求选票：Candidate 向其他节点发送请求选票的消息。
- 接收投票：其他节点收到请求选票的消息后，如果它们没有投票给其他候选人，并且 Candidate 的日志比自己的日志更新，则投票给 Candidate。
- 赢得选举：如果 Candidate 获得多数票（超过半数），它就成为新的 Leader。
日志复制
Leader 负责将客户端的写请求转换为日志条目，并将其复制到 Follower。日志复制过程如下：
- 接收写请求：Leader 接收客户端的写请求，将其作为新的日志条目添加到本地日志中。
- 发送 AppendEntries 消息：Leader 将新的日志条目通过 AppendEntries RPC 发送给所有 Follower。
- 接收确认：Follower 接收并持久化日志条目，并返回确认消息给 Leader。
- 提交日志：当 Leader 收到多数 Follower 的确认后，提交日志条目，并将结果返回给客户端。
- 应用日志：Leader 和 Follower 将已提交的日志条目应用到状态机中。
日志一致性
Raft 通过以下机制确保日志的一致性：
- 日志匹配属性：如果两个日志在同一个索引位置有相同的任期号，那么它们之前的所有日志也必须相同。
- 日志复制规则：Leader 只会提交自己当前任期的日志条目，并且只有在它已知该条目已被大多数节点复制时才会提交。
- 日志修复：如果 Follower 的日志落后于 Leader，Leader 会通过发送缺失的日志条目来修复 Follower 的日志。
- 故障恢复：Raft 能够处理各种故障情况，包括 Leader 故障和网络分区。
故障恢复机制如下：
- Leader 故障：如果 Leader 发生故障，Follower 会在超时后发起选举，选出新的 Leader。
- Follower 故障：如果某个 Follower 发生故障，Leader 继续正常工作，并在 Follower 恢复后重新同步日志。
- 网络分区：当网络分区发生时，少数派无法选出新的 Leader，直到网络恢复后，少数派的节点会重新加入集群并同步数据。
具体实现
在 TiKV 中，Raft 的实现主要通过以下步骤进行：
- 初始化 Raft Group：每个 Region 对应一个独立的 Raft Group，包含多个副本。
- 处理客户端请求：Leader 节点接收客户端请求，生成日志条目并复制到 Follower。
- 日志复制和提交：通过 AppendEntries RPC 进行日志复制，并确保日志一致性。
- 选举和故障恢复：通过心跳机制和选举机制，确保集群在 Leader 故障时能够迅速恢复。
Raft 作为 TiKV 的核心一致性算法，通过选举、日志复制和故障恢复等机制，确保数据在分布式环境中的一致性和高可用性。TiKV 的 Raft 实现不仅保证了数据的一致性，还提供了高性能的读写操作，使其成为分布式存储系统的理想选择。
