精华内容
下载资源
问答
  • 【 什么叫一致性哈希,通常用来解决什么问题?】 【修真院Java小课堂】什么叫一致性哈希,通常用来解决什么问题? 大家好,我是IT修真院北京分院一枚正直纯洁善良的Java程序员,今天给大家分享一下,修真院官网Java...

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

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

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

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

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

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

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

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

    1. 知识剖析
      节点取余分区

    普通哈希算法,使用特定的数据,如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.结束语

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

    展开全文
  • 一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,整个空间按顺时针方向组织 圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推, 0点的左侧是2的32次方-1,把这个圆环叫做Hash环 然后把服务器ip或者...

    一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环,整个空间按顺时针方向组织
    圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,
    0点的左侧是2的32次方-1,把这个圆环叫做Hash环
    然后把服务器ip或者主机名字作为关键字Hash,每个服务器都能确定位置,把数据进行相同的Hash算出的位置,顺时针访问的第一个就是对应的服务器

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

    用来解决的问题:
    hash( key ) % N,N 为 Redis 的数量,在这里 N = 4 ;
    4 台 Redis 不够了,需要再增加 4 台 Redis ;那么这个求余算法就会变成:hash( key ) % 8 ;
    一部分%4一部分%8当前大部分缓存的位置都会是错误的,极端情况下,就会造成 缓存雪崩。

    (如果节点太少或分布不均匀的时候,容易造成 数据倾斜,也就是大部分数据会集中在某一台服务器上。,一致性 Hash 算法提出了【虚拟节点】解决数据倾斜问题)

    展开全文
  • https://blog.csdn.net/qq_32534441/article/details/89670569
    展开全文
  • 一致性哈希什么

    2021-04-14 23:45:25
    写在前面 本文隶属于专栏《100个问题搞定大数据理论体系》,该专栏为笔者原创,引用请注明来源,...一致性哈希解决了简单哈希算法在分布式哈希表(Distributed Hash Table,DHT)中存在的动态伸缩等问题。 补充 Distri

    写在前面

    本文隶属于专栏《100个问题搞定大数据理论体系》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢!

    本专栏目录结构和文献引用请见100个问题搞定大数据理论体系

    解答

    一致性哈希算法是一种特殊的哈希算法,目的是解决分布式缓存的问题。
    在移除或者添加一个服务器时,能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
    一致性哈希解决了简单哈希算法在分布式哈希表(Distributed Hash Table,DHT)中存在的动态伸缩等问题。
    

    补充

    Distributed Hash Table(DHT)

    Distributed Hash Table(DHT) 是一种哈希分布方式,其目的是为了克服传统哈希分布在服务器节点数量变化时大量数据迁移的问题。

    基本原理

    将哈希空间[0,2^n-1看成一个哈希环,每个服务器节点都配置到哈希环上。

    每个数据对象通过哈希取模得到哈希值之后,存放到哈希环中顺时针方向第一个大于等于该哈希值的节点上。

    一致性哈希1

    一致性哈希在增加或者删除节点时只会影响到哈希环中相邻的节点,例如下图中新增节点X,只需要将它前一个节点C上的数据重新进行分布即可,对于节点A、B、D都没有影响。

    一致性哈希2

    虚拟节点

    虚拟节点上面描述的一致性哈希存在数据分布不均匀的问题,节点存储的数据量有可能会存在很大的不同。

    数据不均匀主要是因为节点在哈希环上分布的不均匀,这种情况在节点数量很少的情况下尤其明显。

    解决方式是通过增加虚拟节点,然后将虚拟节点映射到真实节点上。

    虚拟节点的数量比真实节点来得多,那么虚拟节点在哈希环上分布的均匀性就会比原来的真实节点好,从而使得数据分布也更加均匀。

    展开全文
  • https://blog.csdn.net/sparkliang/article/details/5279393
  • 一致性哈希算法

    2019-11-23 00:19:21
    一致性哈希算法一、为什么使用一致性哈希算法二、一致性哈希算法三、哈希偏斜 一、为什么使用一致性哈希算法        在 Redis 分布式锁中,我们通过部署多台 Redis 的 Master ...
  • 一致性哈希

    2015-04-01 23:55:57
    什么一致性哈希呢?(what) 百度百科 上的解释很专业术语. 要一句话定义貌似也有难度: 一致性哈希算法是在哈希算法基础上,提出的在动态变化的分布式环境中,哈希算法应该满足的几个条件: 平衡性, 单调性和分散...
  • 一致性哈希 java

    2018-02-27 13:01:00
    可扩展的分配策略很重要,分配策略一般采用hash算法,一般都是余数等策略,这种hash算法在结点固定的时候会有比较均衡的分布,但是碰到需要扩展结点就比较难处理,涉及迁移的数据特别多,所以引入一致性哈希算法 ...
  • 一致性哈希的出现为了解决什么问题? 为什么叫一致性哈希,是否实现了分布式一致性? 它是怎么做的(基本原理) 优缺点 一致性哈希的诞生 一致性哈希算法是由1997年由麻省理工学院提出一种分布式哈希(DHT)...
  • 一致性哈希+虚拟节点

    2020-10-21 19:07:25
    四、一致性哈希的数据倾斜问题 五、虚拟节点解决数据倾斜问题 原文链接:https://www.jianshu.com/p/735a3d4789fc 一、为什么要使用多个服务器 随着系统流量的增大,出现了应用集群。在 Mysql数据库要存储的量...
  • 1. 什么是一致性哈希 一致性哈希算法核心思想,就是通过构造一个长度为2^32的整数环,这个...2. 一致性哈希解决什么问题 Hash算法解决的是集群管理中请求访问的路由的问题,一般是根据一个请求的某个key值取余,路由到
  • 它是用于解决什么问题?本文将从普通的哈希函数说起,看看普通哈希函数存在的问题,然后再看一致性哈希是如何解决,一步步进行分析,并结合代码实现来讲解。 首先,设定这样一个场景,我们每天有1千万条业务数据,...
  • 一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑(集群)中分布存储和路由。每个节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。 两...
  • 简述一致性哈希算法

    2019-10-06 14:48:08
    今天早上逛B站的时候首页给我推荐了一个视频,关于面试中一致性哈希算法的回答,好奇心驱使我点了进去。 时长:1小时半... 很纳闷为什么这个浅显易懂的概念需要讲这么久,越来越多培训机构的营销号在发一些明明10...
  • 一致性哈希算法的原理与实现 总结: 一致性hash算法在分布式系统中得到了广泛应用,主要可以用来作为负载均衡的算法。 一致性hash算法和普通hash算法区别: 一致性hash算法和普通hash算法都是使用取模的方法,只是...
  • 好好研究了一下,这里总结一波~~~一致性哈希算法是目前分布式缓存系统中广泛采用的处理算法,该算法主要是用来解决分布式缓存系统中因为缓存服务器的数量的变化所造成的缓存命中率大幅度下滑的问题。下面,我们就来...
  • 一致性哈希--分库分表

    千次阅读 2016-12-19 21:52:02
    http://blog.csdn.net/cywosp/article/details/23397179/分库分表是目前解决单点数据库一种比较流行的做法,也相对成熟,但都有一个共同的问题,就是随着业务的增长,之前的分库分表容量不够了,需要扩容了,这时,...
  • 1. 一致性哈希是用来服务器抗压设计的 2. 经典的服务器抗压结构(负载均衡)如何设计? 假如有 3 台机器,要查一大堆字符串对应的 value 值,然后要负载均衡。做法就是每个字符串都计算一下哈希值,然后 %3,...

空空如也

空空如也

1 2 3 4 5
收藏数 96
精华内容 38
关键字:

一致性哈希解决什么问题