#写在前面

一直以来， 对Raft协议的理解感觉都没有非常到位， 本着眼过千遍， 不如手过一遍的原则， 利用空闲时间， 就自己把Raft翻译一遍， 加深自己的理解， 也方便其他同学参考。


Raft协议英文版


参考资料：

https://github.com/ongardie/dissertation#readme

计划分三部分：

第一部分： 原文的1 ~ 4章；

第二部分： 原文的第5 章；

第三部分： 原文的6 ~ 10 章

寻找一种可以理解的一致性算法

摘要

Raft是一种管理复制日志的算法。 它产生了一种结果和（multi-)Paxos一样， 并且和Paxos同样有效， 但是结构不同于Paxos的算法；它使得Raft比Paxos更加容易理解， 同时也为构建实际系统提供更好的基础组件。为了增强可理解性， Raft把一致性的关键元素进行了分割， 例如leader选举， 日志复制以及安全性， 并且Raft增强了要考虑的状态的相关性来减少状态的数量。从一份用户调查的展示结果来看， Raft对于学习者来说比Paxos更加容易。 Raft也包含了一种新的改变集群成员的机制， 它使用包含大多数来保证安全性。

1 简介

一致性算法允许一组机器成为一个相关的工作组， 即便有一些成员发生故障， 它还能提供服务。因此， 它在构建可靠的大规模软件系统中扮演了关键的角色。 Paxos[13,14]在过去十年内在讨论一致性算法一直占据主导地位：绝大部分的一致性的实现是基于Paxos或者受到它的影响， 而且Paxos已经成为教导学生一致性的主要的工具。

在我们自己艰难的尝试过Paxos后， 我们尝试去找到一种新的一致性算法， 它能够提供系统构建和教育的功能。 我们方法不是常规的， 因为我们的主要目标是可理解性： 我们能不能定义一种新的相对于Paxos更容易学习的算法给实际的系统？ 此外，我们想要这个算法为系统构建者提供直观的开发功能。不但该算法能够work很重要， 它为什么可以work的原因很明显也同样重要。

这项工作的结果是一个被称为Raft的一致性算法。 在设计Raft的过程中， 我采用了几种特别的技术来提高可理解性， 包括分解（Raft分割leader选举， 日志复制以及安全性）和状态空间的减少（相对于Paxos， Raft 减轻了不确定性的程度以及服务器相互不一致的程度）。 一份包含2个大学的43名学生的报告显示：Raft比Paxos明显容易理解：学习过2种算法之后， 其中33名学生能够回答关于Raft的问题， 这比Paxos要好。

Raft 和很多现存的一致性算法（最为明显的， OKi和Liskov的Viewstamped Replication[27,10]）类似， 但它有一些新颖的特性：

• Strong leader： Raft相比其他的一致性算法， 使用了更强的领导形式。 例如， 日志单元仅仅从leader流向其他的服务器。 这简化了日志复制的管理同样令Raft更容易理解。
• Leader election： Raft使用随机的定时器来选主。 它只是增加了有限的机制给任意的一致性算法的心跳过程， 但是可以很简单并且迅速的解决冲突。
• Membership changes： Raft针对集群中的状态发生变化的服务器采用了联合一致性（joint consensus）的方法， 这里在状态转变过程中， 2种不同配置的大多数节点是重叠得到。

论文的剩余部分，介绍复制状态机问题（Section 2）， 讨论Paxos的优点和缺陷（section 3）， 描述我们对可理解性的基本方法（section 4), 说明Raft的一致性算法（section 5 – 7）， 评估Raft（Sectoin 8）， 讨论相关的著作（Section 9）。 由于篇幅的原因， Raft 算法的一些元素在这里被省略了， 它们可以从扩展的技术报告【29】里面得到。 其他的资料描述了客户端如何和系统交互， 以及在Raft中 日志空间是如何被回收的。

2 复制状态机

典型的复制算法在上下文中会采用复制状态机【33】。 在这种方法中， 在一组有相同副本的机器上计算状态机， 即便有一些机器发生故障， 系统还可以工作。 复制状态机被用来解决一系列分布式系统的容错问题。 例如， 在大规模的系统中， 有一个集群的leader， 比如GFS【7】， HDFS【34】 以及RAMCCloud【30】， 通常使用一个复制状态机来管理leader选举和保存用来恢复的leader 挂掉时候的配置文件。 Chubby【2】和ZooKeeper【9】是使用复制状态机的例子。

复制状态机的典型实现是采用Figure 1所示的复制日志。 每一个服务器保存一份日志， 里面包含一连串的状态机按顺序执行的命令。每一份日志包含相同顺序的相同的命令， 因此状态机按照相同的顺序执行命令。 由于状态机的确定性， 每一个计算节点有相同的状态以及相同的输出顺序。

一致性算法保持复制日志的一致性。 服务器上的一致性模块从客户端收到命令， 把它们加到日志里。它和其他服务器上的一致性模块进行通信， 来保证即便一些服务器发生故障，每一份日志实际上包含相同的顺序的相同的请求。 一旦命令被正确的复制， 每一个服务器的状态机执行它们按照日志的顺序， 结果被返回给客户端。 结果， 这些服务器看起来形成了一个单一的可靠地状态机。实际系统的一致性算法通常有如下的属性：

• 保证安全性（从来不返回不正确的结果）在非拜占庭条件下， 包括网络延时， 分组， 和报文丢失， 重复， 和重新排序。
• 大多数服务器可用时完全的发挥功能（可用的），相互之间以及与客户端通信。这样， 一个典型的集群包含5个服务器能够容忍2个服务器发生故障。停止服务的服务器被认为发生故障， 它们随后可能会恢复为稳定存储的状态并且重新加入集群。
• 它们不依赖于定时来保证日志的一致性：错误的时钟和极大的消息延时都能在最坏的情况下造成可用性的问题。
• 在通常情况下， 一条命令能够完成一旦集群中的大多数响应了远端程序调用； 少数的慢的服务器不会影响系统的性能。

