一致性哈希
背景
为了实现横向扩展,在服务器之间高效和均匀地分配请求/数据是很重要的。如果你有n个服务器,常见的平衡负载的方法是使用如下哈希方法:
若一个服务器下线,服务器池的大小就变成了3,使用同样的哈希函数,对于同一个键,我们得到的哈希值不变,但是求余操作会发生改变,这就会导致数据分布不均匀。
一致性哈希
如果一个哈希表被调整了大小,那么使用一致性哈希,则平均只需要重新映射k/n个键,这里k是键的数量,n槽的数量。
基本步骤
- 使用均匀分布的哈希函数将服务器和键映射到哈希环上
- 要找出某个键被映射到了哪个服务器上,就从这个键的位置开始顺时针查找,直到找到哈希环上的第一个服务器。
好处
- 添加或移除服务器时,需要重新分配的键最少。
- 保证更容易横向扩展,数据分布更均匀。(引入虚拟节点)
- 减轻了热点key问题。(引入虚拟节点)
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.