均衡加权轮询算法

最近闲来无事打算写一个接口，不过我这个接口要实现的功能也是要通过请求第三方接口实现的，因为第三方接口比较多（要花钱的，不给白嫖），于是就本着不浪费的想法，打算把这些接口全用了。
说好就开干，本来打算直接用最简单的轮询算法的，也就是这次用这个，下次用另一个。后面突然想到第三方接口的额度不一致，有些接口的额度比较多有些比较少，如果按最简单的轮询的话会导致部分第三方接口额度耗尽部分又还有额度，于是就打算使用加权轮询算法。
加权轮询算法其实也就是加了个权重，根据权重来选择对应的接口。说来也简单，只要根据权重把对应的接口放一个数组里依次拿就行，但是这样也会有个问题，也就是有部分请求一直在请求其中一个接口，导致其他接口不会被请求，也就是如果有 3 个接口 a，b，c。权重分别为 4,2,1 的话，那 a 接口先是会被请求 4 次，然后才轮到 b 接口请求 2 次。这样多多少少有点不妥。后面了解到 Nginx 的负载均衡用的是均衡加权轮询算法，也算是完美符合我的要求。
网上查了下资料，均衡加权轮询算法的原理如下：

当前所有节点初始值为 0
所有节点的当前权重值加上设定的权重值
从所有节点中取出当前权重值最大的那个作为命中节点
命中节点的当前权重值减去总权重值作为新的当前权重值
所有节点的当前权重值加上设定权重值作为新的当前权重值

例如节点 A、B、C 三个节点的权重值分别为 4、2、1，其演算步骤如下表：

步骤	选择前当前权重值	命中节点	选择后当前权重
1	{ 4, 2, 1 }	A	{ -3, 2, 1 }
2	{ 1, 4, 2 }	B	{ 1,-3, 2 }
3	{ 5,-1, 3 }	A	{ -2,-1, 3 }
4	{ 2, 1, 4 }	C	{ 2, 1,-3 }
5	{ 6, 3,-2 }	A	{ -1, 3,-2 }
6	{ 3, 5,-1 }	B	{ 3,-2,-1 }
7	{ 7, 0, 0 }	A	{ 0, 0, 0 }

解析：
在步骤一中，当前权重原本为 0:0:0，先加上设定的权重，也就是 4:2:1，变成了 4:2:1，从 4:2:1 中取权重最大的，也就是命中了节点 A，然后节点 A 的权重减去总权重 4+2+1=7，于是变成了-3:2:1。
到步骤二，当前权重为-3:2:1，加上设定的权重 4:2:1，变成了 1:4:2，取出权重最大的节点 B，节点 B 再减去总权重后变成 1:-3:2。
以此类推，最终演算成上表。
由上面的表格可以发现，三个节点的命中符合 4:2:1，而且权重大的节点也不会一直被命中，而是各个节点均衡的被命中，由此循环，一直会保持4:2:1的权重。
原理明白了，接下来就是上代码了。
1、首先我在配置文件中写入 url 配置：

ys:
  urls:
    - url: aaa
      weight: 4
      currentWeight: 4
    - url: bbb
      weight: 2
      currentWeight: 2
    - url: ccc
      weight: 1
      currentWeight: 1

其中 url 是第三方接口，weight 是设定的权重，currentWeight 是当前权重。
2、编写配置类：

@Data
@Configuration
@ConfigurationProperties(prefix = "ys")
public class YsConfig {

    private List<Urls> urls;

}

@Data
public class Urls {

    private String url;

    private Integer weight;

    private Integer currentWeight;

}

3、接下来就是写方法了

@RequestMapping("/api")
@RestController
public class FileController {

    private final YsConfig ysConfig;

    private List<Urls> urlList;
    private Integer totalWeight;

    public FileController(YsConfig ysConfig) {
        // 初始化第三方接口配置
        this.ysConfig = ysConfig;
        urlList = ysConfig.getUrls();
        // 求出总权重
        totalWeight = urlList.stream().mapToInt(Urls::getWeight).sum();
    }

    @GetMapping("/url")
    public String url() {
        return getUrl().getUrl();
    }

