Skip to main content

Consistent Hashing 一致性哈希

info

参考来源 花花酱 - CS 大讲堂 EP17

如有侵权，立即删除

1. 传统 Hashing​

Properties of a good hash function​

  • Uniformity 均匀性。即尽可能将 key 均匀地分布在 bucket里面
  • Deterministic 确定性。无论计算多少次结果必须都一样
  • Efficiency 高效性。至多在 O(n) 时间内完成

如果将 bucket 换成 server​

  • 如果 server size 是固定的话，分布是相对均匀的。如果此时我们 server的 load 比较大，我们希望增加server的数量，hashmode由 3 变成了 4，导致我们之后的 key 都会被 map 到与先前不同的机器上去，会增加很多 network 的工作量。这是非常不好的实现

2. Consistent hashing​

Basic Technique

  • Ring-based
  • Evenly place servers onto a ring
  • Keys are assigned to the next server in clockwise
  • Each server takes 1/n of the circle
  • 通过二分查找来找到下一个节点，即 O(logN)时间

新增节点​

即向集群中添加一台新机器

  • 可以看到 0, 3, 7都被分配到原来的 key上，只有5 remap 到新的key

删除节点​

  • 删除节点 server 3之后，server 1的范围占到了 4-8，5的 key会被 map 到下一节点即server 0
  • 后果是下一节点的 load 可能会大幅度增加，甚至翻倍
  • 做 redistribution 让分布更加均匀

Time Complexity​

OperationClassic hash tableConsistent hashing
Add a nodeO(k)O(K/N + logN)
Remove a nodeO(k)O(K/N + logN)
Add a keyO(1)O(logN)
Remove a keyO(1)O(logN)