分布式 | DBLE 分片算法之 hash 分片

发布时间:2020-11-02 浏览次数:448

作者:赵红杰

DBLE 项目测试负责人,主导分布式中间件的测试,在测试中不断发现产品和自身的 bug。迭代验证,乐在其中。

本文来源:原创投稿 *爱可生开源社区出品,原创内容未经授权不得随意使用,转载请联系小编并注明来源。


背景

社区有大佬分享过跳增 hash 的文章,但是当时并不理解跳增 hash 使用的场景。

刚接触分布式数据库中间件 dble 的时候,最迷惑的概念之一是 hash 分片算法。

看到哈希,第一印象是散列表,感觉是存储相关的。hash 一个重要的特征是需要不同输入产生不同输出,但是在分片算法里,是需要多个值映射到一个分片节点上。这么大的差异,为什么可以用 hash 来对分布式数据库做逻辑分片,并且还命名叫 hash 分片!!!它们之间有哪些神似呢?


概念

散列表

要理解他们之间的相似和差异,先从对 hash 最初的认识——散列表说起。

散列表是一种数据结构,通过散列函数(也就是 hash 函数)将输入映射到一个数字,一般用映射出的数字作为存储位置的索引。

数组在查找时效率很高,但是插入和删除却很低。而链表刚好反过来。

设计合理的散列函数可以集成链表和数组的优点,在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3:

散列表的主要特点:

1. 将输入映射到数字

2. 不同的输入产生不同的输出

3. 相同的输入产生相同的输出

4. 当填装因子超过阈值时,能自动扩展。

填装因子 = 散列表包含的元素数 / 位置总数,当填装因子 =1,即散列表满的时候,就需要调整散列表的长度,自动扩展的方式是:申请一块旧存储容量 X 扩容系数的新内存地址,然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置,拷贝到新申请的地址。

5. 值呈均匀分布。

这里的均匀指水平方向的,即数组维度的。如果多个值被映射到同一个位置,就产生了冲突,需要用链表来存储多个冲突的键值。极端情况是极限冲突,这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n),如果水平方向填充因子很小,但某些节点下的链表又很长,那值的均匀性就比较差。

hash 分片

理解了散列表的基本特点,再来看看分布式数据库的 hash 分片。

hash 分片设计的要点:

1. 固定的数据映射到固定的节点 / 槽位

2. 数据分布均匀

3. 扩容方便

主要是扩容时尽可能移动较少的数据。扩容之后实现新的数据分布均匀。

想要实现动态扩容,尽可能不影响业务并保证效率,需要做到移动尽可能少的数据,一致性 hash 就是为了解决移动较少数据的问题,但是一致性 hash 的缺点是数据分布的均匀性较差。为了解决这个问题,聪明的 dev 们又设计了跳增一致性 hash 算法。

到这里,可以看出 hash 与分片最紧密或者说最神似的点在于:

1. 固定的输入有固定的输出

2. 值呈均匀分布

如果分布式数据库的分片数据分布不均匀,最糟情况就像散列表的极端冲突一样,落在最终数据库上的压力跟不使用分布式相同。

3. 方便扩容

当分片填充满的时候,需要扩容使总数据量在总分片之间再次达到数据均匀分布状态,扩容需要用 hash 函数重新映射旧值到新的分片。

4. 散列表和 hash 分片想要有好的表现都依赖于设计良好的 hash 函数。

正是由于这些相似特点,Hash 在分布式数据库里得到比较多的使用。回到测试的老本行,这些点便是我们测试思考的重点。

了解了分布式与 hash 的关联,再来八几句 hash 函数,可以说hash函数设计的好坏,直接决定了分片策略是否合适。

一致性 hash 和跳增 hash,大家参考社区相关文章:

https://opensource.actionsky.com/20190910-dble/

hash 取模分片

还有一种比较简单的 hash 函数是取模 hash。目前的分布式数据库基本都提供了这种分片支持。主要业务场景是:分片键的值存在单调递增或递减、分片键的值不确定,基数大且重复的频率低、需要写入的数据随机分发、数据读取随机性较大。

取模 hash,举个最简单的例子就能明白:分片数设置为 2,要把数据均匀分布在这 2 个分片上,直接对分片 key 取模 2,这样模值为 0 的数据落在分片 1,模值为 2 的数据落在分片 2。只要输入的数据奇偶均匀,分片数据就保证均衡。

取模 hash 在 dble 里还做了一些变种支持,比如可以指定每个数据分片的连续值的数量,比如自然数 0-99 放分片 1,自然数 100-599 放分片 2,具体配置方式参考官方文档。这样做主要目的是改善 hash 在范围查询时的效率问题。

Hash 取模分片非常简单,均衡性比较好,能分散数据热点,并且能快速人为识别数据所在分片。缺点也很明显。

1. 在业务上范围查询效率比较低

2. 扩容不便

因为取模 hash 强依赖于分片数,当新增或删减分片节点——即扩缩容时,大量的数据在重新映射后都需要挪动。比如上面的 2 分片数据,如果增加到 3 分片,原来分片 1 上的数据只有 1/3 的数据可以保留不动,另外 2/3 的数据都需要挪到新的分片上,分片 2 也是如此。

如果真的使用了 hash 取模分片,为了后期在扩容时移动尽可能少的数据,dble 的建议是:取模的基数不能大于 2880,原因是:2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 144, 160, 180, 192, 240, 288, 320, 360, 480, 576, 720, 960, 1440 是 2880 的约数。

以上是对分布式与 hash 的一些浅显认识,文章内容部分来自对书或互联网知识的个人理解,不当之处欢迎指正。

Ref:

《图解算法》

《分布式系统常用技术及案例分析》

https://actiontech.github.io/dble-docs-cn/1.config_file/1.05_sharding.xml.html

https://tech.antfin.com/docs/2/99411



上一篇: 新特性解读 | MySQL 8.0.22 新特性 Async Replication Auto failover

下一篇: 技术分享 | 基于 GTID 的多源复制

产品试用 产品试用
400-820-6580 免费电话