共识协议分析：从逻辑时钟到筏

在今年的春节期间，我阅读了一些关于共识协议的论文。在阅读这些论文之前，我一直想知道ZooKeeper的ZAB协议和Raft协议之间的实际差异是什么，它们都具有领导者和两阶段提交，以及Paxos协议如何应用于实际工程中。这些论文为我提供了这些问题的答案。现在，我将尝试用我自己的语言解释这些协议，以帮助您理解这些算法。同时，我也在本文中提到了一些问题，希望我们能够一起讨论。我对这些协议的了解可能有限，所以请在我错的地方纠正我。

逻辑时钟实际上不是共识协议。这是Lamport在1987年提出的一个想法，用于解决分布式系统中不同机器之间时钟不一致所引起的可能问题。在独立系统中，机器时间用于识别事件，以便我们可以清楚地识别两个不同事件的发生顺序。但是，在分布式系统中，由于时间偏差可能因机器而异，因此无法通过物理时钟来决定事件顺序。实际上，在分布式系统中，我们只关注两个相关事件的顺序。考虑两个事务：一个是对行A的修改，另一个是对行B的修改。实际上，我们并不关心这两个事务中的哪一个首先发生。所谓的逻辑时钟是用于定义两个相关事件的发生顺序的东西，即“之前发生的”。逻辑时钟无法确定未关联事件的发生顺序。因此，这种“发生在之前”的关系实际上是一种偏序关系。

本文中的图表和示例来自此博客。

在该图中，箭头表示进程间通信;A，B和C表示分布式系统中的三个进程。

逻辑时钟的算法非常简单：每个事件对应一个Lamport时间戳（初始值为0）。

如果节点内发生事件，则时间戳值将加1。

如果事件是发送事件，则时间戳添加1，并将时间戳添加到该消息。

如果事件是接收事件，则时间戳为Max（消息中的本地时间戳）加1。

对于所有相关的发送和接收事件，这可以确保发送事件的时间戳小于接收事件的时间戳。如果两个事件（例如，A3和B5）未关联，则它们具有相同的逻辑时间。我们可以根据需要定义两个事件的发生顺序，因为这两个事件没有关联。例如，如果过程A在过程B之前发生，而过程C在Lamport时间戳相同时发生，我们可以得出“A3在B5之前发生”的结论。然而，在物理世界中，B5发生在A3之前。但这并不重要。

目前逻辑时钟似乎并未得到广泛应用。DynamoDB使用向量时钟来解决多个版本的时间顺序。请通知我我不知道的任何其他特定应用程序。Google的扳手还使用物理时钟来解决时钟问题。但是，我们可以从Lamport的逻辑时钟算法中看到共识协议的原型。

谈到共识协议，我们通常会讨论状态机复制。通常，状态机复制和共识协议算法一起用于在分布式系统中实现高可用性和容错。许多分布式系统使用状态机复制来在副本之间同步数据，例如HDFS，Chubby和Zookeeper。

状态机复制在分布式系统中的每个实例副本中维护持久性日志，并使用某种一致的协议算法来确保日志在每个实例中完全一致。通过这种方式，实例中的状态机按日志顺序回放日志中的每个命令，以便在客户端读取数据时从每个副本中读取相同的数据。状态机复制的核心是图中所示的共识模块，它包含在我们今天要讨论的共识协议算法中。

Paxos是Lamport在20世纪90年代开发的共识协议算法。人们普遍发现这很难理解。因此，Lamport于2001年发表了一篇新文章“Paxos Made Simple”，他说Paxos是世界上最简单的共识算法，很容易理解。但是，在这个行业中，人们普遍认为它仍然很难理解。在阅读了Lamport的论文之后，我认为Paxos协议本身并不难理解除了正确性论证的复杂过程之外。但是，Paxos协议过于理论化，远未应用于特定的工程实践。当我第一次了解Paxos协议时，我也很困惑。我多次阅读这些文章，发现该协议仅适用于单一事件共识，并且不能修改商定的价值。我们如何使用Paxos实现状态机复制？此外，只有Propose和Follower根据Paxos协议知道约定的值。我们怎样才能真正使用这个协议？但是，如果您仅从理论上考虑此协议并且不考虑实际工程中可能出现的问题，则Paxos协议更容易理解。在Lamport的论文中，状态机的应用只是一个普遍的想法，并没有包含具体的实现逻辑。直接使用Paxos进行状态机复制是不可能的。相反，我们需要向Paxos添加许多东西。这就是Paxos有这么多变种的原因。如果您只从理论上考虑该协议并且不考虑实际工程中可能出现的问题，那么Paxos协议更容易理解。在Lamport的论文中，状态机的应用只是一个普遍的想法，并没有包含具体的实现逻辑。直接使用Paxos进行状态机复制是不可能的。相反，我们需要向Paxos添加许多东西。这就是Paxos有这么多变种的原因。如果您只从理论上考虑该协议并且不考虑实际工程中可能出现的问题，那么Paxos协议更容易理解。在Lamport的论文中，状态机的应用只是一个普遍的想法，并没有包含具体的实现逻辑。直接使用Paxos进行状态机复制是不可能的。相反，我们需要向Paxos添加许多东西。这就是Paxos有这么多变种的原因。

