高级主选举算法比欺负算法有什么好处？

Question

我读到当前的主要选举算法如Raft,Paxos或Zab如何选择群集上的主人,并且无法理解为什么他们使用复杂的算法而不是简单的欺负算法.

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

我阅读了一些文章,暗示这种方法无效,应该使用像Paxos这样的更复杂的算法,以便通过心跳消息选出主控或检测故障.我无法理解为什么Paxos比传统的欺负算法更适合裂脑情况或其他网络故障,因为我可以很容易地发现当法定数量的节点离开集群而不使用Raft时.我看到的唯一好处是每个服务器必须处理的数据包数量; 只有master在Raft中发送心跳消息,而在这种情况下,每个节点都必须向对方发送心跳消息.但是我不认为这是一个问题,因为我可以简单地实现类似的心跳算法而不改变我的主选举算法.

有人可以详细说明吗？

Answer 1

从理论的角度来看,Raft,Paxos和Zab不是领导者选举算法.他们解决了一个叫做共识的不同问题

在您的具体方案中,区别如下.使用领导者选举算法,您只能保证最终一个节点是领导者.这意味着在一段时间内,多个节点可能会认为它们是领导者,因此可能就像一个节点.相反,使用上面的一致性算法,您可以保证在逻辑时刻中最多只有一个领导者.

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

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

这里有两个注释.首先,为同步系统定义欺凌算法.如果你真的按照Garcia-Molina的论文中所描述的那样实现它,我相信你的部分同步系统可能会遇到问题.其次,Zab算法依赖于异步系统的一种欺凌算法.通过比较历史长度(最小化系统的恢复时间)来选出领导者.一旦领导者当选,它就会尝试启动Zab协议,从而锁定领导者的时代.