关于hash:分布式-DBLE-分片算法之-hash-分片

6次阅读

共计 2340 个字符，预计需要花费 6 分钟才能阅读完成。

作者：赵红杰
DBLE 我的项目测试负责人，主导分布式中间件的测试，在测试中一直发现产品和本身的 bug。迭代验证，乐在其中。
本文起源：原创投稿
* 爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。

社区有大佬分享过跳增 hash 的文章，然而过后并不了解跳增 hash 应用的场景。刚接触分布式数据库中间件 dble 的时候，最蛊惑的概念之一是 hash 分片算法。看到哈希，第一印象是散列表，感觉是存储相干的。hash 一个重要的特色是须要不同输出产生不同输入，然而在分片算法里，是须要多个值映射到一个分片节点上。这么大的差别，为什么能够用 hash 来对分布式数据库做逻辑分片，并且还命名叫 hash 分片！！！它们之间有哪些神似呢？

要了解他们之间的类似和差别，先从对 hash 最后的意识——散列表说起。散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输出映射到一个数字，个别用映射出的数字作为存储地位的索引。数组在查找时效率很高，然而插入和删除却很低。而链表刚好反过来。设计正当的散列函数能够集成链表和数组的长处，在查找、插入、删除时实现 O(1) 的效率。散列表的存储构造应用的也是数组加链表。执行效率比照能够看下图 1.3：

散列表的次要特点：
1. 将输出映射到数字
2. 不同的输出产生不同的输入
3. 雷同的输出产生雷同的输入

当填装因子超过阈值时，能主动扩大。

填装因子 = 散列表蕴含的元素数 / 地位总数，当填装因子 =1，即散列表满的时候，就须要调整散列表的长度，主动扩大的形式是：申请一块旧存储容量 X 扩容系数的新内存地址，而后把原内存地址的值通过其中的 key 再次应用 hash 函数计算存储地位，拷贝到新申请的地址。

值呈均匀分布。

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

了解了散列表的根本特点，再来看看分布式数据库的 hash 分片。hash 分片设计的要点：
1. 固定的数据映射到固定的节点 / 槽位
2. 数据分布平均 3. 扩容不便次要是扩容时尽可能挪动较少的数据。扩容之后实现新的数据分布平均。想要实现动静扩容，尽可能不影响业务并保障效率，须要做到挪动尽可能少的数据，一致性 hash 就是为了解决挪动较少数据的问题，然而一致性 hash 的毛病是数据分布的平均性较差。为了解决这个问题，聪慧的 dev 们又设计了跳增一致性 hash 算法。到这里，能够看出 hash 与分片最严密或者说最神似的点在于：1. 固定的输出有固定的输入 2. 值呈均匀分布如果分布式数据库的分片数据分布不平均，最糟状况就像散列表的极其抵触一样，落在最终数据库上的压力跟不应用分布式雷同。
3. 不便扩容当分片填充斥的时候，须要扩容使总数据量在总分片之间再次达到数据均匀分布状态，扩容须要用 hash 函数从新映射旧值到新的分片。

散列表和 hash 分片想要有好的体现都依赖于设计良好的 hash 函数。正是因为这些类似特点，Hash 在分布式数据库里失去比拟多的应用。回到测试的老本行，这些点便是咱们测试思考的重点。理解了分布式与 hash 的关联，再来八几句 hash 函数，能够说 hash 函数设计的好坏，间接决定了分片策略是否适合。一致性 hash 和跳增 hash，大家参考社区相干文章：

https://opensource.actionsky….

还有一种比较简单的 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 的一些通俗意识，文章内容局部来自对书或互联网常识的集体了解，不当之处欢送斧正。