面试官问我什么是“一致性哈希算法”，人已经傻了

大家好，我是程序员三金。

在面试中大家可能会遇到这么一个面试题：“你讲一讲什么是一致性哈希算法”,这可不是大多数的Java八股会提前背到的东西，因此大多数人肯定直接懵了。

面试官："好的今天面试就到这里了，你还有什么想问我的吗？"

因此我们这篇文章来向大家介绍一下什么是"一致性哈希算法"。

当我们有多台缓存中间件来缓存数据的时候（比如Redis集群），当一个数据发送过来的时候，我们要面临的一个问题就是：

这个数据要存放在哪台服务器中？

传统的哈希算法采用的是”取余思想“。我用一张图就可以很好的表示：

但是这种质朴的哈希算法的缺点并不少。

1.哈希算法的散列度不够，导致单一服务器攒积过多文件。

2.变化服务器台数之后，就无法正确的从服务器中寻找原有文件。

这样就导致缓存系统无法起到替代数据库分担一部分访问压力的作用，可能会导致大量的请求直接打到数据库，导致数据库崩溃。

通过简单的介绍，我们看到了传统的Hash算法的弊端，那么在不断的改进之下：一致性Hash算法 横空出世。

我们现在可以构想有一个由 232个点所组成的圆环，我们把它叫做哈希环。

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表232-1。

假设我们现在有三台缓存服务器 服务器A，服务器B ， 服务器C 。现在我们可以将这三台服务器编号哈希值 与 232 次方进行取余。得到的数字可以映射在我们设计的这个哈希环上。

当我们在选择把文件存储到哪一个缓存服务器中的时候，采用以下算法：

1.对文件Hash值用 2 32 次方进行取余。得到的结果也能在当前Hash环中有一个映射点。

2.我们选择从顺时针出发， 把文件存储在距离当前结果映射点最近的服务器。

比如 当前文件结果映射点距离 B 缓存服务器最近，那么我们就把文件存储在B服务器上。

其实这就是一致性哈希算法，相比较于传统的哈希算法通过取余来计算位置，一致性哈希算法设计了一个哈希环。

原生的一致性哈希主要解决了传统Hash算法在添加服务器后，缓存失效的场景。

假设我们的A 和 B 缓存服务器中，新增了一个 缓存服务器D：

之前我们A-B这段这段范围的所有缓存映射点的缓存，本来都是存储在缓存B服务器的 ，但是由于新增的缓存服务器D 插进了A和B之间，导致缓存集合1 会 映射到 缓存服务器D中，但是我们的缓存集合2仍然是可用，它依然会被映射到缓存服务器B中。

基于这种思想，在我们这个案例中，插入一个服务器后，需要重建缓存的只有缓存集合1。

这样可以减少新增服务器所带来的缓存失效波及范围。通过哈希环的设计，我们在新增缓存服务器的时候，仍然保存了部分可用文件。

也就是说：使用哈希环之后，当我们新增服务器的时候，不会导致所有的缓存失效，而是部分缓存失效

「哈希环的

PART1

缺陷」

原生的哈希环并不能够解决大量资源堆积在同一个缓存服务器的场景，这是因为在实际缓存服务器映射的时候，并不一定会像我们理想化的三分哈希环。

我们把这种缺陷叫做哈希偏斜。

当出现Hash偏斜的时候，大量的文件仍然会存储在服务器A中。而一致性哈希算法给出的解决方案是：虚拟节点。

虽然物理节点只有三台，但是我们可以映射出很多虚拟节点，当前待存储的文件距离哪一个虚拟节点最近，就把数据存储到哪一个虚拟节点对应的物理节点中。

所以解决哈希偏斜的方案就是：

创建虚拟节点 尝试均分哈希环，虚拟节点越多，我们的映射就越均匀。

相信通过我的介绍，你已经大致了解什么是”一致性哈希算法“。关注我，带你了解更多计算机干货。