CHAPTER 5: DESIGN CONSISTENT HASHING

为了实现水平扩展，有效且均匀地分发请求/数据是很重要的在服务器上。一致散列是实现这一目标的常用技术。但首先，让我们深入了解一下这个问题。

重组问题

如果您有n个缓存服务器，那么平衡负载的常用方法是使用以下散列方法:
serverIndex = hash(key) % N，其中N为服务器池的大小。让我们用一个例子来说明它是如何工作的。如表table5-1所示，我们有4台服务器8串键和它们的哈希值。
在这里插入图片描述
为了获取存储键的服务器，我们执行模块化操作f(key) % 4。为实例，hash(key0) % 4 = 1表示客户端必须联系服务器1才能获取缓存的数据。根据table5-1，密钥分配如figure5-1所示。

当服务器池的大小和数据分布固定时，这种方法在偶数情况下工作得很好。但是，当添加新服务器或移除现有服务器时，就会出现问题。例如，如果服务器1脱机，则服务器池的大小变为3。使用同样的哈希函数，我们得到一个键相同的哈希值。但是应用模块化Operation为我们提供了不同的服务器索引，因为服务器的数量减少了1。我们通过应用hash % 3得到如table5-2所示的结果:
在这里插入图片描述
根据table5-2，新的密钥分布如figure5-2所示。

如figure5-2所示，大多数密钥都是重新分发的，而不仅仅是最初存储在脱机服务器(服务器1)。这意味着当服务器1脱机时，大多数缓存客户机也会脱机连接到错误的服务器以获取数据。这将导致大量缓存未命中。一致的散列是缓解此问题的有效技术。

一致性哈希

引用自维基百科:“一致性哈希是一种特殊的哈希，当a重新调整哈希表大小并使用一致哈希，只需要重新映射k/n个键平均，k是键的个数，n是槽的个数。相反，在大多数情况下在传统的哈希表中，数组槽数的变化会导致几乎所有键都被替换贴图[1]”。

哈希空间和哈希环

现在我们了解了一致哈希的定义，让我们来看看它是如何工作的。假设使用SHA-1作为哈希函数f，哈希函数的输出范围为:x0, x1, x2，在密码学中，SHA-1的哈希空间从0到2^160 -1。也就是x0对应于0,xn对应于2^160 - 1，其他哈希值都在中间在0到2^160 - 1之间。哈希空间如figure5-3所示。
在这里插入图片描述
将两端集合，得到一个哈希环，如图figure5-4所示:

散列服务器

使用相同的哈希函数f，我们根据服务器IP或名称将服务器映射到环上。如figure5-5所示，哈希环上映射了4个服务器。
在这里插入图片描述

散列键

值得一提的是，这里使用的哈希函数与“the”中的哈希函数不同重新散列问题”，并且没有模块化操作。如figure5-6所示，4个缓存键(key0、key1、key2和key3)被散列到散列环上
在这里插入图片描述要确定键存储在哪个服务器上，我们从键的位置顺时针进行直到找到服务器为止。流程如figure5-7所示。顺时针方向，key0被存储在服务器0上;Key1存储在服务器1上;Key2存储在服务器2上，key3存储在服务器上3.

添加服务器

使用上面描述的逻辑，添加一个新服务器只需要重新分配一个键的分数。
在figure5-8中，新增服务器4后，只需要重新分配key0。K1 k2，还有K3仍然在相同的服务器上。让我们仔细看看其中的逻辑。在添加服务器4之前，Key0存储在服务器0上。现在，key0将存储在服务器4上，因为服务器4是第一个从key0在环上的位置顺时针移动所遇到的服务器。其他键是不基于一致性哈希算法重新分发。
在这里插入图片描述

移除服务器

当服务器被删除时，只有一小部分密钥需要重新分配散列。在图5-9中，当服务器1被移除时，只有key1需要重新映射到服务器2。其余的钥匙不受影响。
在这里插入图片描述

基本方法有两个问题

一致性哈希算法是由Karger等人在MIT[1]提出的。基本步骤是:

使用统一分布的哈希函数将服务器和密钥映射到环上。
要找出一个键映射到哪个服务器，从键位置顺时针走，直到找到环上的第一个服务器。

