十堰的网站建设,网站建设服务费的会计处理,免费手机个人网站,搭建网站价格本文主要来自#xff1a;http://www.zsythink.net/archives/1182 摘录防丢失 一致性哈希算法定义
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希#xff08;DHT#xff09;实现算法#xff0c;设计目标是为了解决因特网中的热点(Hot spot)问题#xff0c;初… 本文主要来自http://www.zsythink.net/archives/1182 摘录防丢失 一致性哈希算法定义
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希DHT实现算法设计目标是为了解决因特网中的热点(Hot spot)问题初衷和CARPCommon Access Redundancy Protocol共用地址冗余协议十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题使得分布式哈希DHTDistributed Hash Table可以在P2P环境中真正得到应用。
一致性hash算法提出了在动态变化的Cache环境中判定哈希算法好坏的四个定义 平衡性(Balance)平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。 单调性(Monotonicity)单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去而不会被映射到旧的缓冲集合中的其他缓冲区。 分散性(Spread)在分布式环境中终端有可能看不到所有的缓冲而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时由于不同终端所见的缓冲范围有可能不同从而导致哈希的结果不一致最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的因为它导致相同内容被存储到不同缓冲中去降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生也就是尽量降低分散性。 负载(Load)负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中那么对于一个特定的缓冲区而言也可能被不同的用户映射为不同 的内容。与分散性一样这种情况也是应当避免的因此好的哈希算法应能够尽量降低缓冲的负荷。
在分布式集群中对机器的添加删除或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法那么在有机器添加或者删除后很多原有的数据就无法找到了这样严重的违反了单调性原则。
在了解一致性哈希算法之前最好先了解一下缓存中的一个应用场景了解了这个应用场景之后再来理解一致性哈希算法就容易多了也更能体现出一致性哈希算法的优点那么我们先来描述一下这个经典的分布式缓存的应用场景。
场景描述
假设我们有三台缓存服务器用于缓存图片我们为这三台缓存服务器编号为0号、1号、2号现在有3万张图片需要缓存我们希望这些图片被均匀的缓存到这3台服务器上以便它们能够分摊缓存的压力。也就是说我们希望每台服务器能够缓存1万张左右的图片那么我们应该怎样做呢如果我们没有任何规律的将3万张图片平均的缓存在3台服务器上可以满足我们的要求吗可以但是如果这样做当我们需要访问某个缓存项时则需要遍历3台缓存服务器从3万个缓存项中找到我们需要访问的缓存遍历的过程效率太低时间太长当我们找到需要访问的缓存项时时长可能是不能被接收的也就失去了缓存的意义缓存的目的就是提高速度改善用户体验减轻后端服务器压力如果每次访问一个缓存项都需要遍历所有缓存服务器的所有缓存项想想就觉得很累那么我们该怎么办呢原始的做法是对缓存项的键进行哈希将hash后的结果对缓存服务器的数量进行取模操作通过取模后的结果决定缓存项将会缓存在哪一台服务器上这样说可能不太容易理解我们举例说明仍然以刚才描述的场景为例假设我们使用图片名称作为访问图片的key假设图片名称是不重复的那么我们可以使用如下公式计算出图片应该存放在哪台服务器上。
hash图片名称% N
因为图片的名称是不重复的所以当我们对同一个图片名称做相同的哈希计算时得出的结果应该是不变的如果我们有3台服务器使用哈希后的结果对3求余那么余数一定是0、1或者2没错正好与我们之前的服务器编号相同如果求余的结果为0 我们就把当前图片名称对应的图片缓存在0号服务器上如果余数为1就把当前图片名对应的图片缓存在1号服务器上如果余数为2同理那么当我们访问任意一个图片的时候只要再次对图片名称进行上述运算即可得出对应的图片应该存放在哪一台缓存服务器上我们只要在这一台服务器上查找图片即可如果图片在对应的服务器上不存在则证明对应的图片没有被缓存也不用再去遍历其他缓存服务器了通过这样的方法即可将3万张图片随机的分布到3台缓存服务器上了而且下次访问某张图片时直接能够判断出该图片应该存在于哪台缓存服务器上这样就能满足我们的需求了我们暂时称上述算法为HASH算法或者取模算法取模算法的过程可以用下图表示。 但是使用上述HASH算法进行缓存时会出现一些缺陷试想一下如果3台缓存服务器已经不能满足我们的缓存需求那么我们应该怎么做呢没错很简单多增加两台缓存服务器不就行了假设我们增加了一台缓存服务器那么缓存服务器的数量就由3台变成了4台此时如果仍然使用上述方法对同一张图片进行缓存那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同因为除数由3变为了4被除数不变的情况下余数肯定不同这种情况带来的结果就是当服务器数量变动时所有缓存的位置都要发生改变换句话说当服务器数量发生改变时所有缓存在一定时间内是失效的当应用无法从缓存中获取数据时则会向后端服务器请求数据同理假设3台缓存中突然有一台缓存服务器出现了故障无法进行缓存那么我们则需要将故障机器移除但是如果移除了一台缓存服务器那么缓存服务器数量从3台变为2台如果想要访问一张图片这张图片的缓存位置必定会发生改变以前缓存的图片也会失去缓存的作用与意义由于大量缓存在同一时间失效造成了缓存的雪崩此时前端缓存已经无法起到承担部分压力的作用后端服务器将会承受巨大的压力整个系统很有可能被压垮所以我们应该想办法不让这种情况发生但是由于上述HASH算法本身的缘故使用取模法进行缓存时这种情况是无法避免的为了解决这些问题一致性哈希算法诞生了。
我们来回顾一下使用上述算法会出现的问题。 问题1当缓存服务器数量发生变化时会引起缓存的雪崩可能会引起整体系统压力过大而崩溃大量缓存同一时间失效。 问题2当缓存服务器数量发生变化时几乎所有缓存的位置都会发生改变怎样才能尽量减少受影响的缓存呢
其实上面两个问题是一个问题那么一致性哈希算法能够解决上述问题吗 我们现在就来了解一下一致性哈希算法。
一致性哈希算法的基本概念
其实一致性哈希算法也是使用取模的方法只是刚才描述的取模法是对服务器的数量进行取模而一致性哈希算法是对2^32取模什么意思呢我们慢慢聊。
首先我们把二的三十二次方想象成一个圆就像钟表一样钟表的圆可以理解成由60个点组成的圆而此处我们把这个圆想象成由2^32个点组成的圆示意图如下
圆环的正上方的点代表00点右侧的第一个点代表1以此类推2、3、4、5、6……直到232-1,也就是说0点左侧的第一个点代表232-1 我们把这个由2的32次方个点组成的圆环称为hash环。
那么一致性哈希算法与上图中的圆环有什么关系呢我们继续聊仍然以之前描述的场景为例假设我们有3台缓存服务器服务器A、服务器B、服务器C那么在生产环境中这三台服务器肯定有自己的IP地址我们使用它们各自的IP地址进行哈希计算使用哈希后的结果对2^32取模可以使用如下公式示意。 hash服务器A的IP地址 % 2^32 通过上述公式算出的结果一定是一个0到232-1之间的一个整数我们就用算出的这个整数代表服务器A既然这个整数肯定处于0到232-1之间那么上图中的hash环上必定有一个点与这个整数对应而我们刚才已经说明使用这个整数代表服务器A那么服务器A就可以映射到这个环上用下图示意 同理服务器B与服务器C也可以通过相同的方法映射到上图中的hash环中 hash服务器B的IP地址 % 2^32 hash服务器C的IP地址 % 2^32 通过上述方法可以将服务器B与服务器C映射到上图中的hash环上示意图如下 假设3台服务器映射到hash环上以后如上图所示当然这是理想的情况我们慢慢聊。
好了到目前为止我们已经把缓存服务器与hash环联系在了一起我们通过上述方法把缓存服务器映射到了hash环上那么使用同样的方法我们也可以将需要缓存的对象映射到hash环上。
假设我们需要使用缓存服务器缓存图片而且我们仍然使用图片的名称作为找到图片的key那么我们使用如下公式可以将图片映射到上图中的hash环上。 hash图片名称 % 2^32 映射后的示意图如下下图中的橘黄色圆形表示图片 好了现在服务器与图片都被映射到了hash环上那么上图中的这个图片到底应该被缓存到哪一台服务器上呢上图中的图片将会被缓存到服务器A上为什么呢因为从图片的位置开始沿顺时针方向遇到的第一个服务器就是A服务器所以上图中的图片将会被缓存到服务器A上如下图所示。 没错一致性哈希算法就是通过这种方法判断一个对象应该被缓存到哪台服务器上的将缓存服务器与被缓存对象都映射到hash环上以后从被缓存对象的位置出发沿顺时针方向遇到的第一个服务器就是当前对象将要缓存于的服务器由于被缓存对象与服务器hash后的值是固定的所以在服务器不变的情况下一张图片必定会被缓存到固定的服务器上那么当下次想要访问这张图片时只要再次使用相同的算法进行计算即可算出这个图片被缓存在哪个服务器上直接去对应的服务器查找对应的图片即可。
刚才的示例只使用了一张图片进行演示假设有四张图片需要缓存示意图如下 1号、2号图片将会被缓存到服务器A上3号图片将会被缓存到服务器B上4号图片将会被缓存到服务器C上。
一致性哈希算法的优点
经过上述描述我想兄弟你应该已经明白了一致性哈希算法的原理了但是话说回来一致性哈希算法能够解决之前出现的问题吗我们说过如果简单的对服务器数量进行取模那么当服务器数量发生变化时会产生缓存的雪崩从而很有可能导致系统崩溃那么使用一致性哈希算法能够避免这个问题吗我们来模拟一遍即可得到答案。
假设服务器B出现了故障我们现在需要将服务器B移除那么我们将上图中的服务器B从hash环上移除即可移除服务器B以后示意图如下。 在服务器B未移除时图片3应该被缓存到服务器B中可是当服务器B移除以后按照之前描述的一致性哈希算法的规则图片3应该被缓存到服务器C中因为从图片3的位置出发沿顺时针方向遇到的第一个缓存服务器节点就是服务器C也就是说如果服务器B出现故障被移除时图片3的缓存位置会发生改变 但是图片4仍然会被缓存到服务器C中图片1与图片2仍然会被缓存到服务器A中这与服务器B移除之前并没有任何区别这就是一致性哈希算法的优点如果使用之前的hash算法服务器数量发生改变时所有服务器的所有缓存在同一时间失效了而使用一致性哈希算法时服务器的数量如果发生改变并不是所有缓存都会失效而是只有部分缓存会失效前端的缓存仍然能分担整个系统的压力而不至于所有压力都在同一时间集中到后端服务器上。
这就是一致性哈希算法所体现出的优点。
hash环的偏斜
在介绍一致性哈希的概念时我们理想化的将3台服务器均匀的映射到了hash环上如下图所示 但是理想很丰满现实很骨感我们想象的与实际情况往往不一样。 在实际的映射中服务器可能会被映射成如下模样。 聪明如你一定想到了如果服务器被映射成上图中的模样那么被缓存的对象很有可能大部分集中缓存在某一台服务器上如下图所示。 上图中1号、2号、3号、4号、6号图片均被缓存在了服务器A上只有5号图片被缓存在了服务器B上服务器C上甚至没有缓存任何图片如果出现上图中的情况A、B、C三台服务器并没有被合理的平均的充分利用缓存分布的极度不均匀而且如果此时服务器A出现故障那么失效缓存的数量也将达到最大值在极端情况下仍然有可能引起系统的崩溃上图中的情况则被称之为hash环的偏斜那么我们应该怎样防止hash环的偏斜呢一致性hash算法中使用虚拟节点解决了这个问题我们继续聊。
虚拟节点
话接上文由于我们只有3台服务器当我们把服务器映射到hash环上的时候很有可能出现hash环偏斜的情况当hash环偏斜以后缓存往往会极度不均衡的分布在各服务器上聪明如你一定已经想到了如果想要均衡的将缓存分布到3台服务器上最好能让这3台服务器尽量多的、均匀的出现在hash环上但是真实的服务器资源只有3台我们怎样凭空的让它们多起来呢没错就是凭空的让服务器节点多起来既然没有多余的真正的物理服务器节点我们就只能将现有的物理节点通过虚拟的方法复制出来这些由实际节点虚拟复制而来的节点被称为虚拟节点。加入虚拟节点以后的hash环如下。 “虚拟节点是实际节点”实际的物理服务器在hash环上的复制品,一个实际节点可以对应多个虚拟节点。 从上图可以看出A、B、C三台服务器分别虚拟出了一个虚拟节点当然如果你需要也可以虚拟出更多的虚拟节点。引入虚拟节点的概念后缓存的分布就均衡多了上图中1号、3号图片被缓存在服务器A中5号、4号图片被缓存在服务器B中6号、2号图片被缓存在服务器C中如果你还不放心可以虚拟出更多的虚拟节点以便减小hash环偏斜所带来的影响虚拟节点越多hash环上的节点就越多缓存被均匀分布的概率就越大。
