Java教程

聊一聊 什么是一致性哈希算法

本文主要是介绍聊一聊 什么是一致性哈希算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

为什么会用到哈希?

假如有3GB缓存数据,想要分摊到三台服务器上,如果直接1GB放一台这样做,那么当以后需要查询数据时,是需要遍历三台服务器的所有缓存数据,这样很慢。

我们不妨在分摊的时候,使用哈希进行散列分摊,在查询的时候,进行的同样的操作,就能很快的达到我们想要的效果。

很多类似的场景,都是需要哈希O(1)的查找时间复杂度的。

我们可以设置哈希函数hash = 文件编号%3,给三台服务器分别编号0,1,2 根据哈希结果分别放到这三台服务器上。

上述有什么缺陷?进一步改善

思考一下,上面这样做有什么问题?

  • 假如公司预算增加、业务需求扩展,服务器决定增加到5台,如果还想接着用上面的哈希方法,那么原来三台上的数据都是需要去再次hash的。
  • 再比如,某台服务器挂掉,那么三台服务器的哈希查找特性都会丢失,缓存全部失效,对系统的影响巨大。

怎么解决?

采用一致性哈希算法。

一致性哈希算法本质也是使用哈希表取模的思想,不同的是,前面是对服务器的数量进行取模,一致性哈希算法是对2^32进行取模。

哈希函数为:hash(服务器A的IP地址) % 2^32

第一步:

将三台服务器的IP地址按照上面的哈希函数分别进行计算,计算结果一定是在0-2^32之间的数,考虑到“取模”运算的性质,完全可以把哈希结果看成是一个环,因为线是由点组成的嘛

在这里插入图片描述
第二步:

将缓存通过新的哈希函数:hash(文件名称) % 2^32,映射一下

假如某缓存映射后如下图左下角的红色标记所示,那么代表该文件是需要放到B服务器缓存的,因为它沿顺时针方向遇到的第一个服务器就是B服务器的。
在这里插入图片描述
第三步:

当下次想要访问该缓存时,再次使用相同的算法进行计算,便可以找到该缓存是在哪个服务器。

前面说了一致性哈希算法是怎么用的?

言归正传,为什么能解决我们刚才说的场景问题?

首先我们要注意,一致性哈希算法,哈希结果看作是一个环,这是理解问题的关键。

再重述下刚才的情景:
1.三台服务器=》五台服务器,导致之前hash处理过的三台服务器上的文件数据全都丧失哈希查找的特性,需要重新hash

对于这种情况,可以看成环多了几个服务器结点,原有的并不会变,而新缓存则会逐步分摊到五台服务器上。

2.三台服务器=>两台服务器,即有一台服务器B宕机,缓存全部失效。

对于这种情况,原本属于B的缓存会被缓存到其他的缓存服务器,而其他没问题的则与以前一样,不需要rehash

这篇关于聊一聊 什么是一致性哈希算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!