欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

负载均衡--加权随机算法(Weight Random)

程序员文章站 2022-03-26 17:10:20
加权随机法根据服务器的配置和系统的负载,分配不同的权重,按照权重随机请求后端服务器。一、算法描述假设有 N 台服务器 S = {S0, S1, S2, …, Sn},权重为 W = {W0, W1, W2, …, Wn},权重之和为 weightSum, 服务器列表为 serverList,算法可以描述为:1、初始化 serverList,将 W0 个 S0 加入至serverList,将 W1 个 S1 加入至serverList,依据此规则,将所有的服务器加入至 serverList 中;2...

加权随机法根据服务器的配置和系统的负载,分配不同的权重,按照权重随机请求后端服务器。

一、算法描述

假设有 N 台服务器 S = {S0, S1, S2, …, Sn},权重为 W = {W0, W1, W2, …, Wn},权重之和为 weightSum, 服务器列表为 serverList,算法可以描述为:
1、初始化 serverList,将 W0 个 S0 加入至serverList,将 W1 个 S1 加入至serverList,依据此规则,将所有的服务器加入至 serverList 中;
2、通过随机函数生成 0 到 weightSum 之间的任意整数,将该数字作为索引,从 serverList 中获取对应的服务器;

假定我们现在有如下四台服务器:

服务器地址 权重
192.168.1.1 1
192.168.1.2 2
192.168.1.3 3
192.168.1.4 4

初始化服务列表后, serverList 如下:

服务器地址 序号
192.168.1.1 1
192.168.1.2 2
192.168.1.2 3
192.168.1.3 4
192.168.1.3 5
192.168.1.3 6
192.168.1.4 7
192.168.1.4 8
192.168.1.4 9
192.168.1.4 10

首先,根据权重的不同,向 serverList 添加相应个数的服务器;然后,通过随机算法,随机获取访问的服务器。

二、java代码实现

package com.yidian.wemedia.civilization.schedulealgothrim;

import com.google.common.collect.SortedMultiset;
import com.google.common.collect.TreeMultiset;
import org.apache.commons.collections4.CollectionUtils;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

class Server implements Serializable {
    private static final long serialVersionUID = 7246747589293111189L;

    private String server;
    private Integer weight;
    private String description;

    public Server(String server, String description, Integer weight) {
        this.server = server;
        this.description = description;
        this.weight = weight;
    }

    public String getDescription() {
        return description;
    }

    public void setDescription(String description) {
        this.description = description;
    }


    public String getServer() {
        return server;
    }

    public void setServer(String server) {
        this.server = server;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }
}

class ServerManager {
    public static Map<String, Server> serverMap = new TreeMap<>();

    static {
        serverMap.put("192.168.1.1", new Server("192.168.1.1", "第1台server", 1));
        serverMap.put("192.168.1.2", new Server("192.168.1.2", "第2台server", 2));
        serverMap.put("192.168.1.3", new Server("192.168.1.3", "第3台server", 3));
        serverMap.put("192.168.1.4", new Server("192.168.1.4", "第4台server", 4));
        serverMap.put("192.168.1.5", new Server("192.168.1.5", "第4台server", 0));
    }
}

class RandomBalance {
    private static final Random RANDOM = new Random();
    private static ArrayList<String> middleServerList;
    private static Integer weightSum = 0;

    public static String getServer() {
        if (CollectionUtils.isEmpty(middleServerList)) {
            ArrayList<String> serverList = new ArrayList<>();
            Integer tempWeightSum = 0;

            Set<String> serverSet = ServerManager.serverMap.keySet();
            for (String server : serverSet) {
                Integer weight = ServerManager.serverMap.get(server).getWeight();
                tempWeightSum += weight;
                for (int i = 0; i < weight; i++) {
                    serverList.add(server);
                }
            }
            middleServerList = serverList;
            weightSum = tempWeightSum;
        }

        return middleServerList.get(RANDOM.nextInt(weightSum));
    }
}

public class WeightRandomScheduleTest {
    public static void main(String[] args) {
        SortedMultiset<String> serverSet = TreeMultiset.create();
        for (int i = 0; i < 100; i++) {
            String server = RandomBalance.getServer();
            Server curServer = ServerManager.serverMap.get(server);
            System.out.println(server + ", " + curServer.getDescription());
            serverSet.add(server, 1);
        }

        ServerManager.serverMap.forEach((key, value)->{
            System.out.println(key + ", count:" + serverSet.count(key));
        });
    }
}

运行结果如下所示:

192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.2, 第2台server
192.168.1.1, 第1台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.2, 第2台server
192.168.1.1, 第1台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.3, 第3台server
192.168.1.3, 第3台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.3, 第3台server
192.168.1.2, 第2台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.2, 第2台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.1, 第1台server
192.168.1.2, 第2台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.3, 第3台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.1, 第1台server
192.168.1.2, 第2台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.4, 第4台server
192.168.1.2, 第2台server
192.168.1.3, 第3台server
192.168.1.1, 第1台server
192.168.1.3, 第3台server
192.168.1.1, count:10
192.168.1.2, count:20
192.168.1.3, count:28
192.168.1.4, count:42
192.168.1.5, count:0

说明:
1、首先,使用 Random 对象随机生成 [0, weightSum) 的整数;然后,通过索引获取到服务器。weightSum其实就是serverList.size()。
2、在多线程的情况下,若线程A修改 ServerManager.serverMap 的值,则线程B无法即时拿到线程A修改后的值,可能会导致请求错误,需要调用方进行容错处理。
3、从宏观的角度看,访问量越大,负载越均衡。从微观的角度看,局部并不那么均衡。

本文地址:https://blog.csdn.net/chinawangfei/article/details/109646579