2020-01-09

Jump Consist...

大三一个课的小作业，做得小调研

Consistent Hash就是为了解决负载均衡的问题，如下图，把不同资源的访问分配的不同的服务器缓解压力；算法就是解决服务器和文件的映射

谈到映射就想到hash；如果你打过acm，就不得不说下面的哈希方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

#define ll long long
#define inf 1 << 30
#define base 233
ll mod = inf;

ll myHash(char s[]){
    ll res = 0, len = strlen(s);
    for(int i = 0; i < len; i++){
        res = (base * res + (ll)s[i]) % mod;
    }
    return res;
}

存在很大的问题就是服务器数量相当于mod，数量有改变mod改变，整个hash就乱套了，于是乎有了Consistent Hash，这里不详细解释，这里讲的是Google的Jump Consistent Hash，8行代码，短小精悍。

1
2
3
4
5
6
7
8
9
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;  
}

这么一看你肯定是懵逼了，我一步步来解释。
这里先令f(key, n)为一致性哈希算法,输出的为[0,n)之间的数字，代表数据在对应的节点上。

1.n=1时，对于任意的key，输出应该都是0。（比如你有1个服务器，那么就是无论如何都是分配到这个服务器上）
2.n=2时，负载均衡，应该有1/2的结果保持为0，1/2的结果输出为1。
3.n=3时，负载均衡，应该有1/3的结果保持为0，1/3的结果保持为1，1/3的结果保持为2。
4.依次递推，节点数由n变为n+1时，f(key, n)里面应该有n/(n+1)的结果不变。
结论：
有1/(n+1)的结果变为n

如下图，有个重要的规律，在某条不跳变的路径上，数值是一样的。

这个使用概率公式来表示，就是这样的代码，于是我们可以得到下面这个ch

1
2
3
4
5
6
7
8
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;  
}

增加一个节点后，一个固定的key输出的结果发生了改变。快速计算出这个固定的key在哪些节点下发生了改变，就可以快速计算出最终答案，就是Jump Consistent Hash的思路。
假设某一次结果是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发生变化的节点数量，由此可以得出下面的代码

1
2
3
4
5
6
7
8
9
10
11
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;  
        double r=random.next(); //  0<r<1.0  
        j = floor( (b+1) /r);  
    }  
    return b;  
}

由于r是均匀的，所以期望是1/2。
这样，代码中j就是按照指数级增长的，平均复杂度就是O(log(n))了。

回头看看第一个代码，就可以看懂代码了。

第一个key=key*x+1算是一个伪随机生成器。
而j=(b+1)*x/y则是上面的求上界的公式，其中y/x通过浮点数运算来产生(0,1)内的一个随机数。

我们可以发现一开始的代码是没有random. seed的，因为用了线性同余

haoboxuxu

haoboxuxu

Hello, World!