3 Paxos的问题是什么？

在过去的10年里， Leslie Lamport 的Paxos协议【13】已经几乎成了一致性的同义词：它是课堂上最常教的协议， 许多一致性的实现以它为起点。 Paxos 首先定义了一个可以达成单一的决定的协议，例如一个单一的复制日志项。 我们称该子集为single-decree Paxos。 接着， Paxos 联合多个实例的该协议， 促使产生了一些列的决定， 例如日志（multi-Paxos）。 Paxos安全性和存活性， 并且它支持成员的状态变化。 它已经被验证了正确性， 在一般的实例下很有效。

不幸的是， Paxos有两个重要的缺陷。第一个缺点是Paxos非常的难以理解。 完整的解释【13】是臭名昭著的模糊不清， 付出了极大的努力， 几乎没人能够理解它。 结果， 就有了一些尝试来用更简单的方式解释Paxos 【14,18,19】， 这些解释集中在single-decree 子集， 但是任然有很大的困难。 在NSDI 2012， 有一个非正式的调查，我们发现很少有人对Paxos感到舒服， 包含海量的研究者。我们竭尽全力与Paxos斗争， 我们一直无法理解Paxos直到读了一些简化的解释和花了计划一年设计另外一个协议。

我们推测Paxos的晦涩难懂来自于它选择single-decree子集作为基础。 Single-decree Paxos是密集的和微妙的： 它被分成2个没有简单的直观的解释而且它们不能被独立的理解。 由此， 开发直观性让single-dcree 协议工作是困难的。 Multi-Paxos的合并规则极大地增加了复杂性和微妙性。 我们相信整个一致性的问题在于多个决定（比如， 一份日志而不是一条日志）可以被分解， 采用其他更加直接和直观的方式。

Paxos的第二个问题是他没有为创建实际实现提供好的基础。 一个原因是对于multi-Paxos没有一个广泛一致的算法。 Lamport的说明大部分是single-decree Paxos， 他勾画了可能的multi-Paxos的方法， 不是很多细节是缺失的。已经有一些尝试和优化Paxos， 例如，【24】， 【35】和【11】，但是它们各不相同， 也不同于Lamport的框架。 像Chubby这样的系统实现了类似Paxos的算法， 但是大部分的细节没有公开。

此外， Paxos的结构不太适合构建实际的系统， 这是single-decree分解的另一个结果。 比如， 选择一系列独立的日志单元然后把它们肉合成一个按顺序的日志是没有什么益处的， 它只会增加复杂性。 给日志设计一套系统使得它很明显的按照一定的顺序执行是简单而且有效的。 Paxos的另外一个问题是它的内核里面使用了对称的点到点的方法（尽管它确实建议了一种弱的主从关系作为一种性能优化）。这在只有一个节点做决策的简单环境中是合理的， 但是很少有实际的系统采用这种方法。如果必须要做出一系列的决定， 首先选出一个主节点， 然后由这个主节点协调它们会更简单更快。

结果，实际的系统很少和Paxos协议有相似之处。 每一个实现以Paxos开始， 发现实现它的各种困难， 然后开发一套很不相同的架构。这个过程是费时间的， 并且是容易出错的， 在Paxos之下的这些困难加剧了这些问题。 Paxos的公式也许能够很好的证明它的理论的正确性， 但是实际的实现又是如此的不同， 这使得这些证明的证据毫无意义。如下Chubby开发者的评论是非常典型的：

Paxos的算法描述和实际的系统需求之间有如此巨大的差异…最后的系统将会基于一个没有证明过的理论【4】

由于这些问题， 我们得出结论：Paxos没有给构建系统和学校教育提供一个很好的基础。 考虑到一致性在大规模软件系统的重要作用， 我们决定去尝试看能不能实现另外一种比Paxos有更好的属性的一致性算法， Raft就是该尝试的结果。

4 为可理解性的设计

我们曾为设计Raft设定了几个目标：它必须能够为实际系统提供一个完整而且实用的基础， 以便它可以极大地减少开发者的设计的工作量； 它必须在任何条件下都是安全的并且对于常用的操作是有效的。 但是我们的最重要的目标-且是最难的挑战-是可理解性。它必须使大量的受教育者能够很容易的理解它的算法。另外， 它必须要能够有开发的直观性， 以便系统构者能够在实际设计的时候不可避免的进行扩展。

在设计Raft的时候， 有很多的要点决定这我们从候选的方法中选择出Raft的方案。在这些情况下我们基于可理解性评估这些可选方案：解释每一种方案的难度（例如， 它的状态有多复杂， 并且是否有微妙的不确定性？）， 并且对于读者来说，完全理解这个方法和含义有多容易？

我们认识到这样的分析有高度的主观性， 不过， 我们使用了两种普遍使用的技术。第一个技术是众所周知的问题分解的方法：只要有可能， 我们把问题划分成可以相对独立的被解决， 解释和理解的部分。 比如， 在Raft里， 我们划分了选主， 日志复制， 安全性以及成员变化。

我们的第二个方法是通过要考虑的状态数目， 使系统更耦合和去除不确定性来简化状态空间。尤其是， 日志不允许有间隔， Raft限制了日志不一致的方式。 虽然在大部分情况下我们尽量消除不确定性， 在一些情况下不确定性提高可理解性， 尤其， 随机的方法引进不确定性， 但是它通过处理各种选择用类似的方式（“任选一个， 这不重要”）减少状态空间。 我们使用了随机的方法来简化Raft选主的算法。