Raft 算法

Raft 是 Diego Ongaro 和 John Ousterhout 于 2014 年提出的分布式共识算法，目标是易于理解和实现。Raft 将共识分解为领导者选举、日志复制、安全性三个子问题，广泛应用于 etcd、Consul、TiKV。

Raft 的设计目标

Raft 的设计目标是易于理解。Lamport 的 Paxos 算法虽然理论完备，但难以理解和实现。Raft 通过分解问题、限制状态空间，使得算法易于理解。

Raft 的另一个目标是工程实用。Raft 的实现相对简单，性能良好，适合作为工程实践的参考。

Raft 的角色

Leader（领导者）

Leader 处理所有写请求，将日志复制到 Follower。Leader 是唯一的，系统中最多有一个 Leader。Leader 有一个任期（Term），任期号单调递增。

Leader 的职责：接收客户端请求、将请求追加到日志、复制日志到 Follower、提交已提交的日志、发送心跳维持 Leader 地位。

Follower（跟随者）

Follower 响应 Leader 的请求，包括日志复制请求和心跳请求。Follower 被动接收 Leader 的指令，不主动发起请求。

Follower 的职责：响应 Leader 的日志复制请求、响应 Leader 的心跳请求、如果长时间未收到 Leader 心跳，则转为 Candidate。

Candidate（候选人）

Candidate 是选举时的临时角色，候选投票给自己，请求其他节点投票。获得多数票的 Candidate 成为 Leader。

Candidate 的职责：发起选举、投票给自己、请求其他节点投票、如果获得多数票则转为 Leader、如果发现更高任期的 Leader 则转为 Follower。

Leader 选举

选举触发

Follower 如果长时间（election timeout，通常 150-300ms）未收到 Leader 心跳，则认为 Leader 故障，转为 Candidate，发起选举。

Candidate 增加当前任期号，投票给自己，然后向其他节点发送 RequestVote 请求。

投票规则

节点收到 RequestVote 请求后，如果满足以下条件，则投票给 Candidate：Candidate 的任期号大于自己的任期号，或者相等但未投票；Candidate 的日志至少和自己一样新（日志的任期号和长度比较）。

每个节点在每个任期只能投票一次，先到先得。

选举结果

如果 Candidate 获得多数票（N/2 + 1），则成为 Leader，开始发送心跳。

如果 Candidate 收到更高任期的 Leader 的心跳或 AppendEntries 请求，则转为 Follower。

如果 Candidate 的选举超时，仍未获得多数票，则开始新一轮选举（增加任期号）。

选举安全性

选举安全性：每个任期最多有一个 Leader 被选出。这是因为投票规则保证了只有拥有最新日志的 Candidate 才能获得多数票。

Leader 完整性：如果日志条目在某任期被提交，那么该条目会出现在所有更高任期的 Leader 的日志中。这是因为新 Leader 必须拥有所有已提交的日志条目。

日志复制

日志结构

日志由有序的日志条目组成，每个条目包含索引、任期号、命令。索引是日志条目的位置，从 1 开始。任期号是 Leader 提出该条目时的任期。命令是状态机的操作（如 SET x = 1）。

复制流程

Leader 接收客户端请求，将命令追加到本地日志，然后发送 AppendEntries 请求给 Follower。AppendEntries 请求包含：任期号、前一个日志条目的索引和任期、新日志条目、当前提交索引。

Follower 收到 AppendEntries 请求后，如果前一个日志条目匹配（索引和任期都匹配），则追加新日志条目；否则拒绝。

如果 Follower 的日志与 Leader 不一致（前一个日志条目不匹配），Leader 会递减前一个日志条目的索引，直到找到匹配的条目，然后覆盖 Follower 冲突的日志条目。

日志提交

当日志条目被多数派（N/2 + 1）复制，Leader 认为该条目已提交，可以应用到状态机。Leader 在后续的 AppendEntries 请求中携带提交索引，通知 Follower 提交已提交的日志条目。

日志匹配特性

如果两个日志包含相同的索引和任期号，那么该索引之前的所有日志条目都相同。这是因为 AppendEntries 请求只在匹配时才追加日志，覆盖不一致的日志。

日志压缩

日志无限增长会占用大量磁盘空间。Raft 通过快照（Snapshot）压缩日志。快照是状态机在某个时刻的完整状态，包含最后应用的日志索引和任期。

Leader 定期创建快照，丢弃快照之前的日志。Follower 如果落后太多，Leader 可以发送快照而不是日志条目。

快照的问题：快照创建需要时间，会阻塞状态机。快照传输需要网络带宽。快照的安装需要时间，会阻塞日志复制。

Raft 的安全性

选举安全性

每个任期最多有一个 Leader 被选出。这是因为投票规则保证了只有拥有最新日志的 Candidate 才能获得多数票。

Leader 完整性

如果日志条目在某任期被提交，那么该条目会出现在所有更高任期的 Leader 的日志中。这是因为新 Leader 必须拥有所有已提交的日志条目。

日志匹配性

如果两个日志包含相同的索引和任期号，那么该索引之前的所有日志条目都相同。这是因为 AppendEntries 请求只在匹配时才追加日志。

领导者完备性

如果某个日志条目在某个任期被提交，那么该条目会出现在所有后续任期的 Leader 的日志中。这是因为新 Leader 必须获得多数票，而多数派中必然包含拥有该条目的节点。

Raft 的实现

Raft 的实现相对简单，但有细节需要注意。心跳是空的 AppendEntries 请求，用于维持 Leader 地位。选举超时是随机的（150-300ms），避免同时发起选举导致分裂投票。日志一致性检查通过前一个日志条目的索引和任期实现，确保日志匹配。

Raft 的优化

成员变更

Raft 的成员变更需要安全地增加或删除节点。直接变更可能导致两个 Leader 同时存在（分裂脑）。联合一致性（Joint Consensus）是 Raft 的成员变更方法，通过两阶段变更实现。

优先级选举

Raft 可以给节点设置优先级，优先级高的节点更容易成为 Leader。这可以用于将 Leader 迁移到性能更好的节点。

只读请求

如果只需要读操作，可以绕过 Leader，直接从 Follower 读取。但需要保证读到已提交的数据，可以通过 Leader 线性一致性读或租约机制实现。

Raft 的应用

etcd：CoreOS 的分布式键值存储，用于服务发现、配置管理。etcd 使用 Raft 保证数据一致性。

Consul：HashiCorp 的服务网格工具，用于服务发现、配置管理。Consul 使用 Raft 保证一致性。

TiKV：PingCAP 的分布式事务型键值数据库，使用 Raft 实现数据复制。

Raft 是工程实践的共识算法，易于理解和实现，性能良好。理解 Raft 有助于理解分布式系统的协调问题。