共识算法杂谈

Posted on

本文从共识问题开始讲起，一步步演化出basic paxos，然后分析部分基于paxos的共识算法，包括multi-paxos、raft

共识问题

所谓共识问题就是要在多个参与者之间确定一个不可变变量的值，所谓不可变变量就是这个值一旦确定之后就不可再变了。看到这里，大部分人的疑惑就是，我要做的是一个分布式存储系统或者是数据库，你给我确定一个值有什么用呢？其实这里的不可变变量只是实际应用场景的一个抽象，在日常中通常是要配合状态机进行使用的，所谓状态机就是对于一系列相同的输入，它的最终输出结果总是一样的。所以我们可以用这个不可变变量作为多个状态机的输入，来确保所有状态机下的输出结果是一致的。例如对于一个存储系统来说，这个不可变变量可以是一条日志记录，一条日志记录确定以后，它是永远不会再变的，之后通过在多个数据副本上应用这条日志记录就可以确保副本之间保持一致。

basic paxos演进

通常我们说的paxos算法是指basic paxos，它是共识领域里最经典的算法，本文不讲它的证明，而是从实际应用角度来看它是如何一步步演进而来的。
首先，paxos要解决的是如何设计有一个系统来确定一个不可变变量的值（var），同时它应满足如下特性：

  • 系统需要满足正确性，一旦某个提案被选定后，var的值就不可再变了
  • 系统需要具有容错性

在paxos算法中，主要有两类角色，分别是proposer和acceptor，其中proposer负责生成提案，acceptor负责对提案进行投票，两类角色是可以重合的。为了演进出最终的解决方案，我们可以先将问题简化，先生存简单方案，一步步改进直至演化成最终的方案。

方案1

首先假设系统中只有一个acceptor和多个proposer，在这种情况下，最有效的方式就是加锁，即proposer在生成提案之前，首先需要向acceptor取申请锁，谁先获得锁就获得提案权，所以最终只有一个proposer会获得提案权，这样就可以确保系统的正确性，因为acceptor只会收到一个提案，这个提案会最终被选定。此时方案一就类似一个两阶段提交协议，它的整体流程如下：

  • proposer向acceptor申请锁，acceptor若还未发放锁，则将锁发放给请求锁的proposer
  • proposer获取到锁之后便可发起提案，acceptor则会通过该提案

但是这种方式又一个问题就是容错性很低，acceptor异常退出或者抢到锁的proposer在发出提案之前异常退出都会导致这个系统的不可用，下面来看改进方案2。

方案2

方案1中假设一个acceptor在抢到锁后还没来得及发出提案就异常退出了，此时整个系统就不可用了，为了解决这个问题，这里的锁可以变为抢占式的锁，即acceptor可以向多个proposer发放锁，只有最新的锁才是有效的。所以此时需要给每个锁赋予一个唯一性id来标记锁的新旧程度，这就是paxos中proposal number的意义，proposal number越大，锁就越新。这样当一个proposer异常退出之后，其他的proposer仍旧可以获得提案权。当一个proposer获得锁之后就可以发送提案给acceptor，如果此时没有发放更新的锁，那么该提案就可以被选定，如果已经发放了更新的锁，该提案就会被拒绝。该方案的整体流程如下：

  • proposer向acceptor申请锁，acceptor若还未选定提案，则总是发放锁该proposer，同时记录下当前最新的锁序号
  • proposer获取到锁后，需要生成提案发送给acceptor，同时提案总要带上自身的锁序号
  • acceptor收到提案之后，若该提案对应的锁是最新的，则选定该提案，否则拒绝

方案3

上述方案还有一个明显问题就是acceptor挂掉后整个系统就不可用了，所以在这个方案基础之上我们需要引入多个acceptor，此时仍旧采用可抢占式锁方案，这也是basic paxos的基本流程：

  • proposer在提案之前需要先从acceptor处申请锁，只有获取到半数有以上acceptor发放的锁后才能发起提案
  • 在接收到获取锁的请求后，如果acceptor还未同意提案，则将锁发放给proposer，同时记录下自身当前最新的锁，若已经同意提案，咋需要将提案及对应的锁编号返回给proposer
  • 在获取到半数以上aceptor发放的锁之后，proposer才可以发起提案。若有acceptor已经同意了提案，则acceptor需要从中选出编号最大的提案作为自身的提案发送给acceptor，否则的话可以生成新的提案
  • 一个acceptor收到提案之后，若该提案对应的锁对于自身来说值最新的，则同意该提案
  • 一个提案被半数以上acceptor同意后就表示该提案已经被选定了

上面就是basic paxos的整体流程，大部分描述中，proposal number即是对应上文的锁编号，大部分资料描述中都是proposer自己生成proposal number，proposer需要带上proposal number去请求acceptor，这种描述的整体流程和效果也是一样的。另外proposer采用当前最大编号的提案作为自身提案的原因如下：

  • 为了确保paxos的正确性，即提案被选定后就不能修改了，因为一个提案被选定后一定会被某些acceptor返回给proposer，proposer采用该提案作为自身的提案值就可确保最终的提案值不会被修改了

