分鐘搞定分布式選舉 Bully 算法

作者：DeepNoMind 2025-03-24 11:30:05

開發系統

本文主要介紹了在分布式系統中使用 Bully 算法進行領導者選舉的概念和流程，并以 Go 語言為例展示了具體的編碼實踐。

分布式系統通常需要在一組節點中選出一個領導者，以確保有效協調并做出決策，Bully 算法就是在分布式系統中選舉領導者的一種算法。本文將用 Go 實現 Bully 算法，以了解集群節點如何選舉領導者。

一、Bully 算法簡介

Bully 算法是一種簡單有效的分布式系統選舉算法，其工作原理如下：

節點層次結構：系統中的每個節點都有一個獨一無二的 ID，節點之間可以互相知道對方的 ID。
領導者探測：如果節點探測到當前領導者沒有響應（失敗），就會啟動選舉流程。
選舉：發起選舉的節點（"bully"）向所有 ID 更高的節點發送選舉信息。如果沒有 ID 更高的節點響應，則"bully"獲勝，成為新的領導者。
協調者：領導者是系統的協調者，負責決策和管理分布式任務。

二、過程概述

Bully 算法[2]的基本思想是排序（rank），假定每個節點在集群中都有序號，而領導者必須是序號最高的。因此，在選舉時需要使用節點的排序值。

選舉有兩種情況：

系統剛初始化，還沒有領導者。
某個節點發現領導者宕機了。

選舉方式如下：

節點向其他比自己排序高的節點發送 ELECTION 消息。
節點等待 ALIVE 響應：如果沒有更高排序的節點回應，自己就成為領導者；否則，排序最高節點成為新領導者。

下面來詳細說明一下：

假設節點排序為：node4 > node3 > node2 > node1

由于 node4 在該集群中排序最高，它沒有收到任何來自更高排序的節點的 ALIVE 消息。因此，node4 決定成為領導者，并發送了一條 ELECTED 消息，向其他節點通報選舉結果。

三、領導者失效

其他節點定期發送 PING 消息，探測領導者狀態，并等待領導者的 PONG 響應。

如果領導者宕機，而第一個節點沒有收到 PONG 消息，那么該節點就會重新開始選舉過程。

四、在 Go 中實現 Bully 算法

1. Node.go

var nodeAddressByID = map[string]string{
 "node-01": "node-01:6001",
 "node-02": "node-02:6002",
 "node-03": "node-03:6003",
 "node-04": "node-04:6004",
}

type Node struct {
 ID       string
 Addr     string
 Peers    *Peers
 eventBus event.Bus
}

為簡單起見，所有節點都是硬編碼。

該文件定義了 Node 結構，代表分布式系統中的一個節點。節點有 ID、網絡地址（Addr）、已知對端（Peers）列表和用于通信的事件總線（eventBus）。

nodeAddressByID：該映射保存了群集中所有節點的地址。每個節點都有一個映射到其網絡地址的唯一 ID。

func NewNode(nodeID string) *Node {
 node := &Node{
  ID:       nodeID,
  Addr:     nodeAddressByID[nodeID],
  Peers:    NewPeers(),
  eventBus: event.NewBus(),
 }

  node.eventBus.Subscribe(event.LeaderElected, node.PingLeaderContinuously)
  return node
}

NewNode(nodeID string)：基于給定 ID 創建新節點，并初始化其地址、對端集合以及事件總線。
eventBus.Subscribe：節點訂閱 LeaderElected 事件，當該事件發生時觸發 PingLeaderContinuously 函數

func (node *Node) NewListener() (net.Listener, error) {
 addr, err := net.Listen("tcp", node.Addr)
 return addr, err
}

NewListener()：該方法在節點的網絡地址（node.Addr）上創建新的 TCP 監聽器，用于處理來自其他節點的連接請求。

