Redis压缩列表到底怎么省内存，背后那些设计上的小巧思和实现细节

Redis的压缩列表（ziplist）是一种为节省内存而设计的特殊编码双向链表，它被广泛应用在列表键、哈希键和有序集合键的底层实现中，当这些键包含的元素数量较少或者元素值体积较小时，Redis会自动采用压缩列表来存储，以达到极致省内存的目的。

核心思想：消除元数据开销和紧凑存储

普通链表每个节点除了存储实际数据外,还需要维护前后节点的指针（各占8字节）以及其他一些元信息，对于存储小整数或短字符串来说，这些指针和元数据本身占用的空间可能比数据还大，造成了巨大的浪费。

压缩列表的巧妙之处在于,它完全摒弃了这种传统的链表结构，它不再是一个由指针连接的节点集合，而是将所有数据（包括数据本身和必要的长度信息）一个紧挨着一个地塞进一块连续的内存空间中，你可以把它想象成一个“数据数组”，而不是“指针网络”，这样做最直接的好处就是完全消除了指针带来的内存开销。

具体的设计巧思与实现细节

1. 内存布局：一块连续的内存 压缩列表是一大块连续的内存字节数组，它的整体结构非常简单：

   • 头部信息：开头的几个字节记录了整个压缩列表的总字节数、到尾节点的偏移量（用于反向遍历）以及包含的元素个数，这些信息帮助Redis快速掌握列表的整体情况。
   • 数据实体：紧接着头部，就是一个接一个的列表元素（entry）。
   • 结束标记：最后用一个特殊的字节（0xFF）标示压缩列表的结束。

   这种线性结构本身就比链式结构更节省空间,因为它没有指针的间隙。

2. 灵活的节点编码：因“值”制宜 这是压缩列表省内存的精髓所在，每个节点（entry）的构成不是固定的，而是根据其存储的实际数据内容动态决定如何编码：

   • 对于小整数：如果存储的是一个很小的整数（比如数字5），压缩列表不会傻乎乎地用4字节或8字节的int去存，它会识别出这是一个小整数，然后可能只用1个字节来存储，数字0到12，其值可以直接嵌入到节点的“前一个节点长度”字段中，连实际的数据存储空间都省掉了（引自《Redis设计与实现》）。
   • 对于字符串：每个节点在存储数据之前，会先存储一个“编码”字段，用来说明后面跟着的数据是什么类型、长度是多少，对于短字符串，它会使用1字节的编码来标示长度；对于稍长的字符串，可能会用2字节或5字节的编码，关键是，数据本身存储时，其长度就是字符串的实际长度，没有任何多余填充。

3. “前一个节点长度”的可变字节表示 为了实现从后向前的遍历（双向链表特性），每个节点需要记录前一个节点的长度，但压缩链表在这里又耍了个小花招：这个“前一个节点长度”字段本身占用的字节数也是可变的。

   • 如果前一个节点的长度小于254字节,那么就用1个字节来存储这个长度值。
   • 如果前一个节点的长度大于等于254字节,那就用5个字节来存储（第一个字节固定为0xFE，作为标志，后面4个字节存储实际长度）。 这种设计确保了在绝大多数存储小数据的场景下（这也是压缩列表的适用场景），这个用于维护结构的字段也只需要1字节，进一步压榨了内存空间。

4. 级联更新：为节省空间付出的代价 硬币都有两面性，压缩列表这种高度紧凑和依赖前后关系的设计，也带来了一个潜在的缺点——“级联更新”。 想象一下，在一个所有节点的“前一个节点长度”都是1字节的压缩列表中，如果我们在头部插入了一个较大的新节点，导致紧挨着的第二个节点的“前一个节点长度”从原来的小于254字节变成了大于等于254字节，这第二个节点就需要扩容，将1字节的长度字段扩展为5字节。 这个节点的扩容，意味着它本身的长度也增加了，这又可能导致它后面的第三个节点的“前一个节点长度”字段也需要扩容……如此连锁反应，可能引发一连串的节点空间重分配操作，虽然这种情况在元素较少时影响不大，且发生的概率不高，但它是压缩列表为追求极致空间效率所必须承担的风险。

总结一下

Redis压缩列表的省内存秘诀,归根结底是用计算换空间，它通过：

• 连续内存布局，消灭了指针开销。
• 动态智能编码，根据数据值的大小“量体裁衣”，用小容器装小东西。
• 可变长字段，确保每一个字节都被充分利用。

这些设计上的小巧思,使得它在存储大量小对象时，内存效率远超普通链表或哈希表，正如“级联更新”所揭示的，这种优化并非没有代价，它牺牲了部分修改操作的性能稳定性，Redis聪明地为其设置了配置参数（如hash-max-ziplist-entries, hash-max-ziplist-value），只有当数据规模在阈值以下时，才启用压缩列表，从而在空间和时间之间取得一个最佳的平衡点。