一致性哈希算法

落日映苍穹つ 2021-08-19 13:46 510阅读 0赞

### 一致性哈希算法 ###

*  一、为什么使用一致性哈希算法
 *  二、一致性哈希算法
 *  三、哈希偏斜

# 一、为什么使用一致性哈希算法 #

在 Redis 分布式锁中，我们通过部署多台 Redis 的 Master 服务器解决Redis 的主从架构分布式锁失效的问题，详情请看[Redis 分布式锁][Redis] 。

使用多台Redis Master 服务器部署的集群，好处除了可以解决分布式锁的问题，还可以提高并发性能，避免缓存雪崩。

考虑如下一种场景，当我们需要将一张图片缓存到Redis 服务器中，可以这样做。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]

通过如下计算后，`hash(图片) % (Redis Master 的个数)`，计算的余数便是我们要缓存的服务器。

但是如果我们要临时增加服务器的数量该怎么办呢，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]  
        此时如果我们还是按照刚才的算法计算的话，那么就会出现在缓存中找不到数据，而导致大量请求访问数据库，造成数据库的宕机。比如说，如果有一张图片的 hash 值为5，那么我们按照没有增加服务器时，其应该被缓存到 s2中。而增加服务器后，计算出其应该被缓存到 s1 中，但是s1中并没有实际缓存，从而导致去数据库查询。

由此便产生了一致性哈希算法。

# 二、一致性哈希算法 #

首先，存在这样一个环，其叫做 hash 环，由 2^32 个点组成，我们首先通过通过 Redis 服务器的编号，将其映射到 hash 环上，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]  
       接着，对于要缓存的图片，我们可以使用相同的公式计算其被缓存到hash环中哪一个点上，如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]  
       那么此时我们需要确定图片应该被缓存到哪一台服务器中，只需要沿顺时针查找，碰到的以一个服务器便是我们要缓存的服务器。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]  
       假设此时我们增加以他服务器 S4 之后，按照我们刚才的算法，继续计算，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]  
       此时，如果我们寻找 a.png 后，将去新增加的 s4 中进行缓存，但是可以很明显看到，b.png、c.png 对应的服务器并没有发生变化，所以相较于我们一开始的那种算法，这种方式只是造成一小部分缓存无法访问，大部分缓存依然可以访问，更加容易避免缓存雪崩。

# 三、哈希偏斜 #

在一开始的图中，我们将三台服务器均匀的分布在 hash 环中，但是实际上，很可能存在如下一种情况，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 7]       这种情况便是哈希偏斜，由 S1 来承担大部分的缓存压力，当 s1 发生宕机时，依然有可能导致缓存雪崩。

如果要避免这种情况，那么只能让服务器尽可能的多，但是由于项目实际并不需要特别多的缓存服务器，所以我们可以增加一层虚拟节点。

所以我们可以给每台缓存服务器增加若干台虚拟节点，如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 8]       由此，当我们计算图片被缓存的服务器时，首先计算可以寻找对应的虚拟节点，然后通过虚拟节点找到对应的真实节点即可。

[Redis]: https://blog.csdn.net/wang_zhao_/article/details/103205855#
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/d8faae42ed5348f6b96e2551aa37b9af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 1]: /images/20210813/8b7ba736a4254b65ae981f5b093f0e05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 2]: /images/20210813/a4da2a63b6b849cb90e56b91d246aaf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 3]: /images/20210813/eeafed00f0904e3098f02475e1dc4f65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191122231907988.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 5]: /images/20210813/183cbf860edf410781307c2e7a46397d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 6]: /images/20210813/04f8a65e3969463fb084c0a7c5ea0ae9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 7]: /images/20210813/53bab0292fbe43ed8d39bcce7cbc4993.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70 8]: /images/20210813/122e54d269d940efacd7c6970708a93e.png