分鐘搞定分布式選舉 Bully 算法
分布式系統通常需要在一組節點中選出一個領導者，以確保有效協調并做出決策，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
