前言：最近在关注分布式系统的选举算法，想了解下 ElasticSearch 是如何选主的，以及使用何种选主算法。发现了 elastic 官网上的一篇文章，写得还不错。故翻译过来，供大家学习，如翻译有误，敬请大家指正。原文

介绍

所有的分布式系统必须用这样或那样的方式处理一致性问题。为了简化，我们可以把策略分成两类。一类是试图避免非一致性情况的出现以及定义如何保持一致性。另一类对于适用的问题非常强大，但是对其他问题的数据模型附加了不可接受的约束。

在本文中，我们将研究第一类的一个示例，以及它如何处理网络故障。

为什么要用 Leader ?

在分布式系统中指定一个节点为 Leader 实际上与 Java 中的 synchronized 关键字非常相似。Java synchronized 的经典例子是两个线程尝试递增同一个整数。例如，两个线程试图分别存入 $100 到同一个账户中。每个线程都必须读取余额，增加其值并将其写回。假设初始余额为 $100，并且没有线程同步，则可能发生以下情况：

• 线程 A 读取余额 $100
• 线程 B 读取余额 $100
• 线程 A 计算新的余额 $200
• 线程 B 计算新的余额 $200
• 线程 A 写入新的余额 $200
• 线程 B 写入新的余额 $200

很明显，账户一开始是 $100，总共存了 $200，最后的余额应该是 $300。然而，线程 A 的存款被覆盖，因为线程 B 写入更新的余额是基于已过时的数据计算而来。

Java 中的解决方案是在执行增加计算的代码上使用 synchronized 关键字，它使一个线程在另一个线程读取余额之前，完成其余额计算并写入的工作。「译者注：多线程串行化」

如果将线程视为节点，那么可以想象，在分布式系统中很容易出同样的问题，但没有synchronized 关键字可以解决。因为 synchronized 是使用信号量实现的，而信号量又由底层操作系统和它所运行的硬件支持「译者注：Java 中的 synchronized 的实现原理并不是信号量」。但是如果我们看看 synchronized 的功能，我们可能会将这个概念应用到分布式环境中。在 Java 中把一个代码块声明为 synchronized 时，它总是同步到特定对象的监视器。监视器的大小只是一个。这就意味着在任何给定的时间内，监视器内都可能只有一个线程。当一个线程请求监视器并且监视器可用时，它被允许立即进入。如果监视器被占用，则把线程放入等待队列并挂起，直到监视器被其它线程释放。

我们如何把这种概念应用到分布式环境中？我们可以在每个节点上创建任意多个的监视器，但是对于给定需要保护的资源，只存在一个监视器。换句话说，每个帐户余额只有一个监视器。这将维护数据一致性的问题转化为确保所有节点都同意哪个节点负责实现每个余额的监控的问题。在我们这个简单的例子中，这可以由领导者来处理，剩下要做的就是选出一个领导者。

如果你像我一样有 P2P 背景，你可能会建议使用分布式哈希表（distributed hash table，DHT）而不是领导者来决定哪个节点实现每个资源的监视器。事实上，有一些非常棒的 DHT 实现可以处理每小时数千个节点的离开和加入。考虑到它们也可以在不了解底层网络拓扑的异构网络中工作，4 到 10 个消息跳转的查询响应时间是相当不错的，但是在节点同构且网络相当稳定的网格设置中，我们可以做得更好。

在 Elasticsearch 的典型场景中，一个可以简化的地方是集群没有那么多节点。通常，节点的数量远远少于单个节点能够维护的连接数量，而网格环境不必频繁地处理节点的连接和离开。这就是为什么 Leader 方法更适合于 Elasticsearch。「译者注：官方建议 ES 节点数为百级别，此处解释了为什么 ES 采用 主从架构模式，而不是 P2P 式的无主模式」

ZenDiscovery 机制

