架构师训练营第 5 周 - 一致性 hash 算法总结及作业

关注

发布于: 2020 年 07 月 06 日

在了解一致性 hash 算法之前，最好先来了解一下其应用场景，在了解了其应用场景之后，再来理解一致性 hash 算法，就比较容易了，也能体现一致性 hash 算法的优点。

场景描述

假设有三台服务器，用于缓存图片，我们为这三台服务器编号为：0，1，2。现在有 3 万张图片需要缓存，我们希望这 3 万张图片能均匀的分布在这三台服务器上，以便它们能够分摊缓存的压力。也就是说每台服务器需要缓存大约 1 万张图片，那么，我们应该怎么做呢？如果我们没有任何规则的将这 3 万张图片均匀的分布到这 3 台服务器上，可以满足我们的要求吗？可以！，但是这样做的话，访问某张图片的时候就会遇到问题，我们需要遍历这 3 台服务器，从 3 万个缓存项目找到我们需要的图片，遍历过程效率太低，时间太长，当我们找到需要的缓存项时，时长可能是不被接受的，那么也就失去了缓存的意义。缓存的目的就是提高访问速度，改善用户体验，减轻后端服务器的压力，如果每访问一个缓存项都需要遍历所有缓存服务器时，想想都觉得累。那么我们该怎么办呢？原始的做法是对缓存项进行哈希，将 hash 后的结果对缓存服务器数量进行取模操作，通过取模后的结果，决定将该缓存项缓存在哪台服务器上。

具体的实现过程如下：

1、我们以图片的名称作为访问的 key

2、图片的名称是不重复的，这样经过 hash 计算之后，都会得到一个不同的结果值

3、计算公式为：hash(图片名称)%N，N 代表缓存服务器的数量

在经过以上的过程之后，每张图片都能够对应到一台缓存服务器(3 台缓存服务器)，如下图所示：

由于图片的名称和服务器是固定不变的，所以每次取模出来的值都是一样的，都能唯一映射到一台缓存服务器，这样再访问任意图片的时候，就不用再遍历所有服务器，直接定位至某一台缓存服务器，实现高效访问。

但这种方式存在一些问题，主要的问题就是：

1、取模的 N 是取的缓存服务器的数量，这样就和缓存服务器强耦合，如果增(删)缓存服务器，由于除数变化，被除数不变，就会造成余数发生变化，余数变化，则以前和缓存服务器之间的映射就失效了。放在以上的应用场景中就是：大量的图片通过 hash 取模后不能映射到缓存服务器（也会有一些图片会存在有效映射），那么就只有从后端去拿图片，这样在高并发的场景下，就会造成成缓存雪崩，给后端服务器造成巨大的 IO 压力，有可能造成整个系统瘫痪

由于原始 hash 算法的这种缺陷，所以一致性 hash 算法就出现了。

一致性 hash 算法的概念

其实，一致 hash 算法也是使用取模的方法，只不过它不是对服务器的数量进行取模(这样会跟服务器产生强耦合)，而是对一个固定常数 2^32 取模。

首先，我们把 2^32 想象成一个圆，就像钟表一样，钟表的圆是由 60 个点组成的圆，而此处我们把这个圆想象成是由 2^32 个点组成的圆，示意图如下：

圆上方的点代表 0，0 点右侧第一个点代表 1，以此类推，2、3、4、5......2^32-1，0 点的左侧第一个点就是 2^32-1。我们把这个由 2^32 组成的圆环称为 hash 环。

服务器在经过 hash 运算并取模后，会对应到圆上的一个唯一点，同时被缓存的对象经过同样的运算后也会对应到一个唯一的点，然后从顺时针开始离他最近的服务器节点，就是它需要被缓存的服务器节点。

具体实现过程如下：

1、算法公式为：hash(对象/节点)%2^32

2、将所有的缓存服务器节点结过算法计算后，会唯一对应到环上的一个点，记为:A、B、C

3、将所有需要被缓存的对象结处算法计算后，同样会对应到环上的一个点（有可能会与服务器节点合，正好就是它）,然后按顺时针查找离该对象最近的服务器节点，就是该对象缓存的宿主

我们还是套用上面的应用场景：

1、假设现在的缓存服务器还是 3 台，设为：A、B、C；采用服务器 Ip 进行 hash 计算

2、需要被缓存的图片有 4 张，设为：P1、P2、P3、P4；采用图片名称进行 hash 计算

3、在经过一致性 hash 算法计算后，环上的分布如下图所示

