Consistent Hashing | Creator's Blog (Hugo Theme)

什么是一致性哈希

一致性哈希（Consistent Hashing）是一种分布式哈希算法，用于将键（key）映射到节点的过程。它主要用于解决在分布式系统中，动态添加或移除节点时，如何有效地重新分配数据的问题。

工作原理

一致性哈希的主要思想是将整个哈希空间划分为一定数量的区间，每个区间对应一个节点。当需要映射一个键时，通过哈希函数将键映射到哈希空间的某一点，然后找到离该点最近的节点，将键存储在这个节点上。

具体的步骤如下：

将哈希空间划分成一定数量的区间，形成一个哈希环。
将节点使用哈希函数映射到哈希环上的某个点。
当有新的数据时，使用相同的哈希函数将其映射到哈希环上的某个点。
沿着哈希环的顺时针方向，找到离映射点最近的节点，将键存储在该节点上。
在一致性哈希中，如果某个节点被移除或者新增了节点，只有与这个节点相邻的区间内的键需要重新映射，其他区间的映射保持不变。

下面将举例说明详细说明其工作流程：

哈希空间划分，Hash函数选择

哈希空间划分： 首先定义一个0到n的环，通常n=$2^{32}$ ，n的值也可以根据自己的需求来定义。
选择Hash函数： 选择一个Hash（MD5、SHA-1、SHA-256等）函数用来计算节点和数据所在的位置，对应环上的位置为Hash对n取模。

$$ index =\text{Hash}(x) \bmod n $$

节点分配

通过Hash计算出每个节点的位置，并将其分配到环上。

分配和查找数据

查找存储节点： 采用同样的方式方式计算出数据的位置，将其映射到哈希环上，后顺时针寻找最近的节点上。

存储数据： 找到对应的节点以后将数据存储在该节点上

查找数据： 找到对应的节点以后将从节点上查询数据

节点的添加或移除

经过一段时间的，环可能会如下图所示，在s1区的数据为key1…key4。这些key都存储在N2上。

当新加入节点N5时，N5可能分配在了s1区，此时会进行一下步骤：

N5顺序时针找到最近的节点N2。
然后将N2在s1.1上的数据全部转移到N5。

在整个过程中受影响的节点只有N2，只有一小部分键需要重新映射，其它节点均可以正常工作，这个过程极大的缓解了添加节点是对数据处理的成本。

同理： 如果删除N5，只需要将N5的数据全部转移到N2上即可。

虚拟节点

虚拟节点的主要目的是解决在一致性哈希场景中的负载均衡问题。

有时节点的分配不一定能保障均匀分布，比如下图，节点的分布非常密集。此时大部分数据都会被分配到N1上，从而导致N1的负载过高。

为了解决这个问题，我需要创建虚拟节点，一个物理节点会对应多个虚拟节点，然后将虚拟节点映射到环上。（可以在物理节点上添加编号或标记，然后计算虚拟节点的位置）

通过添加虚拟节点，就能有效减少节点分布不均的情况，从而增加系统的负载均很能力。

一致性哈希有哪些优势

负载均衡： 一致性哈希在节点的增减时，只需要重新映射少量的键，因此能够实现相对均匀的数据分布，提高负载均衡性。
容错性： 由于一致性哈希的设计，增加或移除一个节点只会影响到少量的键的映射，因此系统具有较好的容错性，不会导致大规模的数据迁移。
动态扩展： 一致性哈希适用于动态环境，可以在系统运行时动态地增加或移除节点，而不会对整个系统产生过大的影响。
简单实现： 一致性哈希的实现相对简单，易于理解和部署。它不涉及复杂的数据结构和算法，适用于各种分布式系统。

一致性哈希的缺点是什么

节点分布不均匀： 在一些情况下，由于哈希函数的特性，节点在哈希环上的分布可能不够均匀，导致一些节点负载较重，而其他节点负载较轻。
节点的动荡： 当节点数量变化较频繁时，可能导致一些数据频繁地重新映射，增加系统的维护开销。这一点可以通过引入虚拟节点来缓解。
不适用于有序查询： 由于哈希函数的随机性，一致性哈希对于有序查询的性能可能不如其他算法。一些应用可能更适合使用范围查询等方式。
不适用于复杂查询： 一致性哈希主要用于键-值存储的简单查询，对于复杂的查询场景可能不够灵活

应用领域

一致性哈希在分布式系统中有许多应用场景，其中一些主要的应用包括：

分布式缓存： 一致性哈希常用于分布式缓存系统，如Memcached或Redis。通过将缓存键映射到节点，它能够提供负载均衡和动态节点的支持，减少缓存失效时需要重新分配的数据量。
分布式文件系统： 一致性哈希可用于分布式文件系统，如Hadoop的HDFS。通过将文件块的标识符映射到节点，它能够在节点的增减时实现数据的均匀分布。
分布式数据库： 在分布式数据库中，一致性哈希可用于将数据库键映射到不同的节点。这样可以实现数据的水平划分，支持动态节点的加入和离开。
负载均衡： 一致性哈希可以用于负载均衡器，将请求映射到不同的服务器节点。这使得负载均衡系统能够在节点的变化时尽可能少地影响已有的请求。
分布式存储系统： 一致性哈希广泛应用于分布式存储系统，如Amazon S3或Ceph。它能够实现数据的均匀分布，同时支持节点的动态调整。
反向代理： 在反向代理中，一致性哈希可用于将请求映射到不同的后端服务器。这样可以在后端服务器的变化时最小化影响。
分布式消息队列： 一致性哈希可用于分布式消息队列，将消息路由到不同的队列或节点。这有助于实现消息的分布式处理和负载均衡。
分布式搜索引擎： 在分布式搜索引擎中，一致性哈希可用于将索引分片映射到不同的节点。这有助于提高搜索性能和支持节点的动态调整。