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

Redis 中List 及 quicklist实现 1

quicklist是在Redis 3.2 之后出现的一种Redis底层数据结构用于List结构的具体实现,List在Redis中更像是数据结构中常说的双向链表,可以被用作栈或者队列。

常用的List中的命令:LPUSH(左端插入)、RPUSH(左端插入)、LRANGE(获取所有元素)、LINSERT(在指定名称之后插入)、LINDEX(查看对应索引位置的元素)、LTRIM(删除元素)、LSET(设置指定位置的元素)。其中LPUSH、RPUSH、LINSERT在完成插入之后会返回插入后列表的长度。当如果之前不存在对应的List键,则创建一个新的链表进行插入,同样的Redis会替我们完成对应的回收。

Redis List中的索引:从左到右是:0~N-1,从右到左是:-1~-N,很容易看到,0~-1只的就是整个链表。

这里还有两个比较有趣的命令:POP(L、R),并且对应的有BPOP(L、R),B开头的是一种阻塞结构:阻塞版本也是从左端或者右端弹出元素,但是列表为空时,阻塞版本会将客户端阻塞(这里有一个等待的超时时间,如果超时时间为0时,永久等待,如果是其他的则等待对应的时间),这个特性经常在任务调度场景中使用。

下面来看一下Redis 中List的具体实现QuickList,这里有两个相关的参数来进行quicklist的控制:

list-max-ziplist-size:每个quicklist的节点都是一个ziplist,这个参数指定的是内部节点的最大大小。

list-compress-depth:列表的也锁策略,这个参数指定的是quicklist两端不被压缩的节点的个数,因为照常来说,最常被访问的数据就是位于列表两端的数据。

就具体实现来说,QuickList是一种二合一的数据结构,实现的方式和STL 源码中的Deque实现思想是相似的只不过细节结构上存在差异而已,deque(一个双向开口的可进可出的容器)是一个有map中控器和一个数组构成的数据结构,既有头尾便捷插入的特点、也有数组内存连续&支持下标访问的特点。

image.png

在Redis中sdlsit是途中map中控器地位的存在,然后ziplist作为具体的存储结构(综合了双向链表和ziplist的优点),我们需要关注ziplist的容量如果ziplist中的元素过少,内存随便会增多,可以按照极端情况的双向链表来考虑,如果ziplist中的元素个数过多,那么给ziplist分配最大块连续内存空间的难度就增大,同样会影响效率。所以说确定list-max-ziplist-size的大小十分关键。

和quicklist相关的文件有quicklist.c(具体逻辑实现)、quicklist.h(结构体定义)

下面是quicklist的结构,每个占32字节的空间,里面有一个首尾指针、数据项总和、ziplist的个数、ziplist大小限定(由list-max-ziplist-size来指定,默认16)、节点压缩深度(由list-compress-depth指定,默认16)

image.png

然后是节点信息每个同样占32个字节,一个prev指针、next指针、*zl为数据指针(如果没有被压缩指向ziplist结构,如果被压缩了指向quicklistLZF),sz是ziplist的总长度(内存深度),count是指包含的数据项的个数,encoding是具体的编码方式(1为ziplist、2为quicklistLZF,默认是2),container 是一个预留字段,指存放数据的方式(1 NONE 2 ziplist),recompress是解压标记(需要解压时设置为1之后再重新进行压缩, 默认1),attempted_compress 测试相关,extra是一个扩展字段,临时没什么用。

image.png

上面提到的quicklistLZF结构如下:

image.png

另外quicklist还提供了迭代器结构及指向ziplist中的节点结构:

image.png

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis hash类型

    Hash 表示的是一种字段与值之间的映射关系,与很多编程语言中的map或者字典类型类似。Redis其实本身就可以本身就可以看作一个大Hash,其字符串类型的键关...

    邹志全
  • Redis 压缩链表ziplist 源码解析

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

    邹志全
  • Go 语言基础--string&数组&切片 浅析

    本篇来看一下go语言基本的一些复合结构,最常使用的复合结构有map、数组、切片这几个,string因为底层实现是一个[]byte所以大致可以理解为是一种数组结构...

    邹志全
  • 和柳叶刀、细胞说再见:加州大学宣布取消所有Elsevier期刊订阅

    当地时间 2 月 28 日,UC 发表声明表示:续签集体合同的谈判已经破裂,因为爱思唯尔拒绝达成一揽子协议。因此,加州大学系统的期刊订阅已宣告中断,同时来自 U...

    机器之心
  • TCGA数据库:生存分析

    本文介绍生存分析,其实,在R中,生存分析很简单,大家在网上能找到无数的文章。利用survival包就可以。就是按照下列公式就可以完成简单的生存分析。

    DoubleHelix
  • Git Merge

    程序手艺人
  • 错误提示之(MVC3.0):HTTP 404。您正在查找的资源(或者它的一个依赖项)可能已被移除,或其名称已更改,或暂时不可用。请检查以下 URL 并确保其拼写正确 MVC误设起始页

    MVC3.0框架开发项目: 有时在程序运行的时候会出现“HTTP 404。您正在查找的资源(或者它的一个依赖项)可能已被移除,或其名称已更改,或暂时不可用。请检...

    hbbliyong
  • 大数据推进个性化医疗的五大原因

    大数据文摘
  • 深刻理解HDFS工作原理

    概述 HDFS(Hadoop Distributed File System )Hadoop分布式文件系统的简称。HDFS被设计成适合运行在通用硬件(commo...

    xiangzhihong
  • mybatis教程之原理剖析

      MyBatis是目前非常流行的ORM框架,功能很强大,然而其实现却比较简单、优雅。本文通过代理的方式来看下其实现

    用户4919348

扫码关注云+社区

领取腾讯云代金券