常见轮询算法实现

一、基础轮询

1. 算法实现

基础轮询是轮询算法中最常见的方式之一，即每个元素被选中的几率都是等价的。

基础轮询算法的实现也相对简单，通过类静态变量 OFFSET 与元素集合长度进行取余，每次完成后 OFFSET 都将自增，取余得到的结果的即为数组访问下标。利用 static 保证静态变量的值为全局共享，同时 synchronized 保证了多线程的并发安全问题。

public class BasicRound {

    private static int OFFSET = 0;

    private static List<String> nodeList;

    public static void fill(List<String> list) {
        nodeList = list;
    }

    public static synchronized String round() {
        int size = nodeList.size();
        int index = OFFSET++ % size;
        OFFSET = OFFSET < size ? OFFSET : 0;
        return nodeList.get(index);
    }
}

2. 示例测试

通过一个示例验证上述的算法效果，定义了四个节点的元素集合使用上述算法轮询 1000 次，可以看到最终统计输出的结果每个节点元素都被访问了 250 次，即实现了 1:1 的等价轮询。

@Test
public void basicRound() {
    List<String> nodeList = List.of(
        "127.0.0.1:9091", "127.0.0.2:9092", 
        "127.0.0.3:9093", "127.0.0.3:9094"
    );
    // Fill data
    List<String> list = new ArrayList<>();
    BasicRound.fill(nodeList);
    // Simulation
    for (int i = 0; i < 1000; i++) {
        list.add(BasicRound.round());
    }
    Map<String, Long> count = list.stream().collect(Collectors.groupingBy(p -> p, Collectors.counting()));
    // {
    //      127.0.0.1:9094=250, 
    //      127.0.0.1:9093=250, 
    //      127.0.0.1:9092=250, 
    //      127.0.0.1:9091=250
    // }
    System.out.println("Basic Round: " + count);
}

二、随机轮询

1. 算法实现

随机轮询算法相较基础轮询更为简单，即每次生成一个不大于集合大小的随机数，将这个随机数作为元素集合的访问下标，从而实现随机访问的目的。

随机算法相较于基础轮询可能会造成节点饥饿的问题，即随机的因素导致元素集合中的某个元素一直都未能被访问。

public class RandomRound {

    private static List<String> nodeList;

    public static void fill(List<String> list) {
        nodeList = list;
    }

    public static synchronized String round() {
        int index = new Random().nextInt(nodeList.size());
        return nodeList.get(index);
    }
}

2. 示例测试

同样以四个节点的集合作为目标进行轮询，通过 1000 次轮询后可以看到随机轮询的各个元素访问频次都各不相同，但总体上而言也趋于 1:1 的关系。

@Test
public void randomRound() {
    List<String> nodeList = List.of(
        "127.0.0.1:9091", "127.0.0.2:9092", 
        "127.0.0.3:9093", "127.0.0.3:9094"
    );
    // Fill data
    List<String> list = new ArrayList<>();
    BasicRound.fill(nodeList);
    // Simulation
    for (int i = 0; i < 1000; i++) {
        list.add(RandomRound.round());
    }
    Map<String, Long> count = list.stream().collect(Collectors.groupingBy(p -> p, Collectors.counting()));
    // {
    //      127.0.0.1:9094=247, 
    //      127.0.0.1:9093=258, 
    //      127.0.0.1:9092=235, 
    //      127.0.0.1:9091=260
    // }
    System.out.println("Random Round: " + count);
}

三、权重轮询

1. 算法实现

带权轮询是轮询算法中较为常见的方式，即为每个元素添加对应权重，权重越高访问到的几率也相对越高。

根据实现效果先对权重轮询的功能进行拆分，针对目标集合中权重大小相等的元素而言其实现思路与基础轮询中一致，即访问频率应处于 1:1 的状态，因此第一步要做的就是针对权重大小对目标集合进行分组。

完成分组后则要考虑权重的分配问题，这里通过权重值占比方式解决，即通过分组后的小集合总权重与大集合的权重占比确定轮询频次。如下述四个节点经过分组后得到两个小集合：

node1: 1         分组后        list1: {node1: 1, node2: 1}
node2: 1        =======>      
node3: 2                   
node4: 2                       list2: {node3: 2, node4: 2}

分组后的两个集合 list1 与 list2 权重比分别为 1:2，因此在访问分组集合时应每访问两次 list2 后进行一次 list1 集合的访问，而针对集合内部的元素则按照基础轮询的实现方法进行。

将上述的逻辑思路转化为代码即下述所示：

public class WeightRound {

    private static Map<String, Integer> nodeWeightMap;

    private static int batch = 0;

    private static int weightSum;

    private static final Map<Integer, List<String>> revertMap = new HashMap<>();

    private static final List<Integer> orderKeys = new ArrayList<>();

    private static final Map<Integer, Integer> weightOffsetMap = new HashMap<>();

    public static void fill(Map<String, Integer> map) {
        nodeWeightMap = map;
        weightSum = nodeWeightMap.values().stream().reduce(Integer::sum).orElse(0);
        revert();
    }

    // 根据权重分组并排序
    private static void revert() {
        for (String key : nodeWeightMap.keySet()) {
            List<String> list;
            Integer val = nodeWeightMap.get(key);
            if (Objects.isNull(revertMap.get(val))) {
                list = new ArrayList<>();
                list.add(key);
            } else {
                list = revertMap.get(val);
                list.add(key);
            }
            revertMap.put(val, list);
        }
        orderKeys.addAll(revertMap.keySet());
        orderKeys.sort(Comparator.reverseOrder());
    }

    public static synchronized String roundWight() {
        for (Integer weight : orderKeys) {
            List<String> list = revertMap.get(weight);
            int size = list.size();
            int fullCount = weight * size;
            int offset = weightOffsetMap.getOrDefault(weight, 0);
            if (offset >= fullCount) {
                if (batch >= weightSum) {
                    batch = 0;
                    weightOffsetMap.clear();
                }
                continue;
            }
            int index = offset++ % size;
            weightOffsetMap.put(weight, offset);
            batch++;
            return list.get(index);
        }
        throw new NullPointerException("Node list empty");
    }
}

2. 示例测试

同样这里以四个元素的集合为例，通过上述带权轮询 1000 次，可以看到最终输出的访问频次正好与节点权重相一致。

@Test
public void weightRound() {
    Map<String, Integer> nodeMap = Map.of(
        "127.0.0.1:9091", 1,
        "127.0.0.2:9092", 2,
        "127.0.0.3:9093", 2,
        "127.0.0.3:9094", 1
    );
    // Fill data
    List<String> list = new ArrayList<>();
    BasicRound.fill(nodeMap);
    // Simulation
    for (int i = 0; i < 1000; i++) {
        list.add(WeightRound.roundWight());
    }
    Map<String, Long> count = list.stream().collect(Collectors.groupingBy(p -> p, Collectors.counting()));
    // {
    //      127.0.0.1:9094=167, 
    //      127.0.0.1:9093=334, 
    //      127.0.0.1:9092=333, 
    //      127.0.0.1:9091=166
    // }
    System.out.println("Weight Round: " + count);
}