一致性哈希算法
一致性哈希算法
- 一、为什么使用一致性哈希算法
- 二、一致性哈希算法
- 三、哈希偏斜
一、为什么使用一致性哈希算法
在 Redis 分布式锁中，我们通过部署多台 Redis 的 Master 服务器解决Redis 的主从架构分布式锁失效的问题，详情请看[Redis 分布式锁][Redis] 。使用多台Redis Master 服务器部署的集群，好处除了可以解决分布式锁的问题，还可以提高并发性能，避免缓存雪崩。考虑如下一种场景，当我们需要将一张图片缓存到Redis 服务器中，可以这样做。
通过如下计算后，`hash(图片) % (Redis Master 的个数)`，计算的余数便是我们要缓存的服务器。但是如果我们要临时增加服务器的数量该怎么办呢，如下图所示：
此时如果我们还是按照刚才的算法计算的话，那么就会出现在缓存中找不到数据，而导致大量请求访问数据库，造成数据库的宕机。比如说，如果有一张图片的 hash 值为5，那么我们按照没有增加服务器时，其应该被缓存到 s2中。而增加服务器后，计算出其应该被缓存到 s1 中，但是s1中并没有实际缓存，从而导致去数据库查询。
由此便产生了一致性哈希算法。
二、一致性哈希算法
首先，存在这样一个环，其叫做 hash 环，由 2^32 个点组成，我们首先通过通过 Redis 服务器的编号，将其映射到 hash 环上，如下图所示：
接着，对于要缓存的图片，我们可以使用相同的公式计算其被缓存到hash环中哪一个点上，如下所示：
那么此时我们需要确定图片应该被缓存到哪一台服务器中，只需要沿顺时针查找，碰到的以一个服务器便是我们要缓存的服务器。
假设此时我们增加以他服务器 S4 之后，按照我们刚才的算法，继续计算，如下图所示：
此时，如果我们寻找 a.png 后，将去新增加的 s4 中进行缓存，但是可以很明显看到，b.png、c.png 对应的服务器并没有发生变化，所以相较于我们一开始的那种算法，这种方式只是造成一小部分缓存无法访问，大部分缓存依然可以访问，更加容易避免缓存雪崩。
三、哈希偏斜
在一开始的图中，我们将三台服务器均匀的分布在 hash 环中，但是实际上，很可能存在如下一种情况，如下图所示：
这种情况便是哈希偏斜，由 S1 来承担大部分的缓存压力，当 s1 发生宕机时，依然有可能导致缓存雪崩。
如果要避免这种情况，那么只能让服务器尽可能的多，但是由于项目实际并不需要特别多的缓存服务器，所以我们可以增加一层虚拟节点。所以我们可以给每台缓存服务器增加若干台虚拟节点，如下所示：
由此，当我们计算图片被缓存的服务器时，首先计算可以寻找对应的虚拟节点，然后通过虚拟节点找到对应的真实节点即可。
我不是女神ヾ
╰+哭是因爲堅強的太久メ
今天药忘吃喽~
亦凉
我会带着你远行
太过爱你忘了你带给我的痛
还没有评论，来说两句吧...