作者：赵红杰
DBLE 项目测试负责人，主导分布式中间件的测试，在测试中不断发现产品和自身的 bug。迭代验证，乐在其中。
背景
社区有大佬分享过跳增 hash 的文章，但是当时并不理解跳增 hash 使用的场景。
刚接触分布式数据库中间件 dble 的时候，最迷惑的概念之一是 hash 分片算法。
看到哈希，第一印象是散列表，感觉是存储相关的。hash 一个重要的特征是需要不同输入产生不同输出，但是在分片算法里，是需要多个值映射到一个分片节点上。这么大的差异，为什么可以用 hash 来对分布式数据库做逻辑分片，并且还命名叫 hash 分片！！！它们之间有哪些神似呢？
概念
要理解他们之间的相似和差异，先从对 hash 最初的认识——散列表说起。
散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。
数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。
设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：
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 取模分片非常简单，均衡性比较好，能分散数据热点，并且能快速人为识别数据所在分片。缺点也很明显。
因为取模 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