Basic Paxos是Lamport首先提出的Paxos算法。事实上，它很简单，只需几句话即可解释。接下来，我将用自己的语言描述Paxos并举例说明。要了解Paxos，只需记住一件事：Paxos只能为一个值启用一致，并且一旦确定，提案就无法更改。也就是说，整个Paxos集团只接受一个提案（或几个具有不同价值的提案）。有关如何接受多个值以实现状态机复制的信息，请参阅下一节中的“多个Paxos”。

Paxos协议没有Leader概念。除了Learner（仅学习Propose的结果;此处不再讨论），Paxos中只提供Proposer和Acceptor。Paxos允许多个提议者同时提出一个号码。提议者提出一个值并试图说服所有接受者就价值达成一致。在准备阶段，Proposer向每个Acceptor发送ProposeID n（请注意，Proposer在此阶段不会将值传递给Acceptor）。如果Acceptor发现它从未从任何提议者那里收到大于n的值，它将回复提议者并承诺不接收ProposeID小于或等于n的提案的准备消息。如果Acceptor已承诺建议的数字大于n，则不会回复提议者。如果接受者已接受小于n的提议（在阶段2中），则它将该建议值返回给提议者。否则，返回null值。当提议者收到超过一半的受理人的回复时，就可以开始接受阶段了。但是，在此阶段，提议者可以提出的值是有限的。当且仅当收到的回复不包括先前提案的值时，提议者才能提出新值。否则，Proposer只能将回复中最大的提案值用作提案值。Proposer使用此值和ProposeID n来启动针对每个Acceptor的Accept请求。也就是说，即使提议者已经收到了Acceptor的承诺，Accept可能会失败，因为在启动Accept之前，Acceptor可能已向具有更高proposalID的Proposer发出承诺。换句话说，即使第一阶段成功，第二阶段仍可能由于存在多个提议者而失败。

我将提供一个来自此博客的示例。

考虑三个服务器：Server1，Server2和Server3。他们都希望使用Paxos协议让所有成员都同意他们是领导者。这些服务器是Proposer角色，它们提出的值是它们的名称。他们需要三个成员的同意：接受者1-3。Server2发起提议1（1为ProposeID），Server1发起提议2，Server3发起提议3。

首先，它是准备阶段：

假设从Server1发送的消息首先到达Acceptor 1和Acceptor 2，两者都没有收到请求。因此，他们收到此请求并将[2，null]返回给Server1。同时，他们承诺不会收到ID小于2的请求;

然后，从Server2发送的消息到达Acceptor 2和Acceptor3，并且Acceptor 3没有收到请求。因此，Acceptor 3将[1，null]返回给Proposer 2并承诺不接收ID小于1的消息。因为Acceptor 2已经收到来自Server1的请求并且承诺不接收ID小于2的请求，所以Acceptor 2将拒绝来自Server2的请求。

最后，来自Server3的消息到达了Acceptor 2和Acceptor 3，两者都已收到提案。但是，因为此消息的ID大于2（接收器2已接收的消息的ID）和1（接收器3已接收的消息的ID），所以接收器2和接收器3都是收到此提议并将[3，null]返回给Server3。

此时，由于Server2没有收到超过一半的回复，因此它获取一条新消息，其中包含4作为其ID，并将此消息发送给Acceptor 2和Acceptor 3.由于4大于3（提议的最大ID）接收者2和接受者3已收到），收到此提议并将[4，null]返回给Server2。

接下来是接受阶段：

由于Server3已收到超过一半的回复（2个回复）且返回的值为null，因此Server3提交了提议[3，server3]。

由于Server1在准备阶段也收到了超过一半的回复，并且返回的值为null，因此Server1提交了提议[2，server1]。

由于Server2也收到了超过一半的回复且返回值为null，因此Server2提交了提议[4，server2]。

当Acceptor 1和Acceptor 2从Server1接收提议[2，server1]时，Acceptor 1接受此请求，并且Acceptor 2拒绝此请求，因为它已承诺不接受ID小于4的提议。

