Token Ring Election Algorithm

Posted on Edited on

令牌环领导人选举算法

We start with 6 processes,
connected in a logical ring.
Process 6 is the leader,
as it has the highest number.

Process 6 fails.

Process 3 notices that Process 6 does not respond
So it starts an election,
sending a message containing its id
to the next node in the ring.

Process 5 passes the message on,
adding its own id to the message.

Process 0 passes the message on,
adding its own id to the message.

Process 1 passes the message on,
adding its own id to the message.

Process 4 passes the message on,
adding its own id to the message.

When Process 3 receives the message back,
it knows the message has gone around the ring,
as its own id is in the list.
Picking the highest id in the list,
it starts the coordinator message
“5 is the leader” around the ring.

Process 5 passes on the coordinator message.

Process 0 passes on the coordinator message.

Process 1 passes on the coordinator message.

Process 4 passes on the coordinator message.

Process 3 receives the coordinator message,
and stops it.

让我们分析如何在ZooKeeper集合中选举leader节点，这个过程和令牌环原理是一致的。考虑一个集群中有N个节点。leader选举的过程如下：

  • 所有节点创建具有相同路径 /app/leader_election/guid_ 的顺序、临时节点。
  • ZooKeeper集合将附加10位序列号到路径，创建的znode将是 /app/leader_election/guid_0000000001，/app/leader_election/guid_0000000002等。
  • 对于给定的实例，在znode中创建最小数字的节点成为leader，而所有其他节点是follower。
  • 每个follower节点监视下一个具有最小数字的znode。例如，创建znode/app/leader_election/guid_0000000008的节点将监视znode/app/leader_election/guid_0000000007，创建znode/app/leader_election/guid_0000000007的节点将监视znode/app/leader_election/guid_0000000006。
  • 如果leader关闭，则其相应的znode/app/leader_electionN会被删除。
  • 下一个在线follower节点将通过监视器获得关于leader移除的通知。
  • 下一个在线follower节点将检查是否存在其他具有最小数字的znode。如果没有，那么它将承担leader的角色。否则，它找到的创建具有最小数字的znode的节点将作为leader。
  • 类似地，所有其他follower节点选举创建具有最小数字的znode的节点作为leader。