分布式基础 --- Leader election

为什么需要leader election
Ring election
Bully Algorithm

为什么需要leader election

在一组集群中, 需要选出一个leader来承担一些特别的任务, 比如

协调和控制系统操作：领导者负责协调和控制整个分布式系统的操作。它可以接收和处理其他节点的请求，并根据系统的需求进行决策和操作。
数据一致性和复制：领导者负责确保系统中的数据一致性和复制。它可以处理写入请求，并将写入操作广播到其他节点，以确保数据的一致性和可靠性。
资源分配和调度：领导者可以负责资源的分配和调度，以优化系统的性能和资源利用率。它可以根据系统的负载情况和需求，进行资源分配和任务调度的决策。
错误处理和故障恢复：领导者可以监视系统中的错误和故障，并采取相应的措施进行处理和恢复。它可以检测到其他节点的故障，并执行相应的故障转移和恢复策略，以确保系统的可用性和稳定性.

Ring election

初始化：在环状拓扑中的每个节点都被分配一个唯一的标识，例如节点ID。开始时，每个节点都将自己标记为候选者状态。
发起选举：一个节点决定发起选举时，它将向其后继节点发送选举消息。
选举消息传递：当一个节点收到选举消息时，它会比较消息中的候选者标识和自己的标识。如果收到的候选者标识比自己的标识更大，节点将更新自己的状态为候选者，并将收到的消息继续传递给下一个节点。如果收到的候选者标识与自己的标识相同，节点将宣布自己为领导者，并将选举结果传递回发起选举的节点。
选举结果传递：选举结果通过环状拓扑结构传递回发起选举的节点。每个节点将选举结果与自己的状态比较，如果选举结果中的标识比自己的标识更大，节点将更新自己的状态为候选者，并将选举结果继续传递给下一个节点。如果选举结果中的标识与自己的标识相同，节点将宣布自己为领导者，并选举过程结束。
领导者选举完成：当选举结果回到发起选举的节点时，该节点将宣布选举完成，并将选举结果广播给整个系统，以便其他节点得知新的领导者

接着 N80 的 Message会转一圈,最终回到N80, 表示选举完成. N80发出elected message

import java.util.ArrayList;
import java.util.List;// 节点类定义
class Node {private int id;private int leaderpublic Node(int id) {this.id = id;}public int getId() {return id;}public void receiveElectionMessage(ElectionMessage message) {if (message.type == "Elected" && message.id == this.id) {//election finishedleader = message.id;return }else if (message.type == "Elected") {leader = message.id;passElectionMessage(message)return }if (message.id > this.id) {passElectionMessage(message)}else if (message.getId() < this.id) {passElectionMessage(new ElectionMessage(this.id, "Election"))}else {passElectionMessage(new ElectionMessage(this.id, "Elected"))}}public void passElectionMessage(ElectionMessage message) {Node nextNode = getNextNode(); nextNode.receiveElectionMessage(message);}
}// 选举消息类定义
class ElectionMessage {public int id;public string messageType;
}

复杂度分析

Worst-Case:

(N-1) messages for Election message to get from
Initiator (N6) to would-be coordinator (N80)
N messages for Election message to circulate around ring without message being changed
N messages for Elected message to circulate around the ring
Message complexity: 3N-1 messages

Best-Case: 2N

Initiator is the would-be leader is the initiator
Message complexity: 2N messages

如何应对 Failures

如果在选举中N80挂掉了,则选举会一直进行下去

方案一: 让之前或者之后的节点重新发起选举, 如果收到Election message之后超时没有收到Elected Message

但是如果之前或者之后的节点也挂掉了, 或者之前前,之后后的节点也挂掉了

方案二: 使用Failure Detection：

任何接收到election消息（Election:80）的进程都可以通过Failure Detection检测N80的故障。
如果检测到N80的故障，可以启动新一轮的领导者选举
但是Failure Detection 本身就有不准确性

Bully Algorithm

所有节点都知道其他节点的ID
当之前的leader 挂掉时(通过 Failure Detection)

如果一个节点知道自己的标识是最高的：

它将自己选举为协调者，并向所有标识较低的进程发送一个Coordinator消息
选举过程完成

如果一个节点知道自己的标识不是最高的：

它会通过发送一个选举消息来发起选举。
只向比自己标识更高的进程发送选举消息。
如果在超时时间内没有收到回复，节点将自己称为领导者，并向所有标识较低的进程发送一个协调者消息。选举完成。
如果收到了回复，说明存在一个非故障的更高优先级的节点，节点将等待Coordinator消息。如果在另一个超时时间内没有收到Coordinator消息，节点将重新开始一个新的选举过程.