前言
今天是这一系列分片算法的完结篇. 今天介绍的算法美如画, 谷歌工程师仅仅用了 5 行代码就解决了一个大问题. 可见写代码这件事不在多, 而在于精. 算法真的可以改变世界.
1.hash 分区算法
2.stringhash 分区算法
3.enum 分区算法
4.numberrange 分区算法
5.patternrange 分区算法
6.date 分区算法
7.jumpstringhash 算法
jumpstringhash 分区算法的配置
- <tableRule name="rule_jumpHash">
- <rule>
- <columns>code</columns>
- <algorithm>func_jumpHash</algorithm>
- </rule>
- </tableRule>
- <function name="func_jumpHash" class="jumpStringHash">
- <property name="partitionCount">2</property>
- <property name="hashSlice">0:2</property>
- </function>
和之前的算法一样. 需要在 rule.xml 中配置 tableRule 和 function.
tableRule 标签, name 对应的是规则的名字, 而 rule 标签中的 columns 则对应的分片字段, 这个字段必须和表中的字段一致. algorithm 则代表了执行分片函数的名字.
function 标签, name 代表分片算法的名字, 算法的名字要和上面的 tableRule 中的 < algorithm > 标签相对应. class: 指定分片算法实现类. 此处需要填写为 "jumpstringhash" 或者 "com.actiontech.dble.route.function.PartitionByJumpConsistentHash" 的分区规则, property 指定了对应分片算法的参数. 不同的算法参数不同.
partitionCount: 分片数量
hashSlice: 分片截取长度
在 MyCAT 中有一种分区算法叫一致性 hash 算法, 来源于论文 "Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide web". 而那之后 Google 的 John Lamping 和 Eric Veach 发布了 Jump Consistent Hash, 一种零内存消耗, 均匀, 快速, 简洁的一致性哈希算法. 而 dble 中只使用了 Jump Consistent Hash 而移除了一致性 hash. 这主要是因为跳跃法占用内存消耗更小, 均衡性更高, 计算量也相对较小.
我们来看一下源代码, 这个是我从 dble 的 PartitionByJumpConsistentHash.java 中摘取的一部分:
- public class test2 {
- private static final long CONSTANT = Long.parseLong("286293355577794175", 10) * 10 + 7;
- private static final long JUMP = 1L <<31;
- private static final long UNSIGNED_MASK = 0x7fffffffffffffffL;
- private static void checkBuckets(final int buckets) {
- if (buckets < 0) {
- throw new IllegalArgumentException("Buckets cannot be less than 0");
- }
- }
- private static double toDouble(final long n) {
- double d = n & UNSIGNED_MASK;
- if (n < 0) {
- d += 0x1.0p63;
- }
- return d;
- }
- public static int jumpConsistentHash(final long key, final int buckets) {
- checkBuckets(buckets);
- long k = key;
- long b = -1;
- long j = 0;
- while (j < buckets) {
- b = j;
- k = k * CONSTANT + 1L;
- j = (long) ((b + 1L) * (JUMP / toDouble((k>>> 33) + 1L)));
- }
- return (int) b;
- }
- public static void main(String args[]) {
- System.out.println("======== bucket 4 =========\n");
- for (int i = 20000; i <20020; i++) {
- System.out.println(i+":"+jumpConsistentHash(i, 4));
- }
- System.out.println("======== bucket 3 =========\n");
- for (int i = 20000; i < 20020; i++) {
- System.out.println(i+":"+jumpConsistentHash(i, 3));
- }
- }
- }
运行结果
结果
从输出结果来看, 结论如下:
1). 当 buckets=1 的时候, 对任意 key, 全部落在 0 上面.
2). 当 buckets=2 时时候, 为了使 hash 的结果保持均匀, jumpConsistentHash(k,2)的结果有占比 1/2 的结果保持为 0, 有 1/2 跳变为 1.
由此规律是: 当 buckets 从 n 变化到 n+1 后, jumpConsistentHash(k,n+1)的结果中, 应该有占比 n/(n+1) 的结果保持不变, 而有 1/(n+1) 跳变为 n+1. 所以当 n=2 变成 n+1=3 后, jumpConsistentHash(k,3)的结果, 有占比 2/3 的结果保持不变, 而有 1/3 的跳变成了 2. 而随着这个 bucket 越来越大, 它所变化的概率也就越来越低.
接下来我们来详细测试一下.
1. 启动加载配置
在启动 dble 之后, 就会读取 rule.xml 文件, 加载上述配置. 然后根据 partitionCount 产生物理分区表.
2. 运行过程
如果有用户通过 where 查询 name='buddy'的时候, 就会访问 jumpstringhash 分片算法, 首先根据配置的 hashSlice 进行截取, 这里 hashSlice0,3 会把 bud 截取出来, 然后在对这个截取的字符串做 hash 值. 然后把 hash 值作为 key,partitionCount 作为 bucket 传到 jumpConsistentHash 函数中. 计算出最终一致的 hash 值.
3. 我们建表来测试一下
3.1 在 rule.xml 配置下列内容
- <tableRule name="rule_jumpHash">
- <rule>
- <columns>name</columns>
- <algorithm>func_jumpHash</algorithm>
- </rule>
- </tableRule>
- <function name="func_jumpHash" class="jumpStringHash">
- <property name="partitionCount">4</property>
- <property name="hashSlice">0:3</property>
- </function>
3.2 在 schema.xml 配置下列内容
<table name="test_jumphash" primaryKey="id" rule="rule_jumpHash" dataNode="dn1,dn2,dn3,dn4"/>
3.3 登录管理端口, reload 配置
- [root@mysql5 ~]# MySQL -uman1 -p -P9066 -h192.168.56.185 -p654321
- MySQL> reload @@config;
- Query OK, 1 row affected (0.39 sec)
- Reload config success
3.4 然后使用服务端口登录到 dble 上执行建表测试语句.
可以发现, 我们插入的数据 buddy, 然后存放在了 dn4 上面. 我们来看下是怎么计算的, 我们的截取的字符是 0,3, 也就是截取'bud', 前面计算过这个串 hash 出来的值是 97905. 具体算法参考《数据库中间件分片算法之 stringhash》. 然后我们把 97905 作为 key,partitionCount 作为 bucket 带入到 jumpConsistentHash 函数计算. 得到的结果正好是 3, 也就是该数据一定落在 dn4 分片上.
- public static void main(String args[]) {
- System.out.println(jumpConsistentHash(97905,4));
- }
- }
- [root@mysql5 ~]# java test4
- 3
注意事项:
分片字段值为 NULL 时, 数据恒落在 0 号节点之上; 当真实存在于 MySQL 的字段值为 not null 的时候, 报错 "Sharding column can't be null when the table in MySQL column is not null"
后记
今天介绍了 Jump Consistent Hash 算法, 目前 dble 用这个算法取代了 Mycat 中更加传统的环割一致性 hash 算法. 当然这个里面具体的算法细节还和概率论的一些知识有关, 这里只是给大家演示了一下. 更加详细的该算法介绍可以参考下面的链接.
参考链接
1.jump Consistent hash: 零内存消耗, 均匀, 快速, 简洁, 来自 Google 的一致性哈希算法
2. 一致性哈希算法 (consistent hash) 的黑科技
3. 分布式 | dble 沿用 jumpstringhash, 移除 Mycat 一致性 hash 原因解析
来源: https://www.qcloud.com/developer/article/1574756