写在前面

本文学习自：

简介

一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。

在介绍一致性哈希算法之前，先说一下普通的哈希算法，以便介绍它俩的区别。

在负载均衡中，使用普通的哈希算法进行负载均衡，假如用户上传一个图片，我们有三台服务器可以存储，上传到哪一个图片？

但是，普通哈希有个很大的坏处：假如我又添加了两台机器，此时机器数量变成 5，之前那张图片使用 hash（图片）= 13，取模 13 % 5 = 3，于是程序去 服务器2 找图片，但是我们的图片之前存储在服务器1。bug不就来了？

看到这里你应该意识到：一旦服务器数量修改，hash之后的取模运算就会改变，对应的计算结果也就改变了，之前的计算结果与现在的计算结果不一样，绝大多数数据就需要重新存储。这是个致命错误。

普通哈希失误就失误在对机器数量取模上，我们不对机器数取模，对 2^32 取模，什么意思呢？

我们首先将 [0， 2^32-1] 围成一个圆圈：

如图，0 的左侧就是 2^32-1。我们把这个由 2^32 个数组成的圆圈称为哈希环

于是我们存图片的步骤变为：

将服务器的地址计算哈希值，hash(服务器)，用这个值与 2^32 取模，那么所有服务器都会在这个圆圈上代表一个点

将要存储的图片计算哈希值，hash(图片)，用这个值与 2^32 取模，那么所有图片都会在这个圆圈上代表一个点

怎么给这些图片选择一个服务器呢？只需要在这个环上一直往后遍历就行了，上图中左边三个图片存储在服务器A，右边的三个图片存储在服务器C。

程序查找时也可以这样做：计算hash值 -> 与 2^32 取模 -> 放在哈希环上往右找第一个服务器。

遇到服务器宕机或者新增服务器时，就可以只破坏一部分数据，保护其余数据。

假如此时服务器C 宕机，那么右边的三个文件就只能存储到服务器B 中，但是也仅仅是三个文件。

一致性哈希的的优缺点：

优点：遇到节点不稳定的情况可以保护多数数据
缺点：在节点数量太少的情况下，容易因为节点分布不均匀而造成数据倾斜问题，也就是被缓存的数据大都集中存储在某个节点上，从而出现数据分布不均匀的情况，这种情况被称为哈希倾斜

为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个节点都计算多个哈希值，每个计算结果都放置在哈希环上，称为虚拟节点。一个实际的物理节点可以对应多个虚拟节点，虚拟节点越多，哈希环上的节点就越多，数据被均匀分配的概率就越大，哈希环倾斜造成的影响就越小。

寻找过程就变为：hash（图片）-> 取模得到hash值 -> 向右找到虚拟节点 -> 根据虚拟节点找到物理节点