Raft一致性算法论文
需积分: 1 77 浏览量
2024-05-14
11:23:24
上传
评论
收藏 1.26MB PDF 举报
本篇博客为著名的 RAFT 一致性算 法 论文的中文 翻 译 ，论文名为 《 In search of an
Understandable Consensus Algorithm (Extended Version)》(寻找一种易于理解的一致性算法)。
Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的，但是它
和 Paxos 的结构不一样；这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理
解性，Raft 将一致性算法分为了几个部分，例如领导选取（leader selection），日志复制
（log replication）和安全性（safety），同时它使用了更强的一致性来减少了必须需要考虑
的状态。从用户学习的结果来看，Raft 比 Paxos 更容易学会。Raft 还包括了一种新的机制
来使得动态改变集群成员，它使用重叠大多数（overlapping majorities）来保证安全。
1. 引言
一致性算法允许一组机器像一个整体一样工作，即使其中的一些机器出了错误也能正常工
作。正因为此，他们扮演着建立大规模可靠的软件系统的关键角色。在过去的十年中
Paxos 一直都主导着有关一致性算法的讨论：大多数一致性算法的实现都基于它或者受它
影响，并且 Paxos 也成为了教学生关于一致性知识的主要工具。
不幸的是，尽管在降低它的复杂性方面做了许多努力，Paxos 依旧很难理解。并且，Paxos
需要经过复杂的修改才能应用于实际中。这些导致了系统构构建者和学生都十分头疼。
在被 Paxos 折磨之后，我们开始寻找一种在系统构建和教学上更好的新的一致性算法。我
们的首要目标是让它易于理解：我们能不能定义一种面向实际系统的一致性算法并且比
Paxos 更容易学习呢？并且，我们希望这种算法能凭直觉就能明白，这对于一个系统构建
者来说是十分必要的。对于一个算法，不仅仅是让它工作起来很重要，知道它是如何工作
的更重要。
我们工作的结果是一种新的一致性算法，叫做 Raft。在设计 Raft 的过程中我们应用了许多
专门的技巧来提升理解性，包括算法分解（分为领导选取（leader selection），日志复制
（log replication）和安全性（safety））和减少状态（state space reduction）（相对于
Paxos，Raft 减少了非确定性的程度和服务器互相不一致的方式）。在两所学校的 43 个学
生的研究中发现，Raft 比 Paxos 要更容易理解：在学习了两种算法之后，其中的 33 个学生
回答 Raft 的问题要比回答 Paxos 的问题要好。
Raft 算法和现在一些已经有的算法在一些地方很相似（主要是 Oki 和 Liskov 的 Viewstamped
Replication。但是 Raft 有几个新的特性：
强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志条
目只从领导者发送向其他服务器。这样就简化了对日志复制的管理，使得 Raft 更易于理解。
领导选取（Leader Selection）：Raft 使用随机定时器来选取领导者。这种方式仅仅是
在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。
成员变化（Membership Change）：Raft 为了调整集群中成员关系使用了新的联合一致
性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交迭
（overlap）。这使得在配置改变的时候，集群能够继续操作。
我们认为，Raft 在教学方面和实际实现方面比 Paxos 和其他算法更出众。它比其他算法更
剩余34页未读，继续阅读
资源评论
