分布式系统:领导者选举

Question

我目前正在开发分布式系统,我们必须实施某种领导者选举.问题是我们希望避免所有计算机必须相互了解 - 但只有领导者.有没有一种快速的方式,我们可以使用例如广播来实现我们想要的？

或者,我们是否只需知道至少一个,以进行良好的领导者选举？

可以假设所有计算机都在同一个子网上.

谢谢你的帮助.

Answer 1

问题是我们希望避免所有计算机必须相互了解 - 但只有领导者.

领导者选举是从一组潜在领导者候选人中挑选一名领导者的问题.看它有两个必需的属性:活跃和安全.在这里,活跃意味着"大多数时候,有一个领导者",而安全意味着"有一个或一个领导者".让我们考虑如何使用广播在您的示例中解决此安全属性.

假设每个节点都有一个唯一的ID,我们选择一个简单(破碎)的算法.每个节点广播其ID并侦听.当收到比自己更高的ID时,它将停止参与.如果它收到的ID比自己的ID低,它会再次发送自己的广播.假设一个同步网络,每个人收到的最后一个ID是领导者的ID.现在,介绍一个网络分区.该协议将很快继续在分区的任何一方,并将选出两名领导人.

这种破坏的协议也是如此,但所有可能的协议都是如此.如果您不知道(至少)存在多少个节点,您如何区分无法与之通信的节点和不存在的节点之间的区别？因此,第一个安全结果是:您需要知道存在多少个节点,或者您无法确保只有一个领导者.

现在,让我们放松我们的安全约束,成为一个概率问题:"可能有零个或多个领导者,但大部分时间都有一个".这使问题易于处理,广泛使用的解决方案是八卦(流行病协议).例如,请参阅八卦式故障检测服务,该服务讨论了这个确切问题的变体.本文主要关注概率正确的故障检测和枚举,但如果你能做到这一点,你也可以做出概率正确的领导者选举.

据我所知,你不能在一般网络中进行安全的非概率性领导者选举而不至少列举参与者.

Answer 2

作为我上次看到的有趣的“分布式机制”解决方案之一，我推荐 Apache Zookeeper项目。这是开源解决方案，因此至少您应该能够从那里获得一些想法。此外，它正在集中开发，因此您可能可以将其作为解决方案的一部分重复使用。

ZooKeeper是一个集中式服务，用于维护配置信息、命名、提供分布式同步、提供组服务。所有这些类型的服务都以某种形式由分布式应用程序使用。每次实施它们时，都需要进行大量工作来修复不可避免的错误和竞争条件。由于实现这些类型的服务很困难，应用程序最初通常会忽略它们，这使得它们在发生变化时变得脆弱并且难以管理。即使正确完成，这些服务的不同实现也会导致部署应用程序时的管理复杂性。