专栏首页EffectiveCodingRedis 中List 及 quicklist实现 2

Redis 中List 及 quicklist实现 2

上一篇中看了List的使用方式、quicklist中的各个结构体,这一篇来看看quicklist里面的几个核心函数,quicklistCreate函数、quicklistCreateNode函数、quicklistPush函数、quicklistPop函数。

接下来我们通过源码看一下quicklist中是如何借鉴STL中deque的这种实现思想来完成对于sdlist及ziplist有点的结合的,并且在时间和空间是如何做的均衡,来达到“quick”的效果。

我们打开quicklist.c文件,找到第94行。

首先完成了对于一个quicklist结构体的指针,然后对quicklist进行内存分配操作,之后再设置首尾指针,再指定quicklist的长度、数据项总和、压缩深度、ziplist的的大小限定(这个值可以有五个取值,-1:每个节点的ziplist字节数不能超过4kb,-2:每个节点的ziplist字节数不能超过8kb,-3:每个节点的ziplist字节数不能超过16kb,-4:每个节点的字节数不能超过32kb,-5:每个节点的字节数不能超过64kb, 默认是不能超过4kb的)

image.png

创建完quicklist之后,下一步就是创建quicklist节点了,看一下quicklist的第138行

这个过程和创建quicklist基本上是一致的,声明指针、申请内存、初始化ziplist指针、初始化数据项、ziplist的大小、初始化prev、next指针、初始化节点编码方式默认是QUICK_NODE_ENCODING_RAW、初始化数据的存放方式默认是QUICKLIST_NODE_CONTAINER_ZIPLIST,最后初始完压缩标示然后结束。

image.png

看完初始化操作之后,接下来是PUSH操作:

不管是LPUSH还是RPUSH都包含两个步骤,如果插入节点的ziplist大小没有超过限制直接用ziplistPush函数压入,如果ziplist的大小超过了限制,则新创建一个quicklist来进行压入。

image.png

然后来看一下这两个函数:

likely是linux提供的可选择的编译优化方法,可以讲分支专一的信息提供给编译器,然后减少指令跳转带来的性能下降(likely是编译器级别的优化)。

首先判断首/尾是否允许插入(首部节点的大小和fill参数做比较)然后如果允许插入世界调用ziplistpush插入,然后更新首部大小即可以了,如果节点满了,看一些else里面的内容,就需要重新创建一个节点,将新节点压入心创建的ziplist中,并且与新创建的quicklist节点关联起来,同时更新大小,然后创建一个新的ziplist节点,完成压入,更新数据项等。如果反悔的quicklist指针没变,则返回0,否则返回1。

image.png

接下来看一下quicklistPop函数,然后具体的逻辑其实是在quicklistPopCustom中实现的。

就是进行Pop操作,执行成功返回1,失败返回0,如果弹出的节点是字符串,那么data、sz存放弹出字符串值,如果弹出节点是整型,slong存放弹出节点的整型值。

image.png

然后具体看一下quicklistPopCustom函数,执行成功返回1,失败返回0,如果弹出的节点是字符串,那么data、sz存放弹出字符串值,如果弹出节点是整型,slong存放弹出节点的整型值。

首先判断弹出位置首部或者尾部,如果没有数据直接return 0,然后获取quicklist的节点(ziplist),再获取ziplist的节点,然后获取节点的值,如果是字符串值,通过_quicklistSaver深拷贝取出返回值,如果是整型的则字符串设置为NULL,弹出节点的整型值,删除该节点。

image.png

这里_quicklistSaver 深拷贝取值的原因是避免二次释放。

image.png

quicklist核心的API就这几个,但Redis实际上是实现了好多的,比如说:

1、比较两个quicklist结构数据的:quicklistCount

2、从节点node中取出LZF压缩编码后的数据:quicklistGetLzf

3、翻转quicklist:quicklistRotate

4、删除ziplist节点entry:quicklistDelEntry

5、在node节点前添加一个value:quicklistInsertBefore

6、在node节点后添加一个value:quicklistInsertAfter

7、将ziplist转换为quicklist:*quicklistCreateFromZiplist

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 压缩链表ziplist 源码解析

    之前说quicklist 及 hash 类型的时候都提到了一种底层的实现结构叫做 ziplist。先看一下源码里面官方的介绍:

    邹志全
  • Redis 中List 及 quicklist实现 1

    quicklist是在Redis 3.2 之后出现的一种Redis底层数据结构用于List结构的具体实现,List在Redis中更像是数据结构中常说的双向链表,...

    邹志全
  • Go 语言基础--接口浅析

    go 接口是go语言程序设计中很重要的一部分,如果说Java 中一切皆对象,那么go中的接口就很像是Java中的object,Java的面向对象编程、go的面向...

    邹志全
  • javascript:二叉搜索树 实现

    二叉搜索树:顾名思义,树上每个节点最多只有二根分叉;而且左分叉节点的值 < 右分叉节点的值 。 特点:插入节点、找最大/最小节点、节点值排序 非常方便 二叉搜索...

    菩提树下的杨过
  • 好大一棵树,新春的祝福(一):n级分类的数据结构

         这个树的结构几年前在csdn里面也发过了一次,现在看看,主体结构居然没有什么变化,用了这么长的时间,自我感觉还是很好用的。而且在这个基础之上把其他的功...

    用户1174620
  • RabbitMQ HAProxy负载均衡

    在本章开始之前,我们虽然前面已经创建了集群,但是我们在之前连接集群的方式,都是直连集群中的某一个几点,这样被直连的几点将会承受很大的压力,剩余的节点则比较浪费,...

    shysh95
  • 图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

    江不知
  • 【NLP】ACL20 基于对话图谱的开放域多轮对话策略学习

    论文中提出用图的形式捕捉对话转移规律作为先验信息,用于辅助开放域多轮对话策略学习。为此,研究人员首先从对话语料库中构建了一个对话图谱(Conversationa...

    yuquanle
  • MySQL中GTID和自增列的数据测试(r12笔记第38天)

    昨天的一篇文章MySQL自增列主从不一致的测试(r12笔记第37天),今天有不少网友向我确认一些细节,我想最近正好在看GTID的东西,可以揉在一起来说说。 ...

    jeanron100
  • 8种最坑的SQL错误用法,第一个就很坑?

    分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般 DBA 想到的办法是在 type, name, create_time...

    JAVA葵花宝典

扫码关注云+社区

领取腾讯云代金券