redis源码之:扩容后的dictScan遍历顺序与JDK的concurrentHashMap 扩容机制

这篇具有很好参考价值的文章主要介绍了redis源码之:扩容后的dictScan遍历顺序与JDK的concurrentHashMap 扩容机制。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

进入正题前,先来复习下关于2次幂的mod运算
设n为2次幂,数a mod n 等价于 a & n-1
从二进制来看,相当于余数为a省去n最高位左侧的所有位(含最高位),保留n右侧所有低位即为余数
如:a = 7(0000_0111),n=4(0000_0100),通过7 & (4-1) 即0000_0111 & 0000_0011 结果为3(0000_0011)

dictScan方法中,对游标计算下表用了一个位逆序运算的方法,总体的算法如下:

        v |= ~m0;
        /* Increment the reverse cursor */
        v = rev(v);
        v++;
        v = rev(v);

在分析这个算法前,我准备先大概说下这个算法的目的:

1、首先这里有个前提,即dict的长度都是2的幂,且每次扩容都是扩大一倍,即size1 = size0*2。
扩容前,某个下标idx的若干数据,其实就是key mod size0后同余数idx若干key,在扩容后,因为是扩大一倍,因此这些同余的key,就会分为两部分,idx,和idx+size0的两部分。
redis源码之:扩容后的dictScan遍历顺序与JDK的concurrentHashMap 扩容机制
2、遍历的时候,如果没有扩容,那么所有的数据,都在旧的空间里,只需要遍历旧的空间ht[0]即可,但是如果扩容了,那么已遍历过的下标的数据,可能有部分会分配到idx+size0的位置,如果按下标顺序遍历的话,可能会大量遍历到重复的数据。

假设扩容前空间长度为4,在遍历完idx为0的数据后,发生了扩容,空间扩大到8,,那么原本idx为0的数据,在扩容后,idx就调整为0+4==4,那么新空间idx为4的数据,都是已经遍历过的数据

3、如何尽可能减少数据的重复遍历呢,是不是可以考虑调整遍历的顺序,从而实现扩容后的遍历,跳过新空间中idx+size0下标的位置:

当size=2:
遍历的下标有:0,1

扩容后size=4:
那么原本0下标的数据,在新空间就对应:0,2
原本1下标的数据,在新空间就对应:1, 3
那么按0,2,1,3的顺序遍历,则可在扩容后,跳过已经遍历的数据。

扩容后size=8:
那么按原size=4:0,2,1,3的顺序,新扩容后的空间对应关系就有:
0对应新空间:0,4
2对应新空间:2,6
1对应新空间:1, 5
3对应新空间:3, 7
那么此时的遍历顺序则为0,4,2,6,1,5,3,7

因此,遍历的逻辑为,给定一个下标,在新size下的访问顺序,要按旧size做为模同余的key的顺序进行遍历,二进制的演进如下:
(以下:cursor % size 余数idx小于size/2的称为低位槽,大于或等于size/2小于size的称为高位槽; 掩码位: 即数a,与掩码位数相同的位。)
当size为2时,掩码为1,二进制表示为1,掩码位只有一位;
下标的标识分别为:0,1

当size为4时,掩码为3,二进制表示为11,掩码位两位:
那么原本的下标0,1,调整掩码位后为00 , 01
调整size1 = size0*2后的,原本的idx,分别产生idx与idx+size0两个下标,二进制表示则为下标二进制表示的掩码位的高位(最左的0)置1,如:
00, 高位的0置1,成10,值即为2;
01, 高位的0置1,成11,值即为3.
输出:00,10,01,11

当size为8时,掩码为7,二进制表示为111,掩码位三位:
原本下标为:00,10,01,11,调整掩码位后为000 , 010,001,011
同样掩码位最高位置1:
000 高位的0置1,成100,值即为4;
010 高位的0置1,成110,值即为6
001 高位的0置1,成101,值即为5;
011 高位的0置1,成111,值即为7;
此时的遍历顺序则为0,4,2,6,1,5,3,7

