微信号:talk_about_internet

介绍:互联网架构师成长之路.

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

2018-08-07 21:40 owen

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

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

算法内容

 
           
  1. int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {

  2.    int64_t b = -1, j = 0;

  3.    while (j < num_buckets) {

  4.        b = j;

  5.        key = key * 2862933555777941757ULL + 1;

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

  7.    }

  8.    return b;

  9. }

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

满足算法的要求:

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

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

适用场景

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

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

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

本质

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

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

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

分析

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

我们先构造一个函数,

 
           
  1. ch(key, num_buckets)

  2. 表示有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)要移动。

 
           
  1. int ch(int key, int num_buckets) {

  2.    random.seed(key) ;

  3.    int b = 0; // This will track ch(key, j +1) .

  4.    for (int j = 1; j < num_buckets; j ++) {

  5.        if (random.next() < 1.0/(j+1) ) b = j ;

  6.    }

  7.    return b;

  8. }

  9. //代码中的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))

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

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

  3. 所以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

  4. 对于任意的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)

代码可改写为

 
           
  1. int ch(int key, int num_buckets) {

  2.    random.seed(key

  3.    int b = -1; // bucket number before the previous jump

  4.    int j = 0; // bucket number before the current jump

  5.    while (j < num_buckets) {

  6.        b = j;

  7.        r = random.next();

  8.        j = floor((b + 1) / r

  9.    }

  10.    return = b;

  11. }

假设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的要求不高,不用做转换。

 
           
  1. 参考:

  2. https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf


 
架构学而思 更多文章 改变对思考的想法——读《快思慢想》 关于排期的思考 【思考】一致性hash切分环的问题 三门问题的解释和程序验证
猜您喜欢 【架构合集】ArchSummit独家汇聚的各巨头技术智慧 视频下载器你知道吧?那你听说过文章下载器吗?Python来实现! 田螺汉子 【重磅】人人都熟知的夏普率,如何切实帮助我们提高投资管理水平呢? 谷歌的骄傲,骄傲的谷歌