当接收到该提议时，接受者2和接受者3接受来自Server2的提议[4，server2]。

Acceptor 2和Acceptor 3将拒绝来自Server3的提议[3，server3]，因为他们承诺不接受ID小于4的提议。

此时，超过一半的接受者（接受者2和接受者3）已经接受了提议[4，server2]。学习者认为该提案已通过并开始学习该提案。因此Server2成为最终的领导者。

如前所述，Paxos处于理论阶段，不能直接用于状态机复制。原因如下：

Paxos只能确定一个值，不能用于连续日志复制。

多个提议者的存在可能导致活锁。在前面的示例中，Server2在最终接受提案之前提交了两次提案。在某些极端情况下，可能需要提交更多提案。

部分接受者只知道提案的最终结果。这不能保证状态机复制的每个实例都具有完全一致的日志。

事实上，Multi-Paxos实际上用于解决上述三个问题，因此Paxos协议可用于状态机。解决第一个问题非常简单。日志条目的每个索引值都使用独立的Paxos实例。解决第二个问题也很容易：在Paxos组中只包含一个Proposer，在阅读时使用Paxos协议选择Leader（如上例所示）并让此Leader执行读取以避免活锁问题。此外，单个领导者允许我们省略准备阶段的大部分工作。选择Leader后，只需启动Prepare一次。如果接受者都没有收到其他领导者的准备请求，则每次写入请求时都直接接受请求，除非Acceptor拒绝请求（拒绝表明新领导者正在执行写作）。为解决第三个问题，Multi-Paxos为每个服务器添加firstUnchosenIndex，让Leader将选定的值同步到每个Acceptor。解决了这些问题后，Paxos可用于实际工程。

到目前为止，Paxos有许多新增和变种。事实上，我将在后面讨论的ZAB和Raft可以被视为Paxos的修改和变体。一句广泛的评论说“世界上只存在一种共识算法，即Paxos。”

ZAB（ZooKeeper Atomic BoardCast）是ZooKeeper中使用的共识协议。ZAB是Zookeeper的专用协议。它与Zookeeper强烈绑定，并未被提取到独立的数据库中。因此，ZAB没有被广泛使用，仅限于Zookeeper。但是，关于ZAB协议的论文彻底证明了ZAB能够满足强一致性要求。

ZAB与Zookeeper一起于2007年出生。当时还没有开发出Raft协议。根据ZAB上的文章，Zookeeper没有直接使用Paxos，而是开发了自己的协议，因为Paxos被认为无法满足Zookeeper的要求。例如，允许多个提议者的Paxos可能导致从客户端提交的多个命令无法通过FIFO序列执行。此外，在恢复过程中，某些粉丝的数据可能不完整。这些参数基于最初的Paxos协议。事实上，这些问题已在Paxos的某些变体中得到解决。由于历史原因，原始Paxos协议未能解决上述问题。因此，Zookeeper开发人员决定开发一种新的共识协议-ZAB。

ZAB与随后的Raft协议非常相似。ZAB处理选择领导者和恢复。还通过使用两阶段提交来执行写入。首先，从领导者那里开始一轮投票。在接受超过一半的选票后，启动提交。ZAB中每个领导者的纪元数实际上等同于我将在稍后讨论的Raft中的术语。但是，在ZAB中，纪元号和转换号构成一个zxid，它存储在每个条目中。

ZAB通过使用两阶段提交启用日志复制。第一阶段是投票。当获得超过一半的同意票时，该阶段成功完成。在此阶段，数据并未真正转移给关注者。这是为了确保超过一半的计算机正常工作或在同一网络分区内。第二个是提交阶段。在此阶段，数据将传输到每个关注者，然后每个关注者（以及领导者）将数据附加到日志中。此时，写操作完成。如果第一阶段的投票成功完成但是追随者在第二阶段失败并不重要。重新启动领导者可以确保粉丝的数据与领导者的数据一致。如果领导者在提交阶段失败并且此写操作已经在至少一个关注者上提交，则该关注者肯定会被选为领导者，因为其zxid是最大的。在被选为领导者之后，此关注者允许所有关注者提交此消息。如果领导者失败时没有关注者提交此消息，则此写操作未完成。

由于日志只需要在提交时附加，因此ZAB日志仅需要仅附加功能。

此外，ZAB支持来自副本的陈旧读取。要实现强一致性读取，我们可以使用同步读取。以下是它的工作原理：首先，启动虚拟写操作（没有写入任何内容）。完成此操作后，此同步操作也将在本地提交。然后在本地副本上执行读取，以确保正确读取此同步时间点之前的所有数据。但是，Raft协议下的读写操作是通过主节点执行的。

