分布式 | DBLE 分片算法之 hash 分片作者：赵红杰DBLE项目测试负责

作者：赵红杰
DBLE 项目测试负责人，主导分布式中间件的测试，在测试中不断发现产品和自身的 bug 。迭代验证，乐在其中。
本文来源：原创投稿
*爱可生开源社区出品，原创内容未经授权不得随意使用，转载请联系小编并注明来源。
背景社区有大佬分享过跳增 hash 的文章，但是当时并不理解跳增 hash 使用的场景。
刚接触分布式数据库中间件 dble 的时候，最迷惑的概念之一是 hash 分片算法。
看到哈希，第一印象是散列表，感觉是存储相关的。 hash 一个重要的特征是需要不同输入产生不同输出，但是在分片算法里，是需要多个值映射到一个分片节点上。这么大的差异，为什么可以用 hash 来对分布式数据库做逻辑分片，并且还命名叫 hash 分片！！！它们之间有哪些神似呢？
概念散列表
要理解他们之间的相似和差异，先从对 hash 最初的认识——散列表说起。
散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。
数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。
设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：
文章插图
文章插图
文章插图
散列表的主要特点：
1. 将输入映射到数字
2. 不同的输入产生不同的输出
【分布式 | DBLE 分片算法之 hash 分片】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 ，大家参考社区相关文章：
hash 取模分片
还有一种比较简单的 hash 函数是取模 hash 。目前的分布式数据库基本都提供了这种分片支持。主要业务场景是：分片键的值存在单调递增或递减、分片键的值不确定，基数大且重复的频率低、需要写入的数据随机分发、数据读取随机性较大。