Load Balance算法

列举几种开源框架的常用实现

Dubbo

  1. Random

    • random.nextInt(length)，

  2. 带权重Random

    • 带权重random.next(totalWeight)=offset 再获取分配invoke.getweight;offset-weight <0 当前调用者

  3. RoundRobin

    • counter++%length 余数，带权重同上

  4. least active

    • 最少活跃数，每次调用前后计数 (time)，慢的节点数值大

  5. ConsistentHashLoadBalance

    • 略。常规的一致性hash实现方式

netflix ribbon

  1. BestAvailableRule 最小并发数 ActiveRequestsCount 最少的被选中

  2. AvailabilityFilteringRule 过滤熔断的连接和Active connections(ActiveRequestsCount)超过某个阀值的 -- 简单说，过滤掉不健康的和繁忙的节点

  3. WeightedResponseTimeRule 响应时间小的根据响应时间分配一个weight，响应时间越长，weight越小，被选中的可能性越低。类似 Dubbo - least active

  4. RoundRobinRule

    • 同Dubbo RR类似

  5. RandomRule

    • 同Dubbo Random类似

  6. ZoneAvoidanceRule 网络分区

    • 如果这个 ip 区域内有一个或多个实例不可达或响应变慢，都会降低该 ip 区域内其他 ip 被选中的权重。

  7. retryRule

    • 其实就是RoundRobin策略的增强版，RoundRobin策略服务不可用时不做处理，重试策略服务不可用时会重新尝试集群中的其他节点

nginx

  1. Round Robin
  • 不带weight 类似dubbo RR
  1. 支持权重的Round Robin

  • 经典算法 s[i].cw1000/s[i+1].cw>s[i].w1000/s[i+1].w cw=cw-1

  • smooth算法 best=max-weight-idx

    • s[i].cw+=s[i].effective s[best].cw-total
    • 平滑 effective_weight 每次错误-1 选中再+1
  1. Hash 根据ip/url/url+params计算hash value
  2. Less conn 每个work less conn，如何返回多个，再round robin

LVS

  1. round robin(weight)

    • gcd公约数，cw=cw-gcd 比较s.weight >cw 选中

  2. Round robin counter++%len

  3. Less conn

    Talk is cheap，show me the code

LVS RR，基于最大公约数实现

public class LvsRoundRobinWeight implements LoadBalance{

    private static List<Node> servers = new ArrayList<Node>();
    public int idx=-1;
    public int cw = 0;
    public static int n=0;
    public static int num[]=new int[3];
    public static int gcd = 0;
    static {
        servers.add(new Node(5,"a",5));
        servers.add(new Node(2,"b",2));
        servers.add(new Node(3,"c",3));
        n = servers.size();
        for (int i=0;i<n;i++) {
            num[i] = servers.get(i).getWeight();
        }
        gcd = getGCD(num, n);
    }
    @Override
    public int getPeerIndex() {
        while (true){
            idx = (idx + 1) % n;
            if(idx==0){
                cw = cw - gcd;
                if(cw<=0){
                    cw = getMax();
                    if(cw==0){
                        return -1;
                    }
                }
            }
            if(servers.get(idx).getCurrent_weight()>=cw){
                return idx;
            }
        }
    }

    private static int getMax(){
        int max = 0;
        for (int i = 0; i < servers.size(); i++) {
            int temp=servers.get(i).getCurrent_weight();
            if(temp>max){
                max=temp;
            }
        }
        return max;
    }

    private static int getGCD(int[] num,int n){
        if (n == 1)
            return num[n - 1];
        return gcd(num[n-1],getGCD(num,n-1));
    }

    private static int gcd(int a,int b){
        if (b == 0){
            return a;
        }else{
            return gcd(b, a%b);
        }
    }

    public static void main(String[] args) {

        LvsRoundRobinWeight lvsRoundRobinWeight = new LvsRoundRobinWeight();
        for (int i = 0; i < 10; i++) {
            int result = lvsRoundRobinWeight.getPeerIndex();
            lvsRoundRobinWeight.idx = result;
            System.out.println(servers.get(result));
        }

    }
}

Nginx RR 实现，支持权重

/**
 * https://github.com/yaoweibin/nginx_tcp_proxy_module/blob/master/ngx_tcp_upstream_round_robin.c
 */
public class NginxRoundRobinWeight implements LoadBalance {
    private static List<Node> servers = new ArrayList<Node>();
    static {
        servers.add(new Node(5,"a",5));
        servers.add(new Node(2,"b",2));
        servers.add(new Node(1,"c",1));
    }
    @Override
    public int getPeerIndex() {
        int n = 0;
        for(;;) {//must return
            for (int i = 0; i < servers.size(); i++) {
                Node node = servers.get(i);
                if (node.getCurrent_weight() <= 0) {
                    continue;
                }
                n = i;
                while (i < servers.size()-1) {
                    i++;
                    if (servers.get(i).getCurrent_weight() <= 0) {
                        continue;
                    }

                    if (servers.get(n).getCurrent_weight() * 1000 / servers.get(i).getCurrent_weight()
                            > servers.get(n).getWeight() * 1000 / servers.get(i).getWeight()) {
                        return n;
                    }

                    n = i;
                }
                return n;
            }
            //recover weight
            for (int i = 0; i < servers.size(); i++) {
                servers.get(i).setCurrent_weight(servers.get(i).getWeight());
            }
        }
    }

    public static void main(String[] args) {
        NginxRoundRobinWeight weight = new NginxRoundRobinWeight();
        for (int i = 0; i < 8; i++) {
            int idx = weight.getPeerIndex();
            Node node1 = servers.get(idx);
            node1.setCurrent_weight(node1.getCurrent_weight() - 1);
            System.out.println(node1.toString());
        }
    }
}

Nginx RR smooth实现

public class NginxRoundRobinSmooth implements LoadBalance {
    private static List<Node> servers = new ArrayList<Node>();
    static {
        servers.add(new Node(5,"a"));
        servers.add(new Node(1,"b"));
        servers.add(new Node(1,"c"));
    }
    @Override
    public int getPeerIndex() {
        int best = getMax();
        int total = 0;
        for (int i = 0; i < servers.size(); i++) {
            Node server = servers.get(i);
            server.setCurrent_weight(server.getCurrent_weight() + server.getEffective_weight());
            total = getTotal();
            if (server.getCurrent_weight() > servers.get(best).getCurrent_weight()) {
                best = i;
            }
        }
        servers.get(best).setCurrent_weight(servers.get(best).getCurrent_weight() - total);
        return best;
    }

    private static int getTotal(){
        int total = 0;
        for (int i = 0; i < servers.size(); i++) {
            total += servers.get(i).getEffective_weight();
        }
        return total;
    }

    private static int getMax(){
        int max = 0;
        int idx = 0;
        for (int i = 0; i < servers.size(); i++) {
            int temp=servers.get(i).getEffective_weight();
            if(temp>max){
                max=temp;
                idx = i;
            }
        }
        return idx;
    }

    public static void main(String[] args) {
        NginxRoundRobinSmooth smooth = new NginxRoundRobinSmooth();
        for (int j = 0; j < 14; j++) {
            int best = smooth.getPeerIndex();
            System.out.println(servers.get(best));
        }
    }
}