最近有朋友来问什么是Hash共识算法。他说采访的时候有人问他，但他没有回答，因为他听不懂。他问我有没有推荐的学习资料。我当时正在工作，没有时间。回复，晚上回去的时候忘记了这个。今天突然看到这个，加班加点给大家整理一下什么是Hash共识算法。希望对大家有所帮助！文末送书，长按抽奖助手小程序即可参与，好运连连！经常看我文章的朋友应该对我的写作套路不陌生。当我上来时，我要问为什么？那就是为什么会有Hash共识算法？就像前面介绍为什么会有Spring一样，首先会从历史或者项目发展的角度来分析。今天的分享还是老套路。下面我们从历史的角度一步步来分析一下什么是Hash一致性。算法！一、Redis集群的使用我们在使用Redis的时候，为了保证Redis的高可用，提高Redis的读写性能，最简单的方式就是做主从复制，形成Master-Master或者Master-Slave，或者构建Redis集群进行数据读写分离，类似于数据库主从复制和读写分离。如下图：同样类似于数据库，当单表数据大于500W时，需要分库分表。当数据量很大时（标准可能不同，取决于Redis服务器的容量），我们也可以使用执行类似的操作是分库分表。假设我们有一个社交网站，需要使用Redis来存储图片资源。存储格式为键值对。键值为镜像名称，值为镜像所在文件服务器的路径。我们需要根据文件名找到文件所在的文件服务器。上面的路径，数据量大概是2000W，按照我们约定的规则划分数据库，规则是随机分布，我们可以部署8台缓存服务器，每台服务器大概包含500W条数据，进行master-slave复制，示意图如下：由于规则是随机的，我们所有的数据都可能存储在任意一套Redis中。比如上图中，我们的用户搜索一张名为“a.png”的图片。由于规则是随机的，我们不确定具体是在哪个Redis服务器上，所以需要进行1,2,3,4,4次查询才能查询到（即遍历所有Redis服务器），即显然不是我们想要的结果，有了解的朋友可能会觉得随机规则不够用，可以使用类似数据库的分库分表规则：根据Hash值，取模，根据类别，根据某个字段值等等通用的规则就可以出来了！好吧，根据我们的主题，我们将使用Hash方法。2、Redis集群可以考虑使用Hash。如果我们使用Hash，每张图片在分库时都可以定位到特定的服务器。示意图如下：上图中，假设我们要查找“a.png”，由于有4台服务器（不包括从库），公式为hash(a.png)%4=2，它可以看到2号服务器所在，这样就不会遍历所有的服务器，大大提高了性能！3.使用Hash的问题虽然上面的方法提升了性能，但是我们不再需要遍历整个Redis服务器了！但是在使用上面的Hash算法进行缓存的时候，会存在一些缺陷，主要体现在当服务器数量发生变化时，所有的缓存位置都会发生变化！试想一下，如果4台缓存服务器已经不能满足我们的缓存需求，那怎么办呢？很简单，多加几台缓存服务器就可以了！假设：我们增加了一个缓存服务器，那么缓存服务器的数量从4个变成了5个。那么原来的公式hash(a.png)%4=2就变成了hash(a.png)%5=?，可以想象，这个结果肯定不是2。这种情况的结果是，当服务器数量发生变化时，所有缓存的位置都会发生变化！也就是说，当服务器数量发生变化时，所有的缓存都会在一定时间内失效。当应用无法从缓存中获取数据时，就会向后端数据库请求数据（还记得上一篇文章中的《缓存雪崩》吗？？）！同理，假设4台缓存中的一台突然出现故障，无法进行缓存，那么我们就需要将故障机器移除，但是如果移除一台缓存服务器，那么缓存服务器的数量从4台变为3台，上面提到的也会出现问题！所以，我们应该想办法避免这种情况的发生，但是由于上面提到的Hash算法本身，在使用取模方式进行缓存时，这种情况是不可避免的。为了解决这些问题，Hash一致性算法（consistencyHashalgorithm）诞生了！4、一致性Hash算法的神秘面纱一致性Hash算法也是采用取模的方法，只不过刚刚介绍的取模方法是对服务器个数取模，而一致性Hash算法是对2取模^32，那是什么意思？简单的说，一致性哈希算法将整个哈希值空间组织成一个虚拟的环，比如假设某个哈希函数H的值空间是0-2^32-1（即哈希值是一个32位符号整形），整个哈希环如下：整个空间按顺时针方向组织，环正上方的点代表0，0点右边的第一个点代表1，以此类推，2,3,4,5,6...直到2^32-1，也就是说0点左边的第一个点代表2^32-1，0和2^32-的方向1重合在零点，我们把这个由2^32个点组成的环称为Hash环。下一步是使用Hash在每个服务器上进行哈希。具体来说，可以选择服务器的IP或者主机名作为关键字进行散列，这样每台机器都可以确定自己在散列环上的位置。这里，假设上述四个服务器使用IP地址hash后在环空间中的位置如下：接下来使用如下算法定位数据，访问对应的服务器：使用同样的函数Hash到计算datakey的hash值，确定数据在环上的位置，从这个位置顺时针沿着环“走”，第一个遇到的服务器就是它应该定位的服务器！比如我们有四个数据对象ObjectA、ObjectB、ObjectC、ObjectD，经过hash计算后，在环空间中的位置如下：根据一致性Hash算法，数据A会被分配给节点A，B路由到NodeB，C路由到NodeC，D路由到NodeD。5.一致性Hash算法的容错性和可扩展性现在假设NodeC不幸宕机。可以看到此时对象A、B、D不会受到影响，只有对象C会被迁移到节点D。一般来说，在一致性Hash算法中，如果某个服务器不可用，受影响的数据只是来自本服务器到其环空间中的上一个服务器（即逆时针走时遇到的第一个服务器），其他数据不受影响，如下图：再考虑另一种情况，如果系统中增加了一个服务器节点X，如下图所示：此时对象A、B、D不受影响，只有对象C需要搬迁到新的NodeX！通常，在一致性Hash算法中，如果增加了一个服务器，受影响的数据只是从新服务器到其环空间中的前一个服务器（即逆时针行走时遇到的第一个服务器），其他数据不会受到影响。综上所述，一致性哈希算法对于节点的增减只需要对环空间中的一小部分数据进行迁移，具有良好的容错性和可扩展性。6、Hash环的数据倾斜问题当一致性Hash算法服务节点过少时，很容易因为节点划分不均匀造成数据倾斜（大部分缓存对象都缓存在某台服务器上）。例如，系统中只有两台服务器，环状分布如下：此时，大量的数据必然会集中在节点A上，只有极少量的数据会位于节点B上。为了解决这种数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即为每个服务节点计算多个hash，在每个计算结果位置放置一个服务节点，称为虚拟节点。具体方法可以通过在服务器IP或主机名后加一个数字来实现。例如，在上面的情况下，可以为每个服务器计算三个虚拟节点，所以“节点A#1”、“节点A#2”、“节点A#3”、“节点B#1”、“节点A”#1”可以分别计算出“B#2”和“NodeB#3”的哈希值，形成六个虚拟节点：同时数据定位算法不变，只是多了一个映射步骤从虚拟节点到实际节点，例如定位“NodeA#1”、“NodeA#2”、“NodeA#3”三个虚拟节点的数据都位于NodeA上。这样就解决了数据倾斜的问题当服务节点很少时。在实际应用中，虚拟节点的数量通常设置为32个或更多，这样即使是少数几个服务节点也能实现相对均匀的数据分布。7.小结上面我们一步步分析了什么是一致性Hash算法，主要是考虑到分布式系统的每个节点都可能出现故障，可能会动态增加新的节点。如何保证当系统的节点数量发生变化时，我们的系统仍然能够对外提供良好的服务，这是值得思考的！PHP代码实现示例：$hostsMap=['img1.findme.wang','img2.findme.wang','img3.findme.wang'];$hashRing=[];函数getImgSrc($imgName){全局$hostsMap;全局$hashRing；//将节点映射到哈希环if(empty($hashRing)){foreach($hostsMapas$h){$hostKey=fmod(crc32($h),pow(2,32));$hostKey=abs($hostKey);$hashRing[$hostKey]=$h;}//从小到大排序，方便查找ksort($hashRing);}//计算图像哈希$imgKey=fmod(crc32($imgName),pow(2,32));$imgKey=abs($imgKey);foreach($hashRingas$hostKey=>$h){if($imgKey<$hostKey){返回'http://'.$小时。'/'。$img名称；}}返回'http://'。当前（$hashRing）。'/'。$imgName;}var_dump(getImgSrc("logo1.png"));var_dump(getImgSrc("logo2.png"));var_dump(getImgSrc("logo3.png"));
