算法模型

从系统模型的角度，我们又可以将分布式共识算法（Distributed Consensus Algorithms）看做解决如何在多个节点之间复制deterministic state machine的问题，即构建多副本状态机模型（Replicated State Machine），实现高可用和强一致；这里所谓的状态机即代表了任意的服务，譬如数据库、文件服务器、锁服务器等。

每个节点都会包含一个状态机实例与日志，但是我们希望呈现给客户端使用者的仿佛只有单个可信赖的、能容错的状态机；提供的服务的可用性与准确性不会受到集群中节点的失败而影响。每个状态机都能够从其自身的日志中读取指令，譬如以Hash Table为状态机实例的话，那么存放在日志中的指令就会是 set x to 3 这样子的。共识算法也就是为了保证这些节点上的日志内容的一致性，共识算法必须保证如果某个节点上的第N条指令是 set x to 3，那么其他所有节点上不会出现该序列位不一样的情况。最终，所有的状态机都会以相同顺序执行指令，并得到一致的状态序列。

上述介绍可以形式化如下：一个或多个节点可以提议（propose）某些值，而共识算法决定（decides）采用其中的某个值。在这种形式下，共识算法必须满足以下性质：

• 一致同意（Uniform agreement）：没有两个节点的决定不同。
• 完整性（Integrity）：没有节点决定两次，一致同意和完整性属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。
• 有效性（Validity）：如果一个节点决定了值v，则v由某个节点所提议。有效性属性主要是为了排除平凡的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为null的算法；该算法满足一致同意和完整性属性，但不满足有效性属性。
• 终止（Termination）：由所有未崩溃的节点来最终决定值。如果你不关心容错，那么满足前三个属性很容易：你可以将一个节点硬编码为“独裁者”，并让该节点做出所有的决定。但如果该节点失效，那么系统就无法再做出任何决定。事实上，这就是我们在两阶段提交的情况中所看到的：如果协调者失效，那么存疑的参与者就无法决定提交还是中止。终止属性正式形成了容错的思想。它实质上说的是，一个共识算法不能简单地永远闲坐着等死；换句话说，它必须取得进展。即使部分节点出现故障，其他节点也必须达成一项决定。

共识的系统模型假设，当一个节点“崩溃”时，它会突然消失而且永远不会回来。在这个系统模型中，任何需要等待节点恢复的算法都不能满足终止属性。特别是，2PC不符合终止属性的要求。当然如果所有的节点都崩溃了，没有一个在运行，那么所有算法都不可能决定任何事情。算法可以容忍的失效数量是有限的：事实上可以证明，任何共识算法都需要至少占总体多数（majority）的节点正确工作，以确保终止属性。多数可以安全地组成法定人数。

因此终止属性取决于一个假设，不超过一半的节点崩溃或不可达。然而即使多数节点出现故障或存在严重的网络问题，绝大多数共识的实现都能始终确保安全属性得到满足一致同意，完整性和有效性。因此，大规模的中断可能会阻止系统处理请求，但是它不能通过使系统做出无效的决定来破坏共识系统。大多数共识算法假设不存在拜占庭式错误，正如在“拜占庭式错误”一节中所讨论的那样。也就是说，如果一个节点没有正确地遵循协议（例如，如果它向不同节点发送矛盾的消息），它就可能会破坏协议的安全属性。克服拜占庭故障，稳健地达成共识是可能的，只要少于三分之一的节点存在拜占庭故障。但我们没有地方在本书中详细讨论这些算法了。

共识算法和全序广播

最著名的容错共识算法是视图戳复制（VSR, viewstamped replication），Paxos，Raft以及Zab，这些算法之间有不少相似之处，但它们并不相同。大多数这些算法实际上并不直接使用这里描述的形式化模型（提议与决定单个值，一致同意，完整性，有效性和终止属性）。取而代之的是，它们决定了值的顺序（sequence），这使它们成为全序广播算法。

请记住，全序广播要求将消息按照相同的顺序，恰好传递一次，准确传送到所有节点。如果仔细思考，这相当于进行了几轮共识：在每一轮中，节点提议下一条要发送的消息，然后决定在全序中下一条要发送的消息。所以，全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：

• 由于一致同意属性，所有节点决定以相同的顺序传递相同的消息。
• 由于完整性属性，消息仅发送一次而不会重复。
• 由于有效性属性，消息不会被损坏，也不能凭空编造。
• 由于终止属性，消息不会丢失。

视图戳复制，Raft和Zab直接实现了全序广播，因为这样做比重复**一次一值（one value a time）**的共识更高效。在Paxos的情况下，这种优化被称为Multi-Paxos。

单领导者复制和共识

在单领导复制中，它将所有的写入操作都交给主库，并以相同的顺序将它们应用到从库，从而使副本保持在最新状态。这实际上不就是一个全序广播吗，为何我们并没有导致共识问题呢？答案取决于如何选择领导者。如果主库是由运维人员手动选择和配置的，那么你实际上拥有一种独裁类型的“共识算法”：只有一个节点被允许接受写入（即决定写入复制日志的顺序），如果该节点发生故障，则系统将无法写入，直到运维手动配置其他节点作为主库。这样的系统在实践中可以表现良好，但它无法满足共识的终止属性，因为它需要人为干预才能取得进展。

时代编号和法定人数

一些数据库会自动执行领导者选举和故障切换，如果旧主库失效，会提拔一个从库为新主库，这使我们向容错的全序广播更进一步，从而达成共识。但是还有一个问题。我们之前曾经讨论过脑裂的问题，并且说过所有的节点都需要同意是谁领导，否则两个不同的节点都会认为自己是领导者，从而导致数据库进入不一致的状态。因此，选出一位领导者需要共识。但如果这里描述的共识算法实际上是全序广播算法，并且全序广播就像单主复制，而单主复制需要一个领导者，那么这样看来，要选出一个领导者，我们首先需要一个领导者。要解决共识问题，我们首先需要解决共识问题。我们如何跳出这个先有鸡还是先有蛋的问题？

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个时代中，领导者都是唯一的。

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的时代编号，因此时代编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高时代编号的领导说了算。在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高时代编号的领导者，它们可能会做出相互冲突的决定。领导者如何知道自己没有被另一个节点赶下台？一个节点不一定能相信自己的判断，因为只有节点自己认为自己是领导者，并不一定意味着其他节点接受它作为它们的领导者。

相反，它必须从**法定人数（quorum）**的节点中获取选票，对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。法定人数通常（但不总是）由多数节点组成。只有在没有意识到任何带有更高时代编号的领导者的情况下，一个节点才会投票赞成提议。因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键的洞察在于，这两次投票的法定人群必须相互重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举。因此，如果在一个提案的表决过程中没有出现更高的时代编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

这一投票过程表面上看起来很像两阶段提交。最大的区别在于，2PC中协调者不是由选举产生的，而且2PC则要求所有参与者都投赞成票，而容错共识算法只需要多数节点的投票。而且，共识算法还定义了一个恢复过程，节点可以在选举出新的领导者之后进入一个一致的状态，确保始终能满足安全属性。这些区别正是共识算法正确性和容错性的关键。