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

查看:28
本文介绍了高级主选举算法与欺凌算法相比有什么好处?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我阅读了当前的主选举算法(如 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 比传统的 Bully 算法更适用于脑裂场景或其他网络故障,因为我可以很容易地找出节点的法定人数何时离开集群而不使用 Raft.我看到的唯一好处是每个服务器必须处理的数据包数量;在 Raft 中只有 master 发送心跳消息,而在这种情况下,每个节点必须相互发送心跳消息.但是我不认为这是一个问题,因为我可以简单地实现类似的心跳算法而无需更改我的主选举算法.

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.

有人能详细说明一下吗?

Can someone elaborate on that?

推荐答案

从理论上讲,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,但从来没有一个做 A 而另一个做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.

这里有两个注释.首先,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.

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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