假设我们现在在做一个简单的文件缓存服务。由于文件较多，我们先用3台机器存储文件。为了从文件名中得到存储机器（假设文件名不重复），考虑先对文件名做哈希运算，然后取3的余数，余数就是机器号它所在的位置。这个系统运行了很久，后来文件逐渐增多，3台机器已经放不下了。现在我们正在考虑扩展到4台机器。这时候我们的算法更新为hash(filename)%5。那么在用这个算法获取abc.txt文件所在的缓存机器时，当它的hash值为10时，就会映射到0号机器上，之前是存放在1号机器上的。这时候会重新映射文??件到机器0上，或者机器1上的文件迁移到机器0上。所以，添加两台机器后，缓存失效了。我们通过代码粗略判断缓存失效的比例：publicstaticvoidmain(String[]args){//缓存失效计数intcount=0;//假设共有10000个文件for(inti=0;i<10000;i++){//文件名StringfileName="file#"+i;inthashCode=fileName.hashCode();//原存储位置intoldSite=hashCode%3;//添加两台机器后，当前存储位置intnewSite=hashCode%5;if(oldSite!=newSite){count++;}}System.out.println(count);}运行后发现80%以上的缓存都会失效。也就是说无论是增加机器还是减少机器，都会有大面积的缓存失效。这是我们不想看到的结果，那么有没有新的算法呢？一致性哈希算法应运而生。该算法可以大大减少加减机器时无效缓存的数量。首先，这里有一个圆圈，可以看成是一个从0到2^32-1首尾相接的环。我们先对一台机器的ip进行hash运算，然后对2^32取模，即hash(ip)%2^32，这个数一定要在环上。假设我们使用的哈希算法返回的哈希值是int类型，就相当于取了模。因此，我们在圆环上标出三台机器的位置。这时候我们需要将文件映射到环上，使用相同的哈希函数，即hash(文件名)。假设这里有4个文件，我们在环上标出文件的位置。如何判断文件现在存放在哪台机器上？很简单，从当前文件开始，顺时针找到第一台机器，就是文件的存放位置。假设此时机器2宕机，我们将机器2从环中移除，观察文件3的变化。当机器2宕机时，文件3会重新指向机器3。也就是说，当机器2宕机时，原本映射到机器1和机器2之间位置的文件将重新映射到机器3。因此，一致性哈希可以大大减少缓存失败的范围，从而不会“影响全身”。不知道大家有没有注意到，在上图中，几台机器均匀分布在环上，这是一种非常理想的情况。然而，现实中可能并非如此，假设三台机器在映射后彼此非常接近。当机器数量很少时，映射后，环上节点分布不均匀，导致大部分文件都落在同一台机器上，即存在数据倾斜的问题。如图所示，这4个文件都存储在机器1上，如果有一天，机器1无法处理大量的文件访问，这些文件会立即转移到机器2上。机器2也会承受不住，最终导致整个系统的连锁崩溃。既然问题的根源在于机器数量少，那我们就可以增加机器数量！但机器是实际存在的物理资源。机器形成一些虚拟节点，通过在物理节点的ip上加上后缀序号来实现。当虚拟节点以相同的算法映射到环上时，文件1最终会落在机器2上。理论上，虚拟节点越多，分布越均匀。下面我们以代码的形式来验证一下。publicclassMain{//真实节点privatestaticfinalString[]ipArray=newString[]{"192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4"};//哈希环（哈希值->realnodeip)privatestaticfinalTreeMapcircle=newTreeMap<>();//指定初始化hash环的倍数privatestaticvoidinitCircle(intmul){//映射真实节点for(Stringip:ipArray){circle.put(hash(ip),ip);//根据倍数映射虚拟节点for(inti=1;i<=mul;i++){Stringvirtual=ip+"#"+i;circle.put(hash(virtual),ip);}}}//获取指定文件所在的机器ipprivatestaticStringgetIpByFileName(StringfileName){longhash=hash(fileName);LonghigherKey=circle.higherKey(hash);if(higherKey==null){//返回第一个ipreturncirclehashring.get(circle.firstKey());}//返回最小ipreturncircle.get(higherKey);}//统计落在每个节点上的文件总数(ip->totalnumberoffiles)privatestaticMapcount(longfileCount){//(ip,文件总数)Mapma??p=newHashMap<>();for(longi=1;i<=fileCount;i++){Stringip=getIpByFileName("file#"+i);LongipCount=map.get(ip);map.put(ip,(ipCount==null?0:ipCount)+1);}returnmap;}//打印每个ip存储的文件总数的百分比privatestaticvoidprint(intfileCount){Mapma??p=count(fileCount);for(Stringip:ipArray){LongipCountL=map.get(ip);longipCount=ipCountL==null?0:ipCountL;doubleresult=ipCount*100/(double)fileCount;//保留一位小数Stringformat=String.format("%.1f",result);System.out.println(ip+":"+format+"%");}}//32位Fowler-Noll-Vo哈希算法//https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_functionprivatestaticLonghash(Stringkey){finalintp=16777619;longhash=2166136261L;for(intidx=0,num=key.length();idx>7;hash+=hash<<3;hash^=hash>>17;hash+=hash<<5;if(hash<0){hash=Math.abs(hash);}returnhash;}publicstaticvoidmain(String[]args){//初始化哈希环initCircle(1000000);//文件总数为10000print(10000);}}倍数为0时：192.168.1.1:0.0%192.168.1.2:0.0%192.168.1.3:100.0%192.168.1.4:0.0%相当于没有有虚节点，可以看到极度不平整，坡度严重。当倍数为100时：192.168.1.1:28.4%192.168.1.2:22.4%192.168.1.3:34.6%192.168.1.4:14.6%斜率变好了！但是倍数为10000时还是不满意：192.168.1.1:24.6%192.168.1.2:25.9%192.168.1.3:23.3%192.168.1.4:26.3%基本上是比较均匀的，大胆的，我们调整倍数为100万，文件数也调整为100万个192.168.1.1:25.0%192.168.1.2:24.9%192.168.1.3:25.0%192.168.1.4:25.1%可以看出所有IP下存放的文件总数很均匀！