从0到4,从2到6,从1到5,从3到7是比较容易理解的,但是如果从4到2,从6到1呢:从上面的顺序可以看出,在旧空间同余的key,在新空间表现为低位槽,高位槽交替,也就说说如何从高位槽,遍历到下一个低位槽:
可以看出,下一个低位槽, 其实就是上一个低位槽在旧空间时的高位槽,比如长度为8时,低位槽为0(000),高位槽为4(100),那么4的下一个低位槽2(010),其实是长度为4时,低位槽0的高位槽。也就是说,要从高位槽遍历到下一个低位槽,就要将当前掩码位的最高位置位0,然后将次高位置1,意思就是找在扩容前的低位槽2的高位槽,如:高位槽100,则变成010这个低位槽,而这个低位槽则是掩码只有两位时,即是扩容前的低位槽00 的高位槽。
如果本身低位就是2(010),高位槽是6(110),当6掩码位最高位置0后的010在旧空间也是高位槽那么再找下一个低位槽,就要最高位次高位都置0,次次高位置1即为001,以此类推。

也就是说,对于数a, 掩码位的1,表示以这个位作为掩码位最高位时,这个数都是高位槽
如:7(0000_0111) 掩码位111,最高位的1表示掩码位是三个位(size=8)时,该数是高位槽,次高位的1,表示掩码位是两个位(size=4)时,该数是高位槽,次次高位的1,表示掩码位是两个位(size=2)时,该数是高位槽

至此,也只是理论上,实现了调整遍历顺序,达到减少重复遍历的效果,但是怎么用位运算实现上面的理论呢,采用递归的方法,可以实现高位槽低位槽的切换,不过Redis的dictScan方法中使用了一种逆序运算的方法:

1、将下标逆序,从大端编码变成小端编码,如001,转换成100;
2、逆序后+1,100加1后为101
3、再逆序回来,变回大端编码,转换为101,此时的值就是下一个需要遍历的下标

dictScan的这个算法,实现了给掩码位的最高位置1,但是,神奇的事也发生了,使用同样的方式,竟然可以继续从高位槽遍历到下一个低位槽(即掩码次高位置1)。如:

101逆序后仍为101-》逆序后+1,值为110-》110再逆序回来,成011

前面这一大段的内容,就是描述下面这三行代码的逻辑

v = rev(v);
v++;
v = rev(v);

当然实际计算机位运算中,没法直接就知道只运算掩码覆盖的这几位,那么这三行代码前面那句v |= ~m0;就是通过游标与掩码的反码做或运算,标识需要运算的掩码覆盖的位,比如:

size为4,掩码为3,二进制0000 0011,游标为1,二进制0000 0001
v|= ~m0,即为0000 0001 | 1111 1100,得到v = 1111 1101
逆序后为 v=1011 1111
逆序后+1为 v = 1100 0000
再次逆序 v = 0000 0011,值为3,遍历1之后的下一个游标为3.

二进制的运算就是这样总是充满意想不到的神奇。

二、JDK的concurrentHashMap 的扩容
不同于dict扩容时通过ht[0],ht[1]渐进式的扩容迁移,concurrentHashMap 扩容采用表示低位链(由低位节点组成)、高位链(由高位节点构成)在扩容后,直接按高位链低位链迁移到高位idx和低位idx,但是思想是差不多的。不过concurrentHashMap 在迁移时会对扩容前的下标对应的node上锁:可以参考我之前的笔记concurrentHashMap 1.8笔记
这里重点回顾下相似的位运算逻辑判断高位节点和低位节点:

int b = hash & n; 假设n = 8 0000_1000 记值为1的位为runbit为3(右往左从第0位开始数第三位)
hash1 = 7, 0000_0111 & 0000_1000 -> runbit位值为0
hash2 = 15, 0000_1111 & 0000_1000 -> runbit 位值为1
hash3 = 23, 0001_0111 & 0000_1000 -> runbit 位值为0
即runbit 位为1时,肯定是余数+奇数倍的n, runbit 位为0时,肯定是余数+偶数倍的n
以上三个hash的 mod 8均取余数 m = 7 (或 hash &(n-1))
即hash = a*n + m ;
a为偶数时,hash & n 的runbit位为0,记为低位节点hash
a为奇数时,hash & n 的runbit位为1,记为高位节点hash
扩容后,n<<2 为16,0001_0000
低位节点hash mod 16,与扩容前 hash mod 8 两者取余 m 相等 高位节点hash mod16,扩容后取余 等于 m + 8(即 m + 扩大的容量n)文章来源地址https://www.toymoban.com/news/detail-502202.html

