聊聊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

• Election Algorithms
• The Bully Election Algorithm
• Bully Election Algorithm Example
• A Token Ring Election Algorithm
• Token Ring Election Algorithm Example
• distributedLeaderElection