让我们从重述领导权变更期间请求传播的要求开始：

  • 传播之前完成的请求以满足新领导者的持久性要求。

第1-6部分回顾

  • 我们重新定义了一致性问题，主要目标是解决分布式系统中的持久性问题，并以自顶向下的方式解决该问题。
  • 我们展示了一种使持久性成为抽象要求的方法，而不是使用多数法定人数的更严格方式。
  • 我们定义了一组高级规则，用以满足一致性系统的特性，同时支持任意（但有意义的）持久性要求。
  • 我们证明了将领导权变更概念化为撤销和建立的过程可提供更多现有系统未利用的实现选项。
  • 我们还展示了应对竞争条件的两种基本不同的方法，并分析了它们的权衡。
  • 在上一篇文章中，我们探讨了请求的完成过程，为分析传播做了铺垫。

简单情况

对于基于锁的系统和计划变更，我们可以请求当前领导者自降权限。在这种情况下，当前领导者可以确保其请求被传播到所有必要的跟随者，然后再降级。一旦完成降级，选举者进行领导权变更，系统即可恢复运作。
接下来，我们讨论如果系统遇到故障时传播应该如何工作。

发现已完成的请求

如果系统遇到故障，则选举者必须间接撤销先前的领导权，方法是请求跟随者停止接受来自该领导者的进一步请求。如果足够多的跟随者已停止接受请求，以至于之前的领导者无法满足任何新的持久性标准，那么撤销即被认为成功。
这种方法不仅能够确保该领导者无法完成更多请求，还可以让我们发现所有之前已完成的请求。
接下来，我们需要传播这些请求以满足新领导者的标准。然而，这并不像听起来那么简单。
以下故障情况让这个问题变得异常困难：

  • 某些请求可能是未完成的。在这种情况下，选举者可能发现或未发现该请求。
  • 选举者发现了一个暂定的请求后，可能无法确定该请求是否已经满足了持久性要求。
  • 请求传播可能在完成前失败。
  • 如果选举者未发现某个未完成的请求，它可能会选出一个新的领导者，新领导者可能接受其他新请求，而这些请求可能在完成前失败。
  • 后续选举者可能会发现多个这样的未完成请求。
  • 另一个选举者可能只发现一个未完成的请求，将其传播为暂定状态，但在标记完成前失败。
  • 最终选举者可能发现一个持久完成的请求，以及一个较新的冲突未完成请求，并可能因为信息不足而无法判断应该接受哪一个请求。

基本规则

为了解决上述故障模式，让我们首先看看可以做什么和不能做什么：
必须遵循的规则：

  • 选举者必须能够达到足够数量的跟随者以撤销先前的领导权。如果无法做到这一点，选举者将被阻塞。
  • 选举者不需要（也可能无法）达到领导者的所有跟随者。

一些进一步的推论：

  • 选举者保证可以发现所有已经满足持久性要求的请求。
  • 如果请求是未完成的，选举者可能无法发现它。如果未发现，可以不再关注它。后续发现时，需将其取消。
  • 如果选举者发现未完成的请求，它可能无法确认该请求是否是真的持久完成。因此，它必须假设该请求可能已完成，并尝试传播它。
  • 如果选举者发现了某个未完成请求，并能够确定它确实未完成，就可以选择两种方式之一：作为已发现的处理，或者作为未发现的处理。

一些选项

决策版本化

传播最新发现的决策始终是安全的。传播一个之前的决策就是一个新的决策。
我们可以采用以下方法：

  • 每个请求都有基于时间的版本。
  • 领导者创建请求时，会使用比任何之前请求更高的版本。
  • 如果选举者选择传播一个未完成的请求，将使用一个新版本进行传播。
  • 如果选举者发现多个冲突请求，必须选择传播最新版本的请求。

已完成的请求不需要版本控制。
上述方法解决了两个难点：

  1. 如果发现两个冲突请求，则最新请求的创建，意味着前一个选举者没有发现旧请求。这表明旧请求一定未完成，因此可以安全地接受新选举者的决策。
  2. 如果传播现有请求，也必须使用新版本。这意味着它需满足新版本的持久性要求，而不会与旧版本混淆。

Paxos 使用提案编号对决策进行版本化，Raft 使用领导权任期编号。
当然也可以使用其他方法进行版本化。例如：可以为请求分配时间戳，而不是使用领导权任期或提案编号。

防抖规则

大规模系统通常有防抖规则，避免领导权在刚发生变化后立即再次更改。这通常因为问题源于更深层次的故障，而另一场领导权变更通常无法解决问题。在大多数情况下，这反而会加剧问题。
我知道的一个系统中，请求负载过大以至于传输超时，导致被检测为失败而触发领导权变更。然而，新领导者因同样的故障无法完成请求。最终通过增加超时解决了该问题。
巧合的是，防抖规则也缓解了上述故障模式。在这种系统中，对飞行中请求的版本化问题的重要性相对较低。

MySQL 和 Vitess

MySQL 的 binlog 中包含所有事务的元数据，其中包括两个相关信息：

  1. 全局事务 ID (GTID)，它包含创建该事务的领导者身份信息。
  2. 时间戳。

这些元数据被忠实地传播到所有副本。如果由于故障导致发现冲突事务，这些信息通常足以解决大多数模糊问题。
然而，忠实传播事务元数据打破了版本化规则，即新选举者的决策必须记录在一个新的时间戳下。
Orchestrator 是 MySQL 最流行的领导管理系统，内置了防抖规则，这些规则减轻了上述故障模式。这也是为什么组织能够在大规模运行 MySQL 时避免脑裂问题。
在 Vitess 中，我们使用 VTorc（Orchestrator 的定制版本），继承了相同的安全性。但我们也计划通过优化一些边界情况来降低复杂故障发生时对人工干预的需求。
敬请期待第8部分，我们将总结整个系列并进行最后的思考。


在大规模场景中实现一致性算法：第7部分 – 请求传播插图

关注公众号：程序新视界，一个让你软实力、硬技术同步提升的平台

除非注明，否则均为程序新视界原创文章，转载必须以链接形式标明本文链接

本文链接：http://www.choupangxia.com/2025/09/07/consensus-algorithms-7/