首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >10分钟了解一致性hash算法

10分钟了解一致性hash算法

作者头像
Edison.Ma
发布2019-08-22 18:52:23
6220
发布2019-08-22 18:52:23
举报
文章被收录于专栏:DotNet Core圈圈DotNet Core圈圈

应用场景

当我们的数据表超过500万条或更多时,我们就会考虑到采用分库分表;当我们的系统使用了一台缓存服务器还是不能满足的时候,我们会使用多台缓存服务器,那我们如何去访问背后的库表或缓存服务器呢,我们肯定不会使用循环或者随机了,我们会在存取的时候使用相同的哈希算法定位到具体的位置。

简单的哈希算法

我们可以根据某个字段(比如id)取模,然后将数据分散到不同的数据库或表中。

例如前期规划,我们某个业务数据5个库就能满足了,根据id取模 如下图

我们通过hash取模很方便的路由到对应的库上,但是上述的简单的hash算法还是有一些缺陷的,假如,5个库也无法满足业务的时候,我们需要9个库,那么原来的取模公式mod 5要变成 mod 9了,并且大部分数据都要重新分布,涉及到数据转移工作量也是巨大的。有没有一劳永逸的方法,答案是有的一致性hash算法

一致性哈希算法
算法概述

一致性哈希算法(Consistent Hashing),是MIT的karge及其合作者在1997年发表的学术论文提出的,最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0 - 2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

服务器(ip或者主机名)本身进行哈希,确认每台机器在哈希环上的位置,例如ip:192.168.4.101,192.168.4.102,192.168.4.103 分别对应节点node1-101,node2-102,node3-103 如图

数据key使用相同的函数计算出哈希值h,根据h确定此数据在环上的位置,从此位置沿环顺时针“行走”,最近的服务器就是其应该定位到的服务器。例如 我们使用"10","11","12","13","14" 四个数据对象对应key10,key11,key12,key13,key14,经过哈希计算后,在环空间的位置如下:

根据一致性哈希算法,数据key10,key14会被定位到节点node3-103上,key12,key13被定位到节点node1-10上,而key11会被定位到节点node2-102上。

扩展性
节点添加

如果我们新增一个节点node4-104 对应的ip:192.168.4.104通过对应的哈希算法得到哈希值,并映射到环中,如下图

通过按顺时针迁移的规则,那么key10被迁移到了node4-104中,其它数据还保持这原有的存储位置

节点删除

如果删除一个节点node3-103,那么按照顺时针迁移的方法,key10,key14将会被迁移到node1-10上,其它的对象没有任何的改动。如下图:

如果服务节点太少的时候,会出现数据分配不均,比如极端情况下所有数据都落到node1-101节点上,如何解决数据倾斜问题,需要引入虚拟节点

虚拟节点

如果节点比较少的情况下,在0到2^32-1形成的环中,会出每个节点存放的数据不均匀;一致性哈希算法提出虚拟节点的解决方案。即虚拟节点时实际节点(物理机器)在hash环中的复制品,一个实际节点对应N多个虚拟节点,这个对应个数也成为了复制个数,虚拟节点在hash环中以hash值排列。

例如 我们以删除了一个点,只剩下 node1 和node2 两个节点的图;我们添加4个虚拟节点,两个节点 则对应8个节点,最后映射关系 如图

核心代码
 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))
            {
                //得到大于当前key的那个子Map,然后从中取出第一个key,就是大于且离它最近的那个key 说明详见: http://www.javaeye.com/topic/684087
                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;
        }

最后贴上了实现代码,可以运行跑跑,加深理解,希望对您有所帮助,码字不易请多多支持。

参考

代震军----https://www.cnblogs.com/daizhj/archive/2010/08/24/1807324.html

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-08-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 DotNet技术平台 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简单的哈希算法
  • 一致性哈希算法
    • 算法概述
      • 扩展性
        • 节点添加
        • 节点删除
      • 虚拟节点
        • 核心代码
          • 参考
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档