分布式系统中的领导选举

领导选举可以简单地解释为针对分布式系统中的一件事（进程、主机、线程、对象或人员）授予一些特殊权力。这些特殊权力可能包括分配工作的能力、修改数据块的能力，或甚至处理系统中所有请求的责任。

领导选举是提高效率、减少协调、简化架构以及减少操作的强大工具。另一方面，领导选举可能会引入新的故障模式和扩展瓶颈。此外，领导选举可能会使您更难评估系统的正确性。

由于这些复杂情况，在实现领导选举之前，我们需要仔细考虑其他选择。对于数据处理和工作流程，AWS Step Functions 等工作流程服务可以实现许多与领导选举相同的优势，并避免许多风险。对于其他系统，我们通常会实现幂等 API、乐观锁定和其他使单个领导变得不必要的模式。

在本文中，我将讨论一般情况下领导选举的一些优缺点，以及 Amazon 如何在我们的分布式系统中使用领导选举，包括领导失败见解。

选举领导的方法有很多种，包括 Paxos 等算法、Apache ZooKeeper 等软件、自定义硬件以及租赁。租赁是 Amazon 使用最广泛的领导选举机制。租赁相对容易理解和实现，并且内置容错能力。租赁的工作方式为使用单个数据库存储当前领导。然后，租赁要求领导定期发出检测信号，以表明它仍然为领导。如果现有领导在一段时间后无法发出检测信号，其他领导候选者可能会尝试接管。

我们避免在分布式系统中依赖于时间，即使 Amazon Elastic Compute Cloud (Amazon EC2) 提供出色的时间同步功能。很难确保集群中的系统时钟足够同步，以依赖于同步来排序或协调分布式操作。在 Amazon，分布式系统只对人力消耗使用时间。租赁依赖于时间。但是，它们只依赖于本地运行持续时间，而不是需要多个服务器同步并达成一致的时钟时间。

DynamoDB 锁定客户端源代码提供有关领导选举的示例和详细信息。然而，我们发现，尽管租赁和锁定在概念上很简单，但正确实现可能很精细。实现需要了解服务器如何测量本地持续时间。例如，如果测量时间的服务器或库认为时间偶尔会向后跳，则将打破租赁中内置的持续时间假设。持续时间可以回避全局时钟同步问题，此问题会致使服务器停止对时间达成一致（从闰秒到因持续高 CPU 利用率而逐渐引起的本地时钟偏差）。

对于租赁和所有类型的分布式锁定，一个更大的问题是确保领导只在持有锁定时工作。确保领导持有锁定实际上相当困难。我们发现，确保运行缓慢或有耗网络上的领导不认为它持有锁定的时间比实际时间长非常重要。同样，检查锁定和完成工作之间的垃圾收集暂停可能会导致不正确的行为。在实践中，针对这些问题进行加强往往是最大的挑战。

DynamoDB 和 ZooKeeper 提供了基于租赁的简单锁定客户端，提供了容错领导选举。除非有特别需求，否则我们首选这些客户端，因为我们认为它们提供了最简单、最经过全面测试的领导选举实现方法。Amazon 团队希望避免创建自定义领导选举实现。相反，我们更青睐那些经过全面测试、久经验证的现有客户端。

领导选举是 Amazon 广泛部署的一种模式。例如：

• 几乎所有使用传统关系数据库管理系统 (RDBMS) 的系统都依赖于领导选举来选择一个处理所有写操作（有时为所有读操作）的领导数据库。在这些系统中，选举可能自动完成，但通常由人工手动执行。
• Amazon EBS 会在许多存储服务器上分发对某个卷的读取和写入。为确保一致性，它会使用领导选举来为卷的每个区域选举主节点，并由其来对读取和写入进行排序。如果该主节点失效，从属副本会使用相同领导选举机制充当主节点。在 Amazon EBS 中，领导选举确保了一致性，同时避免了在数据层面上进行协调，从而提高了性能。出于同样的原因，DynamoDB、Amazon Quantum Ledger Database (Amazon QLDB) 和 Amazon Kinesis (Kinesis) 使用类似的方法。
• Kinesis Client Library (KCL) 使用租赁确保每个 Kinesis 分区由一个拥有者处理，从而简化了对 Kinesis 流进行扩展处理的过程。