这种方法存在两个问题。首先，不可能保持相同的规模考虑到可以添加或删除服务器的所有服务器在环上的分区。一个分区是相邻服务器之间的哈希空间。有可能是分配给每个服务器的环上的分区要么非常小，要么相当大。在figure5-10中，如果s1被删除后，s2的分区(用双向箭头突出显示)是so0的两倍大s3的分区。在这里插入图片描述其次，环上可能存在不均匀的密钥分布。例如，如果服务器映射到如figure5-11所示的位置，大部分密钥存储在服务器2上。但是，服务器1和服务器3没有数据。

使用一种称为虚拟节点或副本的技术来解决这些问题。

虚拟节点

虚拟节点是指实节点，每台服务器由多个虚拟节点表示在环上。在figure5-12中，服务器0和服务器1各有3个虚拟节点。3是任意选择;而在现实世界的系统中，虚拟节点的数量要大得多。我们不用s0，而是用s0_0、s0_1和s0_2表示环上的服务器0。同样的,S1_0、s1_1和s1_2代表环上的服务器1。对于虚拟节点，每个服务器都是负责多个分区。标签为50的分区(边)由服务器0管理。另一方面，标签为s1的分区由服务器1管理。
在这里插入图片描述
要查找密钥存储在哪个服务器上，我们从密钥的位置顺时针查找环路上遇到的第一个虚拟节点。在figure5-13中，查看存储的服务器k0On，我们从k0的位置顺时针走，找到虚拟节点s1_1，它指向服务器1。
随着虚拟节点数量的增加，密钥的分布变得更加平衡。这是因为虚拟节点越多，标准差越小，导致均衡的数据分布。标准偏差衡量的是数据的分布情况。的在线研究b[2]进行的一项实验结果表明，有一个或两个100个虚拟节点，标准差在5%(200个虚拟节点)~ 10%之间(100个虚拟节点)的平均值。标准差会变小，当我们增加虚拟节点数。但是，需要更多的空间来存储有关虚拟节点的数据。这是一种权衡，我们可以调整虚拟节点的数量以适应我们的系统需求。

查找受影响的键

当添加或删除服务器时，需要重新分发一小部分数据。我们怎么能找到受影响的范围来重新分配键?如figure5-14所示，服务器4加入到环中。受影响的范围从s4 (new添加节点)并沿环逆时针移动，直到找到服务器(s3)。因此,键
位于s3和s4之间的需要重新分配到s4。
在这里插入图片描述
如figure5-15所示，当一台服务器(s1)被移除时，影响范围从s1开始(移除的节点)并沿环逆时针移动，直到找到服务器(s0)。因此,位于s0和s1之间的键必须重新分配到s2。

总结

在本章中，我们对一致性哈希进行了深入的讨论，包括为什么要这样做需要和它的工作原理。一致性哈希的好处包括:

当服务器被添加或删除时，最小化的密钥将被重新分配。
容易横向扩展，因为数据分布更均匀。
缓解热点密钥问题。对特定分片的过度访问可能导致服务器故障过载。想象一下，凯蒂·佩里、贾斯汀·比伯和Lady Gaga的数据都出现在同样的碎片。一致散列通过更多地分布数据来帮助缓解这个问题均匀。

一致哈希被广泛应用于现实世界的系统中，包括一些值得注意的系统:

Amazon Dynamo数据库[3]的分区组件
Apache Cassandra[4]的跨集群数据分区
不和聊天应用[5]
Akamai内容分发网络b[6]
磁悬浮网络负载平衡器[7]
恭喜你走了这么远!现在给自己点鼓励吧。好工作!

参考资料 Reference materials

[1] Consistent hashing: https://en.wikipedia.org/wiki/Consistent_hashing
[2] Consistent Hashing:
https://tom-e-white.com/2007/11/consistent-hashing.html
[3] Dynamo: Amazon’s Highly Available Key-value Store:
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[4] Cassandra - A Decentralized Structured Storage System:
http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF
[5] How Discord Scaled Elixir to 5,000,000 Concurrent Users:
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b
[6] CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent
Hashing: http://theory.stanford.edu/~tim/s16/l/l1.pdf
[7] Maglev: A Fast and Reliable Software Network Load Balancer:
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf