您好,登录后才能下订单哦!
这篇文章主要介绍“Java一致性哈希算法举例分析”,在日常操作中,相信很多人在Java一致性哈希算法举例分析问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java一致性哈希算法举例分析”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
google 有一个 Jump consistent hash 算法,可以通过数学运算做到和一致性哈希效果一样好的平衡性。
先看代码,下面就是全部的代码。
是不是感觉不可思议,这个代码的语法全部都懂,但是合在一起我们就看不懂了。
我第一眼看到这个代码的时候,也是一脸懵逼的。
这个算法是 Google 的 John Lamping 和 Eric Veach 创造的。
一致性哈希算法有两个目标:
平衡性。即把数据平均的分布在所有节点中。
单调性。即节点的数量变化时,只需要把一部分数据从旧节点移动到新节点,不需要做其他的移动。
我们根据这个单调性可以推算出一些性质来。
这里先令f(key, n)
为一致性哈希算法,输出的为[0,n)
之间的数字,代表数据在对应的节点上。
n=1
时,对于任意的key
,输出应该都是0
。
n=2
时,为了保持均匀,应该有1/2
的结果保持为0
,1/2
的结果输出为1
。
n=3
时,应该有1/3
的结果保持为0
,1/3
的结果保持为1
,1/3
的结果保持为2
。
依次递推,节点数由n
变为n+1
时,f(key, n)
里面应该有n/(n+1)
的结果不变,有1/(n+1)
的结果变为n
。
这个使用概率公式来表示,就是这样的代码。
关于这个算法直接看可能还是看不懂。
所以需要使用实际数据模拟一下,见下图。
关键在于n=2
到n=3
的过程,每个数字的概率从1/2
转化到了1/3
。
之后,我们可以得出一个规律:增加一个节点,数据不发生变化的概率是n/(n+1)
再乘以之前每个数字的概率1/n
,就可以得出每个数字最新的概率1/(n+1)
由此,可以轻松计算出n=4
各数字的概率为1/4
。自此,我们可以确定这个算法确实是有效的。
这个算法唯一的缺点是复杂度太高,是O(n)
的。
所以需要进行优化。
在上一小节中,我们了解到f(key, n)
算法的正确性。
除了复杂度是O(n)
外,我们还可以确定,循环越往后,结果改变的概率会越来越低。
结果改变指的是,增加一个节点后,一个固定的key
输出的结果发生了改变。
如果我们能够快速计算出这个固定的key
在哪些节点下发生了改变,就可以快速计算出最终答案。
假设某一次结果是b
,经过若干次概率测试,下一次改变为a
,则从b
到a-1
这中间,不管节点如何变化,这个key
的结果都是不会变化的。
根据上一小节的到的概率变化公式,新增一个节点数字不变化的概率是n/(n+1)
。
那从b
到i
不变化的概率就是b/i
(中间的抵消了)。
如果我们有一个均匀的随机函数r
,当r<b/i
时,f(i)=f(b)
。
那么i
的上界就是(b+1)/r
。
这个上限也是下一次key
发生变化的节点数量,由此可以得出下面的代码。
由于r
是均匀的,所以期望是1/2
。
这样,代码中j
就是按照指数级增长的,平均复杂度就是O(log(n))
了。
回头看看第一个代码,就可以看懂代码了。
第一个key=key*x+1
算是一个伪随机生成器。
而j=(b+1)*x/y
则是上面的求上界的公式,其中y/x
通过浮点数运算来产生(0,1)
内的一个随机数。
自此,这个代码就可以看懂了。
到此,关于“Java一致性哈希算法举例分析”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。