专栏首页平凡少年一致性Hash算法在Redis分布式中的使用

一致性Hash算法在Redis分布式中的使用

由于redis是单点,但是项目中不可避免的会使用多台Redis缓存服务器,那么怎么把缓存的Key均匀的映射到多台Redis服务器上,且随着缓存服务器的增加或减少时做到最小化的减少缓存Key的命中率呢?这样就需要我们自己实现分布式。

  Memcached对大家应该不陌生,通过把Key映射到Memcached Server上,实现快速读取。我们可以动态对其节点增加,并未影响之前已经映射到内存的Key与memcached Server之间的关系,这就是因为使用了一致性哈希。 因为Memcached的哈希策略是在其客户端实现的,因此不同的客户端实现也有区别,以Spymemcache、Xmemcache为例,都是使用了KETAMA作为其实现。

  因此,我们也可以使用一致性hash算法来解决Redis分布式这个问题。在介绍一致性hash算法之前,先介绍一下我之前想的一个方法,怎么把Key均匀的映射到多台Redis Server上。

由于LZ水平有限且对Redis研究的不深,文中有写的不对的地方请指正。

方案一

该方案是前几天想的一个方法,主要思路是通过对缓存Key中的字母和数字的ascii码值求sum,该sum值对Redis Server总数取余得到的数字即为该Key映射到的Redis Server,该方法有一个很大的缺陷就是当Redis Server增加或减少时,基本上所有的Key都映射不到对应的的Redis Server了。代码如下:

    /// <summary>
        /// 根据缓存的Key映射对应的Server
        /// </summary>
        /// <param name="Key"></param>
        /// <returns></returns>
        public static RedisClient GetRedisClientByKey(string Key)
        {
            List<RedisClientInfo> RedisClientList = new List<RedisClientInfo>();
            RedisClientList.Add(new RedisClientInfo() { Num = 0, IPPort = "127.0.0.1:6379" });
            RedisClientList.Add(new RedisClientInfo() { Num = 1, IPPort = "127.0.0.1:9001" });

            char[] charKey = Key.ToCharArray();
            //记录Key中的所有字母与数字的ascii码和
            int KeyNum = 0;
            //记录余数
            int Num = 0;
            foreach (var c in charKey)
            {
                if ((c >= 'a' && 'z' >= c) || (c >= 'A' && 'Z' >= c))
                {
                    System.Text.ASCIIEncoding asciiEncoding = new System.Text.ASCIIEncoding();
                    KeyNum = KeyNum + (int)asciiEncoding.GetBytes(c.ToString())[0];
                }
                if (c >= '1' && '9' >= c)
                {
                    KeyNum += Convert.ToInt32(c.ToString());
                }
            }
            Num = KeyNum % RedisClientList.Count;
            return new RedisClient(RedisClientList.Where(it => it.Num == Num).First().IPPort);
        }
        //Redis客户端信息
        public class RedisClientInfo
        {
            //Redis Server编号
            public int Num { get; set; }
            //Redis Server IP地址和端口号
            public string IPPort { get; set; }
        }

方案二

1、分布式实现

通过key做一致性哈希,实现key对应redis结点的分布。

一致性哈希的实现:

  1. hash值计算:通过支持MD5与MurmurHash两种计算方式,默认是采用MurmurHash,高效的hash计算。
  2. 一致性的实现:通过java的TreeMap来模拟环状结构,实现均匀分布

什么也不多说了,直接上代码吧,LZ也是只知道点皮毛,代码中还有一些看不懂的地方,留着以后慢慢琢磨

public class KetamaNodeLocator
    {
        //原文中的JAVA类TreeMap实现了Comparator方法,这里我图省事,直接用了net下的SortedList,其中Comparer接口方法)
        private SortedList<long, string> ketamaNodes = new SortedList<long, string>();
        private HashAlgorithm hashAlg;
        private int numReps = 160;
        //此处参数与JAVA版中有区别,因为使用的静态方法,所以不再传递HashAlgorithm alg参数
        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;
        }
    }

2、分布式测试

