數據庫中間件分片算法之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