Aione's blog

一起快乐摸鱼吧🐳

  1. 1. 一致性 hash
  2. 2. 原理

在 MapReduce 里,我们要把 map worker 得到的 kv 对平均分配到 wroker 到磁盘,如果分配不均匀,就会降低总体性能。如果使用普通的 hash 算法,那么分配的均匀性依赖与算法的均匀性,并且一旦 worker 数量发生改变,我们要进行大规划的 rehash,会造成大批量的数据移动。这时我们就需要一致性 hash。

一致性 hash

一致性 hash 的目标就是,当 hash slot 数目发生改变时,需要 rehash 的数目尽可能小并且尽量保证数据分配的平均。

wiki\
一致哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

原理

一致性 hash 将 hash 的值域看作一个环,根据 key 的 hash 值选择环上的节点,这样,当有新的节点添加到环上时,只需要对相邻节点的 key 进行 rehash 就可以解决问题。
image.png

这样会引入一个新的问题,如果节点在环上分配不均匀,会导致 hash 偏移,会使某个节点的负载过重,这种情况下,我们引入虚节点。

image.png
当我们创建hash环的时候,首先在环上平均分配虚拟节点,当有服务器加入的时候,分配给该服务器虚拟节点,通过将hash分配和具体的服务器解耦合达到均衡负载的目的。在这种情况下,如果有节点离开或者加入,我们只需要将该虚拟节点重新分配出去或者给新服务器分配虚拟节点即可。

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.space/2020/09/10/consistent-hashing/

This article was last updated on days ago, and the information described in the article may have changed.