1、假设有两个server:0001和0002,循环调用10次看看Key值能不能均匀的映射到server上,代码如下:

    static void Main(string[] args)
        {
            //假设的server
            List<string> nodes = new List<string>() { "0001","0002" };
            KetamaNodeLocator k = new KetamaNodeLocator(nodes);
            string str = "";
            for (int i = 0; i < 10; i++)
            {
                string Key="user_" + i;
                str += string.Format("Key:{0}分配到的Server为:{1}\n\n", Key, k.GetPrimary(Key));
            }
            
            Console.WriteLine(str);
           
            Console.ReadLine();
             
        }

程序运行两次的结果如下,发现Key基本上均匀的分配到Server节点上了。

2、我们在添加一个0003的server节点,代码如下:

  static void Main(string[] args)
        {
            //假设的server
            List<string> nodes = new List<string>() { "0001","0002" ,"0003"};
            KetamaNodeLocator k = new KetamaNodeLocator(nodes);
            string str = "";
            for (int i = 0; i < 10; i++)
            {
                string Key="user_" + i;
                str += string.Format("Key:{0}分配到的Server为:{1}\n\n", Key, k.GetPrimary(Key));
            }
            
            Console.WriteLine(str);
           
            Console.ReadLine();
             
        }

程序运行两次的结果如下:

对比第一次的运行结果发现只有user_5,user_7,user_9的缓存丢失,其他的缓存还可以命中。

3、我们去掉server 0002,运行两次的结果如下:

对比第二次和本次运行结果发现 user_0,user_1,user_6 缓存丢失。

结论

通过一致性hash算法可以很好的解决Redis分布式的问题,且当Redis server增加或减少的时候,之前存储的缓存命中率还是比较高的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NHibernate总结

    现在的项目中数据访问使用的是NHibernate的一个ORM框架,小弟也是在后期加入项目组,之前对NHibernate就一直没有接触过,所以一直在学习NHibe...

    写代码的猿
  • WebApi与手机客户端通信安全机制

    最近公司有几个项目需要开发手机客户端,服务器端选用WebApi,那么如何保证手机客户端在请求服务器端时数据不被篡改,如何保证一个http请求的失效机制,下面总结...

    写代码的猿
  • 基于Redis缓存的Session共享(附源码)

        在上一篇文章中我们研究了Redis的安装及一些基本的缓存操作,今天我们就利用Redis缓存实现一个Session共享,基于.NET平台的Seesion共...

    写代码的猿
  • 就是快, 10分钟在腾讯云搭建Web服务器

    Web服务器由于它的安全,方便,简洁等优点,已经成为目前使用规模最广的服务器。个人或者企业搭建网站是万万不能离开它的,然而搭建Web服务器却对于一部分非专业人士...

    用户6564282
  • 10分钟在腾讯云搭建Web服务器,就是快

    Web服务器由于它的安全,方便,简洁等优点,已经成为目前使用规模最广的服务器。个人或者企业搭建网站是万万不能离开它的,然而搭建Web服务器却对于一部分非专业人士...

    用户6494714
  • 昨日,面对种种非议,马云发了内部邮件

    大数据文摘
  • Kbone原理解析 & 小程序技术选型

    首先我们来看下普通Web端框架,以Vue框架为例,一份Vue模板对应一个组件,在代码构建阶段编译成调用Dom接口的JS函数,执行此JS函数就会创建出组件对应的D...

    binnie
  • Python 关于图片处理PIL

    PIL (Python Image Library) 库是Python 语言的一个第三方库,PIL库支持图像存储、显示和处理,能够处理几乎所有格...

    matinal
  • PHP 如何获取 BiliBli 指定用户粉丝数量 寻找 API 地址

    前段时间刷13站看到了这个视频 av26280568 那么!要怎么获取呢? 首先咱们打开个人空间 (查看链接»),我们可以看到右下角有关注数和粉丝数 (少的可怜...

    叮当叮
  • 【云安全】应用程序和架构设计在云计算环境下的安全建议

    应用程序可以轻松地在属于自己隔离的云环境中运行,根据提供者的不同,可能是一个单独的虚拟网络(虚拟专有网络VPC),也可能是一个一个单独的账号/子账号。使用账户或...

    一只特立独行的兔先生

扫码关注云+社区

领取腾讯云代金券