26. 一致性哈希
在分布式可扩展系统中，分布式哈希表 (DHT) 是基本组件之一。 哈希表需要一个键、一个值和一个哈希 函数，其中哈希函数将键映射到值所在的存储位置。
假设正在设计一个分布式缓存系统。 给定n个缓存服务器，一个直观的散列函数将是"key % n"。 它很简单常用，但它有两个主要缺点：
1.它不是水平可扩展的。 每当一个新的缓存主机被添加到系统，所有现有的映射都被破坏了。如果缓存系统包含大量数据，在维护时 这将是一个痛点。 在实践中，其实很难安排停机时间来更新所有缓存映射。
2.它可能不是负载均衡的，尤其是对于非均匀分布的数据。 在实践中，可以很容易地假设数据不会均匀分布。对于缓存系统，被解读成为一些缓存变热和饱和，而其他缓存则处于空闲状态或是不饱和状态。
在这种情况下，一致性哈希是改善缓存系统的一个重要方法。
什么是一致性哈希？
一致性哈希是分布式缓存系统和DHTs（分布式哈希表）中一种非常有用的策略 。 当新的节点被添加，旧的节点被删除，它允许在集群中分布数据以最小化的代价进行传输。 因此，缓存系统将更容易扩容或缩容。
在一致性哈希中，当哈希表被调整时（例如一个新的缓存主机被添加到系统中），只有”k/n”个键需要重新映射，其中“k”是key的总数，“n”是服务器总数。 回想一下，在使用mod函数的的缓存系统，所有键都需要重新映射。
在一致性哈希中，对象会尽可能地映射到同一主机。从系统中删除主机时，该主机上的对象将被其他主机共享。当添加一个新主机时，会从少部分主机中进行映射，而大部分主机是无感知的。
如何工作的？
作为一个典型的散列函数，一致性散列将一个键映射到一个整数。假设哈希函数的输出在 [0, 256) 的范围内。想象 范围内的整数被放置在一个环上，值嵌在其中。
以下是一致性哈希的工作原理：
1.给定一个缓存服务器列表，将它们散列为范围内的整数。
2.要将key映射到服务器，需要：
将其散列为单个整数。
在环上顺时针移动，直到找到第一个缓存服务器。
该缓存是包含key的缓存。看下面动画，例如：key1 映射到缓存 A， key2 映射到缓存 C。
要添加一个新的服务器，比如 D，最初驻留在 C 的key将会拆分。其中一些key将移至 D，而其他key则不会被转移。删除缓存或者如果缓存失败，比如 A，删除所有原来的key，并不是所有A上的key都会转移到B，只有那些需要转移的key会到B上去，其他key不会受到影响。
对于负载均衡，正如我们一开始所讨论的，真实数据是基本上是随机分布的，因此可能不均匀。可能使缓存上的key不均衡。
为了解决这个问题，我们为缓存添加了“虚拟副本”的概念。而不是映射每个缓存到环上的一个点，我们将它映射到环上的多个点，即副本。这样，每个缓存都与环上的多个部分相关联。
如果散列函数“混合得很好”，随着副本数量的增加，键将更加均衡。
Last updated