这是一个来自Google的零内存消耗、均匀、快速、简洁的一致性哈希算法 – Jump Consistent Hash
算法的作者是Google的John Lamping和Eric Veach，论文原文链接 – 点这里，一些讨论 – 点这里
整篇文章基于对论文原文的翻译，掺杂自己的一些思想理解，以及对该算法代码的适应场景分析修改，水平有限，难免有偏差：D
一致性哈希(Jump Consistent Hash)算法设计目标
平衡性，把对象均匀地分布在所有桶中。
单调性，当桶的数量变化时，只需要把一些对象从旧桶移动到新桶，不需要做其它移动。
简单理解就是：m个对象，n个桶，每个桶分到的对象应该在m/n个左右，误差不应太大；在桶增加或者桶减少1时，影响到的对象应该也在m/n个左右，其余对象不受影响。
满足这些目标，Jump Consistent Hash的总体设计思路是：计算当bucket数量变化时，有哪些输出需要变化。
直接上代码
int32_t ch(int64_t key, int32_t num_buckets)
{
srand(key);
int32_t b = -1;
int32_t j = 0;
while (j < num_buckets) {
b = j;
double r = rand() / (double)RAND_MAX;
j = floor((b + 1) / r);
}
return b;
}
测试用例与输出
int main()
{
printf("======== bucket 4 =========\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, ch(i, 4));
}
printf("======== bucket 3 =========\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, ch(i, 3));
}
printf("======== bucket 2 =========\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, ch(i, 2));
}
return 0;
}
======= bucket 4 ======= ======= bucket 3 ======= ====== bucket 2 ======
i:20000 b:0 i:20000 b:0 i:20000 b:0
i:20001 b:3 i:20001 b:2 i:20001 b:0
i:20002 b:3 i:20002 b:0 i:20002 b:0
i:20003 b:0 i:20003 b:0 i:20003 b:0
i:20004 b:0 i:20004 b:0 i:20004 b:0
i:20005 b:2 i:20005 b:2 i:20005 b:0
i:20006 b:0 i:20006 b:0 i:20006 b:0
i:20007 b:2 i:20007 b:2 i:20007 b:1
i:20008 b:3 i:20008 b:2 i:20008 b:1
i:20009 b:1 i:20009 b:1 i:20009 b:1
i:20010 b:0 i:20010 b:0 i:20010 b:0
i:20011 b:0 i:20011 b:0 i:20011 b:0
i:20012 b:2 i:20012 b:2 i:20012 b:1
i:20013 b:0 i:20013 b:0 i:20013 b:0
i:20014 b:0 i:20014 b:0 i:20014 b:0
i:20015 b:2 i:20015 b:2 i:20015 b:0
i:20016 b:3 i:20016 b:0 i:20016 b:0
i:20017 b:3 i:20017 b:1 i:20017 b:1
i:20018 b:3 i:20018 b:2 i:20018 b:1
i:20019 b:2 i:20018 b:2 i:20019 b:0
从输出结果来看， 满足了平衡与单调性（这里取得对象数量比较有限，更多的数量会分布更加均匀）。
一致性哈希(Jump Consistent Hash)算法分析
原论文中有大量的概率论证该算法满足平衡与单调性，这里直接忽略，我会撇开概率相关的东西说说我对它直观的理解。
代码的核心部分，srand(key)与rand()。这里一个使用线性同余方法产生伪随机数的接口。他的特点是，一旦key确定，那么在这个接口调用里使用rand()产生的随机数必然是相同的。关于线性同余的原理晚上很多介绍，这里测试验证代码：
int32_t test_rand(int64_t key)
{
srand(key);
printf("1->key:%llu rand:%d\n",key,rand());
printf("2->key:%llu rand:%d\n",key,rand());
}
int main()
{
test_rand(1);
test_rand(2);
test_rand(3);
test_rand(3);
test_rand(2);
test_rand(1);
return 0;
}
1->key:1 rand:1804289383
2->key:1 rand:846930886
1->key:2 rand:1505335290
2->key:2 rand:1738766719
1->key:3 rand:1205554746
2->key:3 rand:483147985
1->key:3 rand:1205554746
2->key:3 rand:483147985
1->key:2 rand:1505335290
2->key:2 rand:1738766719
1->key:1 rand:1804289383
2->key:1 rand:846930886
可以若key一旦确定，那么rand()的伪随机值就是按顺序确定的。这样就保证了，同一个key每次调用ch()后会得到相同的桶索引，除非这个桶索引不在（上例中bucket 4->bucket 3，在bucket 4中b:3的对象会被重新分配）
适用场景分析
比如说我们对于hash桶，存在这样的映射：
0->机器A，1->机器B，2->机器C，3->机器D
当3->机器D从映射表消失后，根据ch()的算法，原来分配到b:3桶的会被重新分配到bucket 0-2。那么问题来了， 若是1->机器B从映射表消失呢？
根据ch()算法，返回还是会重新分配bucket 0-2。那么现在机器映射0,2,3怎么和现在的bucket 0-2对应。外部要维护动态的映射表，实时更新……想想都……
一些小修改
//为测试用例而生的结构体
struct test {
int32_t num;
bool active;
};
int32_t cch(int64_t key, vector<struct test> &v)
{
srand(key);
next:
int32_t b = -1;
uint32_t j = 0;
while (j < v.size()) {
b = j;
double r = rand() / (double)RAND_MAX;
j = floor((b + 1) / r);
}
if (v[b].active) {
return v[b].num;
} else {
goto next;
}
}
active是需要算法外部维护的，标记这个桶是否还在有效状态，有效-true，无效-false。
测试与输出
int main()
{
vector<struct test> v;
for (size_t i = 0 ; i < 4; i++) {
struct test t;
t.num = i;
t.active = true;
v.push_back(t);
}
printf("======== bucket 0 1 2 3 =========\n\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, cch(i, v));
}
v[0].active = false;
printf("======== bucket 1 2 3 =========\n\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, cch(i, v));
}
v[1].active = false;
printf("======== bucket 2 3 =========\n\n");
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, cch(i, v));
}
printf("======== bucket 2 3 8 =========\n\n");
struct test t;
t.num = 8;
t.active = true;
v.push_back(t);
for (size_t i = 20000; i < 20020; i++) {
printf("i:%d b:%lu\n" , i, cch(i, v));
}
return 0;
}
===bucket 0 1 2 3=== ===bucket 1 2 3=== ===bucket 2 3=== ===bucket 2 3 8===
i:20000 b:0 i:20000 b:3 i:20000 b:3 i:20000 b:3
i:20001 b:3 i:20001 b:3 i:20001 b:3 i:20001 b:3
i:20002 b:3 i:20002 b:3 i:20002 b:3 i:20002 b:8
i:20003 b:0 i:20003 b:2 i:20003 b:2 i:20003 b:2
i:20004 b:0 i:20004 b:2 i:20004 b:2 i:20004 b:2
i:20005 b:2 i:20005 b:2 i:20005 b:2 i:20005 b:2
i:20006 b:0 i:20006 b:2 i:20006 b:2 i:20006 b:8
i:20007 b:2 i:20007 b:2 i:20007 b:2 i:20007 b:2
i:20008 b:3 i:20008 b:3 i:20008 b:3 i:20008 b:3
i:20009 b:1 i:20009 b:1 i:20009 b:3 i:20009 b:3
i:20010 b:0 i:20010 b:2 i:20010 b:2 i:20010 b:2
i:20011 b:0 i:20011 b:3 i:20011 b:3 i:20011 b:3
i:20012 b:2 i:20012 b:2 i:20012 b:2 i:20012 b:2
i:20013 b:0 i:20013 b:1 i:20013 b:3 i:20013 b:8
i:20014 b:0 i:20014 b:2 i:20014 b:2 i:20014 b:8
i:20015 b:2 i:20015 b:2 i:20015 b:2 i:20015 b:2
i:20016 b:3 i:20016 b:3 i:20016 b:3 i:20016 b:3
i:20017 b:3 i:20017 b:3 i:20017 b:3 i:20017 b:3
i:20018 b:3 i:20018 b:3 i:20018 b:3 i:20018 b:3
i:20019 b:2 i:20019 b:2 i:20019 b:2 i:20019 b:2
如此一来解决bucket_num与机器唯一映射的问题。付出的代价是：1、在有桶状态变更时，受影响对象重新寻桶的循环次数大约增加0.8倍。2、在桶状态时平衡性会略缺失，这点我没有科学的用概率论证，但是从测试用例结果来看是如此。
（全文结束）
转载文章请注明出处：漫漫路 - lanindex.com
thank u