专栏首页EffectiveCodingRedis 压缩链表ziplist 源码解析

Redis 压缩链表ziplist 源码解析

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

image.png

这段话大体意思是说,ziplist是一种特殊编码的双链表,主要是为了节省内存而存在的,整个都是由字符串和整数值组成的,其中整数值被编码为实际的整数,而不是一系列字符。可以在O(1) 时间内进行push和pop操作,然后具体一些操作的复杂程度和具体使用的内存数量有关,这也就是为什么数量膨胀到一定程度之后很多结构就不采用ziplist。下面具体的来看一下ziplist的实现:

首先ziplist是一种连续&无序的线形数据结构,结构是这样的:

image.png

image.png

与其他的数据结构不同并没有定义专门的数据结构来保存ziplist的信息,而是采用了一组宏来定位每个成员的地址,具体源码的话可以看一src/ziplist.c

image.png

ZIPLIST_BYTES 将zl定位到签字个字节的bytes成员,记录整个ziplist的内存字节数,ZIPLIST_TAIL_OFFSET 将zl定位到4字节到8字节的tail_offset成员,记录了下压缩列表起始地址的偏移字节量,将zl定位到8字节到10字节的length成员,也就是记录了ziplist的节点数量,ZIPLIST_HEADER_SIZE 指的是ziplist头节点的大小(ZIPLIST_END_SIZE 一样),ZIPLIST_ENTRY_HEAD 、ZIPLIST_ENTRY_TAIL、ZIPLIST_ENTRY_END 分别指的是首节点的地址、尾节点的地址、END节点的地址。

然后存在一个叫做zlentry的结构来管理各个节点的所有信息,prevrawlen是指前驱节点的长度,prevrawlensize 编码前驱节点prevrawlen所需要的字节大小,lensize 指的是当前节点值长度len所需要的字节数,len当前节点长度,headersize 当前节点header大小(也就是lensize+prevrawlensize),encoding 为当前节点的编码格式,*p 只想当前节点的指针。然而并没有使用这个结构体来存储数据节点中的结构,因为如果存储小整型或者短字符串就造成了不必要的内存浪费。

image.png

但是为了更加省内存,ziplist对于上述的这种结构都是嫌弃的,直接简单粗暴的采用了下面这种结构:

实际上是这么来存的 <prev_entry_len>(记录前驱节点的长度), <encoding>(当前节点的value成员的数据类型和长度), <value>(保存字节数组和整数)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 中List 及 quicklist实现 2

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

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

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

    邹志全
  • Go 并发实战--管道浅析

    在讲 channel 之前,有必要先提一下 CSP 模型,传统的并发模型主要分为 Actor模型和CSP模型,CSP 模型(communicating sequ...

    邹志全
  • 算法提高 9-1九宫格

    问题描述   九宫格。输入1-9这9个数字的一种任意排序,构成3*3二维数组。如果每行、每列以及对角线之和都相等,打印1。否则打印0。 样例输出 与...

    AI那点小事
  • TCP 三次握手的意义

    在网络的传输层协议中, 存在着两大悍将: TCP 和 UDP . 从前, 我傻傻的以为自己对他们虽谈不上精通, 但还是知道的, 但是, 我错了, 我被自己问住了...

    烟草的香味
  • TCP 三次握手的意义

    在网络的传输层协议中, 存在着两大悍将: TCP 和 UDP . 从前, 我傻傻的以为自己对他们虽谈不上精通, 但还是知道的, 但是, 我错了, 我被自己问住了...

    烟草的香味
  • Linux 、Mac OSX 常见问题 及 笔记

    Linux的很多命令都是依赖libc.so.6的动态链接库,如果不小心把它删除了,基本上所有命令都不能使用

    用户2836074
  • CCF考试——201609-2火车购票

      请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。   假设一节车厢有20排、每一排5个座位。为方便起见,我们用1到100来给所有的...

    AI那点小事
  • Golang Leetcode 310. Minimum Height Trees.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89068745

    anakinsun
  • 直播回顾 | 腾讯分布式数据库TDSQL金融级能力的架构原理解读

    腾讯云数据库国产数据库专题线上技术沙龙正在火热进行中,3月10日张文的分享已经结束,没来得及参与的小伙伴不用担心,以下就是直播的视频和文字回顾。

    腾讯云数据库 TencentDB

扫码关注云+社区

领取腾讯云代金券