Raft: In Search of an Understandable Consensus Algorithm

[Triple-Z]

https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

[Triple-Z]

Raft 是一个用于管理 replicated log 的一致性算法。相比于同类的算法 Paxos，Raft：

• 更容易被理解，因此也更容易被工程师实现。
• 将一致性的关键要素（如 leader 选举，日志复制，安全等）都拆分了出来，使得 Raft 有更好的一致性保证同时还能降低实现中需要考虑的系统状态的数量。
• 提出一个使用重叠大多数（overlapping majority）以保证安全的变更集群 membership （changing the cluster membership）的新机制。

Raft 几大特点：

• 强 Leader：日志记录只能从 Leader 发往其他 server。
• Leader 选举：通过随机计时器来选举 Leader。
• Membership 变更：通过「联合一致性（joint consensus）」机制，使得集群在配置变更时仍然可用。

[Triple-Z]

一致性算法之复制状态机（replicated state machine）

对于单主集群的系统（如 GFS、HDFS、RAMCloud）来说，可以通过使用复制状态机来实现 leader 崩溃后保持系统可用。

复制状态机一般通过一个复制日志来实现，由于状态机都具有确定性，只要顺序给予相同的输入，一定都有相同的结果。这也就是复制状态机的能够复制状态的原理。

一致性算法的作用就是保证复制日志的一致性。节点上的一致性组件将接收到来自客户端的请求（命令）并将其追加到自己的日志中。接着，要把命令顺序地发送到其他节点的一致性组件上。一旦这些命令被正确的复制完成（如达到半数以上节点完成复制任务），每个节点的状态机都会顺序处理这些命令（此处应得到相同的结果），并把结果发送给客户端。因此，这些节点一起组成了一个高可靠的状态机。

在实际系统中，一致性算法具有以下特点：

• 在所有非拜占庭条件[^1]下保证安全性。
• 只要多数节点（$n > N / 2$）存活，系统就能够正常工作。
• 不依赖于计时来保证日志一致性，错误的时钟和极端的信息延迟可能会导致严重的可用性问题。
• 在大多数场景下，命令会在得到多数节点确认后立刻得到响应，这样少数慢速节点不会影响到系统的整体性能。

[^1]: 非拜占庭条件（non-Byzantine conditions）：包括网络延迟、网络分区、网络丢包、网络包重复以及包乱序问题。

[Triple-Z]

面向可理解性设计

作者认为 Paxos 过于学术与复杂，不适合大众理解也不适合工程实现。

作者在设计 Raft 的期望：

1. must provide a complete and practical foundation for system building
2. must be safe under all conditions and available under typical operating conditions
3. must be efficient for common operations
4. must be possible for a large audience to understand the algorithm comfortably
5. must be possible to develop intuitions about the algorithm

提高可理解性使用的两种方式：

1. 拆分子问题：将一致性问题拆分为 领导选举、日志复制、安全以及 Membership 变更四个子问题。
2. 简化状态空间：日志不能有空洞，且 Raft 限制了日志不一致的情况。这样能让我们对更少的状态进行设计和考虑。