在经过一致性 hash 计算之后，P1、P4 对应的缓存服务器为 B；P2 对应的缓存服务器为 C；P3 对应的缓存服务器为 A。这样数据也有大致均匀的分布到各个服务器节点之上，服务器 IP 地址和图片的名称都是相对固定不变的（如果服务器 IP 地址发生变化，就当是增/删节点），那么在经过一致性 hash 算法之后得到的值也是固定不变的，因此满足一次缓存，高效访问的要求。

下面我们再来看一下，增加节点的场景下，一致性 hash 算法是否还能满足我们的需求：

1、现有缓存服务器由于访问压力大，已经快支撑不住了，因此决定再增加一台缓存服务器 D

2、随机访问的图片还是原来的那 4 张图片，设为：P1、P2、P3、P4

3、增加缓存服务器以后，环上的分布如下图所示

可以看到，P1 的缓存失效了（原来是缓存在 B 服务器中的），需要从后端重新获取，但其他（P2、P3、P4）的缓存是有效的，也没有改变，还是映射到原来的缓存服务器中。

总结：对于一致性 hash 算法，往现有环中增加服务节点，只会失效有限的缓存项（这部分数据需要重新从后端获取），其他缓存项仍然可用，这就比原始 hash 算法的效率更高，对前端的影响更小，同时也达到了增加节点，分摊集群压力的效果。

下面我们再来看下删除服务节点的应用场景：

1、C 服务器出现硬件故障，需要更换服务器，但新服务器三天后才能到达，现在需要将 C 服务器从集群中下线，以免造成缓存无服务可用，需从后端拿数据

2、删除 C 服务器后，环上的分布情况如下：

可能看到，将 C 服务器从环上移除后，访问 P2 对象的缓存项失效后，需要从后端拿到数据，然后就可以重新缓存到 A 服务器中，后面再次对 P2 进行访问，就可以直接从 A 服务器中拿取数据，对其他缓存项没有景响。

从上面的分析场景中可以看到，一致性 hash 算法是似完美的解决了原始 hash 算法带来的弊端，同时数据分布也均匀，增加/删除服务节点，对缓存项的影响较小，也就意味着对前端的访问不会造成较大的影响，也能减小对后端服务器的 IO 压力。完美！，NO！在上面的场景中还存在一个假设，那就是服务器节点是均匀分布在环上的。理想很丰满，现实却很骨感。在实际的应用场景中，会出现下面这种情况：

what！这是什么情况，累的累死，闲的闲死。这还是一个集群吗？这不就是个人英雄主义么！

是的，你没看错，这就是一致性 hash 算法的缺点，人无完人，算法也一样，解决一个问题的同时，也会暴露出另一个问题-数据倾斜。

一致性 hash 算法的环上有 2^32 个点，也就是说环上的节越多，分布的就越均匀，但现实情况是，服务器资源有限（3 台，大方一点的来个 9 台），没有那么多服务器拿来给你组个图片缓存集群，就算有这么多的服务器，所有服务器都给你缓存图片了，那公司其他业务还要不要开展了？怎么办呢？没这么多资源，就不可能虚假些节点出来吧

一致性 hash 算法的改良-带虚拟节点

上文中说道，一致性 hash 算法是好，但还存在一个问题，那就是数据倾斜，也就是缓存项分布不均匀（累的累死，闲的闲死）。怎么解决这个问题呢？

我们的思路是，一致性 hash 算法是一个由 2^32 个节点组成的环，每个服务器节点经过取模后，会唯一映射到一个点上，环上的点越多那么缓存项的分布就会越均匀，但现实中没这么多资源呢，那按照环上的点越多，缓存项的分布越均匀这个思路发展下去，那就是用当前有的服务器节点，通过复制，再映射到多个不同的节点，比如说我现在有 3 台服务器，通过这种思路，我可以每台再复制出 2 台节点，总共在环上就会变成 9 个节点，9 个节点的随机分布总比 3 个节点的随机分布要均匀吧（事无绝对，在极端的情况还是会出现不均匀的情况，但总体来说要好很多，我们也没必要为了 1%的概率出现，去用 100%的努力去避免）。优化后如下图所示：

通过增加虚拟节点的方式，就可以在一般情况下避免数据倾斜的问题，同时也达到数据均匀分布的要求，做到缓存项分布大致均匀。现在：完美！，真的比较完美了！

一致性 hash 算法的实现关键点：

1、hash 算法的实现，要做到在 0~2^32-1 之间随机均匀分布，均匀分布得越好，数据缓存项就越均匀

2、虚拟节点的个数，理论上总共保证 2^32 个节点，数据分布得越均匀，但这是有代价的，所以说虚拟节点不是越多越好，要在成本和效率之间找到平衡

