负载均衡中的一致性hash算法

作者: 小吴可是全村的希望 | 来源:发表于2019-06-09 00:51 被阅读0次

hash简介

说到底，他是一种hash算法，那什么是hash算法？
hash算法是一种散列算法，常用的比如MD5。抽象来说，他是将任意长度的输入X，经过hash算法后，变成固定长度的输出Y（输出Y称为散列值），多个X可能对应同一个Y（hash碰撞，概率极小极小极小，MD5的碰撞概率为2/2的64次方），且从Y不能反推出X，对X的任意修改，都将导致输出的Y完全不一样。
基于以上的这些特性，hash算法可以有以下这些应用场景：

用hash算法对网站的登陆密码使用散列值保存（利用的是不可反推这一特性，这样即便淘宝的数据库被盗了，谁也不会知道你到底在淘宝买了些什么...东西）
对比两个文件是否完全一样，假如要对比的txt文件中有上万的字符，如何一个一个去作对比，效率很差，直接对比文件的散列值是否一致即可知道文件是否一致（利用的是输出的散列值是固定长度）
负载均衡算法
作为负载均衡算法时，输入X是客户端请求的某个唯一ID或者key，hash之后的输出Y是一个一定范围内的Long类型数字，然后我们对这个Long类型的数字进行取模，取模得到的余数就是需要访问的节点唯一编号，利用取模的特性（假如集群中服务器数量为3台，那么模数是3，可以将大量的数字，映射到[0-3)这个区间段）将key均匀的映射到集群中的机器上，这样就达到了负载均衡的目的，算法公式：hash(key) % n，如下图：

image.png

最终key1 - keyn会被均匀的分布在图中的三个节点上，看似已经达到了我们想要的负载均衡的效果了，但是，当客户端请求在某一时段激增的时候（比如双十一），我们常常需要增加服务器，双十一过后，这些增加的服务器又需要下线，那么上图中的算法，就不足以支撑这种情况，假如这时候node3需要被下线，那么客户端请求对应的负载均衡算法就变成了hash(key) % 2，这时候客户端所有请求和节点之间的映射关系就全变了，许多请求会被负载均衡到"错误的"节点上去从而拿不到想要的数据（如果是缓存，那么绝大部分的获取缓存的请求都会失效，大量请求会打到DB），人为的去转移数据，那只能996.ICU网站见了。为了解决这个问题，所以，我们需要一致性hash算法

一致性hash算法原理

假设我们采用的hash算法的值空间为0-P，将0-P构建成一个hash环，如下图：

image.png

在普通的hash算法中，我们仅仅对请求唯一标识做了hash，并且它是一个线性的hash空间，而在一致性hash算法中，还会使用同样的hash算法对服务器标识做一次hash运算（一般对服务器IP或者主机名做hash运算），然后将两种hash值映射在这个hash环（java中可以用TreeMap实现）上面，如下图：

image.png

一致性hash算法具备以下特性：

客户端请求最终会落到他所在hash环的顺时针方向的第一个节点上，在上图中，key3，key14，key1024请求最终会落到node1上面，而key5，key76982，key18会落到node3上面。
当集群中删除节点nodex时，原本应该落在nodex上面的请求，会被转移到nodex顺时针的下一个节点，新增节点同理，可以看到，无论新增还是删除一个节点，受影响的都只有一个节点的数据，如下图：
image.png
image.png
以上的一致性hash算法相比较普通的hash算法有了很大的改进，但是依然存在问题，以删除节点为例，删除一个节点后，集群中大部分的请求key都会落到node2这个节点上，已经并不是"负载均衡"了。一般的hash环空间会很大，而如果当集群中节点数量不是很多的时候，节点在环上面的位置可能会挤在很小的一部分区域，这样就导致一大部分请求会落到某个节点上（数据倾斜），为了解决这个问题，一致性hash算法引入虚拟节点。

虚拟节点

对每一个服务器节点进行多次hash，将生成的hash值也分布在hash环上，这些新生成的节点称为虚拟节点。假设我们用服务器IP地址来做hash，那么可以在IP地址后面增加编号来做hash运算生成虚拟节点，增加虚拟节点后，hash环如下图：

image.png

