精华内容
下载资源
问答
  • 算法说明目的: 一致性hash算法的目的, 就是为了解决2个问题:hash算法中损毁节点对应的请求失败;有节点损毁后, 请求落点不均匀问题;2. 示例说明一个hash环, 模拟节点数为1024个, 实际可用的节点有8个(比如线上实际的...

    作者:niewj

    来源:SegmentFault 思否


    1. 算法说明

    目的: 一致性hash算法的目的, 就是为了解决2个问题:

    1. hash算法中损毁节点对应的请求失败;
    2. 有节点损毁后, 请求落点不均匀问题;


    2. 示例说明

    一个hash环, 模拟节点数为1024个, 实际可用的节点有8个(比如线上实际的ip服务节点), 1024个模拟节点跟8个ip节点有均匀的映射关系;

    我们模拟的环上有 1024 个虚拟节点, 真实可用的节点(可以想象为线上实际集群有8个可用ip供存储)


    使用一致性hash使用方法:

    1. 环上的虚拟节点跟所有真实节点之间有个映射关系
      (1024个节点跟8个节点的映射, 用的是除8取模的对应关系,

      例如: 0, 8, 16, 24 都对应到node_0;
      1, 7, 15, 23都映射到node_1);
    2. 发一个请求字符串, 我们计算出hash值, 除 1024 取模;
    3. 将取模结果, 先映射到虚拟节点环上的点, 比如 "hello"的hashcode/1024 = 210
    4. 查询虚拟环和真实节点映射关系, 210对应的真实节点为 node_2; 于是, "hello" 就落到节点 node_2 上;
    5. 我们可以调用 com.niewj.dsalg.ConsistentHashMock#dropBadNode("node_2") 来删除 node_2节点;
    6. 删除 node_2 后, "hello"应该落在 211 上, 对应到环的真实映射, 是 node_3 , 于是, "hello"的请求就落到 node_3;
      这, 就是 一致性hash算法!


    3. 算法代码示例:

    package com.niewj.dsalg;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.TreeMap;/** * Created by niewj on 2020/8/14 18:40 */public class ConsistentHashMock {    /**     * 假设我们一共初始化有8个节点(可以是ip, 就理解为ip吧);     * 把 1024个虚拟节点跟 8个资源节点相对应     */    public static Map realNodeMap = new HashMap<>();    public static int V_NODES = 1024; // 假设我们的环上有1024个虚拟节点    static TreeMap virtualNodeMap = new TreeMap<>();    private static final Integer REAL_NODE_COUNT = 8;    static {        realNodeMap.put(0, "node_0");        realNodeMap.put(1, "node_1");        realNodeMap.put(2, "node_2");        realNodeMap.put(3, "node_3");        realNodeMap.put(4, "node_4");        realNodeMap.put(5, "node_5");        realNodeMap.put(6, "node_6");        realNodeMap.put(7, "node_7");        for (Integer i = 0; i < V_NODES; i++) {            // 每个虚拟节点跟其取模的余数的 nodeMap 中的key相对应;            // 下面删除虚拟节点的时候, 就可以根据取模规则来删除 TreeMap中的节点了;            virtualNodeMap.put(i, realNodeMap.get(i % REAL_NODE_COUNT));        }    }    /**     * 输入一个id     *     * @param value     * @return     */    public static String getRealServerNode(String value) {        // 1. 传递来一个字符串, 得到它的hash值        Integer vnode = value.hashCode() % 1024;        // 2.找到对应节点最近的key的节点值        String realNode = virtualNodeMap.ceilingEntry(vnode).getValue();        return realNode;    }    /**     * 模拟删掉一个物理可用资源节点, 其他资源可以返回其他节点     *     * @param nodeName     */    public static void dropBadNode(String nodeName) {        int nodek = -1;        // 1. 遍历 nodeMap 找到故障节点 nodeName对应的key;        for (Map.Entry entry : realNodeMap.entrySet()) {            if (nodeName.equalsIgnoreCase(entry.getValue())) {                nodek = entry.getKey();                break;            }        }        if (nodek == -1) {            System.err.println(nodeName + "在真实资源节点中无法找到, 放弃删除虚拟节点!");            return;        }        // 2. 根据故障节点的 key, 对应删除所有 chMap中的虚拟节点        Iterator> iter = virtualNodeMap.entrySet().iterator();        while (iter.hasNext()) {            Map.Entry entry = iter.next();            int key = entry.getKey();            String value = entry.getValue();            if (key % REAL_NODE_COUNT == nodek) {                System.out.println("删除节点虚拟节点: [" + key + " = " + value + "]");                iter.remove();            }        }    }    public static void main(String[] args) {        // 1. 一个字符串请求(比如请求字符串存储到8个节点中的某个实际节点);        String requestValue = "hello";        // 2. 打印虚拟节点和真实节点的对应关系;        System.out.println(virtualNodeMap);        // 3. 核心: 传入请求信息, 返回实际调用的节点信息        System.out.println(getRealServerNode(requestValue));        // 4. 删除某个虚拟节点后        System.out.println("==========删除 node_2 之后: ================");        dropBadNode("node_2");        System.out.println("===============删除之后的虚拟节点map: ===========");        System.out.println(virtualNodeMap);        System.out.println("==============删除之后, 获取节点的真正node节点对应者: ");        System.out.println(getRealServerNode(requestValue));    }}

    - END -

    40ad2ecfb1b6e8d8cc9bff153cc12466.png

    3a7624aeb7793a61d635867190231711.gif

    展开全文
  • 一致性hash-java实现treemap

    千次阅读 2018-09-13 09:59:32
    这就是一致性hash一致性hash 算法都是将 value 映射到一个 32 位的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,当有数据过来按顺时针找到离他最近...

     

    2017年02月12日 13:27:45 mae4a8cs 阅读数:478

    把不同号段的数据储存在不同的机器上,以用来分散压力。假如我们有一百万个QQ号,十台机器,,如何划分呢?

    最简单粗暴的方法是用QQ号直接对10求余,结果为0-9 分别对应上面的十台机器。比如QQ号为 23900 的用户在编号为0的机器 23901的用户在编号为1的机器,以此类推。那么问题来了,现在QQ用户急剧上升 由一百万涨到了五百万,显然10台机器已经无能为力

    了,于是我们扩充到25台。这个时候我们发现以前的数据全乱了。完蛋!只能跑路了……

    Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

      单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

    所以在保证合理分散的情况下,我们还是是可拓展的。这就是一致性hash,一致性hash 算法都是将 value 映射到一个 32 位的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,当有数据过来按顺时针找到离他最近的一个点,这个点,就是我要的节点机器。如下图:

    hash("192.168.128.670") ---->A //根据服务器IP hash出去生成节点

    hash("192.168.148.670") ---->C //根据服务器IP hash出去生成节点

     

    hash("81288812") ----> k1 //根据QQ号 hash出去生成值 ----->顺时针找到机器

     

    hash("8121243812") ----> k4 //根据QQ号 hash出去生成值 ----->顺时针找到机器

     

    这样当有新的机器加进来,旧的机器去掉,影响的也是一小部分的数据。这样看似比较完美了,,但假如其中一个节点B数据激增,挂了,所有数据会倒到C--->C也扛不住了---->所有数据会倒到D ……以此类推,最终全挂了!整个世界清静了!!!

    显然,这种方式因为数据的不平均导致服务挂了。所以我们的一致性hash还需要具有平衡性。

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

    为解决平衡性,一致性hash引入了虚拟节点”的概念。“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。这样我们如果有25台服务器,每台虚拟成10个,就有250个虚拟节点。这样就保证了每个节点的负载不会太大,压力均摊,有事大家一起扛!!!

    hash("192.168.128.670#36kr01") ---->A //根据服务器IP hash出去生成节点

    hash("192.168.128.670#36kr02") ---->B //根据服务器IP hash出去生成节点

    hash("192.168.128.670#36kr03") ---->B //根据服务器IP hash出去生成节点

    ……

    final 虚拟节点+murmurhash成了我们的解决方案:

    class Shard<S> { // S类封装了机器节点的信息 ,如name、password、ip、port等
    
        private TreeMap<Long, S> nodes; // 虚拟节点
        private List<S> shards; // 真实机器节点
        private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数
    
        public Shard(List<S> shards) {
            super();
            this.shards = shards;
            init();
        }
    
        private void init() { // 初始化一致性hash环
            nodes = new TreeMap<Long, S>();
            for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点
                final S shardInfo = shards.get(i);
    
                for (int n = 0; n < NODE_NUM; n++)
                    // 一个真实机器节点关联NODE_NUM个虚拟节点
                    nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo);
    
            }
        }
    
        public S getShardInfo(String key) {
            SortedMap<Long, S> tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点
            if (tail.size() == 0) {
                return nodes.get(nodes.firstKey());
            }
            return tail.get(tail.firstKey()); // 返回该虚拟节点对应的真实机器节点的信息
        }
    
        /**
         *  MurMurHash算法,是非加密HASH算法,性能很高,
         *  比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
         *  等HASH算法要快很多,而且据说这个算法的碰撞率很低.
         *  http://murmurhash.googlepages.com/
         */
        private Long hash(String key) {
    
            ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
            int seed = 0x1234ABCD;
    
            ByteOrder byteOrder = buf.order();
            buf.order(ByteOrder.LITTLE_ENDIAN);
    
            long m = 0xc6a4a7935bd1e995L;
            int r = 47;
    
            long h = seed ^ (buf.remaining() * m);
    
            long k;
            while (buf.remaining() >= 8) {
                k = buf.getLong();
    
                k *= m;
                k ^= k >>> r;
                k *= m;
    
                h ^= k;
                h *= m;
            }
    
            if (buf.remaining() > 0) {
                ByteBuffer finish = ByteBuffer.allocate(8).order(
                        ByteOrder.LITTLE_ENDIAN);
                // for big-endian version, do this first:
                // finish.position(8-buf.remaining());
                finish.put(buf).rewind();
                h ^= finish.getLong();
                h *= m;
            }
    
            h ^= h >>> r;
            h *= m;
            h ^= h >>> r;
    
            buf.order(byteOrder);
            return h;
        }
    
    }
    展开全文
  • 关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。 算法的具体原理这里再次贴上...

    对一致性Hash算法,Java代码实现的深入研究

    一致性哈希算法原理分析及实现

    一致性Hash算法

    关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。

    算法的具体原理这里再次贴上:

    先构造一个长度为232的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 232-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 232-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。

    这种算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

    当然,万事不可能十全十美,一致性Hash算法比普通的余数Hash算法更具有伸缩性,但是同时其算法实现也更为复杂,本文就来研究一下,如何利用Java代码实现一致性Hash算法。在开始之前,先对一致性Hash算法中的几个核心问题进行一些探究。

     

    数据结构的选取

    一致性Hash算法最先要考虑的一个问题是:构造出一个长度为232的整数环,根据节点名称的Hash值将服务器节点放置在这个Hash环上。

    那么,整数环应该使用何种数据结构,才能使得运行时的时间复杂度最低?首先说明一点,关于时间复杂度,常见的时间复杂度与时间效率的关系有如下的经验规则:

    O(1) < O(log2N) < O(n) < O(N * log2N) < O(N2) < O(N3) < 2N < 3N < N!

    一般来说,前四个效率比较高,中间两个差强人意,后三个比较差(只要N比较大,这个算法就动不了了)。OK,继续前面的话题,应该如何选取数据结构,我认为有以下几种可行的解决方案。

    1、解决方案一:排序+List

    我想到的第一种思路是:算出所有待加入数据结构的节点名称的Hash值放入一个数组中,然后使用某种排序算法将其从小到大进行排序,最后将排序后的数据放入List中,采用List而不是数组是为了结点的扩展考虑。

    之后,待路由的结点,只需要在List中找到第一个Hash值比它大的服务器节点就可以了,比如服务器节点的Hash值是[0,2,4,6,8,10],带路由的结点是7,只需要找到第一个比7大的整数,也就是8,就是我们最终需要路由过去的服务器节点。

    如果暂时不考虑前面的排序,那么这种解决方案的时间复杂度:

    (1)最好的情况是第一次就找到,时间复杂度为O(1)

    (2)最坏的情况是最后一次才找到,时间复杂度为O(N)

    平均下来时间复杂度为O(0.5N+0.5),忽略首项系数和常数,时间复杂度为O(N)。

    但是如果考虑到之前的排序,我在网上找了张图,提供了各种排序算法的时间复杂度:

    看得出来,排序算法要么稳定但是时间复杂度高、要么时间复杂度低但不稳定,看起来最好的归并排序法的时间复杂度仍然有O(N * logN),稍微耗费性能了一些。

    2、解决方案二:遍历+List

    既然排序操作比较耗性能,那么能不能不排序?可以的,所以进一步的,有了第二种解决方案。

    解决方案使用List不变,不过可以采用遍历的方式:

    (1)服务器节点不排序,其Hash值全部直接放入一个List中

    (2)带路由的节点,算出其Hash值,由于指明了"顺时针",因此遍历List,比待路由的节点Hash值大的算出差值并记录,比待路由节点Hash值小的忽略

    (3)算出所有的差值之后,最小的那个,就是最终需要路由过去的节点

    在这个算法中,看一下时间复杂度:

    1、最好情况是只有一个服务器节点的Hash值大于带路由结点的Hash值,其时间复杂度是O(N)+O(1)=O(N+1),忽略常数项,即O(N)

    2、最坏情况是所有服务器节点的Hash值都大于带路由结点的Hash值,其时间复杂度是O(N)+O(N)=O(2N),忽略首项系数,即O(N)

    所以,总的时间复杂度就是O(N)。其实算法还能更改进一些:给一个位置变量X,如果新的差值比原差值小,X替换为新的位置,否则X不变。这样遍历就减少了一轮,不过经过改进后的算法时间复杂度仍为O(N)。

    总而言之,这个解决方案和解决方案一相比,总体来看,似乎更好了一些。

    3、解决方案三:二叉查找树

    抛开List这种数据结构,另一种数据结构则是使用二叉查找树。对于树不是很清楚的朋友可以简单看一下这篇文章树形结构

    当然我们不能简单地使用二叉查找树,因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等,这里使用红黑树,选用红黑树的原因有两点:

    1、红黑树主要的作用是用于存储有序的数据,这其实和第一种解决方案的思路又不谋而合了,但是它的效率非常高

    2、JDK里面提供了红黑树的代码实现TreeMap和TreeSet

    另外,以TreeMap为例,TreeMap本身提供了一个tailMap(K fromKey)方法,支持从红黑树中查找比fromKey大的值的集合,但并不需要遍历整个数据结构。

    使用红黑树,可以使得查找的时间复杂度降低为O(logN),比上面两种解决方案,效率大大提升。

    为了验证这个说法,我做了一次测试,从大量数据中查找第一个大于其中间值的那个数据,比如10000数据就找第一个大于5000的数据(模拟平均的情况)。看一下O(N)时间复杂度和O(logN)时间复杂度运行效率的对比:

      50000 100000 500000 1000000 4000000
    ArrayList 1ms 1ms 4ms 4ms 5ms
    LinkedList 4ms 7ms 11ms 13ms 17ms
    TreeMap 0ms 0ms 0ms 0ms 0ms

    因为再大就内存溢出了,所以只测试到4000000数据。可以看到,数据查找的效率,TreeMap是完胜的,其实再增大数据测试也是一样的,红黑树的数据结构决定了任何一个大于N的最小数据,它都只需要几次至几十次查找就可以查到。

    当然,明确一点,有利必有弊,根据我另外一次测试得到的结论是,为了维护红黑树,数据插入效率TreeMap在三种数据结构里面是最差的,且插入要慢上5~10倍

     

    Hash值重新计算

    服务器节点我们肯定用字符串来表示,比如"192.168.1.1"、"192.168.1.2",根据字符串得到其Hash值,那么另外一个重要的问题就是Hash值要重新计算,这个问题是我在测试String的hashCode()方法的时候发现的,不妨来看一下为什么要重新计算Hash值:

    复制代码
    /**
     * String的hashCode()方法运算结果查看
     * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
     *
     */
    public class StringHashCodeTest
    {
        public static void main(String[] args)
        {
            System.out.println("192.168.0.0:111的哈希值:" + "192.168.0.0:1111".hashCode());
            System.out.println("192.168.0.1:111的哈希值:" + "192.168.0.1:1111".hashCode());
            System.out.println("192.168.0.2:111的哈希值:" + "192.168.0.2:1111".hashCode());
            System.out.println("192.168.0.3:111的哈希值:" + "192.168.0.3:1111".hashCode());
            System.out.println("192.168.0.4:111的哈希值:" + "192.168.0.4:1111".hashCode());
        }
    }
    复制代码

    我们在做集群的时候,集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为:

    192.168.0.0:111的哈希值:1845870087
    192.168.0.1:111的哈希值:1874499238
    192.168.0.2:111的哈希值:1903128389
    192.168.0.3:111的哈希值:1931757540
    192.168.0.4:111的哈希值:1960386691

    这个就问题大了,[0,232-1]的区间之中,5个HashCode值却只分布在这么小小的一个区间,什么概念?[0,232-1]中有4294967296个数字,而我们的区间只有114516604,从概率学上讲这将导致97%待路由的服务器都被路由到"192.168.0.0"这个集群点上,简直是糟糕透了!

    另外还有一个不好的地方:规定的区间是非负数,String的hashCode()方法却会产生负数(不信用"192.168.1.0:1111"试试看就知道了)。不过这个问题好解决,取绝对值就是一种解决的办法。

    综上,String重写的hashCode()方法在一致性Hash算法中没有任何实用价值,得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。

     

    一致性Hash算法实现版本1:不带虚拟节点

    使用一致性Hash算法,尽管增强了系统的伸缩性,但是也有可能导致负载分布不均匀,解决办法就是使用虚拟节点代替真实节点,第一个代码版本,先来个简单的,不带虚拟节点。

    下面来看一下不带虚拟节点的一致性Hash算法的Java代码实现:

    import java.util.SortedMap;

    import java.util.TreeMap;

     

    /**

     * 不带虚拟节点的一致性Hash算法

     * 

     * @author 五月的仓颉http://www.cnblogs.com/xrq730/

     *

     */

    public class ConsistentHashingWithoutVirtualNode {

    /**

    * 待添加入Hash环的服务器列表

    */

    private static String[] servers = { "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" };

     

    /**

    * key表示服务器的hash值,value表示服务器的名称

    */

    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();

     

    /**

    * 程序初始化,将所有的服务器放入sortedMap中

    */

    static {

    for (int i = 0; i < servers.length; i++) {

    int hash = getHash(servers[i]);

    System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);

    sortedMap.put(hash, servers[i]);

    }

    System.out.println();

    }

     

    /**

    * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别

    */

    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;

    }

     

    /**

    * 得到应当路由到的结点

    */

    private static String getServer(String node) {

    // 得到带路由的结点的Hash值

    int hash = getHash(node);

    // 得到大于该Hash值的所有Map

    SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);

    if (null == subMap || subMap.size() <= 0) {

    subMap = sortedMap;

    }

    // 第一个Key就是顺时针过去离node最近的那个结点

    Integer i = subMap.firstKey();

    // 返回对应的服务器名称

    return subMap.get(i);

    }

     

    public static void main(String[] args) {

    String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333", "222.213.13.23:2323", "223.213.34.67:2341" };

    for (int i = 0; i < nodes.length; i++)

    System.out

    .println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");

    }

    }

    可以运行一下看一下结果:

    复制代码
    [192.168.0.0:111]加入集合中, 其Hash值为575774686
    [192.168.0.1:111]加入集合中, 其Hash值为8518713
    [192.168.0.2:111]加入集合中, 其Hash值为1361847097
    [192.168.0.3:111]加入集合中, 其Hash值为1171828661
    [192.168.0.4:111]加入集合中, 其Hash值为1764547046
    
    [127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
    [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111]
    [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.4:111]
    复制代码

    看到经过FNV1_32_HASH算法重新计算过后的Hash值,就比原来String的hashCode()方法好多了。从运行结果来看,也没有问题,三个点路由到的都是顺时针离他们Hash值最近的那台服务器上。

     

    使用虚拟节点来改善一致性Hash算法

    上面的一致性Hash算法实现,可以在很大程度上解决很多分布式环境下不好的路由算法导致系统伸缩性差的问题,但是会带来另外一个问题:负载不均。

    比如说有Hash环上有A、B、C三个服务器节点,分别有100个请求会被路由到相应服务器上。现在在A与B之间增加了一个节点D,这导致了原来会路由到B上的部分节点被路由到了D上,这样A、C上被路由到的请求明显多于B、D上的,原来三个服务器节点上均衡的负载被打破了。某种程度上来说,这失去了负载均衡的意义,因为负载均衡的目的本身就是为了使得目标服务器均分所有的请求

    解决这个问题的办法是引入虚拟节点,其工作原理是:将一个物理节点拆分为多个虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式,就可以有效地解决增加或减少节点时候的负载不均衡的问题。

    至于一个物理节点应该拆分为多少虚拟节点,下面可以先看一张图:

    横轴表示需要为每台福利服务器扩展的虚拟节点倍数,纵轴表示的是实际物理服务器数。可以看出,物理服务器很少,需要更大的虚拟节点;反之物理服务器比较多,虚拟节点就可以少一些。比如有10台物理服务器,那么差不多需要为每台服务器增加100~200个虚拟节点才可以达到真正的负载均衡。

     

    一致性Hash算法实现版本2:带虚拟节点

    在理解了使用虚拟节点来改善一致性Hash算法的理论基础之后,就可以尝试开发代码了。编程方面需要考虑的问题是:

    1、一个真实结点如何对应成为多个虚拟节点?

    2、虚拟节点找到后如何还原为真实结点?

    这两个问题其实有很多解决办法,我这里使用了一种简单的办法,给每个真实结点后面根据虚拟节点加上后缀再取Hash值,比如"192.168.0.0:111"就把它变成"192.168.0.0:111&&VN0"到"192.168.0.0:111&&VN4",VN就是Virtual Node的缩写,还原的时候只需要从头截取字符串到"&&"的位置就可以了。

    下面来看一下带虚拟节点的一致性Hash算法的Java代码实现:

    import java.util.LinkedList;

    import java.util.List;

    import java.util.SortedMap;

    import java.util.TreeMap;

     

    /**

     * 带虚拟节点的一致性Hash算法

     * 

     * @author 五月的仓颉 http://www.cnblogs.com/xrq730/

     */

    public class ConsistentHashingWithVirtualNode {

    /**

    * 待添加入Hash环的服务器列表

    */

    private static String[] servers = { "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" };

     

    /**

    * 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好

    */

    private static List<String> realNodes = new LinkedList<String>();

     

    /**

    * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称

    */

    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();

     

    /**

    * 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点

    */

    private static final int VIRTUAL_NODES = 5;

     

    static {

    // 先把原始的服务器添加到真实结点列表中

    for (int i = 0; i < servers.length; i++)

    realNodes.add(servers[i]);

     

    // 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高

    for (String str : realNodes) {

    for (int i = 0; i < VIRTUAL_NODES; i++) {

    String virtualNodeName = str + "&&VN" + String.valueOf(i);

    int hash = getHash(virtualNodeName);

    System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);

    virtualNodes.put(hash, virtualNodeName);

    }

    }

    System.out.println();

    }

     

    /**

    * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别

    */

    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;

    }

     

    /**

    * 得到应当路由到的结点

    */

    private static String getServer(String node) {

    // 得到带路由的结点的Hash值

    int hash = getHash(node);

    // 得到大于该Hash值的所有Map

    SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);

    //自己加的,考虑到subMap中没有数据,就取virtualNodes中的第一个值

    if (null == subMap || subMap.size() <= 0) {

    subMap = virtualNodes;

    }

    //

    // 第一个Key就是顺时针过去离node最近的那个结点

    Integer i = subMap.firstKey();

    // 返回对应的虚拟节点名称,这里字符串稍微截取一下

    String virtualNode = subMap.get(i);

    return virtualNode.substring(0, virtualNode.indexOf("&&"));

    }

     

    public static void main(String[] args) {

    String[] nodes = { "127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333", "223.213.34.67:2341" };

    for (int i = 0; i < nodes.length; i++)

    System.out

    .println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");

    }

    }

    关注一下运行结果:

    复制代码
    虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075
    虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081
    虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370
    虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914
    虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629
    虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288
    虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309
    虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528
    虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861
    虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551
    虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222
    虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840
    虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480
    虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074
    虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136
    虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251
    虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739
    虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370
    虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500
    虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780
    虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010
    虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390
    虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117
    虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803
    虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678
    
    [127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
    [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.0:111]
    [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.2:111]
    复制代码

    从代码运行结果看,每个点路由到的服务器都是Hash值顺时针离它最近的那个服务器节点,没有任何问题。

    通过采取虚拟节点的方法,一个真实结点不再固定在Hash换上的某个点,而是大量地分布在整个Hash环上,这样即使上线、下线服务器,也不会造成整体的负载不均衡。

     

    转载于:https://www.cnblogs.com/fanguangdexiaoyuer/p/6549306.html

    展开全文
  • } private void init() { // 初始化一致性hash环 nodes = new TreeMap(); for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点 final S shardInfo = shards.get(i); for (int n = 0...

    把不同号段的数据储存在不同的机器上,以用来分散压力。假如我们有一百万个QQ号,十台机器,,如何划分呢?

    最简单粗暴的方法是用QQ号直接对10求余,结果为0-9 分别对应上面的十台机器。比如QQ号为 23900 的用户在编号为0的机器 23901的用户在编号为1的机器,以此类推。那么问题来了,现在QQ用户急剧上升 由一百万涨到了五百万,显然10台机器已经无能为力

    了,于是我们扩充到25台。这个时候我们发现以前的数据全乱了。完蛋!只能跑路了……

    Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

    所以在保证合理分散的情况下,我们还是是可拓展的。这就是一致性hash,一致性hash 算法都是将 value 映射到一个 32 位的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,当有数据过来按顺时针找到离他最近的一个点,这个点,就是我要的节点机器。如下图:

    a50e0346f82d581effa6db803eae6625.pnghash("192.168.128.670") ---->A //根据服务器IP hash出去生成节点

    hash("192.168.148.670") ---->C //根据服务器IP hash出去生成节点

    hash("81288812") ----> k1 //根据QQ号 hash出去生成值 ----->顺时针找到机器

    hash("8121243812") ----> k4 //根据QQ号 hash出去生成值 ----->顺时针找到机器

    这样当有新的机器加进来,旧的机器去掉,影响的也是一小部分的数据。这样看似比较完美了,,但假如其中一个节点B数据激增,挂了,所有数据会倒到C--->C也扛不住了---->所有数据会倒到D ……以此类推,最终全挂了!整个世界清静了!!!

    显然,这种方式因为数据的不平均导致服务挂了。所以我们的一致性hash还需要具有平衡性。

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

    为解决平衡性,一致性hash引入了虚拟节点”的概念。“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。这样我们如果有25台服务器,每台虚拟成10个,就有250个虚拟节点。这样就保证了每个节点的负载不会太大,压力均摊,有事大家一起扛!!!

    hash("192.168.128.670#36kr01") ---->A //根据服务器IP hash出去生成节点

    hash("192.168.128.670#36kr02") ---->B //根据服务器IP hash出去生成节点

    hash("192.168.128.670#36kr03") ---->B //根据服务器IP hash出去生成节点

    ……

    final 虚拟节点+murmurhash成了我们的解决方案:

    class Shard { // S类封装了机器节点的信息 ,如name、password、ip、port等

    private TreeMap nodes; // 虚拟节点

    private List shards; // 真实机器节点

    private final int NODE_NUM = 100; // 每个机器节点关联的虚拟节点个数

    public Shard(List shards) {

    super();

    this.shards = shards;

    init();

    }

    private void init() { // 初始化一致性hash环

    nodes = new TreeMap();

    for (int i = 0; i != shards.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点

    final S shardInfo = shards.get(i);

    for (int n = 0; n < NODE_NUM; n++)

    // 一个真实机器节点关联NODE_NUM个虚拟节点

    nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo);

    }

    }

    public S getShardInfo(String key) {

    SortedMap tail = nodes.tailMap(hash(key)); // 沿环的顺时针找到一个虚拟节点

    if (tail.size() == 0) {

    return nodes.get(nodes.firstKey());

    }

    return tail.get(tail.firstKey()); // 返回该虚拟节点对应的真实机器节点的信息

    }

    /**

    * MurMurHash算法,是非加密HASH算法,性能很高,

    * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)

    * 等HASH算法要快很多,而且据说这个算法的碰撞率很低.

    * http://murmurhash.googlepages.com/

    */

    private Long hash(String key) {

    ByteBuffer buf = ByteBuffer.wrap(key.getBytes());

    int seed = 0x1234ABCD;

    ByteOrder byteOrder = buf.order();

    buf.order(ByteOrder.LITTLE_ENDIAN);

    long m = 0xc6a4a7935bd1e995L;

    int r = 47;

    long h = seed ^ (buf.remaining() * m);

    long k;

    while (buf.remaining() >= 8) {

    k = buf.getLong();

    k *= m;

    k ^= k >>> r;

    k *= m;

    h ^= k;

    h *= m;

    }

    if (buf.remaining() > 0) {

    ByteBuffer finish = ByteBuffer.allocate(8).order(

    ByteOrder.LITTLE_ENDIAN);

    // for big-endian version, do this first:

    // finish.position(8-buf.remaining());

    finish.put(buf).rewind();

    h ^= finish.getLong();

    h *= m;

    }

    h ^= h >>> r;

    h *= m;

    h ^= h >>> r;

    buf.order(byteOrder);

    return h;

    }

    }

    展开全文
  • 一致性Hash

    2016-02-23 20:35:08
    理解一致性哈希算法(consistent hashing) 关于TreeMap一致性hash
  • 一致性hash算法结构图 分表分库结构图 可进行循环冗余存储,顺时针存储到下一个物理节点(非虚拟节点)package com.haiziwang.platform.kmcsms.route.algorithm;import java.util.Collection;.../*** 一致性Hash算...
  • 一致性hash算法java版本简单实现package com.java4all.grouth.consistent;import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;import org.slf4j.Logger;...
  • 一致性hash算法

    2019-02-21 11:22:28
    一致性hash算法Java demo  package com.wang.hash; import java.util.LinkedList; import java.util.SortedMap; import java.util.TreeMap; /** * 一致性hash算法 */ public class ...
  • package ...import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;import org.slf4j.Logger;import org.slf4j.LoggerFactory;/***...
  • 一致性hash java实现

    2018-09-11 12:53:43
    之前讲了 一致性hash算法的原理,现在撸代码。 环的数据结构,可能首先想到的是常用的List。一致性hash需要找比当前元素大的节点,那么list要么排好序然后比较找到对应的节点,要么是不排序直接遍历算差值。显然在...
  • package ...import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;import org.slf4j.Logger;import org.slf4j.LoggerFactory;/***...
  • 一致性hash算法java实现

    千次阅读 热门讨论 2020-12-09 17:29:51
    一致性hash算法java版本简单实现 package com.java4all.grouth.consistent; import java.util.LinkedList; import java.util.List; import java.util.SortedMap; import java.util.TreeMap; import org.slf4j....
  • import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;/*** 一致性Hash算法* 算法详解:http://blog.csdn.net/sparkliang/article/details/5279393* 算法实现:https:...
  • 一致性hash算法java版本简单实现package com.java4all.grouth.consistent;import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;import org.slf4j.Logger;...
  • import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Collection; import java.util.SortedMap;... * 一致性Hash算法 * * @param &lt...
  • Java代码实现了一致性Hash算法,并加入虚拟节点。,具体代码为: package com.baijob.commonTools; import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; /** * 一致...
  • Jedis中使用一致性Hash解决均衡问题 知识点1: SortedMap, TreeMap 参考:https://www.cnblogs.com/jpfss/p/9772818.html,https://www.jianshu.com/p/e11fe1760a3d 知识点2: 一致性hash概念 参考:...
  • 一致性HASH算法

    2015-08-06 13:11:22
    [code="java"] import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHash { ...
  • 一致性Hash算法

    2018-07-20 18:31:00
    import java.util.Collection;import java.util.HashSet;import java.util.Iterator;import java.util.Set;import java.util.SortedMap;import java.util....import java.util.TreeMap;import java.util.Tree...
  • 一致性hash之java实现

    2012-05-16 10:11:28
    一致性hash的原理 把server和key hash到同一个空间,然后同方向找最近的即可。 import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHash&...
  • import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;/*** 一致性Hash算法* 算法详解:http://blog.csdn.net/sparkliang/article/details/5279393* 算法实现:https:...
  • Java代码public class ConsistentHash {private final HashFunction hashFunction;private final int ...private final SortedMap circle = new TreeMap();public ConsistentHash(HashFunction hashFunc...

空空如也

空空如也

1 2 3 4
收藏数 73
精华内容 29
关键字:

treemap一致性hash