分布式缓存应用场景

假设 3 台缓存服务器，s0,s1,s2

需要将图片均匀缓存到 3 台服务器上，最简单的方式是 hash 计算并取模判断属于哪个服务器

hash(唯一标识) % 机器数量 = 0/1/2

相同标识进行哈希计算的值是不变的，所以可以将图片缓存到各个节点上。

但是有一个缺点，假设新增了一个服务器，机器数量发生了变化，余数就会不同，此时在读取缓存数据就会抛错节点。

一致性哈希

假设有个哈希环，由 2^32 个点组成

假设有 3 台服务器，根据服务器的编号 hash 并对 2^32 取模

将被缓存的图片也映射到哈希环上，从图片的位置开始，顺时针查找，遇到的第一个节点服务器，就是缓存服务器。

如果新增了服务器，先映射到哈希环上，按照顺时针会找到新服务器。

但有一个问题，哈希偏斜，即 0/1/2 三台服务器在哈希环的位置相近，缓存不均匀，可能大量缓存在 1 个服务器上，最好是服务器越多越均匀，增加虚拟节点。

例如 a 节点，引入 a1,a2,a3…an 虚拟节点，这样就会在哈希环上分布比较均匀，先找到虚拟节点，再找真实节点。

最高随机权重 Highest Random Weight

• 每个 key 和每个节点组合计算 H(key:node)，得分最高者胜
• 因为哈希函数对不同输入均匀输出，所以每个节点"赢"的概率天然相等
• 不需要环、不需要虚拟节点、不需要排序查找

代价： 选节点时需遍历所有节点算分，复杂度 O(N)。一致性哈希是 O(log N)。节点数少（< 几百）时无感知差异，节点上千才需要权衡。

可使用 splitmix64 终混器，全部打散，防止过于集中某个节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func splitmix64(x uint64) uint64 {
	x += 0x9e3779b97f4a7c15
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
	x = (x ^ (x >> 27)) * 0x94d049bb133111eb
	return x ^ (x >> 31)
}

// hrwScore 计算节点对卡的 HRW 得分。
func hrwScore(nodeID, phone string) uint64 {
	h := fnv.New64a()
	h.Write([]byte(nodeID))
	h.Write([]byte{':'})
	h.Write([]byte(phone))
	return splitmix64(h.Sum64())
}