深入原理学习之——分布式一致性Hash算法

Hash算法

凡是涉及到分布式的系统，就会有负载均衡和数据分布的问题。为了让连接（或者数据）能够分布得更均匀，很多时候会使用到Hash算法。

那什么是Hash算法呢？

把任意长度的输入，通过Hash算法变换成固定长度的输出，这个输出就是Hash值。哈希值的空间远小于输入的空间，所以可能会发生“哈希碰撞”，即两个不同的输入，产生了同一个输出。

Hash算法只是一个定义，并没有规定具体的实现。

具体有什么应用场景？

Hash算法常用于消息摘要的场景，开发者们或多或少听说过的MD5、SHA都属于Hash算法的实现。

在Java语言里，每个Object对象都有一个hashCode方法，它默认是根据对象的内存地址计算的Hash值。当然我们可以覆盖这个方法，用自己的方法去计算得出一个Hash值。

Hash取模

先Hash再取模的场景，在负载均衡中十分常见。

hash(request) % n

假设我们现在有3个服务器，想要做负载均衡，就可以对请求的ip地址或者用户的id等使用Hash函数，然后将计算得出的Hash值对3取模，余数为几，就把请求分配到相应的服务器上。如图：

这里为了演示方便，直接模拟用的hash后的值。

弊端？

那上述方法有什么弊端呢？

在分布式场景下，横向伸缩缩是一个很正常的需求。试想一下，当上述的3台服务器需要扩展到4台服务器时，那绝大多数请求基本上都需要重新映射到另一个节点。因为Hash值没变，除数变了，余数必然会变。如图：

这种变动有时候是不能接受的。比如在Web负载均衡的场景下，session会保存在每个节点里。当然，如果你是“无状态”的服务，那不会存在这个问题。但如果是数据持久化场景，比如前面的文章里提到的MySQL分库分表，这样大的变动显然是不能接受的。因为如果增加或者删除了一个节点，就会导致几乎所有的数据都需要重新迁移。

无状态服务指的是，应用不保存任何状态。比如不用session，或者session保存在第三方缓存的节点里。

一致性Hash

使用一致性Hash可以解决因为横向伸缩导致的大规模数据变动。它是怎么解决的呢？

前面说到用节点的数量作为除数去求余。而一致性Hash的除数是2^32。从0到2^32 - 1,首尾相连构成了一个环。我们先对服务器节点的IP进行Hash，然后除以2^32得到服务器节点在这个Hash环中的位置：

现在有请求进来了，同样进行Hash然后处于2^32求余。如果落在Hash环上，然后顺时针找到第一个节点，这个节点就负责处理这个请求。如图所示：

一致性Hash分布不均匀的问题

细心的读者可能发现，一致性Hash算法在节点数量较少的时候，会出现分布不均匀的问题。如图所示：

这个时候，绝大多数请求都分配到了A节点，而B节点和C节点分配到的请求很少。解决这个问题的方案就是在Hash环上增加虚拟节点。实现方式也有很多种，比如：

hash(“SERVER_IP_A#1”) % 2^32

hash(“SERVER_IP_A#2”) % 2^32

hash(“SERVER_IP_A#3”) % 2^32

一致性Hash的应用场景？

讲了这么多，一致性Hash到底有什么用？

除了前面提到的负载均衡、Web session和数据库分库分表可以应用外，其实一致性Hash应用得最多的领域是分布式缓存。

分布式缓存系统一般是对Key进行Hash的。试想一下，如果直接对节点数量取模，一旦节点数量发生变化，比如新增一个节点或者删除一个节点，那将使得几乎所有结点的缓存失效。而如果使用一致性Hash，就只有Hash环上相邻的节点缓存受到影响。

从Hash环和顺时针查找原理不难发现，在增加一个节点后，一些原来被分配到下一个节点的请求，被分配到了新的节点。在减少一个节点后，一些原来本分配到这个节点的请求，被分配到了下一个节点。

所以无论是增加还是减少一个节点，都只有下一个相邻的节点会被影响而已。