【免费】Raft一致性算法中文翻译版(格式同原论文)

5星 · 超过95%的资源需积分: 0 155 浏览量更新于2023-05-21 评论 1 收藏 1.78MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Translated by Linqiang Wang (https://github.com/brandonwang001/raft_translation) 1

寻找一种易于理解的一致性算法

(扩展版)

Diego Ongaro and John Ousterhout

Stanford University

摘要—Raft 是一种基于日志复制的一致性算法。Raft 的

结果等价于 (multi-)Paxos 并且和 Paxos 一样的有效，但却

和 Paxos 的结构完全不同。正是 Raft 不同于 Paxos 的结构

使得 Raft 更容易理解，并且更易于工程实现。Raft 通过将一

致性关键点进行拆解，包含选主、日志复制和安全三部分，另外

通过减少状态机的状态使得 Raft 更容易理解。通过学生学习

Raft 和 Paxos 的分析，结果显示 Raft 相比于 Paxos 更容易

理解。Raft 创新的使用了一种新的机制来处理集群中机器的变

更。

I. 简介

一致性算法可以使得若干机器像一个一致集群一

样的工作，即使在集群成员变更或者宕机的情况下，整

个集群仍然可以正常工作。正因为如此一致性算法在大

规模分布式系统中扮演着至关重要的角色。过去的〸

年，paxos 统治了整个一致性算法。大多数一致性算法

的实现都是基于 Paxos 或者受到 Paxos 的影响，同时

一致性算法课程大多也是讲授 Paxos。

不幸的是，Paxos 晦涩难懂，尽管很多人努力尝试

让 Paxos 更容易理解。除此之外，在实际系统中，实现

者必须根据系统作出大量的调整。结果，系统开发者和

学生都为了理解 Paxos 在苦苦挣扎。

我们也是苦苦的与 Paxos 斗争，后来我们希望找到

一个既容易实现又利于学生学习的一致性算法。所以我

们寻找一致性算法的首要目标就是易于理解：我们可以

定义一种比 Paxos 利于实现和学习的一致性算法？进

一步我们希望算法可以让系统开发者有直观感受和理

解。我们认为算法能工作很重要，更重要的是让算法实

现者直观到理解它为什么可以工作。

为了设计 Raft 算法，我们使用了特定的技术来使

算法更容易理解，包括分解法（Raft 分解为选主、日志

复制和安全）和状态空间简化（相较于 Paxos，Raft 减

少了未定状态的数量）。我们分析两个学校 43 名同学

的学习情况，结果显示 Raft 比 Paxos 更容易理解：学

习过两种算法后，他们中的 33 位同学可以更好的解答

Raft 中的问题相比于 Paxos。

Raft 和存在的一些一致性算法是相似的，但是也

有它自己新颖的特点：

• Strong leader：Raft 使用了一种比其它一致性算

法更强的 leader。比如，日志记录只能从 leader 复

制到其它机器，这样可以简化日志复制和降低理解

难度。

• Leader election：Raft 使用了随机定时器来选择

leader。通过在心跳上增加一些小的改动，可以简

单快速的解决冲突。

• Membership changes：Raft 使用了一种联合一

致性的方法，使得集群中的机器发生变更的时候，

整个集群也可以正常的工作。联合一致性配置是两

个不同配置的大多数机器的重叠。

我们相信 Raft 不管是在教学或者实现方面都是优

于其它一致性算法。我们详细的描述可以让开发者更简

单的进行系统的实现。另外已经有几个公司公开了自己

的实现，Raft 的安全性是验证和证明的，同样它也和其

它一致性算法一样有效。

文章接下来会在第二节讲述复制状态机，第三节会

讨论 Paxos 的优缺点，第四节会描述易于理解方法，第

五-八节会描述 Raft 一致性算法，第九节会评估 Raft，

第〸节讨论我们的相关工作。

II. 复制状态机

通常提到一致性算法都会提到复制状态机 [37]。在

复制状态机中，集群中所有的机器有相同的日志副本，

即使集群中某些集群宕机，整个集群仍然可以正常工

作。复制状态机通常被用来解决分布式系统的容错问

Translated by Linqiang Wang (https://github.com/brandonwang001/raft_translation) 2

题。例如：例如 GFS、HDFS 和 RAMCloud 等大规模

系统中，通常使用分离的状态机来管理选主和存储配置

信息。Chubby 和 ZooKeeper 中也使用了复制状态机。

复制状态机通常是通过复制日志来实现的，如图 1

所示。每个机器的 log 文件中包含了一系列的命令，这

些命令将会被按顺序执行到状态机。每个机器的日志包

含相同的命令并且命令都有相同的顺序，如果状态机按

相同的顺序执行命令。由于状态机初始化状态是相同

的，并且按照相同顺序执行相同的命令，那么必然状态

机有相同的输出。

一致性算法的工作就是保证各个状态机一致。机器

上的一致性模块接受到来自客户端的命令，并把命令追

加到自己的日志中。然后和其它机器上的一致性模块进

行通信来保证最终所有机器都按相同的顺序存储了请

求，即使其中的一些机器宕机不能工作。一旦命令被正

确的复制，每个机器都按照日志顺序将命令执行到状态

机，然后将输出返回给客户端。最终，所有的机器呈现

一个高度可靠的状态机。

实际系统的一致性算法具有一下的特性：

• 在非拜占庭条件下必须是安全的，不会返回错误的

结果。例如：网络延时、分区、丢包、重复和乱序

等。

• 在集群中大多数机器可以正常工作的情况下，整个

集群必须是可用的。一个 5 机器的集群可以容忍两

台机器的宕机。我们假定机器宕机后可以从稳定存

储介质恢复并重新加入到集群中。

• 它们不依赖时间来保证日志的的一致性：错误的时

钟和巨大的消息延迟，在极端情况下，会导致集群

的不可用。

• 在正常情况下，集群中的机器在一轮 RPC 下就可

以完成一次日志的复制，个别较慢的机器不能影响

整个系统的性能。

III. Paxos 存在的问题

过去〸年，Leslie Lamport 的 Paxos 算法等同于一

致性算法。许多学校会教授 Paxos 算法，许多算法也是

依据 Paxos 进行实现的。Paxos 是第一个能对单次提议

达成一致的协议，就好像单条日志复制。我们把达成单

次一致的协议称为 single-decree Paxos。Paxos 通过一

系列单次一致的实例来达到对一系列的提议达成一致，

这被称作 multi-Paxos。Paxos 算法可以保证安全和存

活，同时也支持集群成员变更。Paxos 的正确性是被证

明的，并且在正常情况下是有效的。

不幸的是，Paxos 有个显著的缺点。第一个缺点就

是 Paxos 晦涩难懂。很多人投入大量的经历，但是只

有很少的人真正的理解 Paxos。已经有很多学者尝试

以更容易理解的方式解释 Paxos。这些解释都是集中在

single-decree Paxos，但是仍然存在很大的挑战。通过调

研我们发现很多人不满 Paxos，即使很多很有经验的研

究者。为了设计我们的算法，我们阅读了很多简单的解

释，并尝试设计可用的算法，整个过程花费大约 1 年的

时间。

我们认为 Paxis 晦涩难懂的原因是因为 Paxos 选

择了

single-decree Paxos

作为基本的子问题导致的。

single-decree Paxos 是紧凑且精巧的，它的两个阶段

是不能独立分开的，并且通过简单的直觉进行理解和解

释。正因为如此，很难形成 single-decree Paxos 为什么

可以正常工作的直觉。multi-Paxos 更是增加了额外的

复杂度和精密度。我们相信整个问题可以达到一致是通

过多次的决定，并且可以被拆分进行直观的理解。

Paxos 存在第二个问题是它不能简单的转化为工程

实现，一方面是大家没有对 multi-Paxos 算法达成一致。

Lamport 大神只是详细的描述了 single-decree Paxos，

但是很多细节还是缺失的。还存在很多基于 Paxos 的

变种和分支。Chubby 是基于 Paxos 进行实现的，但是

它们的实现细节并没有公开。

另外，Paxos 的结构决定它很难用来实现实际的系

统，这是 single-decree Paxos 不能分解导致的必然结

果。举个例子，通过单独的选择日志记录的集合并把它

们聚合在一个顺序日志中，并不能带来太多的收益，但

Translated by Linqiang Wang (https://github.com/brandonwang001/raft_translation) 3

是却增加了额外的复杂度。设计一种只是按照严格顺序

进行追加的日志是简单和更为有效的。此外 Paxos 采用

了对称的点对点通信的方法作为它的核心（尽管是出于

一种基于弱领导的性能优化）。上面的优化仅仅对于单

次决定是有意义的，但是实际系统很少采用这种方法。

如果有一些的提议需要被决定，首先选举出一个 leader

然后由 leader 进行协调，这样是更为简单和快速的。

现实中的系统仅有很少和 Paxos 中描述的系统相

似。每个实际系统都是从 Paxos 开始，发现实现中有很

多不能解决的难题，然后提出一个新的结构并实现。这

是耗时且容易犯错的，然后 Paxos 的晦涩难懂进一步

使情况恶化。Paxos 的范式可能是一种证明一致性理论

的好方法，但是实际的实现中 Paxos 不具备很大的价

值。下面来自 Chubby 开发者的评论更正说明这一点：

实际系统的实现和 Paxos 所描述的算法中存在巨

大的鸿沟... 最终实现的系统将是基于一个未被证明的

协议

因为这些问题的存在，我们认为 Paxos 并不适合系

统实现和教学。在大规模软件系统中一致性至关重要，

我们决定尝试是否可以设计一种和 Paxos 有相同特性

且易于理解的算法。Raft 正是我们试验的产物。

IV. 为了理解而设计

设计 Raft 时，我们有几个目标：它对于系统的开

发必须是完整和易于实现的，这样可以减少开发者大量

不必要的设计工作；它必须在所有条件下是安全的，并

在典型条件下是可用的；另外对于正常操作它必须是有

效的。但我们最重要的目标是（也是最大的挑战）是易

理解性。它必须是大多数读者可以舒适的理解的。此外，

它必须可以让系统开发者有直观的感受，这样系统开发

者可以在实际的实现中可以更好的进行扩展。

下面会列举一些在设计 Raft 算法过程中，怎样从

很多候选的方法中进行选择的考虑点。我们还是根据候

选方法的可理解性来进行评估：每种候选的方法是否易

于解释的？（例如，它的状态机空间复杂？它是否有暗

含的精巧设计？）是不是可以让一个读者很容易的理解

它的潜在表达。

我们承认这样的分析存在很大主观成分，不可否认

的是我们使用了两种通用的技术：第一个技术是众所周

知的问题分解法，我们尽可能将问题分解为独立的可以

被解决，易于解释和理解的子问题。例如：在 Raft 中

我们利用问题分解法分为 4 个独立的问题：选主、日志

复制、安全和成员变更。

第二个技术是通过减少需要考虑的状态来简化状

态空间。这样使得系统更加一致并尽可能消除不确定的

状态。特别的，Raft 不允许日志中出现空洞，并且禁

止这样的情况发生。空洞会导致集群中的日志产生不一

致。尽管我们尽力来消除不确定状态，但是在一些情况

下，增加不确定状态可以更好的帮助理解算法。特别是，

随机化方法会引进不确定状态，但是它可以简化状态空

间通过以相同的方式来处理所有可能的选择（”choose

any；it doesnt matter”）。我们使用了随机化的方法来

简化 Raft 的选主算法。

V. Raft 一致性算法

Raft 是一种管理如第二节所描述的状态机的算法。

图 2 以紧凑的格式总结了算法中的术语和定义。图 3

列举了算法的关键特性；这些图中的定义和术语将会在

接下来的章节进行详细的讲解。

Raft 实现一致性是首先选择一个确定的 leader，然

后 leader 负责管理日志复制。leader 接受来自客户端的

请求并追加到本地日志，然后把日志复制到其它的机器

并告诉其它机器什么时候可以安全的将日志应用到状

态机。集群存在一个 leader 的好处可以简化日志复制

的管理。例如，leader 可以决定日志的追加，而不需要

经其它机器的同意。整个集群的数据流向也是从 leader

流向其它机器。如果 leader 宕机或者网络断开，其它的

机器可以重新选举一个新的 leader。

使用选主的方法，Raft 可以将一致性问题分解为 3

个相对独立的子问题，下面的子章节将对这些问题进行

讨论:

• Leader election：第 5.2 节将讨论，当一个 leader

宕机后，一个新的 leader 必须被选举。

• Log replication：leader 必须响应客户端的请求，

并把日志复制到整个集群来保证其它机器的日志和

自己的相同。

• Safety：图 3 中的状态机的安全是 Raft 优先保证

的：如果任意一台机器将一条特定的日志应用到自

己的状态机，那么其他的机器就不能应用一条不同

的日志到自己的状态机。在 5.4 节描述了 Raft 是

如何保证这个特性的；解决这个问题的方案就是在

选举是增加额外的规则约束（5.2 节）。

在讲述完一致性算法后，这一章节还会讨论可用性

的问题和时间在系统中的角色。

Translated by Linqiang Wang (https://github.com/brandonwang001/raft_translation) 4

State

所有机器需要持久化的状态：

(在 RPC 响应之前，需要更新稳定存储介质)

currentTerm server 存储的最新任期（初始化为 0 且单调递增）

votedFor 当前任期接受到的选票的候选者 ID（初值为 null）

log[] 日志记录每条日记记录包含状态机的命令

和从 leader 接受到日志的任期。(索引初始化为 1)

所有机器的可变状态：

commitIndex 将被提交的日志记录的索引（初值为 0 且单调递增）

lastApplied 已经被提交到状态机的最后一个日志的索引（初值为

0 且单调递增）

leader 的可变状态：

(每次选举后重新初始化)

nextIndex[] 每台机器在数组占据一个元素，元素的值为下条发送

到该机器的日志索引 (初始值为 leader 最新一条日

志的索引 +1)

matchIndex[] 每台机器在数组中占据一个元素，元素的记录将要复

制给该机器日志的索引的。

AppendEntries RPC

被 leader 用来复制日志 (5.3 节)；同时也被用作心跳 (5.2 节)

Arguments：

term leader 任期

leaderId 用来 follower 重定向到 leader

prevLogIndex 前继日志记录的索引

prevLogItem 前继日志的任期

entries[] 存储日志记录

leaderCommit leader 的 commitIndex

Results：

term 当前任期，leader 用来更新自己

success 如果 follower 包含索引为 prevLogIndex 和任期为

prevLogItem 的日志

接受者的实现：

1. 如果 leader 的任期小于自己的任期返回 false。(5.1)

2. 如果自己不存在索引、任期和 prevLogIndex、prevLogItem

匹配的日志返回 false。(5.3)

3. 如果存在一条日志索引和 prevLogIndex 相等，

但是任期和 prevLogItem 不相同的日志，

需要删除这条日志及所有后继日志。（5.3）

4. 如果 leader 复制的日志本地没有，则直接追加存储。

5. 如果 leaderCommit>commitIndex，

设置本地 commitIndex 为 leaderCommit 和最新日志索引中

较小的一个。

RequestVote RPC

被候选者用来收集选票：

Arguments：

term 候选者的任期

candidateId 候选者编号

lastLogIndex 候选者最后一条日志记录的索引

lastLogItem 候选者最后一条日志记录的索引的任期

Results：

term 当前任期，候选者用来更新自己

voteGranted 如果候选者当选则为 true。

接受者的实现：

1. 如果 leader 的任期小于自己的任期返回 false。(5.1)

2. 如果本地 voteFor 为空，候选者日志和本地日志相同，

则投票给该候选者 (5.2 和 5.4)

Rules for Servers

所有机器：

1. 如果 commitIndex > lastApplied：增加 lastApplied，并将日志

log[lastApplied] 应用到状态机。

2. 如果 RPC 请求中或者响应中包含任期 T>currentTerm，

参与者该机器转化为参与者。

参与者（5.2 节）：

1. 响应来自候选者或者 leader 的请求。

2. 如果选举定时器超时时，没有收到 leader 的的追加日志请求

或者没有投票给候选者，该机器转化为候选者。

候选者（5.2 节）：

1. 一旦变为候选者，则开始启动选举：

1.1 增加 currentTerm

1.2 选举自己

1.3 重置选举定时器

1.4 并行发送选举请求到其他所有机器

2. 如果收到集群大多数机器的选票，则称为新的 leader。

3. 如果接受到新 leader 的追加日志请求，则转化为参与者。

4. 如果选举定时器超时，则重启选举。

leaders：

1. 一旦当选：发送空的追加日志请求（心跳）到其它所有机器；

在空闲时间发送心跳，阻止其它机器的选举定时器超时。

2. 如果接受到来自客户端的请求，追加日志记录到本地日志，

如果成功应用日志记录到状态机则回应客户端。

3. 如果某个参与者的最新日志索引大于等于本地存储该参与者的

最新日志索引：给该参与者发送包含从 nextIndex 开始的

日志追加请求。

3.1 如果成功，更新该参与者的 nextIndex 和 matchIndex。（5.3 节）

3.2 如果由于日志不一致而失败，减少 nextIndex 并重试。(5.3 节)

4. 如果存在 N > commitIndex（本地待提交日志的索引），

majority(matchIndex[i]>= N)（如果参与者大多数的

最新日志的索引大于 N），并且这些参与者索引为 N

的日志的任期也等于 leader 的当前任期：commitIndex =N

（leader 的待提交的日志索引设置为 N）(5.2 和 5.4 节)。

剩余18页未读，继续阅读

JeremyLiao

2021-04-25

不错，不错，收藏学习

sinat_24947735

粉丝: 0
资源: 2

会员权益专享

Raft一致性算法中文翻译版(格式同原论文)

评论1

会员权益专享

最新资源

Raft一致性算法中文翻译版(格式同原论文)

评论1

Raft论文中文翻译版

分布式一致性算法Raft协议

详解分布式共识（一致性）算法Raft

Raft算法在一致性哈希环中的应用

Raft算法与分布式一致性

Raft算法中的安全性保障与数据一致性控制

Raft算法与分布式一致性协议

分布式系统中的一致性算法与Go语言实现

能给我具体讲讲raft一致性算法吗

paxos和raft分布式一致性算法

ap算法 java_对标Eureka的AP一致性，Nacos如何实现Raft算法

什么是一致性算法，以及其应用场景

分散式控制的一致性算法

分布式一致性算法的实现

怎么将分布式一致性算法加入到simulink中

分布式一致性算法matlab

raft的java实现

一致性算法matlab编程

哪些中间件应用Raft算法？

raft共识算法原理

会员权益专享

最新资源