21 January 2018

取模哈希的问题

假设缓存服务中,通过key定位缓存数据节点为如下公式:

n = HashFunction(key) % N

其中:

  • HashFunction 为hash函数
  • key为缓存Key
  • N为缓存节点数量
  • n为节点编号,范围为 0 ~ (N - 1)

假如N个节点中有任意一个节点宕机,即N数值产生变化,则key对应的数据基本需要重新分布。

一致性哈希

取模哈希设计缺陷在于把N当做真实节点的数量,分母一变,取模后大部分数值都发送变化。如果分母保持不变呢?

一致性哈希稍微做了下变通,把N当做虚拟节点的数量,与物理节点数量无关,是一个定值。假如 N = 2^32-1,hash后的值范围为 0 ~ 2^32-1。

将这个空间划分成N个连续的范围,一个节点负责存储一个范围的数据。划分的范围组成一个环,如果一个节点宕机,则该节点上的数据重新分布到环绕环顺时针旋转的下一个相邻范围。如此保证了尽可能少的数据rehash。