    private Urls getUrl() {
        // 获取当前权重最大的url
        Urls max = urlList.stream().max(Comparator.comparingInt(Urls::getCurrentWeight)).get();
        // 拿到最大权重的url后，将其当前权重减去总权重
        max.setCurrentWeight(max.getCurrentWeight() - totalWeight);
        // 当前权重加上设定权重
        for (Urls url : urlList) {
            url.setCurrentWeight(url.getCurrentWeight() + url.getWeight());
        }
        // 返回最大权重的url
        return max;
    }
}

运行之后我们可以发现其结果是符合表格的数据的。
但是如果直接操作这个公共的urlList 的话，并发量一大就会有问题，我们可以测试一下。

@RequestMapping("/api")
@RestController
public class FileController {


    private final YsConfig ysConfig;

    private List<Urls> urlList;
    private Integer totalWeight;

    // 这里使用CopyOnWriteArrayList，可以保证线程安全，保证结果不出错，并且效率高
    private CopyOnWriteArrayList<Urls> list = new CopyOnWriteArrayList <>();

    public FileController(YsConfig ysConfig) {
        this.ysConfig = ysConfig;
        urlList = ysConfig.getUrls();
        totalWeight = urlList.stream().mapToInt(Urls::getWeight).sum();
    }

    @GetMapping("/url")
    public String url() throws InterruptedException {
        // 先清除list的数据
        list.clear();
        // 使用CountDownLatch计数
        CountDownLatch countDownLatch = new CountDownLatch(10);
        // 启动10个线程，每个线程循环70次，获取url，并将url添加到list中
        for (int i = 0; i < 10; i++) {
            // 这里是使用了java21的虚拟线程，没有的可以直接用线程代替
            Thread.ofVirtual().start(() -> {
                for (int j = 0; j < 70; j++) {
                    Urls url = getUrl();
                    list.add(url);
                }
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
        int a = 0;
        int b = 0;
        int c = 0;
        System.out.println("总数：" + list.size());
        // 统计每个url的次数
        for (Urls url : list) {
            if (url.getUrl().equals("aaa")) {
                a++;
            }
            if (url.getUrl().equals("bbb")) {
                b++;
            }
            if (url.getUrl().equals("ccc")) {
                c++;
            }
        }
        System.out.println("aaa：" + a);
        System.out.println("bbb：" + b);
        System.out.println("ccc：" + c);

        return "aaa";
    }

    private Urls getUrl() {
        // 获取当前权重最大的url
        Urls max = urlList.stream().max(Comparator.comparingInt(Urls::getCurrentWeight)).get();
        // 拿到最大权重的url后，将其当前权重减去总权重
        max.setCurrentWeight(max.getCurrentWeight() - totalWeight);
        // 当前权重加上设定权重
        for (Urls url : urlList) {
            url.setCurrentWeight(url.getCurrentWeight() + url.getWeight());
        }
        // 返回最大权重的url
        return max;
    }
}

请求之后，我们发现实际结果并没有按照 4:2:1 的权重，这就是高并发下的问题。

总数：700
aaa：400
bbb：195
ccc：105
总数：700
aaa：399
bbb：203
ccc：98

那我们要如何解决呢，我这里是使用了AtomicInteger 这个类来修饰currentWeight。
在 Urls 类中修改currentWeight

@Data
public class Urls {

    private String url;

    private Integer weight;

    private AtomicInteger currentWeight;

    // 这里需要手动写一下set方法，因为数字类型不能直接赋值到AtomicInteger
    public void setCurrentWeight(Integer currentWeight) {
        this.currentWeight = new AtomicInteger(currentWeight);
    }
}

同时修改一下 getUrl 方法

private Urls getUrl() {
    // 这里修改了currentWeight的获取方式
    Urls max = urlList.stream().max(Comparator.comparingInt(x -> x.getCurrentWeight().get())).get();
    // 这里通过addAndGet方法去减掉总权重
    max.getCurrentWeight().addAndGet(-totalWeight);
    // 当前权重加上设定权重
    for (Urls url : urlList) {
        // 这里设置当前权重加上设定权重
        url.getCurrentWeight().addAndGet(url.getWeight());
    }
    // 返回最大权重的url
    return max;
}