1688网站,汽车租赁企业网站源码,上海网站建设的报价,中国河北网站为了实现横向扩展#xff0c;在服务器之间高效和均匀地分配请求/数据是很重要的。一致性哈希是为了达成这个目标而被广泛使用的技术。首先#xff0c;我们看一下什么是重新哈希问题。
1 重新哈希的问题 如果你有n个缓存服务器#xff0c;常见的平衡负载的方法是使用如下哈希…为了实现横向扩展在服务器之间高效和均匀地分配请求/数据是很重要的。一致性哈希是为了达成这个目标而被广泛使用的技术。首先我们看一下什么是重新哈希问题。
1 重新哈希的问题 如果你有n个缓存服务器常见的平衡负载的方法是使用如下哈希方法
服务器序号hash(key)%NN代表服务器池的大小
我们用一个示例来说明它是如何工作的。如表-1所示我们有4个服务器有8个字符串型的键(key)及其对应的哈希值(hash)。 表-1
为了获取存储了某个键的服务器的序号我们需要做求余运算f(key)%4。比如hash(key0)%41表示客户端必须联系server1以获取缓存的数据。图-1基于表-1展示了键的分布。 图-1
这个方法在服务器池的大小固定不变的时候效果很好并且数据的分布是均匀的。但是当添加服务器或现有服务器被移除时问题就产生了。举个例子如果server1下线服务器池的大小就变成3。使用同样的哈希函数对于同一个键我们得到的哈希值不变。但是因为服务器数量减1通过求余操作计算出的服务器序号就与之前的不同了。这可能会导致数据分布不均匀或错误地分配给错误的服务器。“哈希值%3”得到的结果如表-2所示。 表-2
图-2展示了表-2中键的分布。 图-2
如图-2所示大部分的键都被重新分配了不仅仅是原来存储在宕机服务器(server1)中的那些键。这意味着当server1宕机时大部分缓存客户端都会连接错误的服务器来获取数据。这会导致大量的缓存未命中(Cache Miss)。一致性哈希是缓解这个问题的有效技术。
2 一致性哈希 根据维基百科中的定义“一致性哈希是一种特殊的哈希。如果一个哈希表被调整了大小那么使用一致性哈希则平均只需要重新映射k/n个键这里k是键的数量n是槽(Slot)的数量。对比来看在大多数传统的哈希表中只要槽的数量有变化几乎所有的键都需要重新映射一遍”。
2.1 哈希空间和哈希环 现在我们了解了一致性哈希的定义接下来看看它是如何工作的。假设我们使用SHA-1作为哈希函数f哈希函数的输出值范围是x0x1x2x3…xn。在密码学里SHA-1的哈希空间是0到2160-1。这意味着x0对应0xn对应2160-1。图-3展示了哈希空间。
连接x0和xn两端我们可以得到一个如图-4所示的哈希环。 图-3 图-4
2.2 哈希服务器 使用同样的哈希函数f我们根据服务器的IP地址或者名字将其映射到哈希环上。图-5展示了4个服务器被映射到哈希环上的情况。 图-5
2.3 哈希键 值得一提的是这里使用的哈希函数跟第1节中的不一样这里没有求余运算。如图-6所示4个键key0、key1、key2和key3被映射到哈希环上。 图-6
2.4 查找服务器 为了确定某个键存储在哪个服务器上我们从这个键在环上的位置开始顺时针查找直到找到一个服务器为止。图-7解释了这个过程通过顺时针查找可知key0存储在server0上key1存储在server1上key2存储在server2上key3存储在server3上。 图-7
2.5 添加服务器 按照上面描述的逻辑如果要在哈希环中添加一个新的服务器只有少部分键需要被重新映射到新的服务器上大部分键的位置保持不变。
如图-8所示添加新的服务器后(server4)只有key0需要重新分配位置。key1、key2和key3都保留在原来的服务器上。我们仔细看一下这个逻辑。在添加server4之前key0存储在server0上。现在因为server4是从key0在哈希环上的位置开始顺时针查找时遇到的第一个服务器所以key0会被存储到server4上。根据一致性哈希算法其他的键不需要重新分配位置。 图-8
2.6 移除服务器 当一个服务器被移除时如果使用一致性哈希就只有一小部分键需要重新分配位置。如图-9所示当移除server1时只有key1需要重新映射到server2上其他键则不受影响。 图-9
2.7 两个问题 一致性哈希算法是麻省理工学院的David Karger等人首先提出的。它的基本步骤如下
•使用均匀分布的哈希函数将服务器和键映射到哈希环上。
•要找出某个键被映射到了哪个服务器上就从这个键的位置开始顺时针查找直到找到哈希环上的第一个服务器。
这里有两个问题。第一考虑到可以添加或移除服务器所以很难保证哈希环上所有服务器的分区大小相同。分区是相邻服务器之间的哈希空间。在哈希环上分配给每个服务器的分区可能很小也可能很大。如图-10所示如果server1被移除server2的分区用双向箭头标记就是server0和server3的两倍大。 图-10
第二有可能键在哈希环上是非均匀分布的。举个例子如果服务器映射的位置如图-11所示则大部分键都会被存储在server2上而server1和server3上没有数据。 图-11
一种称为虚拟节点或者副本的技术被用来解决这些问题。
2.8 虚拟节点 虚拟节点是实际节点在哈希环上的逻辑划分或映射。每个服务器都可以用多个虚拟节点来表示。如图-12所示服务器server0和server1都有3个虚拟节点。“3”这个数字是任意选的在真实世界中虚拟节点的数量要大得多。这里我们不用s0而是改用s0_0、s0_1和s0_2来表示哈希环上的server0用s1_0、s1_1和s1_2来表示哈希环上的server1。通过虚拟节点每个服务器都对应多个分区。标记为s0的分区边缘是由server0来管理的。标记为s1的分区是由server1来管理的。 图-12
为了找到某个键存储在哪个服务器上我们从这个键所在的位置开始顺时针找到第一个虚拟节点。如图-13所示为了确定key0键存储在哪个服务器上我们从key0所在的位置出发顺时针查找并找到虚拟节点s1_1它对应的是server1。
当虚拟节点的数量增加时键的分布就会变得更均匀。这是因为有更多虚拟节点以后标准差会变小从而导致数据分布更均匀。标准差衡量的是数据的分散程度。一个线上研究[插图]所做的实验显示使用100个或200个虚拟节点时标准差的均值约为10%100个虚拟节点和5%200个虚拟节点。当我们增加虚拟节点的数量时标准差会更小。但是这也意味着需要更多的空间来存储虚拟节点的数据。这需要权衡我们可以调整虚拟节点的数量来满足系统的需求。 图-13
2.9 找到受影响的键 当添加或移除服务器时有一部分键需要重新分配位置。如何找到受影响的键的范围并重新为它们分配位置呢
如图-14所示服务器server4被添加到哈希环上。从server4新添加的节点开始沿着哈希环逆时针移动直到遇到另一个服务器图中为server3为止这就是受影响的键的范围。从图5-14可以看出位于server3和server4之间的键需要重新分配给server4。
如图-15所示服务器server1被移除。从server1被移除的节点开始沿着哈希环逆时针移动直到遇到另一个服务器图中为server0为止这就是受影响的键的范围。从图-15可以看出位于server0和server1之间的键需要重新分配给server2。 图-14 图-15
总结 在本章中我们对一致性哈希进行了深入的讨论包括为什么需要进行一致性哈希和它是怎么工作的。一致性哈希有如下好处
•添加或者移除服务器的时候需要重新分配的键最少。
•更容易横向扩展因为数据分布得更均匀。
•减轻了热点键问题。过多访问一个特定分区可能会导致服务器过载。想象一下如果Katy Perry、Justin Bieber和Lady Gaga的数据都被存储在同一个分区上会是什么情形。一致性哈希通过使数据更均匀地分布来减轻这个问题。
一致性哈希被广泛地应用于现实世界的系统中包括一些非常出名的系统例如
•亚马逊Dynamo数据库的分区组件。
•Apache Cassandra集群的数据分区。
•Discord聊天应用。
•Akamai内容分发网络。
•Maglev网络负载均衡器。
