# 一致性哈希

分布式哈希表(Distributed Hash Table, DHT)是分布式可伸缩系统的基本组件之一。哈希表需要键、值和哈希函数，哈希函数将键映射到存储值的位置。

index = hash\_function(key)

假设我们正在设计一个分布式缓存系统。给定' n '缓存服务器，直观的哈希函数将是' key % n '。它简单而常用。但它有两个主要缺点:

1.它不是水平伸缩的。每当向系统添加一个新的缓存主机时，所有现有的映射都会被破坏。如果缓存系统包含大量的数据，这将是维护中的一个痛点。实际上，很难安排停机时间来更新所有缓存映射。

2.它可能不是负载均衡的，特别是对于非均匀分布的数据。在实践中，很容易假设数据不是均匀分布的。对于缓存系统来说，这意味着一些缓存变得热且饱和，而其他缓存则闲置且几乎为空。

在这种情况下，一致的哈希是改进缓存系统的好方法。

## 什么是一致哈希?

对于分布式缓存系统和dht，一致哈希是一种非常有用的策略。它允许以这样一种方式在集群中分布数据，从而将添加或删除节点时的重组最小化。因此，让缓存系统更容易扩展或缩小。

在一致哈希中，当哈希表的大小被调整时(例如一个新的缓存主机被添加到系统中)，只需要映射kn键，其中k是键的总数，n是服务器的总数。回想一下，在使用“mod”作为哈希函数的缓存系统中，所有的键都需要被映射。

在一致的哈希中，如果可能，将对象映射到相同的主机。当主机从系统中移除时，该主机上的对象将被其他主机共享;当一个新主机被添加时，它会从几个主机中获取它的份额，而不会触及其他主机的份额。

## 它是如何工作的?

作为一个典型的哈希函数，一致的哈希将一个键映射为一个整数。假设哈希函数的输出在\[0,256]的范围内。假设这个范围内的整数被放置在一个环上，这样值就被包围起来了。

以下是一致哈希的工作原理:

1. 给定一个缓存服务器列表，将它们散列为范围内的整数。
2. 要将密钥映射到服务器，
   * 将其散列为单个整数。
   * 顺时针方向移动，直到找到它遇到的第一个缓存。
   * 这个缓存就是包含键的那个。下面的动画就是一个例子:key1映射到缓存A;key2映射到缓存C。

为了添加一个新的服务器，比如D，原来驻留在C的键将被拆分。其中一些键将被移到D，而其他键将不会被触摸。

为了移除缓存，或者如果缓存失败，比如a，所有原映射到a的键都将落入B，只有那些键需要移动到B，其他键不会受到影响。

对于负载平衡，正如我们在开始时讨论的那样，实际数据基本上是随机分布的，因此可能不是均匀的。它可能使缓存上的键不平衡。

为了处理这个问题，我们为缓存添加了“虚拟副本”。我们不是将每个缓存映射到环上的单个点，而是映射到环上的多个点，即副本。这样，每个缓存都与环的多个部分相关联。

如果哈希函数“混合得很好”，随着副本数量的增加，键将更加平衡。