需要仔细考虑的另一个事项是，当领导出现故障时，领导的工作会发生什么情况。如果领导在任务中发生故障，则新领导如何完成任务？ 如果领导在保持其工作持久性之前就发生故障，系统是否仍然正确？ 许多系统都有单独“保持工作持久性”和“告知其他节点工作已完成”步骤。在 Amazon，我们的系统总是前者先于后者执行（或容忍数据丢失）。同样，幂等性在这里也很有用。它使新领导能够自信地重新推动即将离任的领导可能已经部分完成或已经完成但没有告知其他节点的工作。

为了容忍故障，Amazon 分布式系统没有单个领导。相反，领导力是一个属性，可在服务器间或进程间传递。在分布式系统中，不可能保证系统中只有一个领导。相反，大多数情况下可以是一个领导，故障期间可以是 0 个领导或 2 个领导。

我们如何选择系统在领导失效时的行为取决于系统中有两个领导时系统中的变化。执行幂等工作的系统通常可以容忍两个领导，且效率损失最小。通过两个领导，系统可以提高可用性和选择较弱的领导选举方法。

最多只需要一个领导的系统比多个领导的系统更难构建。领导选举系统必须始终正确一致。此外，还必须确保即将离任的领导在新领导人当选之前离任，这比看起来要难得多。在分布式系统中，通常很难知道一个系统是否失败，或者它只是继续在其他网络分区中工作。在 Amazon，我们确保任何经过领导选举的系统都能处理这种极端情况。

在 Amazon，我们遵循以下领导选举最佳实践：

• 经常检查剩余的租赁时间（或通常检查锁定状态），特别是在开始除领导本身之外具有副作用的任何操作之前。
• 考虑运行缓慢的网络、超时、重试和垃圾收集暂停可能会导致剩余的租赁时间在代码预期的时间之前过期。
• 避免在后台线程中执行发出检测信号的租赁。如果线程在租赁过期或检测信号线程终止时无法中断代码，则会导致出现正确性问题。如果工作线程终止或停止，而检测信号线程继续保持租赁，则会出现可用性问题。
• 有可靠的指标来显示领导可以执行的工作量，以及目前正在执行的工作量。经常检查这些指标，并确保在耗尽容量之前有扩展计划。
• 易于找到哪个主机是当前领导，哪个主机是任何给定时间的领导。保留领导变动的审计跟踪或日志。
• 使用 TLA+ 等工具对分布式算法的正确性进行建模和形式化验证。这可捕获一些微妙、难以发觉和罕见的错误，当应用程序对领导选举协议提供的保证做了过多的假设时，就会出现这些错误。

领导选举是 Amazon 系统中使用的一个强大工具，可帮助我们的系统具备容错能力，且更易于操作。但是，当我们使用领导选举时，我们会仔细考虑每个领导选举协议提供的保证，更重要的是，不提供的保证。

Amazon 系统经常使用领导选举确保内置容错能力。当系统使用领导选举确保至少有一个服务器在处理任务时，它们在同时使用多个领导的情况下利用单独的机制来维护正确性。例如，可能会使用底层数据库来确保两个领导认为它们都持有租赁时，它们不会互相干扰。我们没有对租赁实现提供的保证进行假设，而是关注这些系统中的正确性，通常使用 TLA+ 等技术进行建模。

尽管有细微差别，但在 Amazon 的分布式系统工具包中，领导选举仍然是一个有用的工具，与幂等性和乐观锁定等模式一起使用。

有关租赁工作原理的更多信息，请参阅：

• 如何执行分布式锁定
• Burrows，用于松散耦合分布式系统的 Chubby 锁定服务
• Gray 和 Cheriton，租赁：一种确保分布式文件缓存一致性的高效容错机制