从图中看到，没有增加虚拟节点的时候，大部分的请求会落到node2这个节点上面，导致node2节点请求压力过大，当我们增加虚拟节点后，node1，node2，node3都能均匀的接收到客户端的请求。而删除某个节点nodex的时候，原本应该落在nodex上面的请求，也会被均匀的分配给其他节点。

java实现一致性hash算法

首先我们得需要一个hash算法，hash算法有很多种，这里提供两种实现，一种基于MD5，一种基于FNV1_32_HASH（这种其实是我抄来的，哈哈哈哈~~~~）
基于MD5：

/**
     * hash 运算
     * @param value
     * @return
     */
    public Long hash(String value){
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 not supported", e);
        }
        md5.reset();
        byte[] keyBytes = null;
        try {
            keyBytes = value.getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException("Unknown string :" + value, e);
        }

        md5.update(keyBytes);
        byte[] digest = md5.digest();

        // hash code, Truncate to 32-bits
        long hashCode = ((long) (digest[3] & 0xFF) << 24)
                | ((long) (digest[2] & 0xFF) << 16)
                | ((long) (digest[1] & 0xFF) << 8)
                | (digest[0] & 0xFF);

        long truncateHashCode = hashCode & 0xffffffffL;
        return truncateHashCode;
    }

基于FNV1_32_HASH：

public class HashUtil {
    /**
     * 计算Hash值, 使用FNV1_32_HASH算法
     * @param str
     * @return
     */
    public 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;
    }
}

接下来我们实现hash环，负载均衡一般是读多写少（新增或者删除节点毕竟少数），在读多写少的情况下，我们容易想到用二叉树来实现，在java中一般直接可以用TreeMap来实现，TreeMap是由红黑树实现的，很适合作为hash环的存储结构，先实现一个没有虚拟节点的hash环：

public class ConsistentHashingWithoutVirtualNode {

    /**
     * 集群地址列表
     */
    private static String[] groups = {
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
        "192.168.0.3:111", "192.168.0.4:111"
    };

    /**
     * 用于保存Hash环上的节点
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();

    /**
     * 初始化，将所有的服务器加入Hash环中
     */
    static {
        // 使用红黑树实现，插入效率比较差，但是查找效率极高
        for (String group : groups) {
            int hash = HashUtil.getHash(group);
            System.out.println("[" + group + "] launched @ " + hash);
            sortedMap.put(hash, group);
        }
    }

    /**
     * 计算对应的请求应该落到哪一个节点上
     *
     * @param key
     * @return
     */
    private static String getServer(String key) {
        int hash = HashUtil.getHash(key);
        // 只取出所有大于该hash值的部分而不必遍历整个Tree
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，应该映射到第一个group上
            return sortedMap.get(sortedMap.firstKey());
        }
        return subMap.get(subMap.firstKey());
    }

    public static void main(String[] args) {
        // 生成随机数进行测试
        Map<String, Integer> resMap = new HashMap<>();

        for (int i = 0; i < 100000; i++) {
            Integer widgetId = (int)(Math.random() * 10000);
            String server = getServer(widgetId.toString());
            if (resMap.containsKey(server)) {
                resMap.put(server, resMap.get(server) + 1);
            } else {
                resMap.put(server, 1);
            }
        }

        resMap.forEach(
            (k, v) -> {
                System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");
            }
        );
    }
}

生成10000个随机数字进行测试，最终得到的压力分布情况如下：

[192.168.0.1:111] launched @ 8518713
[192.168.0.2:111] launched @ 1361847097
[192.168.0.3:111] launched @ 1171828661
[192.168.0.4:111] launched @ 1764547046
group 192.168.0.2:111: 8572(8.572%)
group 192.168.0.1:111: 18693(18.693%)
group 192.168.0.4:111: 17764(17.764%)
group 192.168.0.3:111: 27870(27.87%)
group 192.168.0.0:111: 27101(27.101%)

可以看到，请求分布负载不均衡，接下来我们引入虚拟节点：

public class ConsistentHashingWithVirtualNode {
    /**
     * 集群地址列表
     */
    private static String[] groups = {
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
        "192.168.0.3:111", "192.168.0.4:111"
    };

