周末躺不平，摆不烂，卷不动，随便读一篇paper吧
原文：In Search of an Understandable Consensus Algorithm
作者：Diego Ongaro / John Ousterhout —— Stanford University
摘要
Raft是一个用于管理一份被复制的日志的共识算法，它和（multi-）Paxos产出的结果等价，和Paxos一样高效，但它的结构和Paxos不同。这让Raft比它更加易于理解，并且提供一个更好的构建实际系统的地基。为了便于理解，Raft拆分出了共识的关键元素，比如领导选举、日志复制以及安全，并且它使用了一种更强的一致性来减少我们必须考虑的状态数。从用户研究的结果来看，Raft对于学生比Paxos更加好理解。Raft也包含一个新的机制来改变集群的成员，该机制通过覆盖大多数（overlapping majorities）来保证安全。
1 介绍
共识算法允许一组机器作为一个一致组工作，即使某些成员出错了也能活下来。正是由于这一点，它们在构建可靠的大规模软件系统中成为了关键角色。Paxos在过去几十年里在共识算法的讨论中占有霸主地位：大多数共识算法的实现基于Paxos，或者受其影响，Paxos也成为教授学生共识算法时的主要工具。
不幸的是Paxos实在难以理解，尽管人们已经无数次尝试让它变得更简单，此外，想要支撑实际系统的话，它的架构需要复杂的改变，因此，无论是系统构建者还是学生都为Paxos苦苦挣扎。
在我们深陷Paxos泥潭后，我们开始寻找一种新的共识算法，它可以给系统构建以及教学提供更好的基础，我们的方法可能不太寻常，因为我们的主要目的是可理解性：我们是否可以为实际系统定义一个共识算法，并且使用比Paxos学习起来要明显简单的方式来描述它？此外，我们想要该算法可以促进对于系统构建者极为重要的直觉开发。重要的不仅仅是算法如何工作，而是要清楚的知道它为什么可行。
这项工作的结果就是一个被称作Raft的共识算法，在Raft的设计中，我们应用了特定的技术来提升可理解性，包括分解（Raft分解了leader选举、日志复制以及安全）、状态空间缩减（相对于Paxos，Raft减少了不确定性以及服务器之间可能不一致的成因）。一项来自两个大学的43名学生的用户研究表明，Raft显著地要比Paxos易于理解：在学习了两种算法后，33名学生相比于Paxos能够更好的回答有关Raft的问题。
Raft在很多方面与现存的共识算法相似，但它有多种新特性：
- 强leader：Raft使用一个比其它共识算法更强形式的领导权。举个例子，日志项只会从leader传递到其它服务器上，这简化了复制日志的管理，让Raft更加易于理解。
- Leader选举：Raft使用随机计时器来选举leader，这只会比其它共识算法需要的心跳机制添加少量的机制，同时可以快速简单的解决冲突。
- 成员变更：Raft的修改集群中的server集合的机制使用了一种新的共同共识（joint consensus）方式，在这种机制中，两种不同的配置中的大多数会在迁移过程中重叠，这允许集群在配置变更期间继续正常操作。
我们相信Raft比Paxos和其它共识算法更加优越，无论是对于教育用途还是作为真正实现的基础。它比其它算法更加简单，好理解；它的介绍已经足够满足实际系统的需求；它有很多开源实现，并且被很多公司使用；它的安全属性已经被证实定义并证明；并且它的效率也可以和其它算法搏一搏。
论文中的余下部份介绍了复制状态机问题（第二节），讨论了Paxos的优点和缺点（第三节），描述了我们实现可理解性的一般方法（第四节），展示Raft共识算法（第5到8节），评估Raft（第九节）以及讨论相关工作（第十节）。
2 复制状态机
共识算法通常在复制状态机的上下文中被提出。在这种方式下，一组server上的状态机计算相同状态的相同副本，并且在某些其它server down掉时继续操作。复制状态机被用于解决多种分布式系统中的容错问题，比如具有单一集群leader的大规模系统，如GFS、HDFS以及RAMCloud，通常使用一个独立的复制状态机来管理leader选举以及保存即使在leader崩溃时也必须存活的配置信息，复制状态机的例子包括Chubby以及Zookeeper。
图1：复制状态机结构。共识算法管理一个包含客户端发来的状态机指令的复制日志，状态机进程从日志中执行相同的指令，所以它们产生相同的结果
复制状态机通常使用复制日志实现，就像图1中那样。每一个服务器存储一个包含一个指令序列的日志，它的状态机将会按序执行。每一个（服务器上的）日志包含的指令顺序相同，所以每一个状态机进程执行相同的指令序列。因为状态机是确定性的，所以每一个状态机都计算相同的状态以及相同的输出序列。
保持复制日志的一致性是共识算法的任务，在server上的共识模块接受到客户端的指令，将它添加到自己的日志中，它与其他server上的共识模块交流以确保每一份日志最终包含具有相同顺序的相同的请求，即使某些server异常。一旦命令被正确复制，每一个服务器的状态机进程将以日志顺序来处理它们。结果就是，所有server表现得像一个单一的，高可靠的状态机。
实际系统的共识算法具有如下属性：
- 它们在所有非拜占庭条件下确保安全性（永远不会返回一个不正确的结果），包含网络延迟，分区以及丢包、重复包、乱序包
- 只要大多数server正常，并可以互相通信，也可以与客户端通信的话，系统就完全可用。因此一个典型的5个服务器的集群可以容忍任何两个服务器异常。假定服务器以停止的方式失败，并且它们稍后会从稳定性存储中恢复状态，重新加入集群
- 它们不依赖时间来确保日志一致性：错误的时钟和极端的消息延迟在最坏情况下可能导致可用性问题
- 一般情况下，一旦在单一一轮RPC调用中一个命令被集群中的大多数响应，它就可以完成。少量的慢server不会对系统的总体性能造成影响。
3 Paxos犯了什么错？
在过去的十年里，Leslie Lamport的Paxos协议已经成了共识的同义词：它是在课程里被使用的最广泛的协议，大多数共识的实现使用它作为出发点。Paxos首先定义了一个能够就单个决策达成一致的协议能力，比如单个日志条目的复制，我们称这个子集为单一法令 Paxos（single-decree Paxos）。然后，Paxos组合了该协议的多个实例来实现一系列的决策（multi-Paxos）。Paxos确保安全和活性，并且它支持修改就要成员，它的正确性已经被证明，并且它在常规情况下很高效。
不幸不幸不行不行，Paxos有两个显著的缺点。第一个就是Paxos极其难懂，很少有人能理解它的完整解释，并且要做到这一点需要付出巨大努力。结果就是，有很多用简单术语来解释Paxos的尝试。这些解释专注于单一法令Paxos，即使这样还是困难重重。在对NSDI 2012的参会者的非正式调查中，我们发现即使在经验丰富的研究人员中也鲜有人能够适应Paxos。我们选择自己深入Paxos泥潭，读了多份简化的解释，甚至设计了自己的替代协议后，我们也没能完整的理解它，这个过程持续了一年之久。
我们假设Paxos的不透明来源于它选择了单一法令自己作为基础。单一法令Paxos是难懂且微妙的：它氛围两个阶段，没有简单直观的解释，也无法被独立理解。因为这一点，建立关于单一法令协议如何正常工作的直觉很困难。multi-Paxos的组成规则显著的增加了复杂性和微妙程度。我们相信，就多个决策达成共识的问题（比如一份日志而不是单个条目）可以以另一种更加直接和明显的方式被分解。
Paxos的第二个问题是它没有提供一个对于构建实际实现的好的地基。一个原因是目前还没有被广泛认可的multi-Paxos算法。Lamport的大部份解说都是关于单一法令Paxos的，它描绘了达成multi-Paxos的可能性，但是很多细节是缺失的。已经有很多次充实和优化Paxos的尝试，但是它们之间相差甚远，与Lamport的描绘也相差甚远。Chubby这种系统实现了类Paxos的算法，但是它们大多数情况下的详情尚未公布。
此外，Paxos对于构建实际系统来说是一个糟糕的架构，这也是单一法令分解带来的另一个后果。举个例子，独立选择一组日志条目，然后将它们合并进顺序日志中并没有什么好处，只是增加复杂性。围绕日志来设计系统更加简单高效，新的条目以一种首先的顺序被依次添加。另一个问题是Paxos的核心使用对称的点对点方式（即使它最后提出了一种弱领导权形式作为性能优化），这在只有单一决定会被做出的世界中是有意义的，但是很少有系统使用这种方式。如果一系列决策必须被做出，先选择一个leader，然后让leader协调决策将更加简单快速。
作为结果，实际的系统与Paxos几乎没有相似之处，每一个实现从Paxos开始，发现实现中的困难，然后选择了一个显然不同的架构，这耗时且易出错，而理解Paxos的困难加剧了这个问题。Paxos的公式或许能很好的证明它的正确性，但是实际的实现与Paxos天差地别，这个证明几乎没有什么用。下面是一个来自Chubby实现者的典型评论：
在Paxos算法的描述和真实世界系统的需求之间存在着巨大的鸿沟，最终的系统将基于一个未被证明的协议...
因为这些问题，我们可以做出Paxos无法提供一个教学和系统构建的好的基础，因为共识在大规模软件系统中如此重要，我们决定看看是否能够设计出另一个比Paxos具有更好属性的共识算法，Raft就是该实验的结果。
4 为可理解性而设计
在设计Raft时我们有几个目标：它必须为系统建设提供完整和实践的基础，所以它必须显著的降低开发者的设计工作；它必须在所有条件下都是都是安全的，必须在典型的工作条件下是可用的；对于常规操作它必须是搞笑的。但是最最重要的目标——以及最重要的挑战——就是可理解性，它必须让大多数听众可以舒适的理解算法。此外，它必须可能开发对于算法的直觉，所以系统构建者可以做现实世界中的实现不可避免的扩展。
在Raft的设计中，很多时候我们必须在不同的方式中进行选择，在这些情况下，我们基于可理解性评估所有方式：解释每一个方式有多困难（比如它的状态空间有多复杂，是否存在微妙的含义）以及读者理解该方法和含义的难易程度。
我们认识到这种分析具有高度的主观性，尽管如此，我们使用了两种普遍适用的技术。第一个技术是问题分解的常见方式：我们尽可能的将困难拆分成相对独立的可被解决、解释以及理解的单独部分。比如，在Raft中，我们分割了领导选举，日志复制，安全以及成员变更。
我们的第二个方式是通过降低需要考虑的状态来简化状态空间，让系统更加好理解，尽可能的消除不确定性。特别地，日志不允许有洞，Raft限制了日志彼此之间变得不一致的方式。尽管大多数情况下我们尝试消除不确定性，还是有一些不确定性实际帮助理解了的情况。比如，随机方式引入了不确定性，但是它通过以一种想死的方式来处理所有可能的选择来降低状态空间（“随便选，不重要”），我们使用随机化来简化Raft的领导选举算法。
5 Raft共识算法
Raft是一个管理第2节中提到的复制日志的算法。图2简洁的总结了算法供参考，图3列出了算法的关键属性；这些图中的元素将在本节中的剩余部分讨论。
Raft通过先选择一个leader，然后赋予它管理复制日志的全部责任来实现共识。leader从客户端接受日志条目，将它们复制到其它server上，告诉server现在将日志条目应用到它们的状态机上是否安全。单一leader简化了复制日志的管理，比如，leader可以决定是否在日志中放置新条目，而不用咨询其它server，数据流以一种简单的方式从leader流向其它server。一个leader可以失败，或与其它server断连，在这种情况下，新server将会被选出。
在这种模式下，Raft将共识问题分解成三个相对独立的子问题，将在后面的小节中讨论：
- 领导选举：一个新的leader必须在现有leader fail时被选出
- 日志复制：leader必须从客户端接受日志项，将它们向集群中复制，强制其它的日志与它的保持一致（5.3小节）
- 安全：Raft的关键安全属性是在图3中的状态机安全属性：如果任何一个server应用了一个特定日志条目到它的状态机中，那么不会有其它的server应用一个不同的命令到相同的日志位置（log index）上。5.4小节描述了Raft如何保证这一属性；解决办法在选举机制上引入了额外的限制，将在5.2小节中描述。
在展示完共识算法后，本届将讨论可用性问题以及计时（timing）在系统中的作用。