一致性哈希实现负载均衡

快乐de馒头 2020-02-11

一致性哈希实现负载均衡

1 为什么需要哈希算法

解决同一个用户访问服务器是,访问的是不同的服务器的问题

场景:集群造成的session没有同步

当一个用户访问服务器A的时候,该台服务器A会保存这台服务器的session,但是当下次再访问的时候,被负载均衡算法可能算到了不同的服务器B,服务器B中没有用户的session,会要求用户再次登录。

解决:

  1. 加入redis,将session存到redis中
  2. Tomcat同步session
  3. 一致性哈希算法

2 什么是一致性哈希算法

服务器集群接收到一次请求调用时,可以根据请求的信息,比如客户端的ip地址,或请求路径与请求参数等信息进行哈希,可以得出一个哈希值,特点是对于相同的ip地址,或请求路径和请求参数哈希出来的值是一样的,只要能再增加一个算法,能够把这个哈希值映射成一个服务端ip地址,就可以使用相同的请求(相同的ip地址,或请求路径和请求参数)落到同一服务器上。

因为客户端发起的请求是无穷无尽的(客户端地址不同,请求参数不同等等),所以对于的哈希值也是无穷大的,所以我们不能把所有的哈希值都进行映射到服务端ip上,所有这里需要用到哈希环

一致性哈希实现负载均衡

3 虚拟节点

  1. 解决一个服务器挂掉造成的服务不均匀问题
  2. 使得哈希环更加平滑

当时当一台服务器挂掉的话,会造成服务器服务不均匀的情况

一致性哈希实现负载均衡

会发现,ip3和ip1直接的范围是比较大的,会有更多的请求落到ip1上,这是“不公平”,解决这个问题需要加入虚拟节点,比如:

一致性哈希实现负载均衡

其中,ip2-1,ip3-1就是虚拟节点,并不能处理节点,而是等同于对应的服务器。
实际上,这只是处理这种不均衡性的一种思路,实际上就算哈希环本身是均衡的,你也可以增加更多的虚拟节点来使得这个环更加的平滑

一致性哈希实现负载均衡

上面的哈希环更加的散列,平滑

只需要找到大于hashcode的以一个虚拟节点即可

由于哈希环上的点是有序的,那么采用的数据结构是TreeMap

4 代码实现

public class ServerIps {

    public static final List<String> LIST = (List<String>) Arrays.asList(
            "192.168.0.1",
            "192.168.0.2",
            "192.168.0.3",
            "192.168.0.4",
            "192.168.0.5",
            "192.168.0.6",
            "192.168.0.7",
            "192.168.0.8",
            "192.168.0.9",
            "192.168.0.10"
            );

}

======================================

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {

    private static TreeMap<Integer, String> virtualNodes = new TreeMap<>();
    private static final int VIRTUAL_NODES = 160;

    static {
        for(String ip: ServerIps.LIST) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(ip+i);
                virtualNodes.put(hash, ip);
            }

        }
    }

    private static String getServer(String client) {
        int hash = getHash(client);

        //大于hash,virtualNodes的子树的firstkey
        //tailMap,能获得大于等于hash值的一棵子红黑树
        SortedMap subMap = virtualNodes.tailMap(hash);
        Integer firstKey = null;

        if(subMap == null) {
            firstKey = virtualNodes.firstKey();
        } else {
            firstKey = (Integer) subMap.firstKey();
        }

        return virtualNodes.get(firstKey);
    }

    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for(int i = 0; i < str.length(); i++) 
            hash = (hash ^ str.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if(hash < 0)
            hash = Math.abs(hash);
        return hash;
    }

    public static void main(String[] args) {

        for (int i = 0; i < 12; i++) {
            System.out.println(getServer("client"+i));
        }
    }

}

5 最小活跃数

由于服务的时间并不是固定,如果平均分配服务器有的时候并不合理

比如:
有3个消息,分别请求了A、B、C三台服务器,处理的时间依次为3s、2s、1s,当1s后有一个新的请求过来,按道理说应该A服务器来服务,但是C台服务器已经空闲了,所有这样的分配方式有时候并不合理。

解决:
采用最小活跃数,哪台机器服务最少,用哪台机器,当都大致相等的时候可以根据前面的随机、轮询等。

6 算法的魅力

  • 将程序“复杂化”,提升程序效率到极致

相关推荐