一致性哈希算法(consistent hash)的黑科技

这是一个来自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

Leave a Comment

Your email address will not be published.