精华内容
下载资源
问答
  • 一致性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算法(hash环)

    千次阅读 2017-12-01 15:37:07
    一致性Hash(DHT)性质 考虑到分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来,如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务,这是值得考虑的,尤其实在设计分布式缓存系统...

    一致性Hash(DHT)性质

    考虑到分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来,如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务,这是值得考虑的,尤其实在设计分布式缓存系统时,如果某台服务器失效,对于整个系统来说如果不采用合适的算法来保证一致性,那么缓存于系统中的所有数据都可能会失效(即由于系统节点数目变少,客户端在请求某一对象时需要重新计算其hash值(通常与系统中的节点数目有关),由于hash值已经改变,所以很可能找不到保存该对象的服务器节点),因此一致性hash就显得至关重要,良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面:

    • 平衡性(Balance)

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

    • 单调性(Monotonicity)

    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求,如最简单的线性哈希:x = (ax + b) mod (P),在上式中,P表示全部缓冲的大小。不难看出,当缓冲大小发生变化时(从P1到P2),原来所有的哈希结果均会发生变化,从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时,所有的映射关系需要在系统内全部更新。而在P2P系统内,缓冲的变化等价于Peer加入或退出系统,这一情况在P2P系统中会频繁发生,因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。假设有100台redis data服务器,一份数据101进来的时候,以散列公式hash(i)&100,计算所存放的服务器,假设hash(i) = i,那么数据被散列到标号为1的服务器,然后这个时候服务器新增了一台,然后散列公式为hash(i)%101,这个时候请求访问数据101的时候,被分配至0号服务器,但是其实这个时候数据是在1号服务器的。如果是持久化存储的,我们可以让服务器集群对数据进行重新散列,进行数据迁移,然后进行恢复,但是这个时候就意味着每次增减服务器的时候,集群就需要大量的通信,进行数据迁移,这个开销是非常大的。如果只是缓存,那么缓存就都失效了。

    关键问题在于,服务器数量变动的时候,要能够保证旧的数据能够按照老的算法,计算到数据所在的服务器,而新的数据能够按照新的散列算法,计算出数据所在的服务器。

    • 分散性(Spread)

    在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    • 负载(Load)

    负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    • 平滑性(Smoothness)

    平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

    原理

    一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

     

    整个空间按顺时针方向组织。0和232-1在零点中方向重合。

    下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下:

    如果服务器数量不多且个数相对稳定,我们也可以手动设置这些服务器的位置,如设A在2^30-1位置,B在2^31-1位置,C在3*2^30-1位置,D在2^32-1位置,则hash值为0~2^30-1的数据存储在A中,hash值为2^30-1~2^31-1的数据存储在B中,以此类推

    定位数据存储在哪台服务器的方法为:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。可以为这些服务器维护一条二分查找树,定位服务器的过程就是在二分查找树中找刚好比其大的节点。

    例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:

     

    根据一致性哈希算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

    下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

    下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:

     

    此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X 。一般的,在一致性哈希算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

    综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

    另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器,其环分布如下,

     

     

    此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希(可以用原节点key+"##xxxk"作为每个虚拟节点的key,然后求hashcode),每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:

    数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

    虚拟节点还能防止雪崩效应,如上图所示,如果不存在热点数据的时候,当前每台机器的承受的压力是M/2(假设每台机器的最高负载能力为M),原本是不会有问题的,但是,这个时候A服务器由于有热点数据挂了,然后A的数据迁移至B,导致B所需要承受的压力变为M(还不考虑热点数据访问的压力),所以B是必挂的,然后C至少需要承受1.5M的压力。。。。然后大家一起挂。。。

    所以我们通过上面可以看到,之所以会大家一起挂,原因在于如果一台机器挂了,那么它的压力全部被分配到一台机器上,导致雪崩。虚拟节点可以把压力均匀地分配到各个节点,如下图,如果A服务器挂了,访问压力会分配至C2和D1,也就是C和D服务器,而不是像前面,全部被分配到B上,这一看,一个节点出现故障,会影响多个节点,这似乎违反了前面说到的单调性,但受影响的节点相对总节点数来说很少,比如总节点有1000个,当某个节点出现故障时,10个节点受影响,这相对全部都受影响来说好很多了。

    一致性hash算法在分布式环境中应用的很广,只要是涉及到分布式存储的负载均衡问题,一致性hash都是很好的解决的方案。

    实现

    数据结构的选取

     

    一致性Hash算法最先要考虑的一个问题是:构造出一个长度为232的整数环,根据节点名称的Hash值将服务器节点放置在这个Hash环上。那么,整数环应该使用何种数据结构,才能使得定位数据所属服务器的时间复杂度最低?

    1、最简单的实现是采用一个有序的list,每次从第0个元素开始查找,直到找到第一个比数据的hash值大的节点,则该数据属于该节点对应的服务器。时间复杂度为O(n)。

    2、采用二叉查找树,时间复杂度为O(log n)

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

     

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

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

    以TreeMap为例,TreeMap本身提供了一个tailMap(K fromKey)方法,支持从红黑树中查找比fromKey大的值的集合,但并不需要遍历整个数据结构,然后再从集合中取第一个即可,更方便的TreeMap提供了higherKey(k key),可以直接获取第一个比参数key大的对象,这里要注意的是,如果tailMap.isEmpty()==true或higherkey返回null,代表数据在环的末端,这时应该取tailMap中最小的元素作为存储服务器,即tailMap.firstKey()。

    Hash值重新计算

    需要计算Hash值的有:服务器(包括虚拟节点)、存储数据。两者用同一个hash算法即可,当然也可以用不同的hash算法。

    jdk字符串的hashcode源码如下:

        public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }

    这里有两个问题:

    1、如果字符串比较短,hashcode的值就比较小,加入存储数据的key都比较小,hashcode的值就不能撑满[0,2^32-1]

    2、hashcode返回的是一个int类型,int类型的正数最大为2^31,只是2^32的一半,而且还有负数的情况,当然,负数可以通过取绝对值来解决,hash环大小取2^31也足够大了,所以,这一点不是问题。

    关键问题是第一点,String重写的hashCode()方法扩散速度比较慢,如果key比较长,倒还能勉强使用,当然,如果我们的hash环比较小,String提供的hashcode方法也能满足我们的需求,例如,哈希环为[0,999],那么我们可以通过绝对值然后mod(1000)来求位置。一般来说,普通大小的集群,hash环也没必要搞这么大(个人观点)。

    如果就是要用2^32大小的hash环,得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。

    为了能使用int类型,可以适当地把hash环大小调整为2^31

        /**
        * 使用FNV1_32_HASH算法计算服务器的Hash值
        */
        private static int getHash(String str)
        {
              final int p = 16777619;
              int hash = (int)2166136261L;
              for (int i = 0; i )
                   hash = (hash ^ str.charAt(i)) * p;
              hash += hash ;
              hash ^= hash >> 7;
              hash += hash ;
              hash ^= hash >> 17;
              hash += hash ;
     
        // 如果算出来的值为负数则取其绝对值
        if (hash )
           hash = Math.abs(hash);
        return hash;
      }
    /**
         * 使用MD5算法
         * @param key
         * @return
         */
        private static long md5HashingAlg(String key) {
            MessageDigest md5 = null;
            try {
                md5 = MessageDigest.getInstance("MD5");
                md5.reset();
                md5.update(key.getBytes());
                byte[] bKey = md5.digest();
                long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF);
                return res;
            } catch (NoSuchAlgorithmException e) {
                e.printStackTrace();
            }
            return 0l;
        }
     
        /**
         * 使用FNV1hash算法
         * @param key
         * @return
         */
        private static long fnv1HashingAlg(String key) {
            final int p = 16777619;
            int hash = (int) 2166136261L;
            for (int i = 0; i < key.length(); i++)
                hash = (hash ^ key.charAt(i)) * p;
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }

    虚拟节点

    主要是如何产生虚拟节点的hash值以及它们怎么跟物理节点对应。

    加入节点A的key为keyA,我们可以循环生成若干个虚拟节点,key分别为keyA##VN0、keyA##VN1、keyA##VN2.....keyA##VNn。然后采用上面的hash算法分别求这些虚拟节点的hashcode,然后放入hash环中(即TreeMap中),定位数据所属的服务器节点时,假设返回keyA##VNk,则通过截取可以获取物理节点keyA。

     

     

    展开全文
  • 关于一致性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)时间复杂度运行效率的对比:

     5000010000050000010000004000000
    ArrayList1ms1ms4ms4ms5ms
    LinkedList4ms7ms11ms13ms17ms
    TreeMap0ms0ms0ms0ms0ms

    因为再大就内存溢出了,所以只测试到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

    展开全文
  • 图解一致性hash算法和实现

    千次阅读 2019-05-18 18:35:13
    一致性hash算法是什么? 一致性hash算法,是麻省理工学院1997年提出的一种算法,目前主要应用于分布式缓存当中。 一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。 在Memcached、Key-...

    一致性hash算法是什么?

    一致性hash算法,是麻省理工学院1997年提出的一种算法,目前主要应用于分布式缓存当中。
    一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。
    在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了一致性hash算法,可以说一致性hash算法是分布式系统负载均衡的首选算法。

    传统hash算法的弊端

    常用的算法是对hash结果取余数 (hash() mod N):对机器编号从0到N-1,按照自定义的hash算法,对每个请求的hash值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将宕掉的服务器使用算法去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。

    传统求余做负载均衡算法,缓存节点数由3个变成4个,缓存不命中率为75%。计算方法:穷举hash值为1-12的12个数字分别对3和4取模,然后比较发现只有前3个缓存节点对应结果和之前相同,所以有75%的节点缓存会失效,可能会引起缓存雪崩。

    一致性hash算法

    1. 首先,我们将hash算法的值域映射成一个具有232 次方个桶的空间中,即0~(232)-1的数字空间。现在我们可以将这些数字头尾相连,组合成一个闭合的环形。

    2. 每一个缓存key都可以通过Hash算法转化为一个32位的二进制数,也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。

    3. 我们的每一个缓存节点也遵循同样的Hash算法,比如利用IP或者主机名做Hash,映射到环形空间当中,如下图

    image

    1. 如何让key和缓存节点对应起来呢?很简单,每一个key的顺时针方向最近节点,就是key所归属的缓存节点。所以图中key1存储于node1,key2,key3存储于node2,key4存储于node3。

    image

    1. 当缓存的节点有增加或删除的时候,一致性哈希的优势就显现出来了。让我们来看看实现的细节:
    • 增加节点
      当缓存集群的节点有所增加的时候,整个环形空间的映射仍然会保持一致性哈希的顺时针规则,所以有一小部分key的归属会受到影响。

    image

    有哪些key会受到影响呢?图中加入了新节点node4,处于node1和node2之间,按照顺时针规则,从node1到node4之间的缓存不再归属于node2,而是归属于新节点node4。因此受影响的key只有key2。

    image

    最终把key2的缓存数据从node2迁移到node4,就形成了新的符合一致性哈希规则的缓存结构。

    • 删除节点
      当缓存集群的节点需要删除的时候(比如节点挂掉),整个环形空间的映射同样会保持一致性哈希的顺时针规则,同样有一小部分key的归属会受到影响。

    image

    有哪些key会受到影响呢?图中删除了原节点node3,按照顺时针规则,原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

    image

    最终把key4的缓存数据从node3迁移到node1,就形成了新的符合一致性哈希规则的缓存结构。

    说明:这里所说的迁移并不是直接的数据迁移,而是在查找时去找顺时针的后继节点,因缓存未命中而刷新缓存。

    计算方法:假设节点hash散列均匀(由于hash是散列表,所以并不是很理想),采用一致性hash算法,缓存节点从3个增加到4个时,会有0-33%的缓存失效,此外新增节点不会环节所有原有节点的压力。

    一致性hash算法的结果相比传统hash求余算法已经进步很多,但可不可以改进一下呢?或者如果出现分布不均匀的情况怎么办?比如下图这样,按顺时针规则,所有的key都归属于统一个节点。

    image

    一致性hash算法+虚拟节点

    为了优化这种节点太少而产生的不均衡情况。一致性哈希算法引入了虚拟节点的概念。
    所谓虚拟节点,就是基于原来的物理节点映射出N个子节点,最后把所有的子节点映射到环形空间上。

    image

    虚拟节点越多,分布越均匀。使用一致性hash算法+虚拟节点这种情况下,缓存节点从3个变成4个,缓存失效率为25%,而且每个节点都平均的承担了压力。

    一致性hash算法+虚拟节点的实现

    原理理解了,实现并不难,主要是一些细节:

    1. hash算法的选择。Java代码不要使用hashcode函数,这个函数结果不够散列,而且会有负值需要处理。
      这种计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。
    2. 数据结构的选择。根据算法原理,我们的算法有几个要求:
    • 要能根据hash值排序存储
    • 排序存储要被快速查找 (List不行)
    • 排序查找还要能方便变更 (Array不行)

    另外,由于二叉树可能极度不平衡。所以采用红黑树是最稳妥的实现方法。Java中直接使用TreeMap即可。

    哎呀,如果我的名片丢了。微信搜索“全菜工程师小辉”,依然可以找到我

    展开全文
  • 一致性hash算法 ConsistentHashAlgorithm public class ConsistentHashAlgorithm { //虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称 @Getter private SortedMap, String> virtualNodes = new TreeMap...
  • 一致性Hash算法以及java实现

    千次阅读 2019-09-06 14:54:24
    目前我们很多时候都是在做分布式系统,但是我们需把客户端的请求均匀的分布到N个服务器中,一般我们可以考虑通过...一致性Hash就是为了解决这个问题。  Consistent Hashing 一致性Hash的原理  1、环型Hash空间 ...
  • 一致性Hash(Consistent Hashing)原理剖析及Java实现

    万次阅读 多人点赞 2018-08-10 18:04:09
    一、一致性Hash(Consistent Hashing)原理剖析 二、一致性hash算法的Java实现 一、一致性Hash(Consistent Hashing)原理剖析 引入 一致性哈希算法是分布式系统中常用的算法。一致性哈希算法解决了普通余数Hash算法...
  • 一致性hash算法介绍以及Java实现

    千次阅读 2017-08-04 16:42:29
    一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个...
  • 本文主要结合Redis集群来分享一下一致性Hash的相关问题 Redis集群的使用 一般可以对Redis做主从复制和Redis集群模式,组成Master-Master或者Master-Slave的形式,进行数据读写分离 当缓存数据量超过一定的数量时,...
  • 什么是一致性hash 一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法,常用于负载均衡。Memcached client也选择这种算法,解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的...
  • 一致性Hash算法

    2020-03-07 18:53:32
    本文主要描述一致性Hash算法的应用场景,算法原理,以及自己实现一个简单的一致性Hash算法。
  • 应用场景  1. 数据库分表分库规则,数据库服务器扩容降低对之前原有数据库数据的影响,并达到负载的均衡。  2. 分布式缓存负载算法规则,缓存数据库扩容降低对... 一致性Hash:加入一个新节点,对已存在的节点的影
  • 一、分布式一致性hash算法原理 在互联网项目中,海量数据和海量请求时常见的问题,常用的方法是使用缓存来处理,一般会采用分布式缓存集群,如Redis集群 但这样也有两个问题: 1、海量数据,如果缓存的数据也很大...
  • import java.util.LinkedList; import java.util.List; import java.util.SortedMap; import java.util.TreeMap;...分布式缓存一致性hash算法,带虚拟节点 @author lisl */ public class HashCacheT...
  • : 当进行调用时候根据调用方法的哪几个参数生成key,并根据key来通过一致性hash算法来选择调用结点。例如调用方法invoke(String s1,String s2); 若hash.arguments为1(默认值),则仅取invoke的参数1(s1)来生成...
  • 使用mycat分表(一致性hash)

    千次阅读 2017-12-19 20:16:02
    结合 一致性hash的逻辑,可以确认,generateBucketMap是 生成一个主机数*160(160是默认值)的treeMap,其val为主机序列,而calculate的方法,入参为 字段值,出参则为 主机序列. 提示,网上很多说的bucketMapPath...
  • 负载均衡之缓存路由(一致性Hash)算法Java实现   分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息),起到负载...
  • 从redis源码看一致性hash算法

    千次阅读 2018-03-05 15:32:19
    官方在Redis 3也正式推出了集群技术,不同于传统的散列映射的集群方案,jedis(redis的java客户端)支持Redis Sharding功能,结合缓存池ShardJedisPoo和一致性hash算法实现了高效hash。下面就结合redis的使用详细...
  • 一致性hash

    2019-10-24 10:17:30
    目录 一、一致性Hash(Consistent Hashing)原理剖析 二、一致性hash算法的Java实现 一、一致...
  • 一致性Hash算法简介一致性Hash算法是在1997年由麻省理工提出的一种分布式Hash实现算法,设计的目标是为了解决英特网中的热点问题。一致性Hash算法提出了在动态变化的Cache环境中,判定Hash算法好坏的四个定义。 平衡...
  • 一致性Hash算法·Java篇

    2018-08-24 10:10:28
    测试 Markdowna’s和扩展Markdown简洁的语法 代码块高亮 快捷键 加粗 Ctrl + B ... int h = hash; if (h == 0 &amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp; value.l
  • 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:11...
  • 一致性 hash 算法由麻省理工学院的 Karger 及其合作者于1997年提出的,算法提出之初是用于大规模缓存系统的负载均衡。它的工作过程是这样的,首先根据 ip 或者其他的信息为缓存节点生成一个 hash,并将这个 hash ...
  • Redis集群 和 一致性hash算法

    千次阅读 2020-04-30 14:06:15
    一致性hash算法 有些内容是网上找来的, 有些是自己的理解, 在这里进行下记录… 1. redis集群简介 redis集群是一个提供多个Redis(分布式)节点间共享数据的程序集 redis集群的键空间被分隔了16384个hash槽(slot...
  • 路由策略有很多,轮询,随机,一致性hash,今天我们要分析的是是一致性hash,那么它有什么好处呢? 好处 可扩展 很好的容错性 缺点 数据倾斜问题: 可用虚拟节点解决 实现逻辑 将地址列表中每一个地址进行hash...
  • 一致性Hash代码实现

    2019-09-19 14:33:34
    关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法和一致性Hash算法的算法原理做了详细的解读。 算法的具体原理这里再次贴上...
  • 一致性hash算法及java实现

    万次阅读 多人点赞 2018-03-28 14:11:38
    一致性hash算法是分布式中一个常用且好用的分片算法、或者数据库分库分表算法。现在的互联网服务架构中,为避免单点故障、提升处理效率、横向扩展等原因,分布式系统已经成为了居家旅行必备的部署模式,所以也产出了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,735
精华内容 5,894
关键字:

treemap一致性hash