精华内容
下载资源
问答
  • 一致性哈希

    万次阅读 2019-11-08 10:13:16
    一致性哈希 通俗说活

    一、前言

    在解决分布式系统中负载均衡的问题时候可以使用Hash算法让固定的一部分请求落到同一台服务器上,这样每台服务器固定处理一部分请求(并维护这些请求的信息),起到负载均衡的作用。

    但是普通的余数hash(hash(比如用户id)%服务器机器数)算法伸缩性很差,当新增或者下线服务器机器时候,用户id与服务器的映射关系会大量失效。一致性hash则利用hash环对其进行了改进。

    二、一致性Hash概述

    为了能直观的理解一致性hash原理,这里结合一个简单的例子来讲解,假设有4台服务器,地址为ip1,ip2,ip3,ip4。

    • 一致性hash 是首先计算四个ip地址对应的hash值
      hash(ip1),hash(ip2),hash(ip3),hash(ip3),计算出来的hash值是0~最大正整数直接的一个值,这四个值在一致性hash环上呈现如下图:

       

       

    • hash环上顺时针从整数0开始,一直到最大正整数,我们根据四个ip计算的hash值肯定会落到这个hash环上的某一个点,至此我们把服务器的四个ip映射到了一致性hash环

    • 当用户在客户端进行请求时候,首先根据hash(用户id)计算路由规则(hash值),然后看hash值落到了hash环的那个地方,根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip.

       

      如上图可知user1,user2的请求会落到服务器ip2进行处理,User3的请求会落到服务器ip3进行处理,user4的请求会落到服务器ip4进行处理,user5,user6的请求会落到服务器ip1进行处理。

    下面考虑当ip2的服务器挂了的时候会出现什么情况?
    当ip2的服务器挂了的时候,一致性hash环大致如下图:

     

    根据顺时针规则可知user1,user2的请求会被服务器ip3进行处理,而其它用户的请求对应的处理服务器不变,也就是只有之前被ip2处理的一部分用户的映射关系被破坏了,并且其负责处理的请求被顺时针下一个节点委托处理。

    下面考虑当新增机器的时候会出现什么情况?
    当新增一个ip5的服务器后,一致性hash环大致如下图:

     

    根据顺时针规则可知之前user5的请求应该被ip5服务器处理,现在被新增的ip5服务器处理,其他用户的请求处理服务器不变,也就是新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代。

    三、一致性hash的特性

    • 单调性(Monotonicity),单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理,又有新的服务器加入到系统中时候,应保证原有的请求可以被映射到原有的或者新的服务器中去,而不会被映射到原来的其它服务器上去。 这个通过上面新增服务器ip5可以证明,新增ip5后,原来被ip1处理的user6现在还是被ip1处理,原来被ip1处理的user5现在被新增的ip5处理。

    • 分散性(Spread):分布式环境中,客户端请求时候可能不知道所有服务器的存在,可能只知道其中一部分服务器,在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环,那么可能会导致,同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的,因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性hash具有很低的分散性

    • 平衡性(Balance):平衡性也就是说负载均衡,是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求,但是不能保证每个服务器处理的请求的数量大致相同,如下图

       

    服务器ip1,ip2,ip3经过hash后落到了一致性hash环上,从图中hash值分布可知ip1会负责处理大概80%的请求,而ip2和ip3则只会负责处理大概20%的请求,虽然三个机器都在处理请求,但是明显每个机器的负载不均衡,这样称为一致性hash的倾斜,虚拟节点的出现就是为了解决这个问题。

    五、虚拟节点

    当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题,一个解决方法是多加机器,但是加机器是有成本的,那么就加虚拟节点,比如上面三个机器,每个机器引入1个虚拟节点后的一致性hash环的图如下:

     

    其中ip1-1是ip1的虚拟节点,ip2-1是ip2的虚拟节点,ip3-1是ip3的虚拟节点。
    可知当物理机器数目为M,虚拟节点为N的时候,实际hash环上节点个数为M*N。比如当客户端计算的hash值处于ip2和ip3或者处于ip2-1和ip3-1之间时候使用ip3服务器进行处理。

    六、均匀一致性hash

    上节我们使用虚拟节点后的图看起来比较均衡,但是如果生成虚拟节点的算法不够好很可能会得到下面的环:

     

    可知每个服务节点引入1个虚拟节点后,情况相比没有引入前均衡性有所改善,但是并不均衡。

    均衡的一致性hash应该是如下图:

     

    均匀一致性hash的目标是如果服务器有N台,客户端的hash值有M个,那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡

    七、总结

    在分布式系统中一致性hash起着不可忽略的地位,无论是分布式缓存,还是分布式Rpc框架的负载均衡策略都有所使用。

    展开全文
  • 【 什么叫一致性哈希,通常用来解决什么问题?】 【修真院Java小课堂】什么叫一致性哈希,通常用来解决什么问题? 大家好,我是IT修真院北京分院一枚正直纯洁善良的Java程序员,今天给大家分享一下,修...

    这里是修真院后端小课堂,每篇分享文从

    【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】

    八个方面深度解析后端知识/技能,本篇分享的是:

    【 什么叫一致性哈希,通常用来解决什么问题?】

     

    【修真院Java小课堂】什么叫一致性哈希,通常用来解决什么问题?

    大家好,我是IT修真院北京分院一枚正直纯洁善良的Java程序员,今天给大家分享一下,修真院官网Java(职业)任务六,深度思考中的知识点——什么叫一致性哈希,通常用来解决什么问题?

     

    1. 背景介绍

    在了解一致性哈希算法之前,先了解一下一致性哈希算法的应用场景,在做缓存集群时,为了缓解服务器的压力,会部署多台缓存服务器,把数据资源均匀的分配到每个服务器上,分布式数据库首先要解决把整个数据集按照分区规则映射到多个节点的问题,即把数据集划分到多个节点上,每个节点负责整体数据的一个子集。

    数据分布通常有哈希分区和顺序分区两种方式

    顺序分布:数据分散度易倾斜、键值业务相关、可顺序访问、不支持批量操作

    哈希分布:数据分散度高、键值分布业务无关、无法顺序访问、支持批量操作     

    2. 知识剖析

    节点取余分区

    普通哈希算法,使用特定的数据,如Redis的键或用户ID,再根据节点数量N使用公式:hash(key)% N 计算出哈希值,用来决定数据映射到哪一个节点上。

    优点

    这种方式的突出优点是简单性,常用于数据库的分库分表规则。一般采用预分区的方式,提前根据数据量规划好分区数

    缺点 

    当节点数量变化时,如扩容或收缩节点,数据节点映射关系需要重新计算,会导致数据的重新迁移。所以扩容时通常采用翻倍扩容,避免 数据映射全部被打乱,导致全量迁移的情况,这样只会发生50%的数据迁移。

     

     

    一致性哈希分区

    一致性哈希的目的就是为了在节点数目发生改变时尽可能少的迁移数据,将所有的存储节点排列在收尾相接的Hash环上,每个key在计算Hash 后会顺时针找到临接的存储节点存放。而当有节点加入或退 时,仅影响该节点在Hash环上顺时针相邻的后续节点。

          

    优点

    加入和删除节点只影响哈希环中顺时针方向的相邻的节点,对其他节点无影响。

    缺点 

    数据的分布和节点的位置有关,因为这些节点不是均匀的分布在哈希环上的,所以数据在进行存储时达不到均匀分布的效果。

     

    虚拟槽分区

    本质上还是第一种的普通哈希算法,把全部数据离散到指定数量的哈希槽中,把这些哈希槽按照节点数量进行了分区。这样因为哈希槽的数量的固定的,添加节点也不用把数据迁移到新的哈希槽,只要在节点之间互相迁移就可以了,即保证了数据分布的均匀性,又保证了在添加节点的时候不必迁移过多的数据。

    Redis的集群模式使用的就是虚拟槽分区,一共有16383个槽位平均分布到节点上

               

    3.常见问题

    4.解决方案

    5.编码实战

    普通哈希算法

     

    public void hashTest() {
        int[] node = new int[100];
        for(Integer i = 0;i < NUM;i++){
            Integer h = MD5Util.encrypt(i.toString(),"").hashCode();
            int index = Math.abs(h) % 100;
            node[index]++;
        }
        int max = node[0];
        int min = node[0];
        for(int i : node){
            if (max < i){
                max = i;
            }
            if (min > i){
                min = i;
            }
        }
        Arrays.stream(node).forEach(logger::info);
        System.out.println("max :" + max);
        System.out.println("min :" + min);
    }

    节点变化时数据进行迁移

     

    public void hashDiff() {
        int diff = 0;
        for(Integer i = 0;i < NUM;i++){
            Integer h = MD5Util.encrypt(i.toString(),"").hashCode();
            int index = Math.abs(h) % 100;
            int new_index = Math.abs(h) % 101;
            if(new_index != index){
                diff++;
            }
        }
        System.out.println("diff : " + diff);
    }

    一致性哈希算法

     

    public void consistentHash() {
        int[] node = new int[100];
        int[] nodeHash = new int[100];
        for(int i = 0; i < 100; i++) {
            int h = MD5Util.encrypt(Integer.toString(i), "").hashCode();
            nodeHash[i] = Math.abs(h);
        }
        qSort(nodeHash, 0, nodeHash.length - 1);
        for(int i = 0; i < NUM; i++){
            int flag = 0;
            int h = Math.abs(MD5Util.encrypt(Integer.toString(i), "").hashCode());
            for (int j = 0; j < nodeHash.length; j++){
                if(h <= nodeHash[j]){
                    node[j]++;
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                node[0]++;
            }
        }
        Arrays.stream(node).forEach(logger::info);
        System.out.println("max :" + max);
        System.out.println("min :" + min);
    }

    虚拟槽分区

     

    public void clusterHash() {
        int[] node = new int[100];
        int[] nodeSlot = new int[100];
        for (int i = 0; i < 100; i++){
            // nodeSlot存储节点负责的哈希槽范围
            nodeSlot[i] = cluster / node.length * (i + 1);
        }
        for(int i = 0; i < NUM; i++){
            int h = MD5Util.encrypt(Integer.toString(i), "").hashCode();
            int index = Math.abs(h) % cluster;
            for(int j = 0; j < nodeSlot.length; j++){
                if(index <= nodeSlot[j]){
                    node[j]++;
                    break;
                }
            }
        }
        Arrays.stream(node).forEach(logger::info);
        System.out.println("max :" + max);
        System.out.println("min :" + min);
    }

    6.扩展思考

    7.参考文献

    参考资料:https://juejin.im/post/5b8fc5536fb9a05d2d01fb11

    ————深入剖析Redis系列(三) - Redis集群模式搭建与原理详解

    8.更多讨论

     

     

    一致性哈希算法会有哈希冲突吗?

    不冲突的哈希算法是不存在的,但是只要虚拟节点够多,保证在概率上每个真实节点的负载是相等的就好了,一致性哈希的哈希环有细虚拟的2^32个节点。

     

    一致性哈希的哈希槽数为什么是2^32

    一致性哈希一定程度上也解决了哈希冲突,只要哈希槽的范围足够大就能尽可能的减少哈希冲突,因为通常的hashCode都是将数据映射到0 ~ 2^32 数值空间内,所以设置一个2^32个节点的哈希环会尽可能的减少哈希冲突。

     

     

    有没有其他解决节点变化时数据迁移的方法?

    实际上一致性哈希是把可变的哈希槽固定到哈希环上,整数最大值2^32个槽位,所以一致性哈希的本质已经不是节点取模了,每个数据的位置是固定的,只要能保证节点数变化时减少key在节点之间的重映射就可以,比如说虚拟槽分区。

     

    9.鸣谢

    感谢观看,如有出错,恳请指正

    10.结束语

    今天的分享就到这里啦,欢迎大家点赞、转发、留言、拍砖~

     

    PPT链接 视频链接

    展开全文
  • https://blog.csdn.net/qq_32534441/article/details/89670569
    展开全文
  • 一致性哈希用于解决分布式缓存系统中的数据选择节点存储问题和数据选择节点读取问题以及在增删节点后减少数据缓存的消失范畴,防止雪崩的发生。 哈希槽是在redis cluster集群方案中采用的,redis cluster集群没有...

    背景

    随着memcache和redis的出现,更多人认识到了一致性哈希。

    一致性哈希用于解决分布式缓存系统中数据选择节点存储问题数据选择节点读取问题以及在增删节点后减少数据缓存的消失范畴防止雪崩的发生

    哈希槽是在redis cluster集群方案中采用的,redis cluster集群没有采用一致性哈希方案,而是采用数据分片中的哈希槽来进行数据存储与读取的。

    一致性哈希

    一致性hash是一个0-2^32的闭合圆,(拥有2^23个桶空间,每个桶里面可以存储很多数据,可以理解为s3的存储桶)所有节点存储的数据都是不一样的。计算一致性哈希是采用的是如下步骤:

    1. 对节点进行hash,通常使用其节点的ip或者是具有唯一标示的数据进行hash(ip),将其值分布在这个闭合圆上。
    2. 将存储的key进行hash(key),然后将其值要分布在这个闭合圆上。
    3. 从hash(key)在圆上映射的位置开始顺时针方向找到的一个节点即为存储key的节点。如果到圆上的0处都未找到节点,那么0位置后的顺时针方向的第一个节点就是key的存储节点。

    添加节点带来的影响
    图1为一致性hash的分布情况,箭头指向key的分布情况。

    如果现在node2和node4节点中间增加一个node5节点,那么在node4和node2之间的这些数据要存储的节点就会有所变化。在图中的黄色区域的数据将会从原来的node4节点挪到node5节点。

    删除节点带来的影响
    以图1为基准,删除了node2节点后,原本在node2节点上的数据就会被重新定位node4上。这样就产生一个影响:原来node2的数据转移到node4上,这样node4的内存使用率会骤增,如果node2上存在热点数据,node4会扛不住甚至会可能挂掉,挂掉之后数据又转移给node3,如此循环会造成所有节点崩溃,也就是前面所说的雪崩的情况。

    节点太少造成的影响
    节点太少的话可能造成数据倾斜的情况,如图中中只有俩节点,可能会造成大量数据存放在node A节点上,而node B节点存储很少的数据。

    虚拟节点
    为了解决雪崩现象和数据倾斜现象,提出了虚拟节点这个概念。就是将真实节点计算多个哈希形成多个虚拟节点并放置到哈希环上,定位算法不变,只是多了一步虚拟节点到真实节点映射的过程

    以雪崩现象来说明:如下图节点real1节点又俩个虚拟节点v100和v101,real2有俩个虚拟节点v200和v201,real3节点有v300和v301俩个虚拟节点。

    当real1节点挂掉后,v100和v101节点也会随即消失,这时k1数据就会被分配到v301上,k4就会被分配到了v200上,这就解决了雪崩的问题,当某个节点宕机后,其数据并没有全部分配给某一个节点,而是被分到了多个节点。

    正因为加入了虚拟节点机制,数据倾斜的问题也随之解决

    注意:真实节点不放置到哈希环上,只有虚拟节点才会放上去。

    为什么要使用闭合的哈希环
    举个例子,如果在2^23-3处有一个key,而2^23-3~2^23处并没有节点,那么这个key该存在哪里节点呢?说到这里你应该明白来吧

     

    哈希槽

    redis cluster采用数据分片的哈希槽来进行数据存储和数据的读取。redis cluster一共有2^14(16384)个槽,所有的master节点都会有一个槽区比如0~1000,槽数是可以迁移的。master节点的slave节点不分配槽,只拥有读权限。但是注意在代码中redis cluster执行读写操作的都是master节点,并不是你想 的读是从节点,写是主节点。第一次新建redis cluster时,16384个槽是被master节点均匀分布的。

    和一致性哈希相比

    1. 它并不是闭合的,key的定位规则是根据CRC-16(key)%16384的值来判断属于哪个槽区,从而判断该key属于哪个节点,而一致性哈希是根据hash(key)的值来顺时针找第一个hash(ip)的节点,从而确定key存储在哪个节点。
    2. 一致性哈希是创建虚拟节点来实现节点宕机后的数据转移并保证数据的安全性和集群的可用性的。redis cluster是采用master节点有多个slave节点机制来保证数据的完整性的,master节点写入数据,slave节点同步数据。当master节点挂机后,slave节点会通过选举机制选举出一个节点变成master节点,实现高可用。但是这里有一点需要考虑,如果master节点存在热点缓存,某一个时刻某个key的访问急剧增高,这时该mater节点可能操劳过度而死,随后从节点选举为主节点后,同样宕机,依次类推,造成缓存雪崩。解决这个问题请看我的另一篇文章如何应对热点缓存问题

    新建master节点
    使用redis-trib.rb工具来创建master节点

     

    ./redis-trib.rb add-node 172.60.0.7:6379 172.60.0.5:6379
    

    注释:

     

    192.168.10.219:6378是新增的节点
    
    192.168.10.219:6379集群任一个旧节点
    

    注意:新建的master节点是没有槽区的,需要给master节点分配槽,不然缓存无法命中。分配槽的方法自行百度。
    删除master节点
    1.如果主节点有从节点,需要将从节点转移到别的主节点上。
    2.转移后 如果主节点有哈希槽,去调哈希槽,然后在删除master节点
    注意:redis cluster的动态扩容和缩容并不会影响集群的使用。

    展开全文
  • 在日常工作中,经常有这样的情况,我们需要做hash,散列...一致性哈希算法原理  为了解决hash倾斜难题,一致性算法是这样的,节点和节点形成一个环。比如 A-&gt;B-&gt;C-&gt;A,这样一个环。数字hash...
  • 一致性哈希算法

    2016-07-30 13:19:04
    原来对于一致性哈希是一种半知半解的状态,今天刷掘金时刚好发现发现一片特别好的一致性哈希算法文章,在此给大家分享: 本文copy至...
  • 一致性哈希的原理

    2019-06-21 13:54:41
    一致性哈希可以将所有请求大致均匀的分配给所有的服务器,可以解决某几个单独服务器由于请求过多导致的响应变慢的情况。 一致性哈希的核心设计 将服务器(或者线程等各种需要分配的)视为一个节点分布在一个环上。...
  • 一致性哈希算法原理

    2018-01-29 13:13:04
     一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得...
  • 一致性哈希原理说明

    万次阅读 2020-12-13 18:42:06
    一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT...
  • 一致性哈希的理解

    2018-02-06 22:36:44
    首先,让我们了解一下一致性哈希解决了怎样的实际问题, 当我们有了N台服务器(cache)时,我们通常会采用如下的通用算法 将对象(object)均匀映射分配到服务器上, hash(object)%N  试想一下,当其中的一台...
  • 一致性哈希的出现为了解决什么问题? 为什么叫一致性哈希,是否实现了分布式一致性? 它是怎么做的(基本原理) 优缺点 一致性哈希的诞生 一致性哈希算法是由1997年由麻省理工学院提出一种分布式哈希(DHT)...
  • 转载请说明出处:http://blog.csdn.net/cywosp/article/details/23397179 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和...
  • 一致性哈希以及负载均衡的探讨,问题的出现又该如何解决呢 、、、
  • 一致性哈希原理应用

    千次阅读 2021-01-27 14:09:28
    本文主要讲明一致性哈希的 原理,优点,新问题解决,应用场景。 一、基本概念/原理       一致性哈希算法也是使用取模的方法,只不过是对232取模,然后将232个点均匀的散列在一个...
  • 轻松掌握一致性哈希算法

    千次阅读 2016-01-05 11:25:42
    一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,使得...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,373
精华内容 32,549
关键字:

一致性哈希解决的问题