func (node *Node) ConnectToPeers() {
 for peerID, peerAddr := range nodeAddressByID {
  if node.IsItself(peerID) {
   continue
  }

  rpcClient := node.connect(peerAddr)
  pingMessage := Message{FromPeerID: node.ID, Type: PING}
  reply, _ := node.CommunicateWithPeer(rpcClient, pingMessage)

  if reply.IsPongMessage() {
   log.Debug().Msgf("%s got pong message from %s", node.ID, peerID)
   node.Peers.Add(peerID, rpcClient)
  }
 }
}

ConnectToPeers()：與集群中所有對端節點建立 RPC 連接，遍歷 nodeAddressByID 中的每個對端節點，連接并發送 PING 消息。

如果對端節點回應了 PONG 消息，就將該對端節點添加到已知對端節點列表中。

func (node *Node) connect(peerAddr string) *rpc.Client {
retry:
 client, err := rpc.Dial("tcp", peerAddr)
 if err != nil {
  log.Debug().Msgf("Error dialing rpc dial %s", err.Error())
  time.Sleep(50 * time.Millisecond)
  goto retry
 }
 return client
}

connect(peerAddr string) *rpc.Client：與給定的 peerAddr（對端網絡地址）建立 RPC 客戶端連接。

如果連接報錯，利用 goto 語句延遲 50 毫秒后重試。

func (node *Node) CommunicateWithPeer(RPCClient *rpc.Client, args Message) (Message, error) {
 var reply Message

 err := RPCClient.Call("Node.HandleMessage", args, &reply)
 if err != nil {
  log.Debug().Msgf("Error calling HandleMessage %s", err.Error())
 }

 return reply, err
}

CommunicateWithPeer：該方法通過 RPC 客戶端 RPCClient 向對端發送信息 args，并等待回復。

2. Peer.go

type Peer struct {
 ID        string
 RPCClient *rpc.Client
}

type Peers struct {
 *sync.RWMutex
 peerByID map[string]*Peer
}

func NewPeers() *Peers {
 return &Peers{
  RWMutex:  &sync.RWMutex{},
  peerByID: make(map[string]*Peer),
 }
}

func (p *Peers) Add(ID string, client *rpc.Client) {
                ...
}

func (p *Peers) Delete(ID string) {
                ...
}

func (p *Peers) Get(ID string) *Peer {
                ...
}

這是 Peer 和 Peers 結構及其方法。Peer 代表系統中的單個節點，而 Peers 則是對端節點的集合，包含添加、刪除、獲取和轉換為列表或 ID 的方法。

五、實現

通過 Docker Compose 模擬集群中的節點，每個節點都基于相同的 dockerfile。
為了讓算法發揮作用，每個節點都需要了解其他節點的情況，這就需要一種服務發現機制。
每個節點都被硬編碼了其他節點的網絡信息，而不是實現完整的服務發現功能。
這種簡化是為了演示目的。更穩健的實現方式應包括適當的服務發現機制，以動態處理節點的添加和刪除。

在通信過程中，如果領導者出現故障，其連接將被中斷，并返回錯誤信息，以便開始新的選舉過程。

當節點啟動時，node4 成為領導者，因為根據其 ID，它的排序最高。在沒有領導者的情況下，node4 發起選舉，宣布自己為領導者，并廣播 ELECTED 消息通知其他節點。

接下來，我們模擬 node4 被終止的情況，觀察新的領導者是如何被選出來的。

六、算法面臨的挑戰

當出現網絡分區時，該算法就會違反安全保證，導致不同節點子集可能出現多個領導者，這種情況被稱為 "腦裂"。

排序靠前的節點有很強的偏向性，如果它們不穩定，就會出現問題。當不穩定的高排序節點屢次失敗并試圖再次成為領導者時，這種偏向會導致不斷循環重復選舉。

盡管存在這些挑戰，Bully 算法還是為領導者選舉提供了一種清晰實用的方法，使其在可容錯分布式系統中發揮重要作用。

參考資料：

[1] Leader Election: Using Bully Algorithm in Golang: https://medium.com/@jitenderkmr/leader-election-using-bully-algorithm-in-go-60ec03bd277c
[2] Bully 算法: https://en.wikipedia.org/wiki/Bully_algorithm

責任編輯：趙寧寧來源： DeepNoMind