一种快速简洁的一致性哈希算法

在分布式系统路由分配上,一致性哈希算法有很大的优势。在之前的文章中也讲过原理。算法容易理解,但是实现上要注意很多细节,虚节点加入也要消耗更多的存储来维护映射关系。但是今天介绍的jump consistent hash是一种比较新颖的方法,代码简短,内存消耗少。下面我们来详细看看这个算法。

首先我们先了解下这个算法,有个初步的概念。然后看下这个算法适用于哪些场景,有什么作用。最后,详细分析下算法原理。

算法内容

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

以上就是算法的全部代码,输入参数分别是64位的key,桶的数量(一般对应服务器的数量),输出是一个桶的编号(从0开始)。

满足算法的要求:

平衡性,把对象均匀地分布在所有桶中。

单调性,当桶的数量变化时,只需要把一些对象从旧桶移动到新桶,不需要做其它移动。

适用场景

用于分布式存储产品中,而不太适合用在缓存类型的产品。因为有节点不可用时,jumphash用存活节点分担不可用节点的能力不强,会导致分布不均。但是在存储类中,节点都会有主备,主节点不可用路由到备节点,key的分布不会有变化。

适合在分布式系统中,根据key来选择被分配到的服务场景。每次新增新的服务节点,只有1/n的key会变动,不会因为扩容或缩容瞬间
造成大部分缓存失效。

但是也有局限,和其他的一致性hash相比。如果有中间的桶失效,是不能够像割环hash一样,均匀分配到其他节点的,只能找个新替换
节点来取代。但是优点是不用存储,计算量也不大。代码短,易于实现。

本质

利用线性同余计算的固定性,每次输入参数固定,输出就固定的特性,来替代用存储。利用运算,减少存储空间。

由于运算量的优化,比查找存储空间速度更快,所以从时间、空间上算法更优。

引申:有时用运算生成的数字串,映射要存储的空间,会使算法有意想不到的效果。

分析

为什么上面的代码能够实现一致性hash的功能,我们一步一步来看。要实现的功能就是多加一个节点,节点数变为n,只有1/n的key会变动。

我们先构造一个函数,

ch(key, num_buckets) 

表示有num_buckets个桶,一个key的值会分配到的bucket编号[0, num_buckets)。

所以对于任意key,k,ch(k,1)=0,因为只有一个桶。为了让算法平衡,ch(k,2)讲有一半的key留在0号桶中,一半的移到1号桶中。

总结的规律是,ch(k,n+1)和ch(k,n)相比,n/(n+1)的key是不动的,1/(n+1)的key移动到第n号桶。

对于每次新增桶的个数时,计算每个key的新位置,确定是否要移动到新的桶中。

通过随机数生成器,来判定key是否要移动到新的桶中,概率是1/(n+1)要移动。

int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; // This will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j ++) {
        if (random.next() < 1.0/(j+1) ) b = j ;
    }
    return b;
}

//代码中的random.next()产生[0,1)的随机数,随机数序列只和key有关,key为随机种子。

这段代码是满足算法的平衡性和单调性的,算法复杂度是O(N)。满足了正确性,接下来优化性能。

从算法代码可以看出,大多数情况下random.next() < 1.0/(j+1)是不被执行的。

对于一个key来说,ch(key,j+1)的值,很少会随着j增长而变化的。当ch(key,j+1)!=ch(key,j)时,
ch(key,j+1)=j。

//我们假设ch(key,j)是一个随机变量,通过伪随机数,来确定一个数值b,当j增长到b时,ch(key,b)!=ch(key,b-1),
并且ch(key,j)=ch(key,b-1)。

假设一个key的值为k,b为一个跳变的桶数量。则ch(k,b)!=ch(k,b+1),并且ch(k,b+1)=b.

下面寻找下一个比b大的跳变的桶数量j。则ch(k,j+1)!=ch(k,j),ch(k,j)=b,ch(k,j+1)=j。

ch(k,b+1)=b

ch(k,j)=b,

ch(k,j)=ch(k,b+1)

ch(k,j+1)=j

ch(k,b)!=ch(k,b+1)

ch(k,j+1)!=ch(k,j)

所以,我们已知k,b时,要找到j,对于(b,j]区间的变量i,如果不发生跳变,必须满足
ch(k,i)=ch(k,b+1)。

所以有概率

P(j>=i) = P(ch(k,i)=ch(k,b+1))

先举几个例子P(ch(k,10)=ch(k,11))的概率是10/11,

P(ch(k,11)=ch(k,12))的概率是11/12,

所以P(ch(k,10)=ch(k,12))的概率是P(ch(k,10)=ch(k,11))*P(ch(k,11)=ch(k,12))=(10/11)*(11/12)=10/12

对于任意的n>=m,P(ch(k,n)=ch(k,m))=m/n。

所以对于上面的等式,
P(j>=i) = P(ch(k,i)=ch(k,b+1))=(b+1)/i。

假设一个随机数r在(0,1)区间,由k和j确定。

如果r<=(b+1)/i,那么P(j>=i)=(b+1)/i为不跳变。
那么产生随机数r后,就能确定i的最小值为(b+1)/r。
因为r<=(b+1)/i => i<=(b+1)/r.

又因为i是整数,所以有
r!=0

i=floor((b+1)/r)

代码可改写为

int ch(int key, int num_buckets) {
    random.seed(key);
    int b = -1; // bucket number before the previous jump
    int j = 0; // bucket number before the current jump
    while (j < num_buckets) {
        b = j;
        r = random.next();
        j = floor((b + 1) / r);
    }
    return = b;
}

假设r的期望为0.5,时间复杂度为Olg(N)。
这个算法有点绕,通过随机数的产生来判定下一跳的j,优化算法,保证在整体key的跳变满足增加桶数为n+1时,只有1/(n+1)的数据移动。

我们再看

key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));


r = random.next();
j = floor((b + 1) / r);

有什么关系。

利用线性同余算法产生一个64位的整数,然后通过映射到(0,1]区间的小数。

(key>>33)+1是取key值的高31位的值再加1,范围为(1,2^31+1)
1LL<<31的值为2^31。

所以
[(key>>33)+1]/1LL<<31 的取值范围是(0,1],如果(key>>33)=2^31那么会大于1,由于是c的整数运算,大于1也会取证忽略掉小数部分。

总结

该算法的精髓:通过随机种子产生随机数,减少存储;利用概率和随机数,确定key在bucket_num范围内落在的桶序号。

既减少了运算量,也易于实现,对于存储类路由非常适合,而且key的分散性不依赖key本身,只依赖随即生成器,对key的要求不高,不用做转换。

参考:
https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf
https://blog.helong.info/blog/2015/03/13/jump_consistent_hash/

欢迎收听公众号

发表评论

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