Raft是2014年由斯坦福大学开发人员开发的一种新的共识协议。开发人员开发了这种新的共识协议，因为他们认为Paxos难以理解。此外，Paxos只是一种理论，远未应用于实际工程中。Paxos的开发人员列出了Paxos的一些缺点：

Paxos协议不需要领导者。每个提议者都可以创建提案。领导者选择和共识协议在设计Raft的最初阶段是分开的，而领导者选择和提案在Paxos中混合在一起，使得Paxos难以理解。

最初的Paxos协议只是就单个事件达成共识。确定值后，无法修改。但是，在实际场景（包括数据库一致性）中，需要不断就日志条目的值达成共识。因此，Paxos协议本身不能满足要求：我们需要对Paxos协议进行一些改进和补充，以便在实际意义上将Paxos应用于工程中。制作Paxos协议的补充非常复杂。尽管Paxos协议已经被Lamport证实，但基于Paxos和改进的算法（如Multi-Paxos）尚未得到证实。

另一个缺点是Paxos只提供了粗略的描述。这要求对Paxos的后续改进以及使用像Google Chubby等Paxos的项目必须实施一组项目来解决Paxos中的特定问题。像Chubby这样的项目的实施细节没有公开。也就是说，要在您自己的项目中应用Paxos，您必须自定义并实现一组符合您特定要求的Paxos协议。

因此，Raft的开发人员在设计Raft时有一个明确的目标：使这个协议更容易理解，并选择最易理解的设计解决方案，如果有几个Raft设计解决方案可用。开发人员提供了一个例子。在Raft协议的领导者选择阶段，一种可能的解决方案是向每个服务器附加一个ID，让所有服务器选择ID最大的服务器作为领导者，以快速达成共识（类似于ZAB协议）。但是，此解决方案还有一个额外的概念 - ServerID。同时，具有较小ID的服务器必须等待一段时间才能选择具有较高ID的服务器作为新的领导者，这可能会影响可用性。Raft使用非常简单的领导选择解决方案：每个服务器休眠一段时间，首先唤醒的服务器提出建议;如果此服务器收到大多数投票，则选择它作为领导者。在一般网络环境中，首先进行投票的服务器也将首先从其他投票中获得投票。因此，只需要一轮投票就可以选出领导者。整个领导者选拔过程非常简单。

除了领导者选择之外，Raft协议的整体设计也很简单。如果不考虑快照和成员数量的变化，则领导者和追随者之间的交互总共需要两次RPC调用。两个调用之一是RequestVote，只有领导者选择才需要。也就是说，所有数据交互都由AppendEntries RPC执行。

要了解Raft协议算法，我们首先需要查看Term概念。每个领导者都有自己的术语，该术语将应用于日志的每个条目，以表示该条目写入的术语。此外，术语等同于租约。如果领导者在指定的时间段内没有发送心跳（发送心跳也是由AppendEntries RPC调用完成的），则跟随者会认为领导者已经失败并将其收到的最大术语加1一个新名词，开始新的选举。如果候选人的条款不高于该关注者的期限，则关注者将否决这些候选人，以确保所选的新领导者具有最高期限。如果没有粉丝在超时前收到足够的票数（这种情况可能），跟随者将在当前术语中添加1并开始新的投票请求，直到选择新的领导者。Raft最初是用C实现的。可以设置一个非常短的超时（通常以毫秒为单位）。因此，在Raft中，可以在几十毫秒内检测到失败的领导者，并且故障恢复时间可以非常短。对于使用Raft（如Ratis）在Java中实现的数据库，我估计在考虑GC时间时不可能设置这么短的超时。