以上就是basic paxos的基本流程，在实际使用过程中通常proposer和acceptor两种角色都是会重合的，同时也可能会增加learner的角色来学习提案，用它来分担读请求压力。另外上述basic paxos在实际使用过程中可能存在一个活性的问题(liveness)，即有可能无法选出最终提案或花费较长时间才选出，因为锁是抢占式的，所以可能存在一个proposer还来不及生成提案锁又被抢走了，循环反复下系统一直处以抢锁状态而无法生成提案，所以在实际过程中一般会先选定一个proposer leader,只有该leader拥有提案权，这样可能有效解决这个问题，同时降低网络流量。

multi-paxos

前文说到，basic paxos是用来确定一个变量，而multi-paxos则是就一批提案达成一致，这也是日常应用中使用的paxos。最简单粗暴的方法就是对于每个提案都运行basic paxos的完整流程，先抢锁然后再生成提案，这样显然效率不是很高。所以日常使用的multi-paxos在basic paxos基础上做了如下优化：

  • 选取一个proposer leader，只有该leader具有生产提案的权利，通过basic paxos的抢锁流程即可选出leader
  • leader是有任期的，leader需要跟系统中的其他角色保持心跳联系来维持自身的任期
  • 在一个leader的任期内，它可以直接跳过抢锁阶段，直接生成提案，这样能减少网络交互，提高效率

实际应用

raft

基本问题

原始的paxos较难理解同时更多的是停留在理论证明层面，而raft就是以paxos为基础，提出的更加具体、更易懂、更加工程化的一种共识算法。它将paxos拆分成以下三个子问题：

  • 选主
  • 日志复制
  • 安全性

选主

raft限制一个时刻只有一个节点可以发起提案，这样能极大简化算法的实现，这个节点就是leader节点。因为raft需要解决的第一个问题就是：

  • 如何保证一个时刻最多只有一个leader节点
  • 在一个leader节点异常后如何尽快选出新的leader

在raft协议中，存在三种角色，分别是leader,follower,candidate，状态转换图如下所示：

整体流程如下：

  • 所有节点以follower角色启动
  • leader周期性发送心跳给所有follower
  • 在超时时间内未收到心跳包的follower会变为candidate，将自身term增加1，然后发起选主
  • 选举结束：
    • 若收到大多数节点的投票，则该candidate变成leader，并向其他节点发送一个空的AppendEntry请求
    • 若收到相同或更大term的AppendEntry请求，则承认对方为leader，自身变成follower
    • 若超时则重新选主

这里的term及对应paxos中的proposal number，一个term最多只有一个leader与之对应。其中follower节点对于选主的投票规则是对方的日志比自身新，确保最后选出的leader拥有最新最全的日志，从容简化之后的恢复流程，这部分会在第三个子问题中详细阐述。

日志复制

日志复制是为了保证节点的一致性，所有的日志都是先提交到leader节点，再由leader节点follower节点，正常情况下follower节点跟leader节点是一致的，但是在发生节点加入或者leader重新选举之后，follower节点可能落后较多，日志复制需要保证节点的一致性。

raft为了算法实现，要确保日志是连续的，即节点的日志序列不能存在空洞，它的日志复制示意图如下所示：

整体流程如下：

  • leader接收client的请求，先将日志写入本地，之后向所有follower发送AppendEntry请求
  • follower对收到的Entry验证，若该entry对应的前一个位置上，follower对应的日志和leader对应的日志term是相同的，则写入该Entry并返回成功
  • 若对应的term不相等或者是folloer的日志落后，则拒绝该请求，同时回复自身的日之前情况，leader接收到后会发送缺失部分的日志
  • leader在收到半数节点的成功应答后，则认为该日志已经被选定（commit），可以回复成功给客户端
  • 后续的AppendEntry和HeartBeat请求中都会带上leader的commit信息，follower便可以更新自身的commit信息

利用日志连续这个特性可以大大简化raft的整体恢复、选主、应用流程，通过以上日志复制机制可以确保如果两个节点相同位置上的日志项的term是相等的，那么该条日志就一定是相等的（因为一个term只会有一个leader），而该日志是相等的，则可以确认前面所有的日志都是相等的（在AppendEntry前会先比较前一条日志是否相等）。

部分疑问

提交日志回复

最初看论文时，我产生过这样的疑问，就是一个client在想leader节点提交日志之后，该leader节点挂掉了，那么client节点最后会收到什么回复呢？如果回复是超时的话，那么客户端是否需要重试后者怎样才能获取到提交结果呢？如果回复是失败的话，如果该leader节点之后又恢复了，那么此条日志也是有可能会commit的，这样显然也不不行的。
其实这个问题根分布式系统的原则有关，如果server端返回的timeout，那么结果就是不确定的，系统设计者对使用者的期望就是retry，同时系统设计者或者使用者需要确保这种retry操作是幂等的。其次，对于raft来说，如果一个日志在提交时失败了，那么只能给你返回timeout。这是因为，即使只有少数派node接受了这条日志，这条日志还是有可能被后续的选举出来的leader分发给其他的node，从而变成多数派，然后提交。当然也有可能不包含这条日志的node被选为leader，导致这条日志被truncate掉，从而从系统中消失掉。综合以上两种情况，只能给你返回timeout来代表undefined。
最后，raft返回给你成功就是达成了多数派；返回给你失败时就是拒绝你提交，但是这种失败一般不代表日志commit失败，而是因为当前node不是leader或者当前node只读等原因拒绝你；如果返给你timeout，那么结果就是undefined，需要你去查询leader或者干脆重试，而重试的话要求你的操作在你的应用中是幂等的

