数据库中间件分片算法之jumpstringhash

前言

今天是这一系列分片算法的完结篇。今天介绍的算法美如画，谷歌工程师仅仅用了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

注意事项：

1. 分片字段值为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的一致性哈希算法https://blog.helong.info/blog/2015/03/13/jump_consistent_hash/

2.一致性哈希算法（consistent hash）的黑科技https://blog.csdn.net/weixin_33866037/article/details/92487450

3.分布式 | dble 沿用 jumpstringhash，移除 Mycat 一致性 hash 原因解析https://blog.csdn.net/ActionTech/article/details/100703198