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
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Redis主要支持的数据类型有5种:String ,Hash ,List ,Set ,和 Sorted Set。 ...
    爱情小傻蛋阅读 5,330评论 0 0
  • 参考来源 Redis的内存优化 Redis所有的数据都在内存中,而内存又是非常宝贵的资源。对于如何优化内存使用一直...
    秦汉邮侠阅读 5,060评论 0 2
  • Redis的内存优化 声明:本文内容来自《Redis开发与运维》一书第八章,如转载请声明。 Redis所有的数据都...
    meng_philip123阅读 18,985评论 2 29
  • 我上学时,经常看到微信朋友圈里有各种学习打卡,那个时候我觉得:“啊,他们好无聊,学个习还要每天打个卡,多麻烦。” ...
    诗安闪Shan阅读 1,508评论 0 1
  • 阳光爱上了鹅卵石 缕缕柔软 铺上丝丝温暖 挣扎于你的冷硬 又不舍离开你的柔滑 这是一次没有结果的等待 这是一场痛到...
    河洋zj阅读 806评论 0 2