普通hash算法可以对请求和服务器进行映射,达到降低服务器负载的作用.但是普通hash 算法在增加或者删除一个节点后,需要对大部分的节点进行重新映射,避免来自同一请求分布在不同的服务器上.
通过使用一致hash可以在增加或者删除节点时只更新部分映射,避免服务器长时间不可用的状态.
一致性hash算法将整个hash值空间映射为一个虚拟的圆环,整个hash 空间的取值范围为0-2^32 -1.整个空间按照顺时针顺序分布.
一致hash 将每个对象映射到圆环上的一个点,系统再将可用的节点机器映射到圆环的不同位置.查找某个对象对应的机器时,先通过一致hash算法查找对象对应圆环的位置,沿着圆环边上查找直到遇到某个节点机器,这台机器即为保存对象的位置.
当删除一个节点时,这台节点上的所有值都要移动到下一个节点. 添加一台机器到圆环边上某个点时,这个点的下一台机器需要将这个节点之前对应对象移动的新机器上.更改对象在节点机器上的分布可以通过调整节点机器的位置来实现
针对基础一致性 hash 的缺点一种改进算法是引入虚节点(virtual node)的概念。这个本质的改动:值域不再由物理节点划分,而是由固定的虚拟节点划分,这样值域的不均衡就不存在了。
[参考资料]
[1].https://zh.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C
[2].https://liqingqiya.github.io/hash/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C/%E7%AE%97%E6%B3%95/%E5%88%86%E5%B8%83%E5%BC%8F/2020/05/11/dht-hash.html
[3].https://www.toptal.com/big-data/consistent-hashing