Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可理解性,Raft 将一致性算法分解成了几个关键模块,例如领导人选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。一项用户研究的结果表明,对于学生而言,Raft 算法比 Paxos 算法更加容易学习。Raft 算法还包括一个新的机制来允许集群成员的动态改变,它利用重叠的大多数来保证安全性。
一致性算法允许一组机器像一个整体一样工作,即使其中一些机器出现故障也能够继续工作下去。正因为如此,一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色。在过去的 10 年里,Paxos 算法统治着一致性算法这一领域:绝大多数的实现都是基于 Paxos 或者受其影响。同时 Paxos 也成为了教学领域里讲解一致性问题时的示例。
但是不幸的是,尽管有很多工作都在尝试降低它的复杂性,但是 Paxos 算法依然十分难以理解。并且,Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中。因此工业界和学术界都对 Paxos 算法感到十分头疼。
努力研究过 Paxos 算法之后,我们开始寻找一种新的一致性算法,可以为构建实际的系统和教学提供更好的基础。与 Paxos 不同,我们的首要目标是可理解性:我们是否可以在实际系统中定义一个一致性算法,并且比 Paxos 算法更容易学习。此外,我们希望该算法方便系统构建者的直觉的发展。重要的不仅仅是算法能够工作,更重要的是能够很清楚地知道它为什么能工作。
Raft 一致性算法就是这些工作的结果。在设计 Raft 算法的时候,我们使用一些特别的技巧来提升它的可理解性,包括算法分解(Raft 主要被分成了领导人选举,日志复制和安全三个模块)和减少状态机的状态(相对于 Paxos,Raft 减少了非确定性和服务器互相处于非一致性的方式)。一份针对两所大学 43 个学生的研究表明 Raft 明显比 Paxos 算法更加容易理解。在这些学生同时学习了这两种算法之后,和 Paxos 比起来,其中 33 个学生能够回答有关于 Raft 的问题。
Raft 算法在许多方面和现有的一致性算法都很相似(主要是 Oki 和 Liskov 的 Viewstamped Replication),但是它也有一些独特的特性:
我们相信,Raft 算法不论出于教学目的还是作为实践项目的基础都是要比 Paxos 或者其他一致性算法要优异的。它比其他算法更加简单,更加容易理解;它的算法描述足以实现一个现实的系统;它有好多开源的实现并且在很多公司里使用;它的安全特性已经被正式定义和证明;它的效率和其他算法比起来也不相上下。
接下来,这篇论文会介绍以下内容:复制状态机问题(第 2 节),讨论 Paxos 的优点和缺点(第 3 节),讨论我们为了可理解性而采取的方法(第 4 节),阐述 Raft 一致性算法(第 5-8 节),评价 Raft 算法(第 9 节),以及一些相关的工作(第 10 节)。
一致性算法是从复制状态机的背景下提出的(参考英文原文引用37)。在这种方法中,一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如,大规模的系统中通常都有一个集群领导人,像 GFS、HDFS 和 RAMCloud,典型应用就是一个独立的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

图 1
图 1 :复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。