面试题：分布式系统中领导选举算法演进过程中如何解决脑裂问题

Question

在分布式领导选举算法的发展历程里，脑裂是一个关键挑战。请说明在不同阶段的选举算法中，是怎样识别和避免脑裂情况出现的，涉及到的相关机制和技术细节有哪些。

Answer 1

早期基于心跳检测的选举算法

• 识别脑裂：通过心跳检测来感知节点间的连接状态。若主节点在一定时间内收不到部分从节点的心跳，或从节点收不到主节点心跳，可能暗示网络分区，存在脑裂风险。
• 避免脑裂：
  • 多数机制：选举时，需超过半数节点参与并认可，才能选出主节点。例如在5个节点的集群中，至少3个节点同意，才可选举成功。这样即使发生网络分区，也只有一个分区能满足多数条件选出主节点，防止多主脑裂。
  • 时间同步：节点间保持时间同步，避免因时钟差异导致对心跳丢失判断不一致。比如采用NTP协议确保各节点时钟偏差在允许范围内。

基于分布式一致性协议（如Paxos、Raft）的选举算法

• 识别脑裂：
  • 日志一致性检查：以Raft为例，节点通过比较日志的一致性和新旧程度来识别异常。若节点间日志差异过大且无法通过正常同步修复，可能是脑裂导致不同分区独立运行。
  • 任期号：每个选举周期有唯一任期号，节点通过比较任期号识别脑裂。如发现自己任期号落后，且接收到更高任期号的消息，可能处于脑裂场景。
• 避免脑裂：
  • 领导者选举规则：在Raft中，竞选者需获得多数节点投票才能成为领导者。新领导者上任后，会向其他节点发送心跳维持领导地位。若网络分区恢复，旧领导者因任期号低会自动降级为跟随者，避免脑裂产生多主。
  • 日志复制：Paxos通过多数派确认机制复制日志。只有获得多数节点确认，提案才能被提交。这保证所有节点日志最终一致，避免因脑裂导致数据分歧。

基于 gossip 协议的选举算法

• 识别脑裂：
  • 节点信息传播不一致：gossip协议中节点定期互相交换状态信息。若节点发现自己收到的其他节点状态信息存在明显分区特征，如部分节点状态信息长期来自特定子集，可能存在脑裂。
  • 活跃度监测：通过监测节点活跃度，若某些节点活跃度突然下降，且在不同子集表现不同，可能暗示脑裂。
• 避免脑裂：
  • 信息冗余与收敛：节点间广泛传播信息，每个节点保存多个副本。即使网络分区，分区内节点基于已有副本信息仍能在一定程度上维持正常工作。当网络恢复，通过gossip传播最终使所有节点状态收敛，避免脑裂长期存在。
  • 加权投票：在选举时，对不同节点设置权重，综合考虑节点性能、负载等因素。选举结果由加权后的投票决定，降低因网络分区导致错误选举产生脑裂的概率。