一致性哈希 Consistant Hash

2013 年 06 月 26 日

在动态变化的 cache 环境中,hash 算法应该满足4个适应算法:

  • balance, 尽量做到负载均衡.

  • monotonicity, 当 cache 节点变化时, 保护已分配的内容不重新 mapping, 当然, 只能是尽量, 因为没有办法完全做到, 不然这个 cache 节点就没有存在的意义了.

  • spread, 当 cache 节点不是完全可见时, 会导致相同的内容 mapping 到不同的节点中去, 这就是 spread, 要尽量避免这种情况.

  • load, 是指每个 cache 节点的负载要尽量低.


大规模的分布式 cache 系统中, key-value 如何做 hash?

  • 最常规的莫过于 hash 计算得到一个整数再取模.

  • 在 cache 节点变化的时刻, 会导致大量的 cache 不命中, 需要重新建立 mapping 关系, 这显然不是个好主意.


Consistant Hash 的原理

选择具体的 cache 节点不再只依赖于 key 的 hash 计算, cache 节点本身也参与了 hash 计算. 参考文章: Consistant Hash and Random Trees.

Consistant Hash 带来了什么?

在移除, 添加一个 cache 时, 它能够尽可能小的改变已存在 key 映射关系, 尽可能的满足 monotonicity 的要求.


计算步骤

  1. 将整个哈希值空间组织成一个虚拟的圆环, 如假设某哈希函数H的值空间为[0, 2^32-1], 即哈希值是一个32位无符号整形, 整个空间按顺时针方向组织, 0和[2^32-1]在零点中方向重合.
  2. 对各个 cache 节点进行 hash, key 可以参考 ip + 节点名, 并落在圆环上.
  3. 对于数据 key 做相同的 hash 计算, 并确定在圆环上的位置, 从此位置顺时针“行走”, 遇到的第一个 cache 节点就是 mapping 到的节点.

容错性与扩展性分析

  1. 某个 cache 节点宕机时, 只有该节点到它之面的第一个节点中间的数据受影响, 需要做 remapping.
  2. 当增加 cache 节点时, 也只有该节点和它之前的第一个节点中间的数据受影响, 需要做 remapping.

简单的C代码参考(因为是链表组织的, 所以效率一般, 只做简单参考):

``` C
typedef struct conhash_t
{
    struct list_head node_list;
    hash_func key_hash;
    hash_func node_hash;
} conhash_t;

#define CONHASH_NODE_NAME_SIZE 128

struct conhash_node_t
{
    struct list_head link;
    void* data;
    uint32_t hash_value;
};

void* conhash_node(conhash_t* ch, void* key)
{
    uint32_t val;
    struct conhash_node_t* n;
    struct list_head* l;
    if (!ch || !key) return NULL;
    if (list_empty(&ch->node_list)) return NULL;

    val = ch->key_hash(key);
    list_for_each_entry(n, struct conhash_node_t, &ch->node_list, link) {
        if (n->hash_value >= val) return n->data;
    }
    l = ch->node_list.next;
    n = list_entry(l, struct conhash_node_t, link);
    return n->data;
}
```