聊聊Election Algorithms
原创
序
本文主要研究一下Election Algorithms
Election Algorithms
Election Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm；对于大多数的election algorithms通常有如下几个假定：
- 完整的topology，信息可以在topology的nodes之间传递
- 每个node有唯一的id，而且对整个topology其他node可见
- 所有的通信网络是可靠的，只允许node fail，要求消息不丢失，不重复，不损坏
- 要求已经有fail detector机制来处理node fail的情况
Bully Election
- 当有node检测到leader fail之后，就发送election request给其他node，election request中带上自己的id
- 当node接收到election request时判断如果自己的id大于request中的id，则可以"bully"覆盖request中的id，如果小于则不改动，然后发送election request给其他node；当有node接收到election request的id是自己的node id时，则表明自己是leader，于是给其他node发送leader request
- 当node接收到leader request时设置本地leader id，同时判断如果leader id不是自己的node id时则转发该leader request给其他node
Token Ring Election
- 当有node检测到leader fail之后，就发送election request给其他node，election request中带上自己的id
- 当node接收到election request时，则判断自己的node id是否在里面，不在的话则追加自己的node id到election request中；如果自己的node id已经在该election request中时则提取这些node id，取出id最大的作为leader，然后给其他node发送leader request
- 当node接收到leader request时设置本地leader id，同时判断如果leader id不是自己的node id时则转发该leader request给其他node
实例
这里采用distributedLeaderElection的实现
Bully Election
public void onMessage(String message) {
String messageHeader = message.split(":")[0];
String messageBody = message.split(":")[1];
if (messageHeader.equals("Election")){
if (Integer.parseInt(messageBody.trim()) < Node.getMyID() // If we are a better candidate
&& !participant){
System.out.println("I " + Node.getMyID() + " am a better candidate than "+messageBody);
Node.sendMsgToNextNode("Election" + ":" + Node.getMyID()); // Suggest us for election
}
else if (Integer.parseInt(messageBody.trim()) == Node.getMyID()) { // If this is our ID
System.out.println("I " + Node.getMyID() + " received my own pebble, so I am the new leader");
Node.sendMsgToNextNode("Leader" + ":" + Node.getMyID()); // Announce us as the new leader
}
else { // The current candidate is better
System.out.println("I " + Node.getMyID() + " am a worse candidate than "+messageBody);
Node.sendMsgToNextNode(message); // Forward his candidancy
}
participant = true;
}
else if (messageHeader.equals("Leader")){
System.out.println(messageBody + " is the new leader");
leaderID = messageBody;
if (Integer.parseInt(messageBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message);
}
}- 可以看到bully算法在看到election request中node id小于自己node id时，直接bully覆盖该node id；当走了一圈发现请求中node id是自己的node id时，则选举自己为leader
Token Ring Election
public void onMessage(String message) {
String messageHeader = message.split(":")[0];
List<String> messageBody = Arrays.asList(message.replace(messageHeader+":", "").split(":"));
if (messageHeader.equals("Election")){
if (!messageBody.contains(Node.getMyID()+"")){ // If we are not contained in the list
System.out.println("I " + Node.getMyID() + " am not contained in this message "+message);
Node.sendMsgToNextNode(message + ":" + Node.getMyID()); // Suggest us for election
}
else { // If we are in the list
System.out.println("I " + Node.getMyID() + " am contained in this message");
String newLeader = findLeaderInBody(messageBody);
Node.sendMsgToNextNode("Leader" + ":" + newLeader); // Announce the new leader
}
}
else if (messageHeader.equals("Leader")){
String leaderBody = message.split(":")[1];
System.out.println(leaderBody + " is the new leader");
leaderID = leaderBody;
if (Integer.parseInt(leaderBody.trim()) != Node.getMyID()) Node.sendMsgToNextNode(message);
}
}
private String findLeaderInBody(List<String> messageBody) {
int maxID = 0;
if (messageBody.size() > 0){
for (String leaderCandidate : messageBody){
if (Integer.parseInt(leaderCandidate.trim()) > maxID) {
maxID = Integer.parseInt(leaderCandidate.trim());
}
}
}
return maxID+"";
}- 可以看到ring算法是在请求中追加自己的node id；当走了一圈发现自己的node id已经在其中时，通过findLeaderInBody从这些node id中取出最大的那个，选举该node为leader
小结
- Election Algorithms大致有两类，一类是Garcia-Molina提出的Bully Election，一类是Chang & Roberts's Token Ring Election algorithm
- 对于大多数的election algorithms通常有如下几个假定：
- 完整的topology，信息可以在topology的nodes之间传递
- 每个node有唯一的id，而且对整个topology其他node可见
- 所有的通信网络是可靠的，只允许node fail，要求消息不丢失，不重复，不损坏
- 要求已经有fail detector机制来处理node fail的情况
- bully算法与ring算法的共同点是对比node id，在具体的实例中我们可以看到，bully算法顾名思义就是如果自己的node id比较大，则可以覆盖request中的node，最后node id最大的为leader；而ring算法则是采取追加node id方式，最后在从中选取node id最大的为leader
doc
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录