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

小鱼儿 2023-01-23 06:50 157阅读 0赞

#### 为什么会用到哈希？ ####

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

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

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

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

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

思考一下，上面这样做有什么问题？

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

**怎么解决？**

采用一致性哈希算法。

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

**哈希函数**为：`hash（服务器A的IP地址） % 2^32`

第一步：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
**第二步:**

将缓存通过新的哈希函数：**hash（文件名称） % 2^32**，映射一下

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

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

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

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

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

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

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

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

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

#### 参考 ####

https://www.zsythink.net/archives/1182

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221004/ddb3a1c0743e452ab289459502869d67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 1]: /images/20221004/837b5d07e5da4532a5708d2dcfa131e1.png