一致性hash算法有哪些重要性

本篇内容介绍了“一致性hash算法有哪些重要性”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

专注于为中小企业提供网站建设、做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业红山免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了成百上千家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。

一致性hash算法是个啥?相信很多老牌程序员都不太清楚,为什么?因为它主要用于负载均衡,解决数据相对一致性问题的。一般公司搞个哈希、轮询、权重都了不得了,用什么一致性哈希算法,但一致性哈希算法是个啥,有点追求的产品经理还是要了解的。

nginx里面有个哈希算法,这个哈希算法的使用场景大概是,我的某一个客户端要一直连到特定后端服务器上,不许变,变了就会出错,如此可以解决我们实际场景中一些问题,比如:session问题,redis缓存数据存储等等。

如果用于缓存场景,普通哈希算法逻辑大概是这样的,如果有10台缓存服务器,客户端 1数据存储在1节点(1模除10)客户端2数据存储在2节点上......客户端11存储在1节点上,以此类推。但忽然有一天,有一台机器老化了,你的总服务器个数变成了9,可想而知,再次做取模运算,可能原来的数据已经不在,可能你会说,没关系啊,数据库里面还有一份呢?重新加载下就Ok啦,是的(没见识),如果对于上亿级流量场景,可能就会发生缓存击穿问题,导致一连串的崩溃。

这时就轮到一致性hash算法上场了,其实一致性hash算法思想和实现非常简单,每每想到一致性哈希算法,大家都应该想到这个环(不知道怎么回事,每当我看到这个环,总是想到张衡的地震仪)。

实现该算法的大致思路如下:

1、构造一个哈希环

2、把服务器对应的节点映射到哈希环上

3、客户端请求,顺时针找到该哈希环上的服务器节点

如此,足矣!这么简单的逻辑,用代码实现下吧,首先需要构造一个哈希环,哈希环看起来比较抽象,如何实现?找下规律发现哈希环上放的是一个KV数据对,key是哈希,value是对应的服务器,而且是顺序的,自然就想到了SortedMap。

SortedMap sortedMap = new TreeMap(); 但哈希函数如何实现呢?这个就比较有意思了,这里不过多介绍哈希函数的生成过程,反正你应该选择一个分布相对均匀、区间尽可能大的哈希函数,建议采用ketama或者FNV1_32,FNV代码实现如下:

        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;
    }

那么现在如何把服务器节点映射哈希环中呢?且看如下代码实现:

 for (int i = 0; i < servers.length; i++) {
            int hash = FNVHash(servers[i]);
            sortedMap.put(hash, servers[i]);
}```

当然客户端请求过来只需要计算客户端的哈希值,顺时针旋转找到对应的服务端节点即可,如下为代码实现:

```private static String getServer(String key) {
    //得到该key的hash值  
    int hash = FNVHash(key);
    //得到大于该Hash值的所有Map  
    SortedMap subMap = sortedMap.tailMap(hash);
    if (subMap.isEmpty()) {
        //如果没有比该key的hash值大的,则从第一个node开始  
        Integer i = sortedMap.firstKey();
        //返回对应的服务器  
        return sortedMap.get(i);
    } else {
        //第一个Key就是顺时针过去离node最近的那个结点  
        Integer i = subMap.firstKey();
        //返回对应的服务器  
        return subMap.get(i);
    }
}

总结来说,假设有k个节点,数据的取值范围就是[0, n],我们把[0,n]划分为m个区间,m远远大于k,那么每个机器就负责m/k个区间。这样如果有将几个小区间的数据迁移到新区间上,既保证了数据的一致性,也保证了数据的均衡。简单来说,先根据机器IP生成哈希值,当客户端数据key进来时,进行哈希操作,落到圆环中的某一点,顺时针旋转落到第一个节点上。

这个时候你可能会发现一个问题,如果说节点过于稀疏,那么很可能所有数据都落到一个节点上,导致数据倾斜,这个时候可以考虑虚拟节点。虚拟节点的添加实现也非常简单,大致思路是构造哈希环的过程中使用虚拟节点,取出虚拟节点,最后找到对应的真实节点即可。

“一致性hash算法有哪些重要性”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!


文章名称:一致性hash算法有哪些重要性
分享URL:http://myzitong.com/article/jojjso.html