今天是这一系列分片算法的完结篇。今天介绍的算法美如画,谷歌工程师仅仅用了5行代码就解决了一个大问题。可见写代码这件事不在多,而在于精。算法真的可以改变世界。
1.hash分区算法
2.stringhash分区算法
3.enum分区算法
4.numberrange分区算法
5.patternrange分区算法
6.date分区算法
7.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。
在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越来越大,它所变化的概率也就越来越低。
接下来我们来详细测试一下。
在启动dble之后,就会读取rule.xml文件,加载上述配置。然后根据partitionCount产生物理分区表。
如果有用户通过where查询name='buddy'的时候,就会访问jumpstringhash分片算法,首先根据配置的hashSlice进行截取,这里hashSlice0,3会把bud截取出来,然后在对这个截取的字符串做hash值。然后把hash值作为key,partitionCount作为bucket传到jumpConsistentHash函数中。计算出最终一致的hash值。
<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>
<table name="test_jumphash" primaryKey="id" rule="rule_jumpHash" dataNode="dn1,dn2,dn3,dn4"/>
[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
可以发现,我们插入的数据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
今天介绍了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
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。