负载均衡算法（待续）

2023-02-26 16:30:56

轮询算法

据史料记载，乾隆一生妃嫔就有42人，还不算大明湖畔的夏雨荷等在下江南时候留下的情。

假设在某个时期内，皇阿玛最宠幸的有令妃、娴妃、高贵妃、纯妃四位。那普通的轮询算法怎么去选择呢？我们先定义一个妃子集合如下：

/**
 * *所有妃子集合
 */
public static final List<String> PRINCESS_LIST = Arrays.asList("令妃", "娴妃", "高贵妃", "纯妃");

然后从列表中轮询侍寝的妃子，用一个变量index去记录轮询的位置。

// 记录循环的位置
private static Integer index = 0;

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        System.out.println(getPrincess());
    }
}

private static String getPrincess() {
    // 超过数组大小需要归零（每次获取前判断，防止配置变化导致索引越界）
    if (index >= PrincessConfig.PRINCESS_LIST.size()) {
        index = 0;
    }

    String princess = PrincessConfig.PRINCESS_LIST.get(index);

    index++;

    return princess;
}

输出结果就不贴出来了。该算法的特点就是简单、简单、简单！但是也存在很大缺点！如果皇帝更宠爱令妃，想让她侍寝的概率更高呢？那就需要用到下面的加权轮询算法！

加权轮询算法

加权轮询就是可以主观的给每个妃子设置一个喜好值（权重值），以控制被选中的概率，因此我们需要定义如下的配置：

/**
 * *所有妃子集合
 */
public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {
    {
        put("令妃", 5);
        put("娴妃", 1);
        put("高贵妃", 3);
        put("纯妃", 2);
    }
};

　　这里的配置就不再是简单的一个集合，每个妃子都对应了一个权重值，那轮询的时候怎么根据这个值去提高被选中的概率呢？下面我们来讲三种比较常见的实现。

加权轮询实现一

我们的思路是把这个map的key（妃子）根据权重值转存到一个list中，然后再去轮询这个list，如果权重值为5，那就在list中添加5条相同的记录！然后我们去遍历这个list，这样权重值越高，在list中出现的概率就越高，被轮询中的概率也就越高！

// 记录循环的位置
private static Integer index = 0;

public static void main(String[] args) {
    for (int i = 0; i < 11; i++) {
        System.out.println(getPrincess1());
    }
}

private static String getPrincess1() {

    // 遍历map放入到list中
    List<String> princessList = new ArrayList<String>();
    for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
        int weight = PrincessConfig.PRINCESS_MAP.get(princess);
        // 根据权重值重复放入到一个list中
        for (int i = 0; i < weight; i++) {
            princessList.add(princess);
        }
    }

    if (index >= princessList.size()) {
        index = 0;
    }
    String princess = princessList.get(index);

    index++;

    return princess;
}

输出结果如下

该加权轮询算法比较简单，比较容易实现。但是也有个问题，我们配置的权重值是5、1、3、2，那我们是不是也可以配置成50、10、30、20呢？那按照上面的方式，我们是不是就需要把同样的元素往list里面放几百个呢？这显然是比较不合理且耗内存的！

加权轮询实现二

基于上面的算法存在问题，我们考虑用类似占比的方式来处理。比如我们配置的权重值为50、10、30、20，那在横坐标上表示就是0_____50_60__80__110。我们还是用一个index去记录轮询的位置，如果index在0_{50之间就代表第一个妃子被选中，如果在50}60之间就代表第二个妃子被选中......我们看具体代码实现！

// 记录循环的位置
private static Integer indexInteger = 0;

public static void main(String[] args) {
    for (int i = 0; i < 11; i++) {
        System.out.println(getPrincess2());
    }
}

private static String getPrincess2() {
    //记录总权重值
    int totalWeight = 0;
    for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
        int weight = PrincessConfig.PRINCESS_MAP.get(princess);
        totalWeight += weight;
    }

    // 归零
    if (indexInteger >= totalWeight) {
        indexInteger = 0;
    }

    int index = indexInteger;
    String result = null;
    for (String princess : PrincessConfig.PRINCESS_MAP.keySet()) {
        int weight = PrincessConfig.PRINCESS_MAP.get(princess);

        // 落在当前区间 直接返回
        if (index < weight) {

            result = princess;
            break;
        }

        // 没有落在当前区间 继续循环
        index = index - weight;

    }

    indexInteger++;
    return result;
}

输出结果与上面的方法一毛一样：

该加权轮询算法略复杂于第一种，但是这两种实现都存在的共同问题就是，按照我们目前的配置去轮询会连续5次令妃、再1次娴妃、再3次高贵妃......连续5次！就算皇阿玛再喜欢令妃，怕是令妃也有点吃不消~用计算机术语说也就是负载不是很均衡！

加权轮询实现三（平滑加权轮询）

平滑加权轮询算法就是为了解决上面负载不均衡的情况的，该算法实现起来相对比较复杂！每个妃子不仅有一个权重值（weight），还有一个会变化的动态权重值（dynamicWeight）来辅助计算，动态权重值计算逻辑如下：

1、动态权重值dynamicWeight初始为0。

2、每次获取轮询获取目标妃子时先设置dynamicWeight=dynamicWeight+weight。

3、然后找到所有妃子中动态权重值dynamicWeight最大的一个，则为本次轮询到的目标。

4、将本次轮询到的目标的dynamicWeight设置为dynamicWeight-totalWeight(总权重值)

这样看可能会有点不是很明白，我们来做个推算，假设我们还是有如下配置（配置中只有妃子名称及对应的权重值）：

/**
 * *所有妃子集合
 */
public static final Map<String, Integer> PRINCESS_MAP = new LinkedHashMap<String, Integer>() {
    {
        put("令妃", 5);
        put("娴妃", 1);
        put("高贵妃", 3);
        put("纯妃", 2);
    }
};

码农公寓

轮询算法

加权轮询算法

加权轮询实现一

加权轮询实现二

加权轮询实现三（平滑加权轮询）

相关文章