10 分钟搞定分布式选举 Bully 算法

本文主要介绍了在分布式系统中使用 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"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！