一致性哈希.md

一致性哈希

为了保序和充分利用缓存，我们通常希望相同请求 key 的请求总是会被分配到同一个服务节点上，以保持请求的一致性，既有了一致性哈希的调度方式。

• 割环法

  割环法将 N 台服务节点地址哈希成 N 组整型值，该组整型即为该服务节点的所有虚拟节点，将所有虚拟节点打散在一个环上。

  

  请求分配过程中，对于给定的对象 key 也哈希映射成整型值，在环上搜索大于该值的第一个虚拟节点，虚拟节点对应的实际节点即为该对象需要映射到的服务节点。

  代码实现

---

• Jump Consistent Hash

  跳跃哈希 jump consistent hash是由谷歌发明的一致性哈希算法，这个算法的牛逼之处在于，相比传统的环形一致性哈希，空间复杂度更低，根本无内存占用，而且算法非常简洁。计算复杂度为O(logn) 空间复杂度为O(1)。

  int JumpConsistentHash(unsigned long long key, int num_buckets) 
  {
      long long  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;
  }
  

优点：

1. 当桶的数量从 N − 1 增加至 N时, 有 1 / N 的映射结果发生改变。

缺点：

1. 每个节点的权重相同

2. 仅支持在槽位尾端增加或删除节点

更多细节：

https://luyuhuang.tech/2021/06/13/jump-consistent-hash.html

https://zhuanlan.zhihu.com/p/104124045