免费网站建设软件,广东省水利工程建设信息网站,wordpress后台502,怎么做专门卖二手衣服的网站本篇是对文章《一文彻底读懂一致性哈希算法》的重写#xff0c;图文并茂#xff0c;篇幅较长#xff0c;欢迎阅读完提供宝贵的建议#xff0c;一起提升文章质量。如果感觉不错不要忘记点赞、关注、转发哦。原文链接#xff1a; 《一文彻底读懂一致性Hash 算法》 通过阅读本…本篇是对文章《一文彻底读懂一致性哈希算法》的重写图文并茂篇幅较长欢迎阅读完提供宝贵的建议一起提升文章质量。如果感觉不错不要忘记点赞、关注、转发哦。原文链接 《一文彻底读懂一致性Hash 算法》 通过阅读本文你可以获得如下内容 背景
我们的场景就是大数据量的图片或者缓存请求能够在多个服务器之间进行负载均衡实现在某个服务器发生故障时最小的影响系统尽量的减少图片无法查看的请求。
那么我们为什么要提到一致性 Hash 算法呢简单的Hash 算法不能满足我们的需求吗下面跟我一起来学习下一致性 Hash 算法是如何解决我们的问题的。
为什么要用一致性 Hash 算法
为什么要用一致性 Hash 算法那肯定是因为它有优点优点就是可以尽可能小的改变已存在的服务请求与处理请求服务器之间的映射关系从而提高系统的可伸缩性和容错性。 负载均衡 一致性哈希算法能够在节点的增加或减少时最小化数据迁移的数量。在传统的哈希算法中当节点发生变化时几乎所有的数据都需要重新分配导致大量的数据迁移。而一致性哈希只需要迁移一小部分数据使得负载更加均衡。 容错性 当系统中的节点发生故障或需要扩展时一致性哈希算法能够最小化数据的丢失或迁移。新节点加入或旧节点离开时只有部分数据需要重新映射而不是整个数据集。 可伸缩性 一致性哈希算法支持动态地添加或删除节点而不需要重新计算大部分数据的映射关系。这使得系统更容易扩展同时减少了系统维护的复杂性。 简化路由表 在一致性哈希中每个节点仅负责一小部分数据因此路由表的大小相对较小。这降低了路由表的存储和维护成本。 分布式存储 一致性哈希常被用于分布式存储系统如分布式缓存、分布式文件系统等。它能够有效地处理大规模数据集的分片和分布提高系统的性能和可扩展性。
总的来说一致性哈希算法通过减小数据迁移的范围提高了分布式系统的可伸缩性、容错性和负载均衡性使得系统更具弹性和效率。
普通 Hash 算法有什么缺点
通过一个例子来看一下简单 Hash 算法有什么缺点。
假设我们有三台缓存服务器A、B、C用于缓存图片现在需要对请求过来的图片均匀的缓存在这三台服务器上以便它们均摊缓存图片的请求。
假设有三万张图片需要缓存也就是每台服务器平均缓存一万张左右。如果我们以没有任何规律的方式把三万张图片平均的缓存在三台服务器上也能满足我们的需求但是如果这样做的话会有什么问题呢想想看
问题就是
当我们访问某一张图片时最差的情况是需要遍历三台服务器从三万个缓存中找到我们所需要的缓存这样的话其实也就失去了缓存的意义并没有改善用户的体验。那么我们可以怎么做呢原始的做法就是对图片名称进行 Hash 运算假设图片名称是唯一的将 Hash 后的结果与服务器数量进行取模操作通过取模后的结果来决定缓存该存在哪个服务器上那么我们可以使用如下公式来决定图片应该存在哪台服务器上
其中 N 为服务器的数量。
hash(图片名称)%N 因为图片的名称是不重复的所以当我们对一个图片名称做相同的 Hash 计算时得到的结果应该是不变的。
如果我们有三台服务器使用哈希后的结果就是对3进行取余那么余数一定是0、1、2三个中的一个没错正好对应我们的服务器A、B、C所以如果求余的结果是0那么我们就可以把图片缓存在服务器A上相反如果取余的结果是1那就是缓存在服务器B上。
那么当我们访问任意一个图片时只需要对图片名称进行上述的操作即可知道图片缓存在哪个服务器上。如果图片在对应的服务器上不存在则证明对应的图片没缓存也就不需要再去其它的服务器上查询了通过这样的方法就可以平均的把三万张图片分散的放在三台服务器上而且当下次访问某张图片时直接就能判断出当前图片所在的服务器这样就能满足我们的需求了。
当使用了上面的哈希算法之后还会有什么问题呢试想一下如果三台缓存服务器已经不能满足我们的缓存需求那么我们是不是要增加一台那么缓存服务器的数量就由3台变成4台了此时如果仍然采用上述方法对同一张图片进行缓存那么这张图片所在的服务器编号必定与原来三台服务器时产生的结果不一致这种情况带来的后果就是当缓存服务器数量发生变动时所有缓存的位置都要发生改变。
换句话说当服务器数量发生改变时所有缓存在一定时间内是失效的当请求无法从缓存中读取到数据时则会向后端服务器发送请求同理假设三台服务器其中有一台服务器发生了故障无法进行缓存那么我们就需要将故障机器移除此时响应的缓存服务器数量也是发生了变化以前缓存的图片也就失去了意义此时大量图片缓存失效造成缓存雪崩此时缓存无法在分担压力后端服务器将承受压力整个系统也就有可能被压垮所以我们要想办法不让这种情况发生但是由于上述哈希算法本身的缘故使用取模算法进行缓存时这种情况是不可避免的为了解决这些问题一致性 Hash 算法也就应运而生了。
所以我们来回顾下使用简单 Hash 算法会产生的问题
当缓存服务器数量发生变化时引起缓存大量失效缓存雪崩可能会使后端服务器压力变大而崩溃。当缓存服务器数量发生变化时几乎所有的缓存位置都会发生变化那我们怎样才能减少受影响的缓存呢
其实这两个问题都可以使用一致性 Hash 算法解决现在我们继续深入了解一下一致性 Hash 算法。
什么是一致性 Hash 算法
一致性哈希算法是1997年在论文《Consistent hashing and random trees》中被提出的在分布式系统中应用非常广泛。一致性Hash 是一种 Hash 算法简单的说就是在移除或者添加一个服务器时此算法能够尽可能小的改变已存在的服务请求与处理请求服务器之间的映射关系尽可能满足单调性的要求。
在普通分布式集群中服务请求与处理请求服务器之间可以一一对应也就是说固定服务请求与处理服务器之间的映射关系某个请求由固定的服务器去处理。这种方式无法对整个系统进行负载均衡可能会造成某些服务器过于繁忙一直无法处理新来的请求而另一些服务器则过于空闲整体系统的资源利用率低并且当分布式集群中的某个服务器宕机会直接导致某些服务请求无法处理。
进一步的改进可以利用 Hash 算法对服务请求进行处理服务器之间的关系进行映射以达到动态分配的目的。通过 Hash 算法对服务请求进行转换转换后的结果对服务器节点值进行取模计算取模后的值就是服务请求对应的请求处理服务器。这种方法可以应对节点失效的情况当某个分布式集群节点宕机服务请求可以通过 Hash 算法重新分配到其他可用的服务器上。避免了无法处理请求的情况出现。
但这种方法的缺陷也很明显如果服务器中保存有服务请求对应的数据那么如果重新计算请求的 Hash 值会造成大量的请求被重定位到不同的服务器而造成请求所需要的数据无效这种情况在分布式系统中是难以接受的。一个设计良好的分布式系统应该具有良好的单调性即服务器的添加与移除不会造成大量的哈希重定位而一致性哈希恰好可以解决这个问题。
一致性哈希算法将整个哈希值空间映射一个虚拟的圆环整个哈希空间的取值范围为 02 32 ^{32} 32-1 整个空间按顺时针方向。02 32 ^{32} 32-1,在零点方向重合。接下来使用如下算法对请求进行映射将服务请求使用 Hash 算法算出对应的 Hash值然后根据 Hash 值的位置沿圆环顺时针查找遇到的第一个服务器就是所对应的处理请求服务器。当增加一台新的服务器受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器也就是顺着逆时针方向遇到的第一台服务器之间的数据其它都不会受到影响。综上所述一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据具有较好的容错性和可扩展性。
首先一致性哈希算法是采用取模的方法只是刚才的取模算法是对服务器数量进行取模那么我们只要不对服务器数量进行取模而对一个常量进行取模不就可以了吗所以一致性哈希算法是对2 32 ^{32} 32进行取模我们把0-2 32 ^{32} 32次方想象成一个圆就像钟表一样的圆钟表的圆可以想象是圆上有60个点而我们的这个圆是由2 32 ^{32} 32个点组成的圆示意图如下 圆的正上方的点代表00点右侧第一个点代表1左侧第一个点代表2 32 ^{32} 32-1我们把0-2 32 ^{32} 32-1之间的圆环称之为 Hash 环。
下面跟我一起看下一致性 Hash 算法是怎么在这个圆上来体现的。
首先我们还是有三台服务器分别是服务器A服务器B服务器C那么在我们的生产环境中我们对这三台服务器的 IP 地址进行 Hash用 Hash 后的结果对2 32 ^{32} 32进行取模运算得到的结果就是服务器的位置。
Hash(服务器IP地址)%2 32 ^{32} 32
通过这个公式计算的结果肯定是0-2 32 ^{32} 32-1之间的一个数我们就用这个数代表服务器A。 然后我们用同样的方法计算出服务器B和服务器C的位置表示如下。 假设三台服务器经过计算之后的位置如上图所示理想情况下是这个样子但是现实往往很无情。
好了到这里我们已经把服务器与Hash环绑定到了一起下面就是把数据绑定到 Hash环上那么我们下面就用同样的方法把需要缓存的对象放到Hash环上。
还是按照刚才的例子对三万张图片进行缓存此时我们还是使用如下公式。
Hash(图片名称)%2 32 ^{32} 32
第一张图片映射的结果如下图所示假设。 那么图片1保存在哪台服务器上去呢上面的图片会被缓存到服务器A上为什么会这样呢因为从图片1的位置开始沿顺时针方向遇到的第一个服务器就是服务器A所以上图会被缓存到服务器A上如下图所示 所以一致性 Hash 算法就是通过这种方法来判断对象该存储在哪台服务器上的也就是将缓存服务器与缓存对象绑定到 Hash 环上之后从被缓存的对象开始顺时针方向遇到的第一台服务器就是缓存对象要存储的服务器由于缓存对象对服务器 Hash 后的值是固定的所以在服务器不变的情况下一张图片必定会缓存在固定的服务器上所以当下次访问该图片时只要再次使用同样的哈希算法计算即可获取出该图片在哪台服务器上然后直接去对应的服务器上获取即可。
刚才的示例是一张图片下面演示一下多张图片的位置。 图片1图片4会缓存在服务器A上图片2缓存在服务器B上图片3缓存在服务器C上。
经过上面的描述我想同学们应该能够知道一致性 Hash 的原理了所以同学们考虑一下一致性 Hash 可以解决上面的两个问题吗首先还是第一个问题当服务器数量发生变动时缓存会同一时间大量失效造成缓存雪崩从而有可能引发系统的崩溃那么使用一致性Hash 算法能够避免这个问题吗下面我们来看一下。
假设服务器B出现故障现在我们需要把服务器B移除掉那么我们从 Hash 环上移除服务器B之后如下所示 在服务器B没有故障未被移除时图片2应该是缓存在服务器B上可是当服务器B有了故障被移除后图片2按照顺时针方向遇到的第一个服务器就变成了服务器C所以此时图片2就被缓存在服务器C中也就是说如果服务器B出现故障图片2的缓存位置会发生变化。 此时图片3仍然会被缓存中服务器C中图片1与图片4缓存在服务器A中这与服务器B移除前后并不会有影响这也就是 Hash 算法的优点如果使用之前的 Hash 算法服务器数量发生变化时所有的缓存对象都会发生变化而使用一致性哈希算法之后服务器的数量如果发生变化并不是所有的缓存都会失效而只有部分缓存才会失效所以这种情况下不至于所有的缓存失效都在同一时间集中到后端服务器上。
思考一下通过上面的学习可以知道了一致性 Hash 算法带来的优点了那么有什么缺点呢或者说有什么需要注意的点呢这块你可以想到吗
一致性 Hash 算法有什么缺点
在这里也是给同学们举例说明。
在介绍一致性哈希时我们是非常理想化的假设3台服务器均匀的分布在 Hash 环上如下图所示 但是往往现实不会如此在实际的使用过程中服务器有可能会被映射为如下图所示的情况 聪明的你肯定想到如果发生了这种情况那么缓存的对象可能会集中的缓存在一台服务器上这也就是 Hash 环的倾斜如下图所示 此时如图所示图片1图片3图片4图片5都会缓存到服务器A上图片2缓存中服务器B上服务器C上没有图片也就是说服务器资源并没有理想化平均的被使用。最坏的情况下如果此时服务器A发生故障那缓存失效的对象也就达到了最大值极端情况下也有可能造成后端服务器的崩溃。此时这种情况称之为 Hash 环的倾斜那么怎么防止 Hash 环的倾斜呢一致性hash算法使用虚拟节点来解决了这个问题下面我们来看看。
如何最小化一致性 Hash算法带来的影响
还是按照我们说的假设我们只有三台服务器当我们把服务器映射到 Hash 环上的时候很有可能发生 Hash 环偏斜的情况当 Hash环偏斜以后缓存往往会极度不平衡的分布在各个服务器上聪明的你肯定想到了要想均衡的将缓存分布在三台服务器上那么只要这三台服务器尽可能多的均匀的分布在H ash 环不就行了吗但是真实的服务器资源只有3台我们怎么凭空让它多起来呢没错就是凭空让服务器的节点多起来既然没有多余的真正的物理服务器节点我们只能将现有的物理节点虚拟出来这些由实际节点虚拟复制出来的节点被称为“虚拟节点”加入虚拟节点之后的 Hash 环如下图所示 虚拟节点是实际节点在 Hash 环上的复制品一个实际节点可以复制多个虚拟节点。
从上图可以看出ABC三台服务器分别虚拟出来一个虚拟节点当然如果你需要的话也可以虚拟出更多的节点此时为了画图演示我们各只虚拟出一个节点。
增加了虚拟节点的概念后缓存的分布就均匀了很多上图中图片1图片3缓存在服务器A图片2图片4缓存在服务器B图片5缓存在服务器C如果你还不放心的话可以虚拟出更多的虚拟节点以便减少 Hash环倾斜带来的影响虚拟节点越多Hash环的节点越多缓存被均匀分布的可能就越大。
所以此时缓存对象已经均衡的分布在 Hash环上如果在发生服务器故障那么受影响的缓存对象就是发生故障的服务器逆时针方向到遇到的第一台服务器之间的数据受影响的缓存对象大大减少。
总结
读到这了不知道同学们收获了多少如果没有记住没关系下面我来给大家总结一下开头的几个问题。 为什么要用一致性 Hash 算法 能够在服务器发生故障时最小化因为故障造成的影响并且可以提升系统的可伸缩性。 普通 Hash 算法有什么缺点 其中一台服务器故障或者新增服务器时大量缓存同时失效造成缓存雪崩。 什么是一致性 Hash 算法 一致性 Hash 算法就是可以尽可能小的影响已经存在的请求与服务器的映射关系。 一致性 Hash 算法有什么缺点 Hash 环偏移。 如何最小化一致性 Hash 算法带来的影响 使用虚拟节点。
好了一致性哈希算法的原理就总结了这里如果错误欢迎赐教。如果感觉对你有帮助欢迎点赞、评论、转发。
参考链接
百度百科维基百科参考博客1参考博客2参考链接3
