為什么需要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消息，節點將重新開始一個新的選舉過程.