相比于欺凌算法，高级主选举算法有什么好处? [英] What's the benefit of advanced master election algorithms over bully algorithm?

问题描述

我了解了诸如Raft，Paxos或Zab之类的当前主选举算法如何在集群上选举主数据库，却无法理解为什么他们使用复杂算法而不是简单的欺负算法.

I read how current master election algorithms like Raft, Paxos or Zab elect master on a cluster and couldn't understand why they use sophisticated algorithms instead of simple bully algorithm.

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

I'm developing a cluster library and use UDP Multicast for heartbeat messages. Each node joins a multicast address and also send datagram packets periodically to that address. If the nodes find out there is a new node that sends packets to this multicast address, the node is simply added to cluster and similarly when the nodes in the cluster don't get any package from a node, they remove it from the cluster. When I need to choose a master node, I simply iterate over the nodes in the cluster and choose the oldest one.

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

I read some articles that implies this approach is not effective and more sophisticated algorithms like Paxos should be used in order to elect a master or detect failures via heartbeat messages. I couldn't understand why Paxos is better for split-brain scenarios or other network failures than traditional bully algorithm because I can easily find out when quorum of nodes leave from the cluster without using Raft. The only benefit I see is the count of packets that each server have to handle; only master sends heartbeat messages in Raft while in this case each node has to send heartbeat message to each other. However I don't think this is a problem since I can simply implement similar heartbeat algorithm without changing my master election algorithm.

有人可以详细说明吗?

推荐答案

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

From a theoretical perspective, Raft, Paxos and Zab are not leader election algorithms. They solve a different problem called consensus.

在您的具体情况下，区别如下.使用领导者选举算法，您只能保证最终一个节点是领导者.这意味着在一段时间内，多个节点可能会认为自己是领导者，因此可能会表现得像一个领导者.相比之下，使用上述共识算法，您可以保证在逻辑时刻最多有一位领导者.

In your concrete scenario, the difference is the following. With a leader election algorithm, you can only guarantee that eventually one node is a leader. That means that during a period of time, multiple nodes might think they are the leader and, consequently, might act like one. In contrast, with the consensus algorithms above, you can guarantee that there is at most one leader in a logical time instant.

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

The consequence is this. If the safety of the system depends on the presence of a single leader, you might get in trouble relying only on a leader election. Consider an example. Nodes receive messages from the UDP multicast and do A if the sender is the leader, but do B if the sender is not the leader. If two nodes check for the oldest node in the cluster at slightly different points in time, they might see different leaders. These two nodes might then receive a multicast message and process it in different manners, possibly violating some safety property of the system you'd like to hold (eg, that all nodes either do A or B, but never one does A and another does B).

使用Raft，Paxos和Zab，您可以克服该问题，因为这些算法创建了一种逻辑时期，每个时期最多具有一个领导者.

With Raft, Paxos, and Zab, you can overcome that problem since these algorithms create sort of logical epochs, having at most one leader in each of them.

这里有两个注释.首先，为同步系统定义了欺凌算法.如果您按照Garcia-Molina的论文中的描述真正实现了它，那么我相信您可能会在部分同步的系统中遇到问题.其次，Zab算法依赖于异步系统的一种欺凌算法.通过比较他们的历史记录长度来选出领导者(这可以最大程度地缩短系统的恢复时间).选出领导者后，它将尝试启动Zab协议，这反过来又锁定了领导者的时代.

Two notes here. First, the bully algorithm is defined for synchronous systems. If you really implement it as described in the paper by Garcia-Molina, I believe you might experience problems in your partially synchronous system. Second, the Zab algorithm relies on a sort of bully algorithm for asynchronous systems. The leader is elected by comparing the length of their histories (that minimizes the recovery time of the system). Once the leader is elected, it tries to start the Zab protocol, which in turn locks the epoch for the leader.

这篇关于相比于欺凌算法，高级主选举算法有什么好处?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！