分布式数据路由的基石，聊聊一致性哈希算法

在上一节我们提到了一致性哈希算法，本节我们就详细的介绍一下一致性哈希算法。在介绍一致性哈希之前，我们先简要的介绍一下哈希索引算法。大家对哈希索引都比较熟悉，哈希索引在数据库和内存数据结构中有着非常广泛的应用。比如STL中的unordered_map就是用的哈希索引，还有Linux内核中inode缓存也是用的哈希索引。

哈希索引原理非常简单，其由哈希表和哈希算法构成。其中哈希表就是一个数组，每个元素可以理解为一个槽位，在该槽位上可以通过链表的方式管理若干元素，或者称为值。当我们存储或者检索某个数据的时候，通过哈希算法将数据的特征计算出一个哈希值来，这个哈希值称为键（Key）。将该哈希值通过对哈希表长度取余就可以定位到哈希表的具体的槽位。

基于上述哈希索引的原理，我们可以很容易的应用在分布式存储系统的数据索引方面。比如在哈希表中存储的元素改为物理服务器的IP地址，这样哈希表的槽位就跟具体的物理服务器建立的索引关系。当我们访问某一个文件的时候，可以根据文件名称（或者是inode ID） 计算出一个哈希值，然后通过哈希表找到具体存储该文件的服务器。  

原理就是这么简单，但是基于这种普通哈希索引实现的数据索引算法有个非常大的缺陷。这个缺陷是什么呢？我们知道在大规模分布式存储系统当中变化成为常态，这里变化主要是是指存储系统内设备状态的变化，比如设备故障、新增设备和设备离线等等。这样上述哈希索引在数据索引方面就有诸多的不便。

我们举一个具体的例子，比如我们现在容量不够了，需要扩容，这个时候怎么办呢？这个时候就要添加物理设备，同时也就需要将上图中的哈希表哈希表扩容，比如从8台设备扩容成10台设备。还以上图中映射到槽位3中的文件为例，由于哈希表长度发生了变化，此时就映射到了新的位置1。大家可以找几个例子实验一下，我们会发现此时的映射关系发生了非常剧烈的变化。  

虽然我们可以通过一些手段找到数据的原始位置，能够保证原始数据仍然可以被访问。但是数据最终还是要搬运到新的位置，这样就会造成大量的数据迁移，显然这不是我们所希望。

为了保证数据在物理节点的均衡性，一致性哈希算法被发明了。一致性哈希的原理也非常简单，其核心点有两个，一个是将哈希表做的非常大，比如

个槽位，物理设备映射到某些槽位上（这里关键的一点是槽位不会被填满）；另一点是计算出哈希值后得到的槽位ID并不一定会被直接使用（大概率），而是顺时针找到一个具有设备映射的槽位。基于上述两点就实现了一个一致性哈希算法。

我们通过下图详细描述一下一致性哈希算的实现细节。首先我们需要定义一个具有

的哈希表，然后将物理设备尽量均匀的映射到该哈希表的某些槽位上。本图中，服务器3的某个硬盘映射到了槽位5上面。以此类推，这些物理设备会映射到哈希表的不同的槽位上，具体如下图右侧不同颜色的圆圈所示。

如果计算出哈希值后，我们对哈希表长度取模，这样这个哈希表就被虚拟成为一个哈希环，常规哈希算法也是这样做的。如下图左侧所示，当我们想确定某个数据的位置时，我们计算出的哈希值可能会落到槽位2上面，但是槽位2上并没有映射物理设备，于是沿着顺时针方向我们可以找到第一个映射物理设备的槽位5。此时就说明数据应该在槽位5对应的物理设备上，接下来我们就与其上物理设备做进一步的交互即可。  

基于上述算法，系统应对扩容、缩容或者设备故障时就会比较从容了。以扩容为例，假设我们新增加了一个服务器4，此时服务器4被映射到如图所示的一个空闲的槽位上。由于哈希环的长度没有变化，所以数据的映射关系并不会发生变化。但是这个新加入的节点仍然会影响某些节点数据映射，如下图红色箭头所示的节点。如果哈希值在红色箭头所指向的节点到右侧绿色节点之间的区域，那么数据本来应该被映射到服务器3的。但是由于新增加的服务器4，此时有一部分数据将被映射到服务器4。

对比一下就会发现，对于新增加服务器的操作，绝大多数的数据的位置都不会发生变化，影响范围非常小。但是传统一致性哈希有个问题，比如我们新加入的节点运行一段时间后需要下线（可能是故障或者缩容），此时其上的数据会全部迁移到箭头指向的节点，这样的话目的节点负载就会非常大，容量上也不一定能满足要求。如何解决这个问题呢？  

为了解决上述问题，有人提出了虚拟节点的概念。仍然以扩容为例，新增加一个服务器4时，会在哈希环的3个槽位（本文仅仅是示意，其实可以是几十个或者更多）添加虚拟节点，其中包含与物理设备的映射关系。新增加的3个虚拟节点如下图所示的有编号的圆圈。

此时，如果出现节点宕机或者缩容的场景，物理服务器4上的数据仍然会被迁移到顺时针的下一个节点。如果我们观察一下就会发现，这个三个节点的下一个节点的颜色是不一样的，这代表着不同的物理服务器。所以，物理服务器4上的数据会被迁移到多个服务器上。如果虚拟节点足够的，哈希算法足够好，那么物理服务器4上的数据会被均匀的迁移到系统内的所有服务器上。

一致性哈希算法在分布式存储系统中有着非常广泛的应用，如OpenStack Swift和GlusterFS等都使用了一致性哈希算法。后面我们将以Swift为例介绍一下它是如何使用一致性哈希算法的。