Bully选举算法

in with 0 comment

触发选举的条件

  1. 当进程P从错误中恢复
  2. 检测到Leader失败

选举过程中会发生的三种消息

  1. Election消息:表示发起一次选举
  2. Answer(Alive)消息:对发起选举消息的应答
  3. Coordinator(Victory)消息:选举胜利者向参与者发送选举成功消息

选举流程

  1. 如果P是最大的ID,直接向所有人发送Victory消息,成功新的Leader;否则向所有比他大的ID的进程发送Election消息
  2. 如果P再发送Election消息后没有收到Alive消息,则P向所有人发送Victory消息,成功新的Leader
  3. 如果P收到了从比自己ID还要大的进程发来的Alive消息,P停止发送任何消息,等待Victory消息(如果过了一段时间没有等到Victory消息,重新开始选举流程)
  4. 如果P收到了比自己ID小的进程发来的Election消息,回复一个Alive消息,然后重新开始选举流程
  5. 如果P收到Victory消息,把发送者当做Leader

算法前提假设

  1. 系统是同步的
  2. 进程在任何时候都可能失败,包括算法在执行的过程中
  3. 进程失败后停止工作,重启后重新工作
  4. 有失败监控者,它可以发现失败的进程
  5. 进程之间消息传递是可靠地
  6. 每一个进程知道自己和其他每一个进程的id以及地址

实际选举例子

  1. 一开始6个节点,相互连通,P6是leader
    image.png
  2. P6挂断
    image.png
  3. P3发现P6不再响应,发送Election消息,发起一次选举,通知所有大于3的节点
    image.png
  4. P4和P5回应Answer(Alive)消息,告诉P3,P4,P5还存活着
    image.png
  5. P4发送Election消息,发起一次选举,通知所有大于4的节点
    image.png
  6. 只有P5回应回应Answer(Alive)消息,告诉P4,P5还存活着
    image.png
  7. P5发送Election消息,发起一次选举,通知所有大于5的节点
    image.png
  8. 当P6没有响应,P5发送Coordinator(Victory)消息,宣布自己是新的leader
    image.png

參考