在大规模系统中实现共识算法：第5部分 – 处理竞争条件
在这篇文章中，我们将探讨在存在竞争条件的情况下如何实现领导权的撤销与建立。同时，我们也会讨论前进进展的要求。
第1至4部分回顾
- 持久性是我们使用共识系统的主要原因。
- 由于持久性需求取决于具体的使用场景，我们将其设为抽象需求，即共识算法不假设任何特定的持久性要求。
- 我们从Paxos定义的共识系统初始特性开始，并进行了修改，使其能够在实际场景中使用。与其收敛到一个值，不如让系统接受一系列请求。
- 我们将范围缩小到单领导者系统。
- 我们提出了一组与持久性无关的新规则。关键在于：一个遵循这些规则的系统能够满足共识系统的要求。尤其是，我们排除了一些传统上用作核心构件的要求，比如多数派的法定人数（majority quorum）。
- 我们研究了一些实际场景，其中法定多数划分的方法难以很好地工作。一个灵活的共识系统可以更舒适地适应这些使用场景。
- 我们将领导权变更过程概念化为两个独立问题：撤销（Revoke）和建立（Establish）。这种分离为其实现提供了更多选择，是传统算法之前未曾提供的。
处理竞争条件的两种方法
如果领导权变更只有一个代理执行，就无需担心竞争条件。但这是不现实的，因为网络分区可能会隔离这个代理，导致其无法执行必要的操作。
如果系统中有多个代理可以进行领导权变更，则需要处理竞争条件。这有两种主要解决方法：第一个代理获胜或最后一个代理获胜。决定谁是第一个或最后一个根据具体方法而异。我们将在分析每种方法时进一步阐明。
一种使第一个代理获胜的方法实际上是防止后续代理成功。这可以等价于获取一个锁（lock）。因此，我们将这一方法称为基于锁（lock-based）。而另一种方法便称为无锁（lock-free）。
我们将分别分析这些方法。正如我们将在下文中看到的，这种差异是非常根本性的，令人惊讶的是此前并没有被明确指出在共识算法中。
选举者（Elector）
在详细分析之前，我们需要引入一个新的术语。
在YouTube中，每个分片（shard）有15个主候选节点（eligible primaries）。如果让所有这些节点都扫描故障并执行主动故障恢复，则效率不高。因此，我们在每个区域都有一个代理，负责故障扫描并执行领导权选举。
换言之，被选为领导者的候选节点并不需要自己完成选举操作。一个单独的代理可以执行选举所需的所有步骤，将候选节点晋升为领导者。我们将这种代理称为选举者（elector）。在许多情况下，例如在YouTube中，这种角色分离是必要的。不出所料，Vitess也继承了这一分离：VTorc是Vitess中的一个组件，用来充当选举者。
我们将选举者的角色与候选节点的角色进行概念化分离。这不会排除候选节点来担任选举者的角色，但在接下来的讨论中，这种术语区分将发挥重要作用。
基于锁的方法
获取锁可以简化领导权变更的问题。这确保了成功获得锁的选举者是唯一可以更改系统的代理。
但是，基于锁的方法带来了前进进展的问题。例如，一个选举者成功获取锁后可能崩溃或因为网络分区而与系统隔离。这会阻止其他选举者修复这种情况。为了解决这个问题，基于锁的系统必须引入时间组件：任何获取锁的选举者必须在一定时间内完成它的任务，否则锁会自动释放。
基于锁的方法一般比无锁方法具有更快的收敛速度。这是因为尝试领导权变更的第一个节点很可能在完成任务方面已经取得了最多进展。在大多数情况下，给予第一个选举者成功机会可以以最小的扰动完成领导权变更。
获取锁的动作需要多个节点的参与。这确保了即使部分节点失败或发生网络分区，也能保证前进进展。巧合的是，这个问题与分布式共识共享一些特性。因此，可以重用参与法定多数的现有节点来获取锁。事实上，这正是Raft所做的，但其过程是隐性的。
锁功能的独立性
有人可能认为Raft并没有显式获取锁，尽管它实现了让第一个选举者获胜。这是因为获取锁的行为被其他操作（例如撤销和建立）的步骤所隐藏。如果你从执行选举的代码中减去撤销、建立和传播的部分，剩下的内容实际上就是获取分布式锁的行为。
一个算法可以选择将锁功能实现为一个显式且独立的步骤。这种选择为我们提供了更大的灵活性，因为我们可以对锁功能进行微调，而不会干扰撤销和建立的任务。
后续详细内容到基于无锁（lock-free）的方法、优势与挑战部分，架构概念会更深入，由您选择是否继续翻译或者摘取重点部分补充汇总。
关注公众号：程序新视界，一个让你软实力、硬技术同步提升的平台
除非注明，否则均为程序新视界原创文章，转载必须以链接形式标明本文链接
本文链接：https://www.choupangxia.com/2025/05/23/consensus-algorithms-at-scale-part-5/