领导者的写操作也是两阶段提交过程。首先，领导者将编写在其自己的日志中找到的第一个空缺索引，并通过AppendEntries RPC将该条目的值发送给每个追随者。如果领导者从超过一半的粉丝（包括他们自己）收到“真实”，则在下一个AppendEntries中，领导者将1添加到committedIndex，表明已经提交了书面条目。如下图所示，领导者将x = 4写入索引= 8的条目，并将其发送给所有关注者。从第一台服务器（领导者本身），第三台服务器和第五台服务器（图中未显示索引= 8的条目）收到投票后，该服务器肯定会同意投票，因为此服务器之前的所有条目与领导者一致），领导者获得多数票。在下一个RPC中，Committed索引将增加1，表示已提交索引≤8的所有条目。第二台服务器和第四台服务器的日志内容明显滞后。一个原因是在先前的RPC调用失败之后，领导者将重试，直到关注者的日志更新为领导者的日志。另一个原因是两台服务器已重新启动并且当前处于恢复状态。当两个服务器收到写入索引= 8的条目的RPC时，跟随者还会将最后一个条目的术语和索引发送到这些服务器。也就是说，prevLogIndex = 7和prevLogTerm = 3的消息将被发送到第二个服务器。对于第二个服务器，index = 7的条目为空（即，日志与领导者不一致）。它将向领导者返回“false”，并且领导者将无限期地向后遍历，直到找到与第二个服务器的日志内容一致的条目。从那时起，领导者的日志内容被重新发送给关注者以完成恢复。Raft协议确保所有成员的复制日志中的每个索引在其条款一致时具有一致的内容。如果内容不一致，领导者将修改该索引的内容以使其与领导者保持一致。将领导者的日志内容重新发送给关注者以完成恢复。Raft协议确保所有成员的复制日志中的每个索引在其条款一致时具有一致的内容。如果内容不一致，领导者将修改该索引的内容以使其与领导者保持一致。将领导者的日志内容重新发送给关注者以完成恢复。Raft协议确保所有成员的复制日志中的每个索引在其条款一致时具有一致的内容。如果内容不一致，领导者将修改该索引的内容以使其与领导者保持一致。

实际上，我之前的描述几乎完全解释了Raft中的领导者选择，写作和恢复。我们可以找到一些有关Raft的有趣方面。

第一个有趣的方面是可以修改Raft中的日志条目。例如，跟随者从领导者处接收准备请求并将该值写入索引。如果该领导者失败，新选出的领导者可以重用该索引，并且可以修改该跟随者的索引内容。这会导致两个问题：Raft中的Logs无法在仅附加文件或文件系统中实现。对于ZAB和Paxos协议，仅附加日志。这仅需要文件系统具有附加功能，并且不需要随机访问和修改功能。

第二个有趣的方面是在Raft中只维护一个Committed索引以确保简单性。也就是说，任何小于或等于此committedIndex的条目都将被视为已提交。这导致领导者在获得大多数选票之前（或者在领导者可以通知任何关注者他们已经编写了自己的日志之前）在写作过程中失败。如果在重新启动后再次选择此服务器作为领导者，则仍将提交此值并使其永久有效。由于此值包含在领导者的日志中，因此领导者肯定会确保所有关注者的日志与其自己的日志一致。默认情况下，在执行后续写入并增加committedIndex之后将提交此值。

例如，考虑五台服务器。S1是领导者。当S1写入索引为1的条目时，它首先将数据写入其自己的日志中，并在它可以通知其他服务器附加条目之前经历停机时间。

重新启动后，S1可能仍有机会被选为领导者。当再次选择S1作为领导者时，它仍然会将index = 1的条目复制到每个服务器（但是，提交的索引不会向前移动）。

此时，S1执行另一个写操作。写入完成后，Committed索引将移动到位置2.因此，index = 1的条目也被视为已提交。

这种行为有点奇怪，因为它等同地意味着Raft允许在未经多数人同意的情况下提交值。这种行为取决于领导者。在前面的示例中，如果在重新启动后未选择S1作为领导者，则索引= 1的条目的内容将被新领导者的内容覆盖，并且不会提交未经历投票阶段的内容。

虽然这种行为有点奇怪，但它不会引起任何问题，因为领导者和追随者会达成共识。另外，在写入过程期间领导者的失败是对客户端的待定语义。关于Raft的论文还说，如果需要“恰好一次”的语义，用户需要在写入过程中添加类似UUID的东西，以允许领导者在写入操作之前检查UUID是否已被写入。这可以在一定程度上确保“恰好一次”的语义。

关于Raft的论文还将Raft与ZAB算法进行了比较。ZAB协议的一个缺点是在恢复阶段期间领导者和追随者之间需要数据交换。我真的不明白这一点。在我看来，为了重新选择ZAB中的领导者，将选择具有最大Zxid的服务器作为领导者，并且其他粉丝将从领导者处完成数据 - 领导者不是从关注者完成其数据的情况。

目前，改进的Paxos协议已经在许多分布式产品中使用，例如Chubby，PaxosStore，Alibaba Cloud X-DB和Ant Financial OceanBase。通常认为Raft协议的性能低于Paxos，因为它只允许按顺序提交条目。然而，使用Raft的TiKV正式声明它已对Raft进行了许多优化，并显着改善了Raft的性能。POLARDB是另一个阿里巴巴云数据库，它也使用Parallel-Raft（Raft的改进版本）来实现Raft中的并行提交功能。我相信将来会有更多基于Paxos / Raft的产品，并且将对Raft / Paxos进行更多改进。