本文主要介绍了在分布式系统中使用 Bully 算法进行领导者选举的概念和流程，并以 Go 语言为例展示了具体的编码实践。原文：Leader Election: Using Bully Algorithm in Golang
分布式系统通常需要在一组节点中选出一个领导者，以确保有效协调并做出决策，Bully 算法就是在分布式系统中选举领导者的一种算法。本文将用 Go 实现 Bully 算法，以了解集群节点如何选举领导者。
Bully 算法简介
Bully 算法是一种简单有效的分布式系统选举算法，其工作原理如下：
- 节点层次结构：系统中的每个节点都有一个独一无二的 ID，节点之间可以互相知道对方的 ID。
- 领导者探测：如果节点探测到当前领导者没有响应（失败），就会启动选举流程。
- 选举：发起选举的节点（"bully"）向所有 ID 更高的节点发送选举信息。如果没有 ID 更高的节点响应，则"bully"获胜，成为新的领导者。
- 协调者：领导者是系统的协调者，负责决策和管理分布式任务。
过程概述
Bully 算法的基本思想是排序（rank），假定每个节点在集群中都有序号，而领导者必须是序号最高的。因此，在选举时需要使用节点的排序值。
选举有两种情况。
- 系统刚初始化，还没有领导者。
- 某个节点发现领导者宕机了。
选举方式如下：
- 节点向其他比自己排序高的节点发送 ELECTION 消息。
- 节点等待 ALIVE 响应。
- 如果没有更高排序的节点回应，自己就成为领导者。
- 否则，排序最高节点成为新领导者。
下面来详细说明一下：
假设节点排序为：node4 > node3 > node2 > node1
由于 node4 在该集群中排序最高，它没有收到任何来自更高排序的节点的 ALIVE 消息。因此，node4 决定成为领导者，并发送了一条 ELECTED 消息，向其他节点通报选举结果。
领导者失效
其他节点定期发送 PING 消息，探测领导者状态，并等待领导者的 PONG 响应。
如果领导者宕机，而第一个节点没有收到 PONG 消息，那么该节点就会重新开始选举过程。
在 Go 中实现 Bully 算法
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，并等待回复。
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 算法还是为领导者选举提供了一种清晰实用的方法，使其在可容错分布式系统中发挥重要作用。
你好，我是俞凡，在Motorola做过研发，现在在Mavenir做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI等技术始终保持着浓厚的兴趣，平时喜欢阅读、思考，相信持续学习、终身成长，欢迎一起交流学习。为了方便大家以后能第一时间看到文章，请朋友们关注公众号"DeepNoMind"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！
本文由mdnice多平台发布
