• 一、一致性Hash算法原理 基本概念  一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下: 整个空间按顺时针方向...

    一、一致性Hash算法原理

    基本概念

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

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

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

    接下来使用如下算法定位数据访问到相应服务器:将数据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上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器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甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

    二、C#代码实现

     public class KetamaNodeLocator
        {
            
            private SortedList<long, string> ketamaNodes = new SortedList<long, string>();
            private HashAlgorithm hashAlg;
            private int numReps = 160;
        
            public KetamaNodeLocator(List<string> nodes/*,int nodeCopies*/)
            {
                ketamaNodes = new SortedList<long, string>();
                //numReps = nodeCopies;
                //对所有节点,生成nCopies个虚拟结点
                foreach (string node in nodes)
                {
                    //每四个虚拟结点为一组
                    for (int i = 0; i < numReps /4; i++)
                    {
                        //getKeyForNode方法为这组虚拟结点得到惟一名称 
                        byte[] digest = HashAlgorithm.computeMd5(node + i);
                        /** Md5是一个16字节长度的数组,将16字节的数组每四个字节一组,分别对应一个虚拟结点,这就是为什么上面把虚拟结点四个划分一组的原因*/
                        for (int h = 0; h < 4; h++)
                        {
                            long m = HashAlgorithm.hash(digest, h);
                            ketamaNodes[m] = node;
                        }
                    }
                }
            }
            public string GetPrimary(string k)
            {
                byte[] digest = HashAlgorithm.computeMd5(k);
                string rv = GetNodeForKey(HashAlgorithm.hash(digest, 0));
                return rv;
            }
            string GetNodeForKey(long hash)
            {
                string rv;
                long key = hash;
                //如果找到这个节点,直接取节点,返回   
                if (!ketamaNodes.ContainsKey(key))
                {
                 
                    var tailMap = from coll in ketamaNodes
                                  where coll.Key > hash
                                  select new { coll.Key };
                    if (tailMap == null || tailMap.Count() == 0)
                        key = ketamaNodes.FirstOrDefault().Key;
                    else
                        key = tailMap.FirstOrDefault().Key;
                }
                rv = ketamaNodes[key];
                return rv;
            }
        }
        public class HashAlgorithm
        {
            public static long hash(byte[] digest, int nTime)
            {
                long rv = ((long)(digest[3 + nTime * 4] & 0xFF) << 24)
                        | ((long)(digest[2 + nTime * 4] & 0xFF) << 16)
                        | ((long)(digest[1 + nTime * 4] & 0xFF) << 8)
                        | ((long)digest[0 + nTime * 4] & 0xFF);
                return rv & 0xffffffffL; /* Truncate to 32-bits */
            }
            /**
             * Get the md5 of the given key.
             */
            public static byte[] computeMd5(string k)
            {
                MD5 md5 = new MD5CryptoServiceProvider();
    
                byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k));
                md5.Clear();
                //md5.update(keyBytes);
                //return md5.digest();
                return keyBytes;
            }
        }

     

    展开全文
  • 一致性HASH算法"(Consistent Hashing),用于解决memcached集群中当服务器出现增减变动时对散列值的影响。后来 在JAVAEYE上的一篇文章中,找到了其中的 KetamaHash 算法的JAVA实现(一种基于虚拟结点的HASH...
  • 一致性Hash算法的实现 2017-04-16 11:02:07
    一致性hash作为一个负载均衡算法,可以用在分布式缓存、数据库的分库分表等场景中,还可以应用在负载均衡器中作为作为负载均衡算法。在有多台服务器时,对于某个请求资源通过hash算法,映射到某一个台服务器,当增加...
  • 一致性哈希算法(c#版) 2019-01-06 10:00:18
    一致性HASH算法"(Consistent Hashing),用于解决memcached集群中当服务器出现增减变动时对散列值的影响。后来 在JAVAEYE上的一篇文章中,找到了其中的 KetamaHash 算法的JAVA实现(一种基于虚拟结点的HASH...
  • 基本场景 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N ...求余算法: hash(object)%N 一切都运行正常,再考虑如下的两种情况; 1 一个 cache 服务器 m down 掉了(在实际应用中
  • 一致性Hash算法背景  一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希...
  • 其实就是我最近写的一个项目,采用Hash一致满足负载均衡。Hash一致环带虚拟节点。 在前面的博文中说明了我采用的方法,MurmurHash+红黑树(底层其实是sortedlist).经过多次测试结合的。 但是最近2天研究测试,...
  • 一致性hash算法 2019-07-18 01:27:31
    hash一致性算法hash函数的一种,他的目的在于实现负载均衡,并且每次访问的目标具有一致性,举个例子来说,根据客户端请求ip,经过hash一致性算法,每次计算出来的一致性hash值都是相同的因此每次 请求的目标主机将...
  • 一致性Hash算法简介一致性Hash算法是在1997年由麻省理工提出的一种分布式Hash实现算法,设计的目标是为了解决英特网中的热点问题。一致性Hash算法提出了在动态变化的Cache环境中,判定Hash算法好坏的四个定义。 平衡...
  • 10个Memcached节点,填充100000数据的测试结果如下:   192.168.1.199:11211 => 13046 192.168.1.191:11211 => 18230 192.168.1.197:11211 => 6382 192.168.1.194:11211 => 5242 ...192.168.1.193:11211 => 25554...
  • jump Consistent hash:零内存消耗,均匀,快速,简洁,来自Google的一致性哈希算法 2015-03-13 简介 jump consistent hash是一种一致性哈希算法, 此算法零内存消耗,均匀分配,快速,并且只有5行代码。 ...
  • 一致性hash算法[C#] 2019-08-21 05:19:41
    using System; using System.Collections.Generic; using System.Linq; using System.Security.Cryptography; using System.Text; using System.Threading.Tasks;...namespace DevelopmentBasicSkill....
  • 一致性Hash算法背景  一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单...
  • 这里介绍的是C#的redis客户端 ServiceStack 对一致性hash算法的实现.主要涉及到类如下: ShardedConnectionPool ShardedRedisClientManager 而ShardedConnectionPool又是继承自PooledRedisClientManager ...
  • 一致性Hash算法 2019-01-08 04:21:03
    转自:... ... 一致性Hash算法背景  一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Ho...
  • 在了解一致性哈希算法之前,最好先了解一下缓存中的一个应用场景,了解了这个应用场景之后,再来理解一致性哈希算法,就容易多了,也更能体现出一致性哈希算法的优点,那么,我们先来描述一下这个经典的分布式缓存的...
1 2 3 4 5 ... 20
收藏数 6,095
精华内容 2,438