分布式系统中的算法设计（一） -- 一致性 Hash

Hash 大家都知道，把某个要存储的内容的索引 key 通过某个规则计算一下，算出来一个值，这个值往往范围比原来小，且概率意义上不会冲突。

由于 Hash 计算复杂度往往比查找要快，被大量应用到各种大规模的系统中，特别是分布式系统。具体实践中有几个典型的问题。

问题来源

一致性 Hash 讨论地已经很多，基本故事就是分布式存储系统中，通过 Hash 来决定内容存到哪个节点上。

典型的比如 cache 系统，后面放若干节点，查找某个 key，hash 到某个节点，再进一步检索。

最简单的自然是按照节点数量取个模，理想状态下不会有啥问题。

但是如果发生如下情况，就无法正常工作了。 加节点（一般是有计划的） 减节点（可能突然故障，无法预知）

所以提出了一致性 hash，即考虑如下四个方面的算法： 平衡性(Balance)：哈希结果尽可能分布到所有的节点，这样可以使得所有的节点都得到利用； 单调性(Monotonicity)：加入新的节点后，已经分配节点的 hash 结果 被映射到原有的或者新的节点上去，而不会被映射到其他节点； 分散性(Spread)：同样内容尽量避免 hash 到不同节点； 负载(Load)：不同内容避免 hash 到同样节点。

简单的说，就是有一个算法，首先分配尽量均匀，其次，当节点个数变化的时候，尽量维持原来内容的映射，并进行局部调整。

能满足的算法有很多，这里介绍两个比较经典的。

基于环的实现

该算法最初于 1997 年在论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web 中提出。算法复杂度为 O(log(n))。

主要设计思想为：构造一个环（顺序标上编号比如 0 ~ 2^32-1），将已有节点编号并分配到这个环上，分割环为不同的段。

对每个内容，hash 后是一个独一无二的数字，这个数字肯定会落入某个段上，按照固定方向往前找到的第一个节点编号即为要分配到的节点。

考虑两个相邻的节点 A 和 C，如果要在中间添加一个节点 B，那么 AB 段上内容会从 C 节点重新分配到 B 节点。反之，如果删除掉 B 节点，那么 AB 段上内容会再次分配到 C 节点上。

这种算法很好的满足性质 2-4，唯独平衡性没有解决。即当节点个数不多的时候，内容可能会集中在某些段，划分到部分节点上。要解决这个问题也很简单，把一个节点虚拟为多个虚节点，提高整体节点个数，然后再分散放到环上。这样就提高了平衡性。

基于概率转移的实现

该算法最初于 2014 年在论文 A Fast, Minimal Memory, Consistent Hash Algorithm 中由 Google 工程师 John Lamping 和 Eric Veach 提出。算法复杂度为 O(log(n))。

主要设计思想为：假设原先有 n 个节点，新加上一个节点后，每个 key 都有 1/n+1 的概率转移到新的节点上，n/n+1 的概率留在原先分配的节点。

举个例子，原先有 1 个节点，再加一个节点，那么已有内容有 1/2 的概率跳转到到第二个节点。原先有 2 个节点（每个里面有 1/2 的内容），再加一个节点，则已分配内容应该有 1/3 的概率转移到新的节点。

一个简单的实现代码为：

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 生成 num_buckets-1 个（0~1.0）的伪随机数，依次检查随机数序列：

• 第一个随机数 <1/2，则放第二个节点；
• 第二个随机数 <1/3，则放第三个节点；
• ...

注意伪装随机数序列由 key 唯一确定。意味着同样的内容在多次分配中，分配结果将是一致的。

另外，可以计算出如果当前分配为 b，下一个结果 j >= i 的概率（即 b+1 到 i-1 的过程都不发生跳变）

P(j>=i) = (b+1)/i

最终优化为如下代码：

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;
}

这个算法依赖于伪随机算法的输出，特点有： 分布均匀性由伪随机算法决定，而跟 key 自身均匀性无关，实践均匀性远好于基于环的算法； 不需要对 key 进行计算，复杂度低，实践计算时间也比基于环的算法好。

算法没解决的问题：当中间减掉节点的时候，序号会发生变化，变为 0...n-1。因此需要在外面维护一个映射关系，动态映射到原先的节点上。