3、加入虚拟节点后的一致性 hash 计算方法调整为：hash(节点 ip+虚拟节点号)%2^32

4、要保证整个一致性 hash 算法的效率（时间复杂度和空间复杂度）

课后作业：

用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

package com.consistent.hash;import java.util.Map;import java.util.SortedMap;import java.util.TreeMap;
public  abstract class DistributeHash {    private TreeMap<Long,String> virtualNodes = new TreeMap<>(); //hash=>物理节点    private int vitual_copies = 64;  //物理节点至虚拟节点的复制倍数    private Map<String,Integer> objectNodeMap = new TreeMap<>();


    public abstract  Long hash(String key);

    //添加物理节点    public void addPhysicalNode(String key){        for(int ind=0;ind<vitual_copies;ind++){            long hash = hash(key +"#"+Integer.toString(ind));            virtualNodes.put(hash,key);        }    }
    public int getVitual_copies() {        return vitual_copies;    }
    public void setVitual_copies(int vitual_copies) {        this.vitual_copies = vitual_copies;    }

    public Map<String,Integer> getobjectNodeMap(){        return objectNodeMap;    }

    //删除物理节点    public void removePhysicalNode(String key){        for(int ind=0 ; ind < vitual_copies ; ind++){            long hash = hash(key+"#"+Integer.toString(ind));            virtualNodes.remove(hash);        }    }
    //查找对象映射的节点    private String getObjectNode(String object){        long hash = hash(object);
        SortedMap<Long,String> tailmap = virtualNodes.tailMap(hash);        Long key = tailmap.isEmpty() ? virtualNodes.firstKey():tailmap.firstKey();        return virtualNodes.get(key);    }
    //对象与节点映射    public void objectNodeMap(String label,int objectMin,int objectMax){        for(int object = objectMin;object <= objectMax;++object){            String nodeIp = getObjectNode(Integer.toString(object));            Integer count = objectNodeMap.get(nodeIp);            objectNodeMap.put(nodeIp,(count == null ? 0:count + 1));        }
        //打印        double totalcount = objectMax - objectMin + 1;        System.out.println("======== " + label + " ========");        for(Map.Entry<String, Integer> entry : objectNodeMap.entrySet()){            long percent = (int)(100 * entry.getValue() / totalcount);            System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%");        }    }}


package com.consistent.hash;public class ConsistentHash extends DistributeHash {
    // 32位的 Fowler-Noll-Vo 哈希算法    // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function    @Override    public Long hash(String key) {       final int p = 16777619;       Long hash = 2166136261L;
       for(int ind = 0,num = key.length();ind<num;ind++){           hash = (hash^key.charAt(ind))*p;       }
       hash += hash <<13;       hash ^= hash >>7;       hash += hash <<3;       hash ^= hash >>17;       hash += hash <<5;
       if(hash < 0){           hash = Math.abs(hash);       }       return hash;    }}



package com.consistent.hash;import org.junit.Test;import java.util.Map;import java.util.TreeMap;
public class ConsistentHashTest {
    //标准方差    public double getstd(Map<String,Integer> objectnodes){        double sum = 0;        int cnt = 0;        for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){            sum += entry.getValue();            cnt++;        }
        double average  = sum/cnt;
        int total = 0;        for(Map.Entry<String,Integer> entry : objectnodes.entrySet()){            total += (entry.getValue() - average) *(entry.getValue() - average);        }
        double standardDeviation = Math.sqrt(total/cnt);
        return standardDeviation;    }
    @Test    public void test(){        Map<String,Integer> objectNodes = new TreeMap<>();
        //添加物理服务器节点        DistributeHash ch = new ConsistentHash();
        ch.setVitual_copies(102400);        ch.addPhysicalNode("192.168.100.101");        ch.addPhysicalNode("192.168.100.102");        ch.addPhysicalNode("192.168.100.103");        ch.addPhysicalNode("192.168.100.104");        ch.addPhysicalNode("192.168.100.105");        ch.addPhysicalNode("192.168.100.106");        ch.addPhysicalNode("192.168.100.107");        ch.addPhysicalNode("192.168.100.108");        ch.addPhysicalNode("192.168.100.109");        ch.addPhysicalNode("192.168.100.110");
        //对象与节点映射        ch.objectNodeMap("10台服务器，单台"+ch.getVitual_copies()+"个虚拟节点",1,1000000);
        //计算标准方差        objectNodes = ch.getobjectNodeMap();        System.out.println("标准方差为:"+getstd(objectNodes));
    }}