cluster-computing - 高级主选举算法与欺凌算法相比有什么好处？

Question

我阅读了当前的主选举算法(如 Raft、Paxos 或 Zab)如何在集群上选举主，但不明白为什么他们使用复杂的算法而不是简单的欺凌算法。

我正在开发一个集群库并使用 UDP 多播来处理心跳消息。每个节点加入一个多播地址，并定期向该地址发送数据报包。如果节点发现有一个新节点向该多播地址发送数据包，则将该节点简单地添加到集群中，并且类似地，当集群中的节点没有从某个节点获取任何数据包时，它们会将其从集群中删除。当我需要选择一个主节点时，我只需遍历集群中的节点并选择最旧的一个。

我读过一些文章，这些文章暗示这种方法无效，应该使用更复杂的算法，如 Paxos，以便通过心跳消息来选择主节点或检测故障。我不明白为什么 Paxos 比传统的 Bully 算法更适用于脑裂场景或其他网络故障，因为我可以很容易地找出节点的法定人数何时离开集群而不使用 Raft。我看到的唯一好处是每个服务器必须处理的数据包数量；在 Raft 中只有 master 发送心跳消息，而在这种情况下，每个节点必须相互发送心跳消息。但是我不认为这是一个问题，因为我可以简单地实现类似的心跳算法而不改变我的主选举算法。

有人可以详细说明吗？

Answer 1

从理论上讲，Raft、Paxos 和 Zab 都不是领导者选举算法。他们解决了一个不同的问题，称为共识。

在您的具体场景中，不同之处如下。使用领导者选举算法，您只能保证最终一个节点是领导者。这意味着在一段时间内，多个节点可能认为它们是领导者，因此可能会像一个节点一样行事。相比之下，通过上面的共识算法，你可以保证在一个逻辑时刻最多有一个领导者。

结果就是这样。如果系统的安全性取决于单个领导者的存在，那么仅依靠领导者选举可能会遇到麻烦。考虑一个例子。节点从 UDP 多播接收消息，如果发送者是领导者，则执行 A，但如果发送者不是领导者，则执行 B。如果两个节点在稍微不同的时间点检查集群中最旧的节点，它们可能会看到不同的领导者。然后这两个节点可能会收到一个多播消息并以不同的方式处理它，这可能会违反你想要持有的系统的某些安全属性(例如，所有节点要么做 A 要么做 B，但从来没有一个做 A 而另一个做B)。

使用 Raft、Paxos 和 Zab，你可以克服这个问题，因为这些算法创建了某种逻辑时代，每个时代至多有一个领导者。

这里有两个注释。首先，bully 算法是为同步系统定义的。如果您真的按照 Garcia-Molina 的论文中的描述来实现它，我相信您可能会在部分同步系统中遇到问题。其次，Zab 算法依赖于异步系统的一种欺凌算法。通过比较他们的历史长度来选出领导者(这可以最大限度地减少系统的恢复时间)。 Once the leader is elected, it tries to start the Zab protocol, which in turn locks the epoch for the leader.