精华内容
参与话题
问答
  • 一致性hash算法

    2020-10-15 23:54:13
    文章目录一致性hash算法一、简介二、传统hash算法的问题三、一致性hash算法特点四、一致性hash算法设计五、一致性hash算法的java实现六、一致性hash算法的简单实现 一、简介 一致性hash算法是1997年由麻省理工学院...

    一致性hash算法

    一、简介

    一致性hash算法是1997年由麻省理工学院提出的,用于在分布式环境中,当增加或删除结点时,尽可能小的减少对结点映射和请求映射的改变,进而减少其带来的存储改变、请求处理改变的影响。通常用于分布式环境中缓存分布、负载均衡等场景。

    二、传统hash算法的问题

    在缓存场景,以结点取模为例,假设有5个缓存结点,即数据存入及读取分布这5个结点上,请求hash值为x,那么请求对应的结点为:x%5=(0,1,2,3,4)。

    • 当新增1个结点
      此时结点个数变为6,那么请求hash值对应的结点变为x%6=(0,1,2,3,4,5),以前hash值为5对应结点0,现在是hash值为6才对应结点0,其它hash值对应的结点类似,对应的相关操作如数据存入及读取,都会发生改变,结点上的数据也随着都会发生改变。影响太大。
    • 删除1结点
      同上新增结点带来的问题类似。

    三、一致性hash算法特点

    一致性hash算法拥有均衡性(balance)、单调性(monotonicity)、分散性(spread)、负载(load)这些特点。最终表现,即是当有结点加入或删除时,除少数结点外,大多数结点的映射关系不会改变,且新增结点时,请求要么到新结点,要么到原结点,而不会到其它旧结点,删除时,请求到其它结点,只是删除结点对应的原请求映射关系改变,其它结点对应的请求映射关系不会改变 。

    1. 均衡性(balance)
      均衡性是指hash结果尽可能均衡分散在所有结点中。
    2. 单调性(monotonicity)
      单调性是指某hash值一旦映射到某结点,当有新结点加入时,该hash值要么映射到原结点,要么映射到新加的结点,而不会映射到其它旧结点。
    3. 分散性(spread)
      分散性是指分布式场景中,不同终端可能见不到所有所有输出结点,进而相同hash值映射的结点可能不同。这需要避免。
    4. 负载(load)
      负载是从另一角度看分散性,指同一输出结点,不能被不同终端存储不同的内容。

    四、一致性hash算法设计

    一致性hash算法设计,是将请求和输出结点都映射到抽象的hash环上,结点查找时,请求hash值在抽象hash环上,按顺时针查找结点,遇到的第一个结点即为输出结点。

    1. hash环
      这是抽象的环,请求和结点按指的hash算法,都映射到hash环上。
    2. 虚拟结点
      为了更均衡地将请求映射到所有结点,可以将结点虚拟为多个虚拟结点,这样各个结点在hash环上分布的更均衡,相应的处理请求也更均衡。

    五、一致性hash算法的java实现

    这里使用java来实现一致性hash算法,使用TreeMap作为hash环的数据结构,使用MurmurHash作为hash算法(借助guava27.1-jre的jar包),具体请参考代码注释。

    import com.google.common.collect.Lists;
    import com.google.common.hash.HashCode;
    import com.google.common.hash.HashFunction;
    import com.google.common.hash.Hashing;
    
    import java.nio.charset.Charset;
    import java.util.List;
    import java.util.SortedMap;
    import java.util.TreeMap;
    import java.util.function.Consumer;
    import java.util.function.Function;
    import java.util.stream.Collectors;
    import java.util.stream.Stream;
    
    public class ConsistentHashAlgMain {
        public static void main(String[] args) {
            / 环境模拟 /
            //模拟物理机器结点
            List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");
            //模拟请求
            List<String> reqs = Lists.newArrayList("request one", "request two", "request three", "request four", "request five");
            //生成抽象的hash环(使用TreeMap作为hash环的数据结构)
            TreeMap<String, String> serverRing = new TreeMap<>();
            //指定hash算法为murmur
            HashFunction hf = Hashing.murmur3_128();
    
    
            / 辅助方法 /
            //生成hash值方法
            Function<String, HashCode> hash = t -> hf.hashString(t, Charset.forName("utf8"));
            //生成虚拟结点后缀列表的方法
            List<Integer> virNum = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
            //单台物理机器生成虚拟机器结点列表的方法
            Function<String, List<String>> buildVirServer = s -> virNum.stream().map(t -> s + "#" + t).collect(Collectors.toList());
    
    
            / 增加、删除机器方法 /
            //添加一台物理机器方法
            Consumer<String> addServer = t -> {
                //获取物理机对应的虚拟机器列表
                List<String> virServers = buildVirServer.apply(t);
    
                //将虚拟机器列表加入到hash环中
                virServers.forEach(v -> {
                    //获取虚拟机器的hash值
                    HashCode h = hash.apply(v);
                    //将虚拟机器加入到hash环中
                    serverRing.put(h.toString(), t);
                });
            };
    
            //删除一台物理机器方法
            Consumer<String> delServer = t -> {
                //获取物理机对应的虚拟机器列表
                List<String> virServers = buildVirServer.apply(t);
    
                //将虚拟机器列表从hash环中删除
                virServers.forEach(v -> {
                    //获取虚拟机器的hash值
                    HashCode h = hash.apply(v);
                    //将虚拟机器从hash环中删除
                    serverRing.remove(h.toString());
                });
            };
    
            //初始化物理机器(每台物理机器会先生成多台虚拟机器列表)到hash环方法
            Consumer<List<String>> initServerRing = list -> {
                list.forEach(t -> addServer.accept(t));
            };
    
    
            / 请求处理方法 /
            //处理请求方法
            Function<String, String> ringHashHost = t -> {
                //获取请求的hash值
                HashCode h = hash.apply(t);
    
                //查找请求hash值后对应的剩余hash环机器
                SortedMap<String, String> tailRing = serverRing.tailMap(h.toString());
                //获取请求hash值后找到的第一台机器的key
                String idx = tailRing.size() < 1 ? serverRing.firstKey() : tailRing.firstKey();
    
                //获取请求hash值后找到的第一台机器
                String s = serverRing.get(idx);
                System.out.println(t + " : " + s);
                return s;
            };
    
            //批量处理请求方法
            Consumer<List<String>> handleReqs = list -> {
                list.forEach(t -> ringHashHost.apply(t));
            };
    
    
            / 测试 /
            //初始化hash环
            initServerRing.accept(servers);
            //处理请求
            handleReqs.accept(reqs);
    
            //添加新机器并处理请求
            System.out.println("###### add server #####");
            addServer.accept("192.168.0.6");
            handleReqs.accept(reqs);
    
    
            //删除机器并处理请求
            System.out.println("###### del server #####");
            delServer.accept("192.168.0.4");
            handleReqs.accept(reqs);
        }
    }
    

    结果输出:

    request one : 192.168.0.5
    request two : 192.168.0.5
    request three : 192.168.0.3
    request four : 192.168.0.4
    request five : 192.168.0.1
    \###### add server #####
    request one : 192.168.0.5
    request two : 192.168.0.5
    request three : 192.168.0.6
    request four : 192.168.0.4
    request five : 192.168.0.1
    \###### del server #####
    request one : 192.168.0.5
    request two : 192.168.0.5
    request three : 192.168.0.6
    request four : 192.168.0.1
    request five : 192.168.0.1
    

    分析结果可以发现,新增结点时,旧的映射要么不改变,要么映射到新结点,删除结点时,除少数结点外,大多数的映射关系也不会改变。

    六、一致性hash算法的简单实现

    另外也可以借助google的guava包提供的一致性hash算法的基本实现,直接使用,其关键使用代码(在此不详解)如下:

    //所有结点
    List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");
    //请求映射到结点
    int idx = Hashing.consistentHash(Hashing.sha256().hashString("request one", Charset.forName("utf-8")), servers.size());
    
    展开全文
  • 一致性Hash算法

    2021-01-11 18:21:01
    文章目录前言一、常规Hash算法1.Hash算法应用2.Hash表3.Hash算法在分布式架构的应用场景4.Hash算法简单代码实现5.Hash算法存在的问题二、一致性Hash算法1.一致性Hash算法思路2.虚拟节点3.手写实现简单的一致性Hash...

    资料参考来源拉钩Java高薪训练营


    前言

    在分布式和集群环境下负载均衡和分布式存储时,常规的Hash算法在服务器扩容和缩容、或者某个节点宕机的情况下影响很大,所以出现了一致性Hash算法,可以在服务器扩容和缩容情况下把影响降到最低。

    一、常规Hash算法

    1.Hash算法应用

    Hash算法主要应用于安全加密领域、数据存储和查找的Hash表。平时使用最多的比如说MD5加密密码、HashMap的使用等。

    2.Hash表

    这里我们主要说下Hash表,它的查询速度非常的快,只要其中的Hash算法设计的合理的话,查询数据的时间复杂度接近于O(1)。

    比如说我们现在有这样一个需求:保存一组数据1,3,4,7,9。

    在不使用Hash表的情况下直接使用一个数组保存:[1,3,4,7,9],那么查询只能使用顺序查找法(循环数组一个一个对比查找),或者使用二分查找法,这样在数据量很大的情况下效率就不那么好了。

    针对上面的情况我们可以进行一个优化,我们可以定义一个10个长度的数组,然后每个数据都对数组长度10进行取余数,那么这个余数就是这个数据在这个数组中存放的下标。
    在这里插入图片描述
    从上图可以看到,这几个数字就存放到了对应的下标中了,当我们需要查询某个值时,也可以与数组长度10取余得出下标,直接通过数组下标取出数据,这种方式叫做直接寻址法

    与数组长度10取余得出下标这个过程就是Hash算法,这个Hash算法比较简单,计算出来的下标大概率会重复,比如再加上一个数字11,计算出来的下标是1,这个时候就和数据1的位置重复,那这种情况就叫做Hash冲突,怎么解决Hash冲突呢:

    开放寻址法:下标为1的位置有数据了,那就向前或者向后找下一个位置,直到找到空闲位置为止进行存储。这个方法也有确定,比如数据量有11个,不管会不会产生Hash冲突,肯定是存放不下的。
    拉链法:数组元素存放一个链表,发生Hash冲突时就往这个链表插入就行了。
    在这里插入图片描述

    Hash表的查询效率⾼不⾼取决于Hash算法,hash算法能够让数据平均分布,既能够节省空间⼜能提⾼查询效率。Hash算法的研究是很深的⼀⻔学问,⽐较复杂,⻓久以来,Hash表内部的Hash算法也⼀直在更新,很多数学家也在研究。

    3.Hash算法在分布式架构的应用场景

    Hash算法在很多分布式集群产品中都有应用,比如说分布式集群架构Redis、Hadoop、ElasticSearch等。
    主要应用场景归纳为两个:

    • 请求负载均衡
      比如说Nginx的IP_hash策略,可以在客户端ip不变的情况下,讲请求始终路由到同一台服务器上,可以避免Session共享问题。
    • 分布式存储
      比如说一个集群中有redis1、redis2、redis3三台Redis服务器,那么可以针对key进行Hash处理hash(key)%3来定位存储到那台服务器上。

    4.Hash算法简单代码实现

    //服务器ip
    String[] services = new String[]{"110.135.13.12","123.111.24.13","10.211.12.14"};
    //客户端ip
    String[] clientIps = new String[]{"192.168.1.10","192.168.1.11","192.168.1.12","192.168.1.13","192.168.1.14","192.168.1.15"};
    
    for (String clientIp : clientIps) {
        //取余计算下标
        int index = clientIp.hashCode()%services.length;
        String service = services[index];
        System.out.println("客户端:"+clientIp+" 被路由到服务器:"+service);
    }
    

    5.Hash算法存在的问题

    普通的Hash算法在服务器数量变动下,之前数据的所有计算都需要重新Hash才行。

    比如说ip_hash策略为例:假设有3台tomcat服务器,在客户端ip不变的情况下,那么之前负载计算是hash(ip)%3,当tomcat3挂了,计算策略就会变成hash(ip)%2,那么之前在tomcat3的客户端会话都会路由到其他服务器,当然其他客户端的路由服务器也可能会变,当服务器和客户端都很多的情况下。这个影响就很大了。这种情况在服务器扩容和缩容都可能会出现。

    针对这种情况,就出现了一致性Hash算法来解决。

    二、一致性Hash算法

    1.一致性Hash算法思路

    在这里插入图片描述
    首先是一条直线,相当于一个地址,这条直线弯过来就构成了一个圆环形,这个圆环形就可以称为Hash环。我们首先把服务器ip通过Hash算法定位在这个环上面,然后把客户端ip也通过Hash算法对应到Hash环上,从客户端在Hash环的位置开始,顺时针查找到的第一个服务器就是需要路由的服务器。
    在这里插入图片描述
    当增加一个服务器节点5后,如下图所示,原先路由到服务器3的客户端有一部分就路由到服务器5上面了,受影响的就只有这一小部分,这样就把服务器扩容缩容的影响讲到最低了。

    在这里插入图片描述

    2.虚拟节点

    但是一致性Hash算法在服务器节点非常少或者Hash算法计算的不均匀的情况下,很容易发生数据倾斜,如下图:
    在这里插入图片描述
    这时服务器1接收到了大量的请求,二服务器2只能复制少量范围的请求,为了解决数据倾斜的问题,我们可以使用虚拟节点,就是把真实节点计算多个Hash值,每个结算结果都在Hash环上放置这个服务器节点,这个就称为虚拟节点。
    在这里插入图片描述

    上图所示,服务器1和服务器2都计算三个虚拟节点,当客户端被路由到虚拟节点的时候其实是被路由到对应的真实服务器上的。

    3.手写实现简单的一致性Hash算法

    //服务器ip
    String[] services = new String[]{"110.135.13.12","123.111.24.13","10.211.12.14"};
    
    //每个真实节点的虚拟节点数量
    int virtualNum = 3;
    
    SortedMap<Integer,String> serviceMap = new TreeMap();
    //计算服务器在Hash环的位置
    for (String service : services) {
        //可能为负数,取绝对值
        int hash = Math.abs(service.hashCode());
        serviceMap.put(hash,service);
    
        for (int i = 0; i < virtualNum; i++) {
            int virtualHash = Math.abs((service+"#"+i).hashCode());
            serviceMap.put(virtualHash,"----由虚拟节点"+ i + "映射过来的请求:"+ service);
        }
    }
    
    //客户端ip
    String[] clientIps = new String[]{"12.168.122.10","192.112.14.11","34.132.1.12","44.118.12.13","53.144.1.14","23.183.1.15"};
    
    for (String clientIp : clientIps) {
        //计算客户端ip Hash
        int hash = Math.abs(clientIp.hashCode());
        //获取大于客户端ip hash的服务器
        SortedMap<Integer,String> sortedMap = serviceMap.tailMap(hash);
        if (sortedMap.isEmpty()){
            //如果为空,则取第一个服务器
            String service = serviceMap.get(serviceMap.firstKey());
            System.out.println("客户端:"+clientIp+" 被路由到服务器:"+service);
        }else {
            //如果有值,取结果集的第一个
            String service = sortedMap.get(sortedMap.firstKey());
            System.out.println("客户端:"+clientIp+" 被路由到服务器:"+service);
        }
    }
    
    展开全文
  • 一致性HASH算法

    2018-03-05 00:25:07
    一致性Hash算法,Java代码实现的深入研究 一致性Hash算法 关于一致性Hash算法,在我之前的博文中...部分,对于为什么要使用一致性Hash算法一致性Hash算法的算法原理做了详细的解读。 算法的具体原理这里再次...
    转载自:https://www.cnblogs.com/xrq730/p/5186728.html
    
    
    对一致性Hash算法,Java代码实现的深入研究
    一致性Hash算法
    
    关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。
    
    算法的具体原理这里再次贴上:
    
    先构造一个长度为232的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 232-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 232-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。
    
    这种算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。
    
    当然,万事不可能十全十美,一致性Hash算法比普通的余数Hash算法更具有伸缩性,但是同时其算法实现也更为复杂,本文就来研究一下,如何利用Java代码实现一致性Hash算法。在开始之前,先对一致性Hash算法中的几个核心问题进行一些探究。
    
     
    
    数据结构的选取
    
    一致性Hash算法最先要考虑的一个问题是:构造出一个长度为232的整数环,根据节点名称的Hash值将服务器节点放置在这个Hash环上。
    
    那么,整数环应该使用何种数据结构,才能使得运行时的时间复杂度最低?首先说明一点,关于时间复杂度,常见的时间复杂度与时间效率的关系有如下的经验规则:
    
    O(1) < O(log2N) < O(N) < O(N * log2N) < O(N2) < O(N3)  < O(N!)
    
    一般来说,前四个效率比较高,中间两个差强人意,最后一个后比较差(只要N比较大,这个算法就动不了了)。OK,继续前面的话题,应该如何选取数据结构,我认为有以下几种可行的解决方案。
    
    1、解决方案一:排序+List
    
    我想到的第一种思路是:算出所有待加入数据结构的节点名称的Hash值放入一个数组中,然后使用某种排序算法将其从小到大进行排序,最后将排序后的数据放入List中,采用List而不是数组是为了结点的扩展考虑。
    
    之后,待路由的结点,只需要在List中找到第一个Hash值比它大的服务器节点就可以了,比如服务器节点的Hash值是[0,2,4,6,8,10],带路由的结点是7,只需要找到第一个比7大的整数,也就是8,就是我们最终需要路由过去的服务器节点。
    
    如果暂时不考虑前面的排序,那么这种解决方案的时间复杂度:
    
    (1)最好的情况是第一次就找到,时间复杂度为O(1)
    
    (2)最坏的情况是最后一次才找到,时间复杂度为O(N)
    
    平均下来时间复杂度为O(0.5N+0.5),忽略首项系数和常数,时间复杂度为O(N)。
    
    但是如果考虑到之前的排序,我在网上找了张图,提供了各种排序算法的时间复杂度:
    
    
    
    看得出来,排序算法要么稳定但是时间复杂度高、要么时间复杂度低但不稳定,看起来最好的归并排序法的时间复杂度仍然有O(N * logN),稍微耗费性能了一些。
    
    2、解决方案二:遍历+List
    
    既然排序操作比较耗性能,那么能不能不排序?可以的,所以进一步的,有了第二种解决方案。
    
    解决方案使用List不变,不过可以采用遍历的方式:
    
    (1)服务器节点不排序,其Hash值全部直接放入一个List中
    
    (2)带路由的节点,算出其Hash值,由于指明了"顺时针",因此遍历List,比待路由的节点Hash值大的算出差值并记录,比待路由节点Hash值小的忽略
    
    (3)算出所有的差值之后,最小的那个,就是最终需要路由过去的节点
    
    在这个算法中,看一下时间复杂度:
    
    1、最好情况是只有一个服务器节点的Hash值大于带路由结点的Hash值,其时间复杂度是O(N)+O(1)=O(N+1),忽略常数项,即O(N)
    
    2、最坏情况是所有服务器节点的Hash值都大于带路由结点的Hash值,其时间复杂度是O(N)+O(N)=O(2N),忽略首项系数,即O(N)
    
    所以,总的时间复杂度就是O(N)。其实算法还能更改进一些:给一个位置变量X,如果新的差值比原差值小,X替换为新的位置,否则X不变。这样遍历就减少了一轮,不过经过改进后的算法时间复杂度仍为O(N)。
    
    总而言之,这个解决方案和解决方案一相比,总体来看,似乎更好了一些。
    
    3、解决方案三:二叉查找树
    
    抛开List这种数据结构,另一种数据结构则是使用二叉查找树。对于树不是很清楚的朋友可以简单看一下这篇文章树形结构。
    
    当然我们不能简单地使用二叉查找树,因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等,这里使用红黑树,选用红黑树的原因有两点:
    
    1、红黑树主要的作用是用于存储有序的数据,这其实和第一种解决方案的思路又不谋而合了,但是它的效率非常高
    
    2、JDK里面提供了红黑树的代码实现TreeMap和TreeSet
    
    另外,以TreeMap为例,TreeMap本身提供了一个tailMap(K fromKey)方法,支持从红黑树中查找比fromKey大的值的集合,但并不需要遍历整个数据结构。
    
    使用红黑树,可以使得查找的时间复杂度降低为O(logN),比上面两种解决方案,效率大大提升。
    
    为了验证这个说法,我做了一次测试,从大量数据中查找第一个大于其中间值的那个数据,比如10000数据就找第一个大于5000的数据(模拟平均的情况)。看一下O(N)时间复杂度和O(logN)时间复杂度运行效率的对比:
    
     	50000	100000	500000	1000000	4000000
    ArrayList	1ms	1ms	4ms	4ms	5ms
    LinkedList	4ms	7ms	11ms	13ms	17ms
    TreeMap	0ms	0ms	0ms	0ms	0ms
    因为再大就内存溢出了,所以只测试到4000000数据。可以看到,数据查找的效率,TreeMap是完胜的,其实再增大数据测试也是一样的,红黑树的数据结构决定了任何一个大于N的最小数据,它都只需要几次至几十次查找就可以查到。
    
    当然,明确一点,有利必有弊,根据我另外一次测试得到的结论是,为了维护红黑树,数据插入效率TreeMap在三种数据结构里面是最差的,且插入要慢上5~10倍。
    
     
    
    Hash值重新计算
    
    服务器节点我们肯定用字符串来表示,比如"192.168.1.1"、"192.168.1.2",根据字符串得到其Hash值,那么另外一个重要的问题就是Hash值要重新计算,这个问题是我在测试String的hashCode()方法的时候发现的,不妨来看一下为什么要重新计算Hash值:
    
    复制代码
    /**
     * String的hashCode()方法运算结果查看
     * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
     *
     */
    public class StringHashCodeTest
    {
        public static void main(String[] args)
        {
            System.out.println("192.168.0.0:111的哈希值:" + "192.168.0.0:1111".hashCode());
            System.out.println("192.168.0.1:111的哈希值:" + "192.168.0.1:1111".hashCode());
            System.out.println("192.168.0.2:111的哈希值:" + "192.168.0.2:1111".hashCode());
            System.out.println("192.168.0.3:111的哈希值:" + "192.168.0.3:1111".hashCode());
            System.out.println("192.168.0.4:111的哈希值:" + "192.168.0.4:1111".hashCode());
        }
    }
    复制代码
    我们在做集群的时候,集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为:
    
    192.168.0.0:111的哈希值:1845870087
    192.168.0.1:111的哈希值:1874499238
    192.168.0.2:111的哈希值:1903128389
    192.168.0.3:111的哈希值:1931757540
    192.168.0.4:111的哈希值:1960386691
    这个就问题大了,[0,232-1]的区间之中,5个HashCode值却只分布在这么小小的一个区间,什么概念?[0,232-1]中有4294967296个数字,而我们的区间只有114516604,从概率学上讲这将导致97%待路由的服务器都被路由到"192.168.0.0"这个集群点上,简直是糟糕透了!
    
    另外还有一个不好的地方:规定的区间是非负数,String的hashCode()方法却会产生负数(不信用"192.168.1.0:1111"试试看就知道了)。不过这个问题好解决,取绝对值就是一种解决的办法。
    
    综上,String重写的hashCode()方法在一致性Hash算法中没有任何实用价值,得找个算法重新计算HashCode。这种重新计算Hash值的算法有很多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法,用别的Hash算法也可以,比如FNV1_32_HASH算法的计算效率就会高一些。
    
     
    
    一致性Hash算法实现版本1:不带虚拟节点
    
    使用一致性Hash算法,尽管增强了系统的伸缩性,但是也有可能导致负载分布不均匀,解决办法就是使用虚拟节点代替真实节点,第一个代码版本,先来个简单的,不带虚拟节点。
    
    下面来看一下不带虚拟节点的一致性Hash算法的Java代码实现:
    
    复制代码
     1 /**
     2  * 不带虚拟节点的一致性Hash算法
     3  * @author 五月的仓颉http://www.cnblogs.com/xrq730/
     4  *
     5  */
     6 public class ConsistentHashingWithoutVirtualNode
     7 {
     8     /**
     9      * 待添加入Hash环的服务器列表
    10      */
    11     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
    12             "192.168.0.3:111", "192.168.0.4:111"};
    13     
    14     /**
    15      * key表示服务器的hash值,value表示服务器的名称
    16      */
    17     private static SortedMap<Integer, String> sortedMap = 
    18             new TreeMap<Integer, String>();
    19     
    20     /**
    21      * 程序初始化,将所有的服务器放入sortedMap中
    22      */
    23     static
    24     {
    25         for (int i = 0; i < servers.length; i++)
    26         {
    27             int hash = getHash(servers[i]);
    28             System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
    29             sortedMap.put(hash, servers[i]);
    30         }
    31         System.out.println();
    32     }
    33     
    34     /**
    35      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
    36      */
    37     private static int getHash(String str)
    38     {
    39         final int p = 16777619;
    40         int hash = (int)2166136261L;
    41         for (int i = 0; i < str.length(); i++)
    42             hash = (hash ^ str.charAt(i)) * p;
    43         hash += hash << 13;
    44         hash ^= hash >> 7;
    45         hash += hash << 3;
    46         hash ^= hash >> 17;
    47         hash += hash << 5;
    48         
    49         // 如果算出来的值为负数则取其绝对值
    50         if (hash < 0)
    51             hash = Math.abs(hash);
    52         return hash;
    53     }
    54     
    55     /**
    56      * 得到应当路由到的结点
    57      */
    58     private static String getServer(String node)
    59     {
    60         // 得到带路由的结点的Hash值
    61         int hash = getHash(node);
    62         // 得到大于该Hash值的所有Map
    63         SortedMap<Integer, String> subMap = 
    64                 sortedMap.tailMap(hash);
    65         // 第一个Key就是顺时针过去离node最近的那个结点
    66         Integer i = subMap.firstKey();
    67         // 返回对应的服务器名称
    68         return subMap.get(i);
    69     }
    70     
    71     public static void main(String[] args)
    72     {
    73         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
    74         for (int i = 0; i < nodes.length; i++)
    75             System.out.println("[" + nodes[i] + "]的hash值为" + 
    76                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
    77     }
    78 }
    复制代码
    可以运行一下看一下结果:
    
    复制代码
    [192.168.0.0:111]加入集合中, 其Hash值为575774686
    [192.168.0.1:111]加入集合中, 其Hash值为8518713
    [192.168.0.2:111]加入集合中, 其Hash值为1361847097
    [192.168.0.3:111]加入集合中, 其Hash值为1171828661
    [192.168.0.4:111]加入集合中, 其Hash值为1764547046
    
    [127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
    [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111]
    [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.4:111]
    复制代码
    看到经过FNV1_32_HASH算法重新计算过后的Hash值,就比原来String的hashCode()方法好多了。从运行结果来看,也没有问题,三个点路由到的都是顺时针离他们Hash值最近的那台服务器上。
    
     
    
    使用虚拟节点来改善一致性Hash算法
    
    上面的一致性Hash算法实现,可以在很大程度上解决很多分布式环境下不好的路由算法导致系统伸缩性差的问题,但是会带来另外一个问题:负载不均。
    
    比如说有Hash环上有A、B、C三个服务器节点,分别有100个请求会被路由到相应服务器上。现在在A与B之间增加了一个节点D,这导致了原来会路由到B上的部分节点被路由到了D上,这样A、C上被路由到的请求明显多于B、D上的,原来三个服务器节点上均衡的负载被打破了。某种程度上来说,这失去了负载均衡的意义,因为负载均衡的目的本身就是为了使得目标服务器均分所有的请求。
    
    解决这个问题的办法是引入虚拟节点,其工作原理是:将一个物理节点拆分为多个虚拟节点,并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。采取这样的方式,就可以有效地解决增加或减少节点时候的负载不均衡的问题。
    
    至于一个物理节点应该拆分为多少虚拟节点,下面可以先看一张图:
    
    
    
    横轴表示需要为每台福利服务器扩展的虚拟节点倍数,纵轴表示的是实际物理服务器数。可以看出,物理服务器很少,需要更大的虚拟节点;反之物理服务器比较多,虚拟节点就可以少一些。比如有10台物理服务器,那么差不多需要为每台服务器增加100~200个虚拟节点才可以达到真正的负载均衡。
    
     
    
    一致性Hash算法实现版本2:带虚拟节点
    
    在理解了使用虚拟节点来改善一致性Hash算法的理论基础之后,就可以尝试开发代码了。编程方面需要考虑的问题是:
    
    1、一个真实结点如何对应成为多个虚拟节点?
    
    2、虚拟节点找到后如何还原为真实结点?
    
    这两个问题其实有很多解决办法,我这里使用了一种简单的办法,给每个真实结点后面根据虚拟节点加上后缀再取Hash值,比如"192.168.0.0:111"就把它变成"192.168.0.0:111&&VN0"到"192.168.0.0:111&&VN4",VN就是Virtual Node的缩写,还原的时候只需要从头截取字符串到"&&"的位置就可以了。
    
    下面来看一下带虚拟节点的一致性Hash算法的Java代码实现:
    
    复制代码
     1 /**
     2  * 带虚拟节点的一致性Hash算法
     3  * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
     4  */
     5 public class ConsistentHashingWithVirtualNode
     6 {
     7     /**
     8      * 待添加入Hash环的服务器列表
     9      */
    10     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
    11             "192.168.0.3:111", "192.168.0.4:111"};
    12     
    13     /**
    14      * 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
    15      */
    16     private static List<String> realNodes = new LinkedList<String>();
    17     
    18     /**
    19      * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
    20      */
    21     private static SortedMap<Integer, String> virtualNodes = 
    22             new TreeMap<Integer, String>();
    23     
    24     /**
    25      * 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
    26      */
    27     private static final int VIRTUAL_NODES = 5;
    28     
    29     static
    30     {
    31         // 先把原始的服务器添加到真实结点列表中
    32         for (int i = 0; i < servers.length; i++)
    33             realNodes.add(servers[i]);
    34         
    35         // 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
    36         for (String str : realNodes)
    37         {
    38             for (int i = 0; i < VIRTUAL_NODES; i++)
    39             {
    40                 String virtualNodeName = str + "&&VN" + String.valueOf(i);
    41                 int hash = getHash(virtualNodeName);
    42                 System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
    43                 virtualNodes.put(hash, virtualNodeName);
    44             }
    45         }
    46         System.out.println();
    47     }
    48     
    49     /**
    50      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
    51      */
    52     private static int getHash(String str)
    53     {
    54         final int p = 16777619;
    55         int hash = (int)2166136261L;
    56         for (int i = 0; i < str.length(); i++)
    57             hash = (hash ^ str.charAt(i)) * p;
    58         hash += hash << 13;
    59         hash ^= hash >> 7;
    60         hash += hash << 3;
    61         hash ^= hash >> 17;
    62         hash += hash << 5;
    63         
    64         // 如果算出来的值为负数则取其绝对值
    65         if (hash < 0)
    66             hash = Math.abs(hash);
    67         return hash;
    68     }
    69     
    70     /**
    71      * 得到应当路由到的结点
    72      */
    73     private static String getServer(String node)
    74     {
    75         // 得到带路由的结点的Hash值
    76         int hash = getHash(node);
    77         // 得到大于该Hash值的所有Map
    78         SortedMap<Integer, String> subMap = 
    79                 virtualNodes.tailMap(hash);
    80         // 第一个Key就是顺时针过去离node最近的那个结点
    81         Integer i = subMap.firstKey();
    82         // 返回对应的虚拟节点名称,这里字符串稍微截取一下
    83         String virtualNode = subMap.get(i);
    84         return virtualNode.substring(0, virtualNode.indexOf("&&"));
    85     }
    86     
    87     public static void main(String[] args)
    88     {
    89         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
    90         for (int i = 0; i < nodes.length; i++)
    91             System.out.println("[" + nodes[i] + "]的hash值为" + 
    92                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
    93     }
    94 }
    复制代码
    关注一下运行结果:
    
    复制代码
    虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075
    虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081
    虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370
    虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914
    虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629
    虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288
    虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309
    虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528
    虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861
    虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551
    虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222
    虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840
    虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480
    虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074
    虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136
    虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251
    虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739
    虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370
    虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500
    虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780
    虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010
    虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390
    虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117
    虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803
    虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678
    
    [127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
    [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.0:111]
    [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.2:111]
    复制代码
    从代码运行结果看,每个点路由到的服务器都是Hash值顺时针离它最近的那个服务器节点,没有任何问题。
    
    通过采取虚拟节点的方法,一个真实结点不再固定在Hash换上的某个点,而是大量地分布在整个Hash环上,这样即使上线、下线服务器,也不会造成整体的负载不均衡。
    
     
    
    后记
    
    在写本文的时候,很多知识我也是边写边学,难免有很多写得不好、理解得不透彻的地方,而且代码整体也比较糙,未有考虑到可能的各种情况。抛砖引玉,一方面,写得不对的地方,还望网友朋友们指正;另一方面,后续我也将通过自己的工作、学习不断完善上面的代码。
    
    
    ================================================================================== 
    
    我不能保证写的每个地方都是对的,但是至少能保证不复制、不黏贴,保证每一句话、每一行代码都经过了认真的推敲、仔细的斟酌。每一篇文章的背后,希望都能看到自己对于技术、对于生活的态度。
    
    我相信乔布斯说的,只有那些疯狂到认为自己可以改变世界的人才能真正地改变世界。面对压力,我可以挑灯夜战、不眠不休;面对困难,我愿意迎难而上、永不退缩。
    
    其实我想说的是,我只是一个程序员,这就是我现在纯粹人生的全部。
    

    展开全文
  • 一致性 hash 算法

    2019-03-27 12:41:49
    一、什么是一致性hash算法一致性Hash算法是使用取模的方法,是对2^32取模,什么意思呢?简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个...

    一、什么是一致性hash算法 ?

    一致性Hash算法是使用取模的方法,是对2^32取模,什么意思呢?简单来说,一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数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地址哈希后在环空间的位置如下:

    在这里插入图片描述
    接下来使用如下算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器!

    例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:
    在这里插入图片描述
    根据一致性Hash算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

    二、一致性hash算法的可扩展性和容错性

    现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性Hash算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响,如下所示:
    在这里插入图片描述
    下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:
    在这里插入图片描述
    此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X !一般的,在一致性Hash算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

    综上所述,一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性

    三、Hash环的数据倾斜问题

    一致性Hash算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜(被缓存的对象大部分集中缓存在某一台服务器上)问题,例如系统中只有两台服务器,其环分布如下:
    在这里插入图片描述
    此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性Hash算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。

    例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:
    在这里插入图片描述
    同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 3,516
精华内容 1,406
关键字:

一致性hash算法