一致性hash切分环的问题

在《了解一致性hash算法》中介绍了一致性hash ring的实现算法。

但是切割hash环的时候,遇到一个思考题:

在数字环上随机落N个点,把环切分成N个区间,原点要算一个切分点吗?如果算,就只产生N-1个随机数就可以了,如果不算,要产生N个随机点。

image

为什么会产生这个疑问?如上图,把hash用三个绿色点分割了三段。如果把环从蓝色的0点打开,变成右边的直线。直线被分成了四段。随机分割直线四段,肯定用右边的方法,为啥切割hash环就用左边的方法呢?

最终owen认为,还是要把0点当作一个已经切分过的node来处理,因为每次产生的随机数,都是按照右边展开的直线的空间来落点,分割直线的。环只是一个让人容易理解的模型,真正实现时还是按照一维来生成随机点的。否则,跨过0点的区间段,会是其他区间的二倍。

在工程实践中,为什么也没发生不均匀的问题,用的好好的呢?

有两个原因:

一、引入了虚节点,分割的区间太多,即使跨0点有两个区间段,也在程序接受的误差范围内。

二、由于是随机落点,分割的区间段大小不一,检测程序也会控制各实节点间的误差符合项目要求。

顺便说一下,把0点作为一个已切分的点还有个好处:不用特别考虑跨0区间key的归属情况,程序容易写。

总结

把零点算作一个node,产生N-1个节点切分hash环;

实际切分的区间是否均匀,要靠检测程序来检查,不能只依赖理论推断。



转载请注明来源:一致性hash切分环的问题
欢迎收听公众号

发表评论

电子邮件地址不会被公开。 必填项已用*标注