Redis知识梳理(28) [ 压缩列表 ]

- 日理万妓 2022-02-03 13:59 250阅读 0赞

Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链 表 linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。

> // 链表的节点  
> struct listNode \{  
> listNode\* prev;  
> listNode\* next;  
> T value;  
> \}  
> // 链表  
> struct list \{  
> listNode \*head;  
> listNode \*tail;  
> long length;  
> \}

考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎 片化，影响内存管理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

> > rpush codehole go java python  
> (integer) 3  
> > debug object codehole  
> Value at:0x7fec2dc2bde0 refcount:1 encoding:quicklist serializedlength:31 lru:6101643 lru\_seconds\_idle:5 ql nodes: 1 ql avg node:3.00 ql\_ziplist max:-2 ql\_compressed:0 ql\_uncompressed\_size:29

注意观察上面输出字段 encoding 的值。quicklist 是 ziplist 和 linkedlist 的混 合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

![img][]

>  struct ziplist \{  
> …  
> \}
> 
>  struct ziplist\_compressed \{  
> int32 size;  
> byte\[\] compressed\_data;  
> \}
> 
>  struct quicklistNode \{  
> quicklistNode\* prev;  
> quicklistNode\* next;  
> ziplist\* zl; // 指向压缩列表  
> int32 size; // ziplist 的字节总数  
> int16 count; // ziplist 中的元素数量  
> int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储  
> …  
> \}
> 
>  struct quicklist \{  
> quicklistNode\* head;  
> quicklistNode\* tail;  
> long count; // 元素总数  
> int nodes; // ziplist 节点的个数  
> int compressDepth; // LZF 算法压缩深度  
> …  
> \}

上述代码简单地表示了 quicklist 的大致结构。为了进一步节约空间，Redis 还 会对 ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。

# 每个 ziplist 存多少元素? #

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起 一个 ziplist。ziplist 的长度由配置参数 list-max-ziplist-size 决定。

# 压缩深度 #

![img][img 1]

quicklist 默认的压缩深度是 0，也就是不压缩。压缩的实际深度由配置参数 list-compress-depth 决定。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时深度就是 1。如果深度为 2，就表示 quicklist 的首 尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

[img]: /images/20220203/6e45f9f69a114570882ec00086151630.png
[img 1]: /images/20220203/2ea959e940f847d6b0dc7e6a37104536.png