Raft vs Paxos 我们是否在分布式共识上取得共识
概要
分布共识是构造分布式容错和强一致的分布式系统基本的原语。虽然许多分布式算法被提出了，但只有俩个主导了生产系统：paxos，一个传统的，著名的算法和raft一个最近被设置作为更容易被理解的选择。
在这篇论文中我们考虑思考问题，paxos和raft哪个才是更优秀的分布式共识，我们对俩者进行分析，通过描述一个简化的paxos算法使用raft的术语和实用的抽象。
我们发现paxos和raft是非常相似的分布式共识算法，只是在领导人选举上有所不同。值得注意的是，Raft只允许拥有最新日志的服务器成为leader，paxos允许任何服务成为leader，只要它随后更新的日志确保它是最新的。raft的方法非常的简单，不像paxos，它不需要日志条目在leader选举时切换。我们推测，raft大部分的可理解性来自论文清晰的表达，而不是底层算法的基础。
介绍
状态机复制被广泛用于构建基于一组不可靠的主机到单个可靠的服务，并提供强一致性于线性一致性。因此，程序可以使用状态机复制作为单个系统的实现，使得更容易推理预期的行为。状态机复制需要每个相同的服务以相同的顺序接受相同的日志，这可以通过分布式共识来实现。
Paxos算法与分布式共识紧密相关。尽管paxos取得了成功，但是它还是出了名的难以理解，难以推理，正确的实现以及安全的优化。我这在用更简单的术语解释算法的无数次尝试中是显而易见的，这也是raft算法的动机。
raft算法的作者声称raft和paxos一样有效， 并且比paxos更容易理解因此提供了基础来构建现实的分布式系统。raft通过三种不同的方式来实现这一点。
- presentation：首先，raft论文在状态机复制的上下文中介绍了一个新的基于共识算法的抽象。这个务实的表达已经被证明了非常受工程师的欢迎。
- 简单：其次，raft论文将简单至于性能之上。例如，Raft按需决定日志条目，而paxos通常允许乱序决策，但需要额外的协议来填补可能出现的空白。
- 底层算法：最后，raft算法使用了一个新的领导选举，从而改变了安全的保证方式。
raft立刻变得欢迎并且如今生产系统分为使用paxos的系统和使用raft的系统。
为了回答paxos和raft哪个是分布式共识更好的方案，我们必须先回答这俩个算法有什么不同。不止是能帮助我们评估这些算法，也让raft能够从paxos数十年的性能优化中所受益。
然而回答这个问题并不是直接的事，paxos通常paxos通常被认为不是一个单一的算法，而是解决分布式共识一系列的算法。paxos的通用性（或者说不规范）意味着对算法的描述各不相同，有的时候非常多。
为了克服这个问题，我们提出简化paxos的版本，这是通过调查研究发布的paxos中得出的结果。这个算法我们简称为paxos，更接近于paxos今天的使用方式，而不是最初的描述方式。在很多地方，它被称作multi-decree paxos，或者multi-paxos，不同于single-dcree paxos，单命令paxos决定于一个值，而不是一个完全有序的值序列。我们描述简化的算法使用raft论文中的风格，使得俩个算法更容易比较。
我们的结论是俩个算法没有明显的不同，raft的leader选举非常简单，效率高的惊人。
背景
这篇论文审查了状态机复制下的分布式共识算法。状态机复制需要应用确定的状态机被复制到跨越n个服务同时按照相同的方式应用。其使用通过分布式共识算法管理的日志复制来得到，通常是paxos或者raft。
我们假设系统是非拜占庭的，但不假设系统是同步的。消息可能存在任意的延迟，并且参与的服务可以以任意速度运行，但我们假设消息是可靠和有序的（通过使用TCP）。为了安全性，我们不依赖始终同步，但是为了活性，我们必须依赖时钟。假设n个服务都有自己独立的id。我们假设操作是唯一的，可以通过向每个操作添加一对序列号和服务器id轻松实现。
paxos和raft算法
许多共识算法包括paxos和raft使用基于leader的方法来解决分布式共识。在高层，这些算法运行如下。
n个中的一个服务被设计为leader。所有的状态机操作被发往leader。日志被发往主节点，然后主节点告诉其他服务做相同的事情。一旦leader收到了大部分服务的确认，它应用操作到自己的状态机。这个过程执行到leader故障，当leader故障哈斯，另一个服务接管leader。选举新leader的过程涉及大不分服务器，确保新的leader不会重写之前leader的日志。
我们现在评估paxos和raft算法的细节。我们关注与主要的元素，由于篇幅限制不比较垃圾收集，日志合并，读操作和变形的算法。
3.1 基本
如图1所示，一个服务器可以在三个状态中的一个
Multi-Paxos:
- Proposer：发起提案的节点（可能同时是Leader）。
- Acceptor：投票接受或拒绝提案的节点（类似Raft的Followers）。
- Learner：学习最终达成一致的值的节点（所有节点通常都是Learner）。
- Leader：通过竞争或优化产生的稳定Proposer（非正式角色，实际是Proposer的子集）。
Raft:
- Leader：唯一处理客户端请求、管理日志复制的节点。
- Follower：被动响应Leader和Candidate的请求。
- Candidate：竞选Leader的临时角色（选举期间）。
- follower：一种被动状态，只负责回复RPC
- candidate：当尝试使用RequestVotes RPC成为主节点时的一个活跃状态。
- leader：一个活跃状态，使用AppendEntries添加操作到日志中
最开始服务是follower状态。每个服务都是follower状态直到leader出现了故障。follower然后成为candidate，并且尝试使用requestVote RPC选举成为leader。如果成功了，candidate就变成leader。新leader定时发送Appendentries EPC作为保持来防止follower超时，重新变为candidate。
每个服务存储一个自然数term，term随着时间单调递增。发送服务器（以下简称发送方）的当前术语包含在每个RPC中。当服务接受到一个RPC，它（之后简称服务）首先检查当前任期。如果发送方的任期大于服务的任期，则服务端将会再响应消息之前更新自己的term号，如果服务器是candidate或者leader。如果发送者的任期等于服务端，那么服务端将会正常回复rpc。如果发送者的任期小于服务端，服务器将对发送者做出负面响应，包括响应任期。当发送方接收到这样的响应，它会降级为follower并且更新它人任期。
3.2 常规操作
当一个leader接收到一个操作，它伴随当前任期将操作追加到日志的结尾。这个操作条目被称为log entry。之后主节点发送Appendentries RPC给所有的其他服务并且附带新的log entry。每个服务维护一个提交索引，以记录哪些日志条目可以安全地应用于其状态机，并响应leader确认其成功接收到的日志条目。一旦leader接收到大部分服务器正面的回复，leader更新它的commit index并且应用操作到其状态机。之后leader将更新后的提交索引包含在后续的Appendentries中。
follower只会在其之前的日志与领导者的日志相同的情况下追加一个日志条目（或一组日志条目）。这确保了日志条目按顺序添加，防止了日志中的空洞，并确保了从节点应用正确的条目到它的状态机中。
3.3 处理leader故障
paxos中其实没有任期 term的概念，只有提案编号的概念proposal number。
这个过程程序到leader故障，需要建立一个新的leader。paxos和raft使用了不同的方法，因此我们依次描述它们。
paxos
follwer将会在没有接收到定期从leader那的Appendentries rpc后超时。然后它变成一个candidate，并将自己的任期号更新满足为满足以下条件的最小下一任期： t mod n =s.其中t代表下一任期号，n是服务器总数，s是该候选者的服务器id。candidate将会发送requestVote RPC给其他服务器。这个rpc包括了candidate的新任期和commit index。当一个服务器接收到requestVote rpc，如果发现任期比自己大，就给出正面回应。该响应还包含服务器在commit index之后日志中包含的所有日志项。
图2，三个服务器运行paxos算法。图a展示了当leader选举被触发时的日志。图b-d展示了在leader被选举之后，第一个Appendentries rpc被发出之前。黑线展示了提交日志，红线字体高亮日志的修改。
一旦candidate收到了大部分服务器的正面回复，candidate 在成为leader之前必须确保它的日志包含所有已提交的日志条目。它的做法如下。对于commit log之后的每个index，leader会检查它收到的日志条目以及它自己的日志。如果candidate看到了索引的日志条目，那么它将使用该条目和term语更新自己的日志。如果leader看到了同一个索引的多个日志条目，那么它将使用最大任期和新的条目更新自己的日志。一个例子在图2中给出。candidate服务器现在可以成为leader，并开始将其日志复制到其他服务器。
paxos会将之前任期的未提交的日志全部改成当前任期。
paxos实际上存在俩个阶段，prepare阶段和accpet阶段。假设有三个节点，b和c。
- prepare，节点A（提议者）生成一个Proposal number，发送给节点B和C。
- promise，节点B和C承诺之后不再接受更小的编号，并返回自己收到过最大的提案号。
- accept，节点A发现大部分节点收到了这个请求，那么发送accpet告诉B和C。B和C如果发现此时accept的id是自己收到过最大的则返回accepted。（如果B和C收到了更大的承诺就会返回更大的承诺号）
raft
至少一个follower会在收不到主节点的定期Appendentries rpc时超时。candidate将会发送requestVote RPC到其他的服务器。每个都包括了candidate的任期以及最后的日志条目和索引。当服务器接收到RequestVote请求时，如果候选人的任期大于或等于它自己的任期，它正面极响应，在这个任期内，它还没有为候选人投票，候选人的日志至少和它自己的日志一样最新。最后这个标准可以通过以下方式验证：确保候选人的最后日志任期大于服务器的最后日志任期；如果任期相同，则需验证候选人的最后日志索引大于服务器的最后日志索引。
一旦候选服务器从大多数服务器接收到积极的RequestVote响应，候选服务器就可以成为leader并开始复制其日志。但是为了安全起见，raft要求leader在提交只少一个新的条目之前不更新其commit index。由于在一个任期内可能会有多位候选人，因此选票可能会被分割，这样就不会有候选人获得多数选票。在这种情况下，候选人暂停并开始下一任期的新选举。
raft则避免去修改之前日志的任期，通过不允许节点提交之前任期的日志来实现。以防止之前的日志被当前节点提交
3.4安全性
俩个算法都遵循如下特性
状态机安全：如果一个服务已经将给定索引处应用于状态机，没有其他服务会应用在相同index下的不同的日志条目。
每个任期最多有一个leader，并且leader不会覆盖自己的日志，因此我们可以通过证明以下内容来证明这一点。
leader完备性：如果一个操作op是在任期t的index i提交的，那么所有term大于t的日志也会有操作op在index i处。
证明略。。。。
讨论
如果节点5尝试以编号5发起prepare，节点1,2,3会返回它们已经接受的值(来自节点4的提案)，节点5必须使用这个值而不是提出新值。因为这个值已经被大多数节点接受。
| paxos | raft | |
|---|---|---|
| 如何保证每个任期只有一个leader | 如果t mod n = s，服务器只能是term t中的候选者。每个term只有一个候选者，所以每个term只有一个leader | follower可以在任何任期内成为follower每个follwer每个任期只投票给一名candidate，因此只有一名能得到多数票。 |
| 它如何确保新领导的日志包含所有已提交的日志条目？ | 每个requestVote回复都包含follower的日志条目。一旦对象收到了来自大多数followerVote响应，它就会将term最高的条目添加到日志中。 | 当candidate的日志只少与follower一样新时，才会给它投票。整确保了candidate只有在其日志只少与大多数follower一样新时才能成为leader。 |
| 如何确保从之前的任期中安全的提交日志？ | 之前任期的日志被添加到leader的日志并附上leader的任期。然后leader复制日志条目，就好像它们来自leader的任期一样。 | leader将日志条目复制到其他服务器，而不更改term。leader在从自己的term复制后续的日志条目之前，不能认为这些条目（之前任期的）已经提交。 |
Raft和paxos的方法不同之处在table1中。我们比较俩个维度，可理解性和有效性来确定哪个最好的。
可理解性
raft保证了如果俩个日志维持相同的操作，那么它们会有相同的index和任期。也就是说，每个操作被指派一个唯一的索引和任期对。然而paxos确不是，其中操作可能被未来的leader被指派更高的任期，就像在图2b中演示的操作B和C一样。在paxos中，一个日志条目在修改之前可能会被重写。这是安全的，因为日志条目将只会被具有相同操作覆盖，但它不像raft那样直观。
另一方面，Paxos使得在大多数服务器上提交日志条目是安全的；但Raft的情况并非如此，它要求leader只提交前一个任期的日志条目，如果它存在于大多数服务器上，并且leader已经提交了当前学期的后续日志条目。
在paxos中，日志条目复制通过leader，要么来自当前任期，要么已经提交。我们可以在图2中看到这一点，其中leader上提交索引之后的所有日志条目都具有当前期限。而在raft中leader可能复制以前项中未提交的项。
总的来爱说，我们觉得raft的方法比paxos的方法更容易理解，但不明显。
有效性
在paxos中，如果多个服务同时变为了candidate，有更高任期的candidate会胜选。在raft中，如果多个服务同时变为了candidate，它们可能会切分选票，直到它们有相同的任期，因此没有人会赢得选举。Raft让follower在超时后从均匀随机分布中额外等待一段时间来缓解这种情况。因此我们预计raft在leader选举的时间上，既慢又有更高的方差。
然而，raft的选举阶段比paxos更轻量级。raft只允许有最新日志的candidate成为leader，因此在leader选举时不需要发送日志条目。而paxos不一样，其中每个每个正面的requestVote响应都包括在candidate提交索引之后的follower日志。有多重选项可以减少发送的日志条目数量，但最终，如果leader的日志不是最新的，则总是有必要发送一些日志条目。
paxos比raft发送更多的日志条目，不仅仅是requestVote响应，一旦一个candidate成为leader，它将会复制它的日志到所有的其他服务中。在paxos中，一个日志条目可能被leader赋予了新的term，因此leader可能发送将该日志条目的另一个副本发送到已经拥有副本的服务器。
而在raft中每个日志条目在日志中始终保持相同的term。paxos中有多个选项可以缓解这个问题，但它们超出了我们简化paxos的范围。
总的来说与paxos相比，raft的leader选举方法对于这样简单的方法来说是惊人的高效。
和经典paxos的关系
熟悉Paxos的读者可能会觉得我们对Paxos的描述与以前发表的描述不同，因此我们现在概述一下我们的Paxos算法与文献中其他地方发现的Paxos算法的关系。
角色：一些paxos的描述划分了paxos角色到三个部分：proposer，accepter和learner 或者leader，Acceptor 和replica。我们的表述使用了一个角色，即服务器，它包含了所有的角色。这个使用单个角色的表示也使用了副本名。
通常阶段1就是prepare和promise
阶段2就是accept和accpeted
术语：term（任期）也被指代view，ballot numbers，Proposal numbers，round numbers， squence numbers 或者 epochs。我们的leader也指代了master，primary，coordinator或distinguished proposer。通常服务器作为candidate的时期称为阶段1，prepare请求和响应或prepare和promise消息。Appendentries RPC通常指的是阶段2a和阶段2b的信息，accpet请求和响应或者propose和accpet消息。
任期：paxos需要全序的任期，每个服务器被分配一组不相交的任期（为了安全）并且每个服务可以使用任何大于之前的任期（为了活性）。同时一些paxos的描述使用了循环自然数，其他使用了按字典序排序，由整数和服务器ID组成，其中每个服务只使用term包含自己id的任期。
排序：我们的日志条目被复制并按顺序确定。这不是必须的单这避免了填充日志空都的复杂性。类似地，Paxos的一些描述限制了并发决策的数量，这通常是重新配置所必需的。
总结
raft算法解决了长期存在的学习paxos算法中的可理解性问题。在这篇论文中我们演示了更容易理解的raft的实际抽象和更优雅的表达。通过使用raft的方法描述paxos，我们发现俩个算法只在leader选举时有区别。
- paxos在服务器之前划分term，而raft允许follower称为任何term的后选人，但follower每个term只能投票给一个candidate。
- paxos的follower会投票给任何的candidate，而raft的follower只会投票给日志最新的candidate。
- 如果leader未能在之前的任期提交日志，paxos会复制他们到当前的任期，而raft会保持它们的原始状态
raft论文声称raf更容易理解和有效。相反，我们发现这两种算法在可理解性上没有显著差异，但Raft的leader选举与Paxos相比，惊人的轻量级。俩个算法的表达都非常的原始，可以优化来提高性能，尽管通常以增加复杂性为代价。