一致性Hash算法

发表于 更新于 分类于

一致性hash 算法

hash环

一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环。

假设某哈希函数H的值空间为0- \(2^{32}-1\)（即哈希值是一个32位无符号整形），整个哈希环如下：

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到\(2^{32}-1\)，也就是说0点左侧的第一个点代表\(2^{32}-1\)， 0和\(2^{32}-1\)在零点中方向重合，我们把这个由\(2^{32}\)个点组成的圆环称为Hash环。

服务器hash， 例如ip或主机名，获得hash环位置

1

使用同样hash算法计算来确定数据落到的hash环位置，“顺时针”找到第一台服务器

2

容错和可扩展性

删除服务器C

如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响，如下所示：

新增服务器X

增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

数据倾斜问题

当节点太少时，分布不均导致数据倾斜

Action:

增加虚拟节点 - 即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。

Reference

什么是一致性Hash算法？

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