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

  • 2020 年 1 月 16 日
  • 筆記

前言

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

VirMach 便宜 VPS

QNews

QNews