Redis数据结构之listpack

前言

当数据量较小时，Redis 会优先考虑用 ziplist 来存储 hash、list、zset，这么做可以有效的节省内存空间，因为 ziplist 是一块连续的内存空间，它采用一种紧凑的方式来存储元素。但是它也有缺点，比如查找的时间复杂度高、内存分配的开销、连锁更新的风险等。
于是 Redis 在 3.0 版本推出了 quicklist，它可以看作是 ziplist 的升级版，本质是把多个 ziplist 串联成链表，把每个 ziplist 限制在一定的大小，以此来降低 内存分配、连锁更新 的影响，但是它并没有完全解决连锁更新的问题，并且链表的每个节点也是要额外占用内存的。
Redis 5.0 终于推出了一个新的紧凑列表 listpack，它沿用了 ziplist 的内存布局，元素紧挨在一起，没有指针的额外开销，同时解决了连锁更新的问题。

listpack

listpack 的设计和 ziplist 如出一辙，如果你了解 ziplist，相信很容易理解 listpack。
listpack 也叫 紧凑列表，它采用紧凑的内存布局，本质上仍是一个字节数组。为了节省空间，它采用了多种编码方式来表示不同长度的整型和字符串。最后，它不再像 ziplist 一样元素还要记录上一个元素的大小，而是记录当前元素的大下，彻底解决了连锁更新的问题。

• totalbytes：listpack 占用的字节数，4 字节
• size：listpack 元素数量，2 字节
• element：元素
• end：结尾符 0xFF 1 字节

totalbytes + size 也被称作 listpack 头部，大小是 6 字节，再加上 1 字节的结尾符，所以一个空的 listpack 大小是 7 字节。

编码方式

为了节省内存，listpack 针对不同长度的整型和字符串定义了多种编码方式：

#define LP_ENCODING_7BIT_UINT 0
#define LP_ENCODING_13BIT_INT 0xC0
#define LP_ENCODING_16BIT_INT 0xF1
#define LP_ENCODING_24BIT_INT 0xF2
#define LP_ENCODING_32BIT_INT 0xF3
#define LP_ENCODING_64BIT_INT 0xF4
#define LP_ENCODING_6BIT_STR 0x80
#define LP_ENCODING_12BIT_STR 0xE0
#define LP_ENCODING_32BIT_STR 0xF0

• _UINT 结尾：无符号整型
• _INT 结尾：有符号整型
• _STR 结尾：字符串

这里对编码方式举例解释一下，其它几种以此类推：

• LP_ENCODING_7BIT_UINT：代表 7Bit 无符号整型，1 个字节表示，高 1 位是 0，低 7 位表示整型值
• LP_ENCODING_13BIT_INT：代表 13Bit 有符号整型，2 字节表示，高 3 位是 110，低 13 位 表示整型值
• LP_ENCODING_6BIT_STR：长度不超过 63 的字符串。1 字节表示 encoding，高 2 位是 10，低 6 位代表字符串的长度，data 部分是具体的字符串值

避免连锁更新

listpack 彻底解决了 ziplist 连锁更新的问题，怎么做的呢？
ziplist 为什么会存在连锁更新的问题？就是因为每个元素要记录上一个元素的长度，而且采用变长字节记录，小于 254 就用1字节，否则用5字节。如此一来，某个元素修改时，影响的就不仅仅是自己了，还会影响后面的元素，引发连锁反应。
listpack 解决方式就是元素不再记录上一个元素的大小了，而是改为记录自身的大小，这样元素与元素之间就独立了，不会相互影响到。

遍历问题

ziplist 元素记录上一个元素的大小，是为了支持从后向前遍历。listpack 改为记录元素自身大小了，那么还支持双向遍历吗？
答案是支持的，我们来看一下双向遍历的过程。

• 正向遍历

正向遍历时，listpack 首先跳过 6 字节的头部，指针就会指向第一个元素，再根据元素的 encoding 字段得到元素的长度和类型，然后就可以正常访问元素了。再根据 encoding 计算当前元素长度占用的字节数，跳过当前元素占用的字节数，就可以访问下一个元素了，直到访问到结尾符，代表结束。

• 反向遍历

首先访问 listpack 的前4字节得到总长度，然后就可以定位到末尾结尾符位置。然后指针左移就可以访问到最后一个元素的长度 len，指针再左移 len 就可以访问最后一个元素的 encoding，根据编码方式访问元素。指针再左移又可以访问到倒数第2个元素的长度，以此类推。
访问元素长度len字段时，有一个关键点，就是如何判断 len 部分结束了。因为 len 可能占用1字节，也可能占用多个字节。listpack 的做法是，每个字节只使用 7 Bit，最高位来表示是否还要继续读。

尾巴

listpack 是 Redis 对 ziplist 的改进版本，彻底解决 ziplist 连锁更新的问题。紧凑的内存布局，避免了传统链表指针带来的访问效率和内存占用问题，非常适合小数据量的存储。
需要注意的是，listpack 查询效率依然是 O(N)，查找时间会随着元素数量线性增长，不过好在 Redis 基本拿它存储少量数据，所以 N 的值一般不会太大。