因此我们有一个 Leader 定期将当前版本的全局集群状态推送到每个节点。如果 Leader 宕掉了怎么办？即便我们的节点相当可靠也并不意味着我们可以接受单点故障。假设只有 Leader节点崩溃，而所有其他节点仍然能够通信，则 Elasticsearch 可以优雅地处理这一问题。因为其余节点将检测到 Leader 的失败（更确切地说是没有收到来自 Leader 的消息），并启动Leader 选举。如果使用的是 ZenDiscovery（默认），过程如下「译者注：从ZenDiscovery过程看，它使用类 Bullly 算法来进行选举，使用法定人数来解决脑裂问题」：

• 每个节点计算已知的最小节点 ID，并向该节点发送投票
• 如果一个节点获得足够多的投票「译者注：多数派」，并且该节点也为自己投票，那么它将扮演 Leader 的角色，并开始向其它节点发布集群状态。

赢得选举所需足够票数的定义就是法定人数。ElasticSearch 中的法定人数是一个可配的参数。在分布式系统中，一个节点不能确定另一个节点是死亡还是网络消息不可达，因此通常有一个先前商定的阈值——法定人数大小（quorum size，也可翻译成仲裁大小）——来代表另一方的投票。以以下场景为例：一个集群有 A、B、C、D、E 五个节点，法定人数为 3。A 是 Leader。碰巧，A 和 B 在一个网络上，C、D、E 在另一个网络上，这些网络通过一条链路连接起来。

image

当这条链路失效时，A 和 B 仍然可以通信，但不能与 C、D、E 通信。同样，在另一个网络上，C、D、E 可以通信，但不能与 A、B 通信。

image

接下来会发生的是：节点 C、D、E 探测到它们无法与 Leader A 通信，随后向 C 发起投票选举。一旦 C 获得了三票，它就开始扮演领导者的角色，并开始向 D、E 发布通知。在另一个网络中，Leader A 探测到它无法与节点 C、D、E 通信。Leader A 计算新的集群大小小于法定人数大小并放弃 Leader 角色，有效地阻止节点 A、B 响应查询，直到链路恢复。在现实生活中，不太可能有人被重要的网络电缆绊倒，但是网络比我上面的例子更复杂，而且网络分区实际上并不少见。不难想象，当一个系统依赖于多个数据中心时，很容易出现网络分裂；另一种就是错误的网络路由和交换机配置。正如在《网络是可靠的》中提到的，网卡确实会在发送出站包的同时丢弃所有入站包，导致服务器仍然发送心跳，但无法处理任何请求。

避免脑裂（Brain Split）

法定人数大小有两个明显的优势：首先，它简化了选举过程，因为选票只需要送给它们重新投票的节点。其次，更重要的是，这是避免大脑分裂的唯一方法。想象一下，相同的集群和相同的网络分裂，但法定人数大小为 2。C 仍然会被选为领导者，但是 A 不会放弃领导者的角色。这样就会产生两个领导者以及彼此无法感知的集群。这就是所谓的脑裂。两个集群都将接受读写操作，并且如预期的那样，它们将不同步。如果没有人为干预，他们可能永远都无法恢复。根据数据模型的不同，也许不可能统一两个数据版本，而迫使其中一个集群丢弃所有的数据。

不要重复造轮子

正如你所料，多年来，领导者选举一直是学术界一个有趣的话题，不少聪明的人也进行了大量的思考。如果你更热衷于让分布式系统工作，而不是投入大量精力进行研究和开发，那么你最好尝试实现一个众所周知的算法。在将来的某一天，当你最终发现了系统中那个疯狂的 bug时，它很可能只是实现中的一个 bug，而不是算法中的一个主要设计缺陷。当然，这同样适用于调整或集成现有的实现，而不是从头开始实现，特别是如果你希望使用更高级的算法。这份 bug 报告 说明了创造一个好的领导者选举实现是多么的复杂，即使你有一个合理的算法。

Bully 算法

Bully 算法是领导者选举的基本算法之一。它假设所有节点都有一个惟一的 ID，它强制按所有节点排序。任何时候的当前 Leader 都是集群中 ID 最大的节点。此算法的优点是易于实现，但不能很好地处理 ID 最大的节点不稳定的情况。特别是在繁琐的 Leader角色下， ID 最大的节点容易过载。因此，作为领导者它将崩溃；选择 ID 第二大的节点；而最大的 ID 节点将恢复——因为它不再超载——并随后再次启动领导者选举，只有当选和再次崩溃。然而，在底层的硬件接口中，bully 算法非常常见。将选举推迟到现任领导者失败之后，可能会避免选举失败，但很容易导致脑裂。

