专栏首页蘑菇先生的技术笔记探索C#之虚拟桶分片

探索C#之虚拟桶分片

阅读目录

  1. 背景
  2. 虚拟桶(virtual buckets)
  3. 实现
  4. 总结

背景

关于数据分片讨论最多的是一致性hash,然而它并不是分布式设计中的银弹百试百灵。 在数据稳定性要求比较高的场景下它的缺点是不能容忍的。 比如在Redis分布式缓存设计中,使用一致性Hash进行key分片存储,通过虚拟节点最大化降低添加或删除节点带来的影响。这里强调降低二字,即是它还是有影响的,在一般情况下我们还可以接受。 但是某些场景下要求动态扩容无影响就无法满足了。

上次(探索c#之一致性Hash详解)提到过Hash取模的分片算法,是把数据mod后直接映射到真实节点上面,这造成节点个数和数据的紧密关联、后期缺乏灵活扩展。 而一致性Hash分片算法多增加一层虚拟映射层,数据与虚拟节点映射、虚拟节点与真实节点再映射。

虚拟桶(virtual buckets)

虚拟桶是取模和一致性hash二者的折中办法。

  • 采用固定节点数量,来避免取模的不灵活性。
  • 采用可配置映射节点,来避免一致性hash的部分影响。

其运行机制如下:

key对虚拟桶层

虚拟桶层采用预设固定数量,比如楼主在项目中预设N=1024。意味之后这个分布式集群最大扩容到1024个节点,带来的好处就是mod后的值是不变的(非常重要),这保证了第一层映射挖宝去不受实际节点变化的影响。 关于最大数量,可根据实现需要预先定义好即可,比如Redis官方的糟最大65000个节点,豌豆荚的codis默认也是1024个节点。 当然如果数据量超过1024节点存储时,可以再起另外个集群应对。

虚拟桶对实际节点

举个例子,项目刚开始使用时配置节点映射: Redis Server1对应桶的编号为0到500。 Redis Server2对应桶的编号为500到1024。

缓存数据量增长后需要增加新节点,在加之前需要重新分配节点对应虚拟桶的编号。 比如增加server3并配置对应桶的编号400到600,这时对于key映射虚拟桶层完全无影响。  实际上mod 400到600的真实数据还在另外两台节点上,请求过来后还会发生无法命中的影响。 这就要求在增加新节点前,需要在后台把另外二台的400到600编号数据拷贝到新节点上面,完成后再添加配置到映射上面。 因为新来请求会命中到新节点,所以另外2台的400到600编号数据就无用了,需要进行删除。这种做法就能最大限度(100%)的保证动态扩容后,对缓存系统无影响。

实现

算法实现这块比较简单,数据迁移、配置等这块需要单独的系统来做。

private Dictionary<int, RedisGroup> RedisGroups;
private const ulong Slot = 1024;

 public RedisGroup GetGroup(string key)
        {
            var longVal = Md5Hash(key);
            var index = (int) (longVal%Slot);
            return RedisGroups[index];
        }

        public ulong Md5Hash(string key)
        {
            using (var hash = System.Security.Cryptography.MD5.Create())
            {
                byte[] data = hash.ComputeHash(Encoding.UTF8.GetBytes(key));
                var a = BitConverter.ToUInt64(data, 0);
                var b = BitConverter.ToUInt64(data, 8);
                ulong hashCode = a ^ b;
                return hashCode;
            }
        }

总结

采取虚拟桶这种预分片的算法,可以避免一致性hash扩容时引起的缓存不命中。文中使用1024个实例作为最大节点数量,实际中是完全足够用的。如果以后可能超过这个数量,可以部署另外一套1024节点的集群,最后形成一个超大规模的redis集群。

关于Redis的整套解决方案可以参考使用豌豆荚的codis。

分享了项目中一些使用经验,希望对大家有所帮助。 

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法数据结构(一)-B树

    蘑菇先生
  • 探索c#之一致性Hash详解

    蘑菇先生
  • Go中原始套接字的深度实践

    原始套接字(raw socket)是一种网络套接字,允许直接发送/接收更底层的数据包而不需要任何传输层协议格式。平常我们使用较多的套接字(socket)都是基于...

    蘑菇先生
  • Zookeeper 分布式协调服务介绍

    分布式系统的简单定义:分布式系统是一个硬件或软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

    小旋锋
  • Java数据结构和算法(十一)——红黑树

      上一篇博客我们介绍了二叉搜索树,二叉搜索树对于某个节点而言,其左子树的节点关键值都小于该节点关键值,右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为...

    IT可乐
  • 动画 | 什么是红黑树?(基于2-3树)

    学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

    我脱下短袖
  • 我画了 20 张图,给女朋友讲清楚红黑树

    红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分...

    范蠡
  • Redis主从复制

    爱撒谎的男孩
  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • Gephi实战,从零开始

    Gephi 是一款网络分析领域的数据可视化处理软件,开发者对它寄予的希望是:成为 “数据可视化领域的Photoshop” ,可运行在Windows,Linux及...

    咻咻ing

扫码关注云+社区

领取腾讯云代金券