到了这里,关于redis源码之:扩容后的dictScan遍历顺序与JDK的concurrentHashMap 扩容机制的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 源码分析——ConcurrentHashMap源码+底层数据结构分析

    1. 存储结构 Java 7 中 ConcurrentHashMap 的存储结构如上图,ConcurrnetHashMap 由很多个 Segment 组合,而每一个 Segment 是一个类似于 HashMap 的结构,所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦 初始化就不能改变 ,默认 Segment 的个数是 16 个,你也可以认为 ConcurrentH

    2024年02月13日
    浏览(52)
  • Java进阶(ConcurrentHashMap)——面试时ConcurrentHashMap常见问题解读 & 结合源码分析 & 多线程CAS比较并交换 初识

    List、Set、HashMap作为Java中常用的集合,需要深入认识其原理和特性。 本篇博客介绍常见的关于Java中线程安全的ConcurrentHashMap集合的面试问题,结合源码分析题目背后的知识点。 关于List的博客文章如下: Java进阶(List)——面试时List常见问题解读 结合源码分析 关于的Set的博

    2024年02月06日
    浏览(60)
  • 结合底层源码介绍ConcurrentHashMap如何保证线程安全,佬会爱上这篇文章嘛

    前言: 本篇文章主要讲解 结合底层源码介绍ConcurrentHashMap如何保证线程安全 的知识。该专栏比较适合刚入坑Java的小白以及准备秋招的大佬阅读。 如果文章有什么需要改进的地方欢迎大佬提出,对大佬有帮助希望可以支持下哦~ 小威在此先感谢各位小伙伴儿了😁 以下正文开

    2024年02月11日
    浏览(42)
  • Redis6集群安装及其扩容缩容

    虚拟机拷贝2-3台centos机器,作为Redis6集群的主备节点 部署规划: master 192.168.28.132 8001 192.168.28.132 8002 192.168.28.132 8003 slaver 192.168.28.135 8001 192.168.28.135 8002 192.168.28.135 8003 一、安装依赖环境 1、安装编译依赖 yum install gcc tcl tcl-devel   此处使用yum,也可以下载RPM包后安装 2、安装

    2024年02月09日
    浏览(46)
  • Redis扩容与一致性Hash算法解析

    作者:zhaokk 在分布式系统中,随着数据量的增加和负载的变化,对于存储系统的扩容变得尤为重要。Redis作为一种高性能的内存数据库,其在扩容方面采用了一致性Hash算法,以实现无缝的数据分布和负载均衡。本篇博客将详细探讨Redis的扩容机制,同时深入解析一致性Hash算法

    2024年02月12日
    浏览(56)
  • Redis扩容机制与一致性哈希算法解析

    在分布式系统设计中,Redis是一个备受欢迎的内存数据库,而一致性哈希算法则是分布式系统中常用的数据分片和负载均衡技术。本文将深入探讨Redis的扩容机制以及一致性哈希算法的原理,同时提供示例代码以帮助读者更好地理解这两个重要概念。 Redis是一种高性能的内存数

    2024年02月11日
    浏览(47)
  • Android Studio版本升级后的问题 gradle降级、jdk升级 Compose 与 Kotlin 的兼容性对应关系

    AGPBI: {“kind”:“error”,“text”:“Can’t determine type for tag ‘macro name=“m3_comp_switch_disabled_selected_handle_color”?attr/colorSurface’”,“sources”:[{“file”:“/Users/fausto/.gradle/caches/transforms-3/4948d05d0ff6027d2e3c9f4a6010103b/transformed/material-1.7.0-alpha02/res/values/values.xml”}],“tool”:“Resource and

    2024年02月04日
    浏览(78)
  • 源码分析——ArrayList源码+扩容机制分析

    ArrayList 的底层是数组队列,相当于动态数组。与 Java 中的数组相比,它的容量能动态增长。在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。 ArrayList 继承于 AbstractList ,实现了 List , RandomAccess , Cloneable , ja

    2024年02月14日
    浏览(46)
  • 12、SpringCloud -- redis库存和redis预库存保持一致、优化后的压测效果

    redis库存 是指初始化是从数据库中获取最新的秒杀商品列表数据存到redis中 redis的预库存 是指每个秒杀商品每次成功秒杀之后,该商品的剩余库存数量是多少,这个数量和数据是一致的。 数据库的库

    2024年02月06日
    浏览(40)
  • 分布式项目08 redis的扩容,预备redis宕机的哨兵处理 和 最后集大成redis集群

    01.redis扩容 由于redis的容量也是有限的,所以,就会有扩容的操作。也就好像内存中扩容一样。redis有分片这种说法,具体实现操作如下: 第一步:首先在/usr/local/src中去找到redis文件夹。cd /usr/local/src 而后进入redis文件夹。使用的linux命令是 cd redis 。 第二步: 01.使用查看当前

    2024年02月05日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包