0。我为什么要写这篇文章？有朋友在做分布式存储。他在一次聊天中问了我一些问题：什么是一致性哈希？如何实现？有什么好处？对于这个问题，脑子里只闪过几个词：md5，哈希函数，哈希环。在我看来，哈希是一种算法。一句话概括就是：一种将无限数据映射到有限集合的算法。朋友说：你这话很官方，但等于什么都没说。哈哈，身为某厂高级开发工程师，此刻感到惭愧。惭愧，惭愧，请允许我做出一个悲伤的表情。1.散列对于散列，在日常开发中很多场景都会用到，例如：md5等散列函数分库分表时，通过某个字段的散列值对一个固定值取模来确定对应的库表是大量数据的集合。根据某个字段作为拆分键，对数据进行拆分。PHP的HashTable、Go的map、Python的dict等数据结构在实现Redis分片时都使用crc16对key进行hash。然后取16384的模来判断分片等等...除了上面的场景，还有很多地方用到了hash，都是hash的一种实现。哈希函数1.1哈希碰撞无限的原始数据经过哈希函数运算后，得到的哈希结果会有一定的概率相同。那么，当这些不同的原始数据得到相同的哈希值时，就是哈希冲突。例如，如下图所示：c和d经过某个哈希函数计算得到相同的哈希值10，则c和d之间发生了哈希冲突。哈希冲突须知：哈希冲突无法避免（因为哈希结果范围是有限的，而原始数据是无限的）。哈希值范围越大，碰撞概率一般越低。一个好的散列函数不仅仅关乎运算速度1.2散列冲突有两种方案。哈希冲突情况下常用的方案有：开放地址法拉链法开放地址法一般不经常使用，读者可以自行查阅相关资料。拉链法则被用在很多场景，甚至开源系统。比如：PHP的HashTable（PHP5使用双向链表，PHP7使用数组），Go的map底层实现。zipper的方法如图，c和d的hash结果都是10，存储的时候用一个链表把它们串起来（像拉链子一样）。其中，bucket是某个时刻固定大小的数组，hash值对固定值取模后得到下标。通常，桶的大小会在某些临界条件下自动膨胀和收缩。查找时，先根据计算出的哈希值定位到桶对应的位置，然后遍历链表找到对应的数据。注意：原始数据经过Hash计算后一般会得到一个比较大的hash值。这时候就需要用hash值对bucketsize取模来确定数据存储位置。理想情况下，不会发生哈希冲突，并且该值落入桶中。不同位置，搜索时间复杂度为O(1)最坏情况，所有数据哈希碰撞，值都落在桶的同一个位置，搜索时间复杂度为O(n)1.3为什么要用hash作者之前接过一个项目，每天有2亿多条数据，这些数据需要投放市场。如果建表，如果存在于表中，那将是一场灾难。当时作者建了10张表，通过用户uid对10取模来判断当前数据落在哪个表，其中uid%10相当于hash算法。这样，2亿多条数据被分到不同的表中，减少了单表的数据量。好处：可以提高查询速度，提升数据同步效率等等。在这种情况下，使用哈希来拆分大量数据是完美的。1.4普通哈希的优缺点说了很多，下面说说缺点。假设有这样一个场景：原本用10张表来存储数据，完全没有问题。突然有一天，业务需要20张表或者5张表来存储数据，怎么办？由于表数发生变化，此时的hash函数uid%10应该改为uid%20或uid%5。这时候就需要对旧数据进行处理。我应该怎么办？重复！Rehash全量数据，使用新的哈希函数重新计算所有数据，然后将数据存储到新表中。实际开发中会有很多rehash的场景，所以需要提前做好一些预案。如果数据量很大，一般有两种解决方案：停服维护，在维护期间进行数据rehash迁移；异步迁移，在写数据的时候，用一个新的hash函数来确认落到哪个表。查询时如果发现数据没有迁移，需要同时使用多个hash函数从多个表中读取数据（如果还涉及到分页，会比较麻烦）。在提供服务的同时，对旧数据进行rehash迁移。方案一需要停止服务，这要看产品和公司业务是否允许。如果可能，这是最好的解决方案。方案二是在不停止服务的情况下进行迁移，相当于边开飞机边换轮胎。高风险和复杂的逻辑处理。另外，在数据量很大的情况下，rehash可能是一个很长的过程。那么，还有什么好的解决办法吗？答案是肯定的。解决问题的角度已经从迁移全量数据转变为迁移部分数据。它就是：一致性哈希。2.Consistenthashing维基百科告诉我们：Consistenthashing是一种特殊的哈希算法。使用一致性哈希算法后，哈希表槽数（size）的变化平均只需要重新映射K/n个关键字，其中K为关键字数，n为槽数。然而，在传统的哈希表中，添加或删除槽位需要重新映射几乎所有键。Consistenthashing是由MIT的Karger和他的合作者提出的，现在这个想法已经扩展到其他领域。这篇1997年的学术论文描述了如何将“一致性哈希”应用于具有易变用户的分布式Web服务。每个哈希表代表分布式系统中的一个节点，在系统中添加或删除节点只需要移动K/n项。一致性哈希还可以用于实现健壮的缓存，以减少大型Web应用程序中部分系统故障的负面影响。一致性哈希的概念也被应用到分布式哈希表（DHT）的设计中。DHT使用一致性哈希来划分分布式系统的节点。通过连接所有节点的覆盖网络，可以将所有关键字有效地定位到某个节点。DavidKarger和他的合作者列出了几个使一致性哈希在Internet分布式缓存中有用的属性：更少的冗余负载平衡过渡平滑的存储平衡关键字monotonic2.1实现-哈希环一致性哈希将每个对象映射到环边缘的一个点，系统将可用的节点机器映射到环上的不同位置。在寻找一个对象对应的机器时，需要使用一致性哈希算法计算出该对象在环的边缘上的位置，沿着环的边缘搜索，直到遇到某个节点机器。这台机器是应该保存对象的位置。.当删除一个节点机器时，这台机器上保存的所有对象都会被移动到下一台机器上。当在环的边缘某个点添加机器时，该点的下一个机器需要将这个节点之前的对应对象移动到新的机器上。改变对象在节点机上的分布可以通过调整节点机的位置来实现。假设有一个环形结构，上面有很多节点，一般是2的32次方。我们需要在hashring中做的事情大致如下：对某些参数（mac地址，IP地址等）进行hash计算上传数据存储时，对指定的key进行hash计算，然后使用hash值来取2^32的模来确定数据落在环中的哪个节点上。得到环的节点值后，顺时针找到遇到的第一个节点。一个服务器，这个服务器就是存放当前数据的地方。普通哈希环从图中可以看出，一共有三台服务器，分别位于哈希环的不同节点。数据A、B、C、D、E也落在环的不同位置。根据一致性哈希的要求，数据计算出自己在环中的节点后，顺时针找到第一个服务器节点，该服务器就是数据的存储位置。那样的话，可以看出：数据D、E、A存放在服务器1，数据B、C存放在服务器2，没有数据存放在服务器32.2场景重现场景1（收缩）假设即服务器2发生故障，以上数据都需要迁移，此时只需要将服务器1和服务器2之间的数据B和C迁移到服务器3即可。场景2（扩容）假设在数据B和C之间增加了服务器4，那么只需要将服务器2上存储的数据B迁移到服务器4。从以上两个场景可以看出，无论是扩容或缩容，与传统的hash方法相比，扩容或缩容时只需要迁移部分数据。大大简化了数据迁移量，大大降低了出现问题的概率。2.3哈希环优化版从上面的例子可以看出：数据D、E、A存放在服务器1中，数据B、C存放在服务器2中，服务器3中没有存放任何数据。'知道你是否发现了：服务器3不存储数据。服务器1存储的数据最多，此时出现数据倾斜。那么，有没有办法解决数据倾斜呢？解决方案是优化负载策略，引入虚拟服务器节点。原始服务器在哈希环上只能有一个节点。所以，此时我们虚拟化每台服务器。例如：原来的服务器1现在被虚拟成两台服务器，服务器1-A和服务器1-B。这时，这两个虚拟服务器就会在哈希环上有两个不同的节点（但在真实服务器上却映射到同一个）。此时，哈希环发生变化。在带有虚拟节点的哈希环中，服务器节点的数量从原来的3个节点变成了6个节点。根据一致性哈希的要求，数据存储的位置变为：数据A存储在服务器1-A，数据B存储在服务器3-A，数据C存储在服务器2-A，数据D存储在服务器1-B，数据E存放在服务器2-B由于上面的服务器节点是虚拟服务器节点，所以最终数据存放在真实位置：数据A和D存放在服务器1，数据C和E存储在服务器2，数据B存储在服务器3。可以看出，通过引入服务器虚拟节点，数据存储变得更加均衡。3.总结通过一系列的场景分析，我们了解了哈希、哈希碰撞以及哈希碰撞的解决方案，并提出了普通哈希存在的全量数据迁移问题。同时，我们也找到了全量数据迁移的解决方案——一致性哈希。通过对一致性哈希的理解，我们了解到它的巨大潜力。但是，面对存储大量数据的场景，可能会出现数据倾斜，导致部分服务器负载过高。引入服务器虚拟节点后，优化一致性哈希的负载，实现各服务器的均衡状态。在实际场景中，面对不同的业务可能会有一些差异。但是，一般逻辑是相似的。