    /**
     * 真实集群列表
     */
    private static List<String> realGroups = new LinkedList<>();

    /**
     * 虚拟节点映射关系
     */
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();

    private static final int VIRTUAL_NODE_NUM = 1000;

    static {
        // 先添加真实节点列表
        realGroups.addAll(Arrays.asList(groups));

        // 将虚拟节点映射到Hash环上
        for (String realGroup: realGroups) {
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                String virtualNodeName = getVirtualNodeName(realGroup, i);
                int hash = HashUtil.getHash(virtualNodeName);
                System.out.println("[" + virtualNodeName + "] launched @ " + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
    }

    private static String getVirtualNodeName(String realName, int num) {
        return realName + "&&VN" + String.valueOf(num);
    }

    private static String getRealNodeName(String virtualName) {
        return virtualName.split("&&")[0];
    }

    private static String getServer(String key) {
        int hash = HashUtil.getHash(key);
        // 只取出所有大于该hash值的部分而不必遍历整个Tree
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNodeName;
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，应该映射到第一个group上
            virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
        }else {
            virtualNodeName = subMap.get(subMap.firstKey());
        }
        return getRealNodeName(virtualNodeName);
    }

    public static void main(String[] args) {
        // 生成随机数进行测试
        Map<String, Integer> resMap = new HashMap<>();

        for (int i = 0; i < 100000; i++) {
            Integer widgetId = i;
            String group = getServer(widgetId.toString());
            if (resMap.containsKey(group)) {
                resMap.put(group, resMap.get(group) + 1);
            } else {
                resMap.put(group, 1);
            }
        }

        resMap.forEach(
            (k, v) -> {
                System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");
            }
        );
    }
}

在上面的代码中，我给每个节点增加了1000个虚拟节点，测试结果如下：

group 192.168.0.2:111: 18354(18.354%)
group 192.168.0.1:111: 20062(20.062%)
group 192.168.0.4:111: 20749(20.749%)
group 192.168.0.3:111: 20116(20.116%)
group 192.168.0.0:111: 20719(20.719%)

可以看到负载已经基本均衡了。我们试一下删除和新增节点的情况：

private static void refreshHashCircle() {
    // 当集群变动时，刷新hash环，其余的集群在hash环上的位置不会发生变动
    virtualNodes.clear();
    for (String realGroup: realGroups) {
        for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
            String virtualNodeName = getVirtualNodeName(realGroup, i);
            int hash = HashUtil.getHash(virtualNodeName);
            System.out.println("[" + virtualNodeName + "] launched @ " + hash);
            virtualNodes.put(hash, virtualNodeName);
        }
    }
}
private static void addGroup(String identifier) {
    realGroups.add(identifier);
    refreshHashCircle();
}

private static void removeGroup(String identifier) {
    int i = 0;
    for (String group:realGroups) {
        if (group.equals(identifier)) {
            realGroups.remove(i);
        }
        i++;
    }
    refreshHashCircle();
}

测试结果如下：

running the normal test.
group 192.168.0.2:111: 19144(19.144%)
group 192.168.0.1:111: 20244(20.244%)
group 192.168.0.4:111: 20923(20.923%)
group 192.168.0.3:111: 19811(19.811%)
group 192.168.0.0:111: 19878(19.878%)
removed a group, run test again.
group 192.168.0.2:111: 23409(23.409%)
group 192.168.0.1:111: 25628(25.628%)
group 192.168.0.4:111: 25583(25.583%)
group 192.168.0.0:111: 25380(25.38%)
add a group, run test again.
group 192.168.0.2:111: 15524(15.524%)
group 192.168.0.7:111: 16928(16.928%)
group 192.168.0.1:111: 16888(16.888%)
group 192.168.0.4:111: 16965(16.965%)
group 192.168.0.3:111: 16768(16.768%)
group 192.168.0.0:111: 16927(16.927%)

我们可以看到删除和新增节点，一致性hash算法依然能保持良好的负载均衡。

redis中的一致性hash算法

未完，待续。。。。。睡觉！

负载均衡中的一致性hash算法

hash简介

一致性hash算法原理

虚拟节点

java实现一致性hash算法

redis中的一致性hash算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读