面试题：分布式系统中常见的领导选举算法有哪些及简述其工作原理

Question

请列举至少两种分布式系统中的领导选举算法，并简要描述它们是如何确定领导者的。例如从节点通信、选举规则等方面阐述。

Answer 1

• Bully算法：
  • 节点通信：在一个分布式系统中，每个节点都有一个唯一的标识符，当一个节点（假设为A）发现当前领导者（如果有）失效时，A向所有标识符比它大的节点发送选举消息。
  • 选举规则：如果A没有收到任何响应，意味着A的标识符最大，A就宣布自己为领导者；如果收到响应，说明存在标识符更大的节点，A就等待新领导者的广播消息。
• Raft算法：
  • 节点通信：Raft算法中有三种角色：领导者（Leader）、跟随者（Follower）和候选人（Candidate）。跟随者在一段时间内没有收到领导者的心跳消息（心跳是领导者定期发送给跟随者的消息，用于维持领导地位），就会转换为候选人，并向其他节点发送请求投票的消息。
  • 选举规则：候选人在收到大多数节点（超过半数）的投票后，就成为领导者。如果在选举过程中，多个候选人同时竞争，可能会出现选举超时，此时会重新进行选举。新的领导者产生后，会向所有节点发送心跳消息，以维持领导地位。