工程优化

  • 预选举：candidate每次在发起选举的时候都会提升自己的term，如果某些candidate因为日志原因肯定无法成为leader，但是它却不断参与选举导致系统的term增加，使真正能当选的candidate要花费一段时间将自身的term跟上之后才能选出leader，容易导致选举周期过长。所以在实际实现过程中，可以增加pre-vote阶段，先发去预投票而不增加自身的term，只有确认可以当选为leader后才会增加自身的term
  • 乱序提交：raft为了简单性，采用了高度串行化设计，在实际使用中可能会存在性能问题，因此PolarFS因为实现了ParallelRaft，即raft的乱序提交版本。简单来说，就是对于无冲突的log之间可以乱序提交，而由冲突的log之间则需要顺序提交，然后在选主阶段引入额外的流程来填补leader中的log空洞，具体可参考PolarFS

一致性达成

在讨论分布式系统的时候，很容易混淆共识算法和一致性这两个概念，或者混为一谈，认为paxos和raft是一种强一致性算法，这其实是错误的。raft和paxos只是一种共识算法，共识达成之后如何达到所要求的一致性（线性一致、最终一致等），仍需要其他的实现手段，具体可参考线性一致性和 Raft

安全性

所谓安全性就是在前两个问题的基础之上如何确保日志不会丢失，以下是它的具体方案：

  • 为了简化数据同步和恢复流程，raft中的日志总是从leader流向follower节点的，所以选出来的leader一定要确人是拥有最多以选定日志的节点，这样才不会造成日志的丢失。因此follower向candidate的投票原则是：candidate的最后一条日志的term比follower大，或者在term一样大的情况下，candidate的日志更长，这样就可以确保最终选择的leader包含了大多数节点的日志
  • 此外论文中还描述了一种情况是一条日志被commit之后又被否定了，其核心原因是根据多数派判断当前日志是否可以commit只适用于当前term，所以一个leader在当选之后会提交一个空的AppendEntry，通过日志的连续性来确保提交该日志的同时也提交之前任期的日志

与paxos的对比

这里说的paxos是指multi-paxos，raft比paxos更容易理解和实现，可以视为paxos的加强限制版，它也paxos的主要区别是：

  • raft强化了leader的地位，leader一定是拥有最全的日志，日志只会从leader流向follower
  • raft节点中日志是连续的，日志之间是不会存在空洞的

multi-paxos中可以不存在leader，这样的话就退化成了经典的basic paxos实现，raft正是通过这两个限制来简化paxos的工程实现。而paxos和raft都是一旦一个entry（raft叫日志，paxos叫提案）被多数派同意，该提案计算被选定了，被选定的提案就不会丢失也不会更改。事实上，paxos和raft都是用一个唯一性id来标识leader的合法性（proposal-number和term），id最大的leader才是有效的leader，对于paxos和raft来说，同一时刻是可能存在两个leader的，但只有一个是合法的，即同一个term期间只会有一个leader。

此外，raft中强调了leader拥有最新的日志，而multi-paxos没有强调这点，所以在paxos中一个节点当选为leader之后需要额外的流程从其它acceptor处来补全自身的日志，而raft的恢复流程则简单得多，日志只会从leader流向follower。此外需要注意的是，leader此时恢复的日志可能还不是已经选定的日志，所以paxos和raft中，leader节点在当选之后都需要重新走一遍流程来提交自身的日志。

raft还有一个很重要的点就是日志的连续性保证，所谓连续性就是说不同节点上相同位置的日志只要他们的term是相同的，这两条日志就一定是相同的，且它们之前的日志也都是相同的，这是通过前文所述的日志复制策略来保证的。这样leader只需对比下follower的日志id和term就知道该节点的日志情况，这样能极大简化日志恢复、选主过程。

从根本上来说，raft更加易懂、易实现，而paxos侧重于理论描述，两种协议之间不存在绝对的优劣。但是只要有leader角色的存在，选主就一定需要花费一点时间，而paxos中没有强调leader的存在，所以对于极端可用性要求的场景，可以选用paxos。存在此外有资料说raft要求日志是连续的这点会导致系统在网络环境较差的环境里性能较差，个人认为不是这样的，除非是这个环境里慢节点是会不断变化的，才会带来raft性能的明显下降。但是这里也跟具体的日志存储实现有关，当有大量并发写请求执行时，要求所有的日志写入是按顺序写入，那么处于尾部的请求，必须等待之前所有的请求都被处理后才能被提交和返回，这个对性能也是会有影响的。此外，在并发较大的场景下，日志请求的到达可能是乱序的，这对于写入也会造成一定影响。

Reference