【Redis从入门到精通】第18篇：压缩列表——Redis的内存压缩黑科技

上一篇【第17篇】整数集合——Redis集合的省内存利器下一篇【第19篇】String对象的七十二变——int/embstr/raw编码的切换逻辑在Redis的数据结构全家桶里有一个名声在外但又让人又爱又恨的角色——压缩列表ziplist。它曾经是Redis节省内存的头号功臣但同时也因为一个叫连锁更新的幽灵bug级机制让无数DBA头疼。今天我们就来彻底拆解这个结构看看它的精妙之处和隐患。一、ziplist是什么为什么要压缩ziplist是Redis为了极致节省内存而设计的一种特殊列表结构。普通的链表每个节点都需要存储前后指针各8字节如果节点存的是一个很小的数据比如1字节的字符那指针的开销比数据本身还大——这太浪费了。普通双向链表的内存开销 ┌──────┐ ←prev── ┌──────┐ ←prev── ┌──────┐ │ prev │──────────→│ prev │──────────→│ prev │ │ next │←──────────│ next │←──────────│ next │ │ data │ 1B │ data │ 1B │ data │ └──────┘ └──────┘ └──────┘ 17B 17B 17B 存3个1字节数据需要51字节其中48字节是指针开销 ziplist的内存开销 ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐ │H │H │H │H │D1│D2│D3│E │ ... │ ← 连续内存无指针 └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘ 约12字节固定开销 3字节数据≈ 15字节ziplist通过把所有数据紧凑地存在一块连续内存里消除了所有指针开销。代价是插入和删除需要移动数据像数组一样但Redis认为在数据量小的场景下这个代价完全可以接受。二、ziplist的整体结构一个完整的ziplist由以下几个部分组成┌──────────┬──────────┬──────────┬──────────┬──────────┬──────┐ │ zlbytes │ zltail │ zllen │ entry1 │ entry2 │ zlend│ │ (4字节) │ (4字节) │ (2字节) │ (变长) │ (变长) │(1字节)│ └──────────┴──────────┴──────────┴──────────┴──────────┴──────┘ ↓ ↓ ↓ ↓ ↓ ↓ 整个列表 尾部entry entry 第一个 第二个 结束 的字节总数 的偏移量 数量 元素 元素 标记各字段详解字段大小作用zlbytes4字节整个ziplist占用的内存字节数包括自身zltail4字节最后一个entry相对于ziplist起始地址的偏移量用于快速定位尾部实现RPUSH等O(1)操作zllen2字节entry的数量。当数量超过655352^16-1时需要遍历整个ziplist来获取真实数量entryN变长具体的数据节点zlend1字节固定值0xFF标记ziplist的结束踩坑提示zllen字段用2字节存储最大值65535。如果你的ziplist真的有超过65535个entry虽然不太可能那zllen会存65535实际数量需要遍历计算。Redis认为65535个entry的ziplist已经足够大了这时候早就该切换到其他编码了。三、entry节点的完整结构每个entry由三个部分组成┌───────────────────────┬───────────────────────┬──────────┐ │ previous_entry_length │ encoding │ content │ │ (1字节或5字节) │ (1字节、2字节或5字节) │ (变长) │ └───────────────────────┴───────────────────────┴──────────┘3.1 previous_entry_length指向前一个节点的指针这个字段记录了前一个entry的总长度用于从当前节点向前遍历实现ZREVRANGE等逆序操作。它有两种大小前一个entry长度previous_entry_length大小编码 254字节1字节直接存长度值0-253 254字节5字节第1字节固定为0xFE后4字节存实际长度情况1前驱254字节 entry: [prev_len5] [encoding] [content] ↑ 1字节直接存5 情况2前驱254字节 entry: [0xFE][0x00][0x00][0x01][0x00] [encoding] [content] ↑ 5字节0xFE开头 4字节长度(256)这个设计很巧妙——用变长编码来节省空间大多数小entry只需要1字节就能记录前驱长度。3.2 encoding标识数据类型和长度encoding字段负责告诉Redis后面的content存的是什么类型的数据、占了多少字节。它有两类编码第一类字节数组编码存字符串、二进制数据encoding前两位encoding长度content长度00xxxxxx1字节≤ 63字节01xxxxxx xxxxxxxx2字节≤ 16383字节10______ xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx5字节≤ 2^32-1字节第二类整数编码存整数更省空间encoding值encoding长度content类型content长度110000001字节int162字节110100001字节int324字节111000001字节int648字节111100001字节24位有符号整数3字节111111101字节8位有符号整数1字节111111111字节无contentzlend标记0字节踩坑提示注意111111110xFF被用作ziplist的结束标记所以不能作为entry的encoding使用。这也是ziplist不能存任意二进制数据的原因之一。一个具体例子存字符串 hello previous_entry_length: [0x05] ← 1字节前一个entry长度5 encoding: [0x05] ← 1字节00xxxxxxxxxxxx5表示content长5字节 content: [h][e][l][l][o] ← 5字节 存整数 42 previous_entry_length: [0x05] ← 1字节 encoding: [0xFE] ← 1字节111111108位整数 content: [0x2A] ← 1字节值42 存整数 100000 previous_entry_length: [0x02] ← 1字节 encoding: [0xF0] ← 1字节1111000024位整数 content: [0xA0][0x86][0x01] ← 3字节值100000四、连锁更新ziplist的阿喀琉斯之踵ziplist最臭名昭著的问题就是连锁更新cascade update。要理解这个问题我们需要回顾previous_entry_length的设计。4.1 触发场景假设我们有一串连续的entry每个entry的长度都在250~253字节之间修改前 ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ entry_1 │←→│ entry_2 │←→│ entry_3 │←→│ entry_4 │←→│ entry_5 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ │prev:1B │ │prev:1B │ │prev:1B │ │prev:1B │ │prev:1B │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘每个entry的previous_entry_length都是1字节因为前一个entry的长度252 254。现在我们在 entry_1 前面插入一个新的大entry比如300字节插入后 ┌──────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ NEW │←→│ entry_1 │←→│ entry_2 │←→│ entry_3 │←→│ entry_4 │←→│ entry_5 │ │ 300字节 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ │ 252字节 │ └──────────┘ │prev:5B! │ │prev:1B │ │prev:1B │ │prev:1B │ │prev:1B │ └─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘entry_1 的前驱变成300字节了≥254所以previous_entry_length需要从1字节扩展到5字节。entry_1 从252字节变成了252 4 256字节。这下 entry_2 也遭殃了——entry_2 的前驱entry_1从252字节变成了256字节≥254了entry_2 的previous_entry_length也要从1字节扩展到5字节连锁反应开始 entry_1: 252 → 256字节prev从1B→5B4B ↓ entry_2 的前驱从252→256≥254 entry_2: 252 → 256字节prev从1B→5B4B ↓ entry_3 的前驱从252→256≥254 entry_3: 252 → 256字节prev从1B→5B4B ↓ entry_4 的前驱从252→256≥254 entry_4: 252 → 256字节prev从1B→5B4B ↓ entry_5 的前驱从252→256≥254 entry_5: 252 → 256字节prev从1B→5B4B这就是连锁更新一次操作引发了N次内存重分配。最坏情况下时间复杂度是O(N²)。4.2 为什么实际上没那么可怕虽然最坏情况是O(N²)但在实际生产中连锁更新几乎不会造成严重问题触发条件极其苛刻需要连续N个entry的长度都在250~253字节这个极窄的范围内ziplist本身有大小限制通过配置参数限制ziplist的最大元素数和最大元素大小N通常很小Redis操作是原子的在Redis单线程模型下连锁更新不会导致数据不一致只是偶尔某次操作变慢# 观察连锁更新极端场景构造# 假设我们有100个252字节的entry# 插入一个300字节的新entry# 可能触发100次内存重分配# 但在正常业务中几乎不可能遇到踩坑提示虽然连锁更新在实际中很少触发但如果你发现Redis偶尔出现延迟毛刺而且你的Hash或List恰好用了ziplist编码可以检查一下是否有大量大小在250字节左右的entry。可以通过调小hash-max-ziplist-entries等参数来规避。五、ziplist的APIRedis为ziplist提供了一组操作API// 创建一个空的ziplistunsignedchar*ziplistNew(void);// 释放ziplistvoidziplistFree(unsignedchar*zl);// 在指定位置插入元素unsignedchar*ziplistInsert(unsignedchar*zl,unsignedchar*p,unsignedchar*s,unsignedintslen);// 在尾部追加元素unsignedchar*ziplistPush(unsignedchar*zl,unsignedchar*s,unsignedintslen,intwhere);// 删除指定位置的元素unsignedchar*ziplistDelete(unsignedchar*zl,unsignedchar**p);// 查找元素unsignedchar*ziplistFind(unsignedchar*zl,unsignedchar*fstr,unsignedintslen,unsignedintskip);// 获取指定位置的元素unsignedchar*ziplistIndex(unsignedchar*zl,intindex);// 获取ziplist的元素数量unsignedintziplistLen(unsignedchar*zl);// 获取ziplist的总字节数size_tziplistBlobLen(unsignedchar*zl);其中ziplistInsert是最复杂的操作——它需要计算新entry的大小检查是否需要更新后续entry的previous_entry_length可能触发连锁更新移动后续数据为新entry腾出空间写入新entry的数据更新ziplist头部信息六、Redis中使用ziplist的场景ziplist在Redis中曾经被广泛使用作为多种数据结构在小数据量时的底层实现数据类型使用ziplist的条件相关配置参数Hash元素数≤阈值 且 值大小≤阈值hash-max-ziplist-entries(默认512),hash-max-ziplist-value(默认64字节)ZSet元素数≤阈值 且 值大小≤阈值zset-max-ziplist-entries(默认128),zset-max-ziplist-value(默认64字节)List元素数≤阈值 且 值大小≤阈值list-max-ziplist-size(默认-2),list-max-ziplist-value(默认-2)# Hash使用ziplist的例子127.0.0.1:6379HMSET user:1 nameTomage25cityBeijingOK127.0.0.1:6379OBJECT ENCODING user:1ziplist# 小Hash使用ziplist# 添加大量字段后切换为hashtable127.0.0.1:6379EVALfor i1,513 do redis.call(HSET,user:1,field..i,value..i) end0(nil)127.0.0.1:6379OBJECT ENCODING user:1hashtable# 超过512个字段切换为hashtable# ZSet使用ziplist的例子127.0.0.1:6379ZADD scores90Tom85Jerry95Alice(integer)3127.0.0.1:6379OBJECT ENCODING scoresziplist# 小ZSet使用ziplist七、listpackziplist的继任者ziplist的连锁更新问题困扰了Redis社区很多年。Redis 7.0终于引入了listpack来替代ziplist彻底解决了这个问题。listpack vs ziplist的关键区别ziplist entry结构 ┌──────────────────┬──────────┬──────────┐ │prev_entry_length │ encoding │ content │ │ (1B 或 5B) │ │ │ └──────────────────┴──────────┴──────────┘ ↑ 记录前一个entry的总长度 ↑ 前一个entry大小变化时当前entry也要变 listpack entry结构 ┌──────────┬──────────┬──────────┐ │ encoding │ content │back_len │ │ │ │ │ └──────────┴──────────┴──────────┘ ↑ 记录自己entry的总长度编码内容back_len本身 ↑ 前一个entry大小变化时当前entry完全不受影响核心改变listpack的每个entry只记录自己的长度通过尾部的back_len字段而不记录前驱的长度。这意味着向后遍历时读取当前entry的back_len就能知道当前entry的总大小从而找到前一个entry的起始位置修改某个entry时只有该entry自身的back_len可能需要更新不会影响其他entry连锁更新被消灭了listpack修改entry_1不会导致连锁反应 ┌──────────┬──────────┬──────────┐ ┌──────────┬──────────┬──────────┐ │ encoding │ content │back_len │←│ encoding │ content │back_len │ │ entry_1 │ (修改) │ 自己长度 │ │ entry_2 │ 不变 │ 不变 │ └──────────┴──────────┴──────────┘ └──────────┴──────────┴──────────┘ entry_1 的长度变了 → 只需要更新 entry_1 自己的 back_len → entry_2 完全不受影响 → 连锁更新不复存在listpack的其他改进改进点ziplistlistpack前驱长度记录记录前驱长度可变不记录前驱长度连锁更新可能发生不会发生最大元素数65535zllen字段限制无限制内存效率极高几乎相同八、ziplist vs linkedlist内存对比让我们用具体数字对比一下ziplist和普通链表的内存效率场景存储5个10字节的字符串 双向链表linkedlist 每个节点 prev指针(8B) next指针(8B) 数据(10B) 26字节 5个节点 26 × 5 130字节 加上链表头节点(24B) 154字节 ziplist 头部 zlbytes(4) zltail(4) zllen(2) 10字节 每个entry ≈ prev_len(1) encoding(1) content(10) 12字节 5个entry 12 × 5 60字节 尾部 zlend(1) 1字节 总计 ≈ 71字节 节省比例(154 - 71) / 154 ≈ 54%ziplist比链表节省了一半以上的内存这就是为什么Redis对ziplist情有独钟。九、实际演示用OBJECT ENCODING观察压缩列表# 观察Hash使用ziplist127.0.0.1:6379HMSET product:1 nameiPhoneprice999brandAppleOK127.0.0.1:6379OBJECT ENCODING product:1ziplist# 3个字段远小于512127.0.0.1:6379MEMORY USAGE product:1(integer)72# 非常紧凑# 观察ZSet使用ziplistRedis 7.0127.0.0.1:6379ZADD rank100Alice90Bob80Charlie(integer)3127.0.0.1:6379OBJECT ENCODING rankziplist# 3个元素小于128# 当元素增多或值变大时切换127.0.0.1:6379ZADD rank70Dave(integer)1# 如果是Redis 7.0编码显示可能是 listpack踩坑提示从Redis 7.0开始ziplist被listpack替代。如果你用OBJECT ENCODING看到的是listpack而不是ziplist不要慌——这是正常的版本演进。十、总结ziplist是Redis对节省内存这个目标最极致的追求方面评价内存效率极高消除了所有指针开销查找性能O(N) 遍历但N通常很小插入/删除平均O(N)最坏O(N²)连锁更新实现复杂度高特别是连锁更新的处理适用场景小数据量、内存敏感的场景虽然ziplist因为连锁更新的隐患被listpack替代但它代表了Redis不惜一切代价省内存的设计哲学。理解ziplist的设计能帮助我们更好地理解Redis的内存优化思路。下一篇我们将切换到Redis对象编码的话题看看最常见的String对象是如何根据数据大小在不同编码之间切换的——传说中的44字节魔数到底是什么上一篇【第17篇】整数集合——Redis集合的省内存利器下一篇【第19篇】String对象的七十二变——int/embstr/raw编码的切换逻辑