共识算法在规模上的应用：第二部分 —— 共识规则
共识规则
YouTube的规模
当我们在“YouTube”运行Vitess时，系统中有数万个节点处理着非常高的QPS（每秒查询数）。规模横向扩展涉及多个维度：其中一些分片（shards）甚至有超过50个副本。这些节点分布在多个数据中心之间，使得拓扑结构相当复杂。要实现这一点，我们需要在延迟、可用性和持久性之间找到一个平衡点。为了满足这些要求，我们会定期执行几乎完全自动化的故障切换。我很高兴地告诉您，我们从未因为硬件故障而丢失数据。
第一次听到Paxos时，它听起来像是一种魔法：一种算法可以动态地选择一个领导者，确保所有请求都能在没有错误、分歧或数据丢失的情况下完成。Vitess 的故障切换通常需要几秒钟，而我们希望避免在此期间发生服务错误。
我们开始评估是否可以将Paxos集成到Vitess中。但很快我们发现，我们的仲裁组大小对于基于多数原则的算法来说过于庞大。此外，MySQL的复制机制与Paxos描述的持久性机制完全不同。唯一的选择就是对这两个系统进行差异分析。从某种意义上说，这促成了FlexPaxos的发现：一个额外的调节器，允许您在性能与安全性之间实现更有意义的权衡。
还有其他不同之处：我们用于故障切换的算法完全不像Paxos推荐的算法。研究两者之间的差别导致我们发现一组通用原则，任何基于领导者的系统都可以遵循这些原则来保证正确性和安全性。我们将在这篇文章中探讨这些规则。
为什么需要共识?
我们专注于通过共识解决规模上的持久性问题。可能还有其他用途，但我们不关注那些内容。
没有系统可以提供绝对的持久性保证；总有可能发生比预期更严重的灾难性失败。您必须决定需要容忍的失败程度，这取决于资源的可靠性和数据的重要性。换言之，持久性需求是用例相关的。
为了适应所有可能的用例，我们将持久性视为一个抽象需求。算法必须与这些需求无关，并能够适应任意复杂的规则。这改变了我们解决问题的方法，我们将在以下章节中进行这种分析。
单值行为
引用Paxos的定义：我们对共识系统的主要要求是它不能忘记已经确认接受的值。一旦一个值被接受，所有其他值必须被拒绝。
当要求系统接受单一值时，操作可能有以下三种结果：
- Accepted（接受）：该值成功被接受。
- Rejected（拒绝）：该值被拒绝。
- Failed（失败）：操作未成功，但可能在以后完成。
如果第一个请求被接受了，那么任何后续写入不同值的尝试会被拒绝。
如果第一个请求被拒绝了，这可能意味着早前有一个值已被接受。在这种情况下，后续请求也将被拒绝。
如果第一个请求失败了，然后发起第二次请求，系统可以选择将任何一个请求最终定为“Accepted”，但不能同时接受两个值。由于第二次请求也可能失败，我们需要更加泛化地重新定义：系统可以选择接受之前任何一次请求的值作为最终结果。而路径上的灾难性失败可能让系统无限期地停留在失败状态，不过通常预计系统能够逐渐收敛到正确状态。
实际应用中的行为
一个系统仅接受单一值并不实际。相反，来看如果定义一个系统接受一系列值会发生什么，这是存储系统通常的行为。
如果系统首先接受了值v1，然后收到一条值v2的请求，它必须记录v2发生在v1之后。 更重要的一点是：如果请求v1失败，未能满足持久性要求，那么对于请求v2，系统需要做出最终决定是完成还是拒绝v1。如果完成，它将记录v2在v1之后；否则，v1将被丢弃，而v2将成为唯一被接受的值。
Raft很好地理解了这一点，这也是为什么他们把自己的系统描述为一种实现一致性日志复制（log replication）的方式。
在我们的案例里，我们将以请求而非值进行思考。请求可以是存储系统需要执行的任何操作，比如事务、设定键值对，或其他原子操作。
让我们重新定义：共识系统的目的是严格按照顺序接受一系列请求，并在多个节点之间保持一致性。
单领导者
为了限制系统复杂性和研究范围，我们专注于单领导者设计。目前主流实现中我所了解的都是单领导者模式。尽管也有研究针对无领导者和多领导者的算法，但我对这些研究并不熟悉。
一个单领导者的共识系统是两个工作流的协作组合：
- 领导者接受请求并使其持久化。
- 可以选举新的领导者以在没有数据分歧或丢失的情况下继续处理请求。
Paxos和Raft也使用单领导者方法。
共识规则
现在我们已经花了足够的时间构建前提，接下来是系统化地将共识系统的规则进行总结：
- 领导者的职责是通过满足既定的持久性要求来完成请求。
- 选举新领导者的操作必须包括：
- 终止之前的领导状态（如果存在）。
- 招募新领导所需的节点。
- 传播之前已经完成的请求以满足新领导的持久性要求。
- 前进性： 如果领导者选举失败，后续的重试必须有成功的路径，即必须能够选出新领导者而不会破坏持久性和安全性保证。
- 竞争： 如果存在并行的领导者选举尝试，最多只允许一个领导者成功。
实际上，这些规则中第3和第4点已经隐含在第2条中。但这些属性非常重要，因此值得单独明确指出。
这些规则是故意设计为通用的，以允许实现目标的创造性方法。事实上，如果规则太具体，会排除一些有效的实现方式。然而，我们会展示多种方法来满足这些规则，并验证现有的流行算法是否符合这一新规则集。
您会注意到以下不同之处：
- 没有提到多数仲裁组（majority quorum）。
- 没有提到节点的交集条件。
- 没有提到提议编号（proposal numbers）。
这是我们与传统系统的不同之处，因为我们认为这些并非严格意义上必须的。例如，您可以构建一个由50个节点组成的共识系统，但依然仅使用两节点的仲裁组。这些仲裁组之间没有必要在领导者之间交叠。至于提议编号，很少有人理解它们为何需要。因此更好的方法是先讨论我们试图实现的目标，然后将提议编号作为一种选择，同时考虑其他不使用提议编号的替代方案。我们会深入每一个特性，探索不同实现方式之间的权衡。
在下一篇文章中，我们将探讨这一泛化规则集可以解决的一些实际用例。同时，我们还会深入挖掘规则的含义及其重要性。
关注公众号：程序新视界，一个让你软实力、硬技术同步提升的平台
除非注明，否则均为程序新视界原创文章，转载必须以链接形式标明本文链接