Paxos 算法

Paxos 实际上不仅仅是一个领导者选举算法。Paxos 是一组协议族，用于保持分布式系统的一致性。我不会详细介绍 Paxos 的各种类型，而是讨论 Paxos 的一般概念和特点。Paxos中使用的数据模型是一个不断增长的语句列表，其中每个语句都有一个惟一的编号。经过数学证明，Paxos 可以保证是，对于相同编号的语句，两个节点永远不会出现不同，并且只要有一个仲裁者参与，算法就会继续。这意味着节点永远不会不一致，算法永远不会陷入死锁，但是如果没有足够的节点在线，它可能会停止。这些保证实际上与我们想要的领导者选举算法非常相似。我们希望参与集群的所有节点都能就哪个节点是领导者达成一致，我们不希望任何其他节点能够运行并创建自己的集群，从而导致脑裂。用 Paxos 进行领导者选举就变得像提出“我是领导者”这样简单。如果它被接受，那么它就是领导者，直到另一个节点提议成为领导者。然而，这还不足以避免脑裂。在上面的网络分区示例中，现有的 Leader A 不会收到来自另一个交换机上节点 C 的通知。这就需要有另一个标准来结束这种领导关系。一种方法是，当发起领导者选举时，所使用的语句将出现在表单上：“I am leader until”。但另一种更好的方法是，领导者能够探测到与之通信的节点数低于法定人数，然后将自己降级。

根据上面的网络分区示例，让我们假设一个看门人将网络线缆连接到节点 C，然后将线缆重新连接到另一个交换机，从而产生一个新的网络分区。

image

有趣的是，法定人数现在由节点 A、B、C组成，而不是以前的C、D、E。如果这些节点使用的是 Paxos，它们的数据可能是这样的：

image

根据 Paxos 进行领导者选举的具体实施情况，有许多可能的结果，但它们都有两个共同点。节点 D、E 不能选举新的领导者，因为它们没有达到法定人数。在得知节点 C 在第二轮选举中当选之前，节点 A、B 不会选举新的领导者。假定每个 Leader 任期（leader term）的结束条件都是超时，那么有两种可能的结果。如果节点 C 在其任期结束前与节点 A、B 建立了联系，则节点 C 将重新建立一个法定人数，恢复其领导角色，且无需进行领导者选举。如果它的任期结束，则可以选举节点A、B、C。假定节点 A 是网络上第一个发现 C 的节点，它将尝试连任第 2 期的 Leader，但节点 C 会拒绝，因为它已经有了第 2 期的 Leader。然后，节点 A 可以选择尝试竞选第 3 任期。如果这样，它还将通知节点 B 关于节点 C 的第 2 任期时间。现在，如果节点 C 和 A 同时当选呢？「译者注：出现平票，票数相同」对这个问题的完整回答需要深入研究 Paxos 的细节，这超出了本文的范围，但是简短的回答是选举将会失败。事实上，原始Paxos 论文提出使用领导者选举算法来决定应该哪些节点开始一个新提案，但自从 Paxos 协议保证不会出现不一致，即使有多个节点提出矛盾的语句，这种领导者选举可能只是一个简单的启发式算法，以避免连续失败。例如，一个节点可能决定在重新尝试提出一个失败的语句之前等待一段随机时间。Paxos 在何时以及如何进行领导者选举方面的灵活性，比简单的恃强凌弱算法有很大的优势，因为在现实生活中有比死网络链接多得多的失败模式。

总结

在这篇文章中，我试图给一些已经进入学术界的领导者选举算一个简单的洞察。浓缩版是这样：

• 如果您关心数据，则法定人数大小非常重要。
• Paxos 算法确实很稳健，但实现起来并不容易。
• 最好是实现一个众所周知的算法，其中的优点和缺点都是已知的，而不是在以后得到一个大惊喜。这当然有很多选择。