# 一致性哈希

分布式哈希表(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，其他键不会受到影响。

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

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://vagrant.gitbook.io/grokking-system-design/yi-zhi-xing-ha-xi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.