Understanding Redis Ziplist and Listpack: Memory‑Efficient List Implementations

What Is a Compressed List?

A compressed list in Redis is a tightly packed list used as the underlying data structure for List. Redis supports two encodings: ZIPLIST and LISTPACK . LISTPACK was introduced in Redis 4.0 and fully replaced ZIPLIST in Redis 7.0.

Why Use a Compressed List?

The compressed list provides a compact storage format for List, reducing memory consumption while still supporting list operations.

ZIPLIST Overall Structure

Although LISTPACK exists, ZIPLIST is still frequently discussed in interviews. The Redis source code documents the ZIPLIST layout as follows:

* The general layout of the ziplist is as follows:
*
* <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

Example of a ZIPLIST with three nodes:

The fields mean:

zlbytes : total number of bytes occupied by the ZIPLIST, including the zlbytes field itself.

zltail : byte offset from the start to the last entry, enabling fast tail access.

zllen : number of data entries (3 in the example).

entry1~entry3 : the actual data entries.

zlend : a special entry marking the end of the ZIPLIST.

ZIPLIST Entry Structure

Each entry consists of three parts:

<prevlen> <encoding> <entry-data>

Field explanations:

prevlen : length of the previous entry, allowing backward traversal.

If the previous entry is shorter than 254 bytes, prevlen uses 1 byte; otherwise it uses 5 bytes.

encoding : type and length information of the entry data.

entry-data : the actual stored value.

Encoding Details

The encoding field is an integer whose binary representation encodes both the data type and its length. For strings, the first bits indicate the type and the remaining bits indicate length; for integers, the encoding alone determines the size (e.g., int16, int32, int64).

Typical string encodings: 00pppppp – 1 byte, string length ≤ 63. 01pppppp|qqqqqqqq – 2 bytes, length ≤ 16383. 10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt – 5 bytes, length ≤ 2³²‑1.

Integer encodings: 11000000 – 2‑byte int16. 11010000 – 4‑byte int32. 11111110 – 8‑byte int64.

ZIPLIST Data Queries

Query Total Number of Entries

The header field zllen allows O(1) retrieval of the entry count. However, because zllen is a 2‑byte field, if the list exceeds 65 535 entries the field overflows to 0, and the true count must be obtained by traversal.

Query a Specific Entry

Finding a particular entry requires scanning the list, which has an average time complexity of O(N).

ZIPLIST Updates

Adding or removing entries is supported at both head and tail, but the average complexity is O(N) because inserting an entry may shift subsequent entries. In worst‑case scenarios, chain updates can lead to O(N²) complexity when multiple entries need their prevlen fields expanded.

In practice, chain updates affecting more than two nodes are rare, so the average update cost remains O(N), but the potential for unstable performance is a notable drawback of ZIPLIST.

LISTPACK Optimizations

Root Cause of Chain Updates

ZIPLIST’s need to store prevlen for backward traversal is the primary source of chain‑update overhead.

Design of LISTPACK

LISTPACK eliminates

prevlen> and instead stores the total length of the preceding element, enabling backward navigation without explicit length fields. Each LISTPACK entry is defined as:</p><pre><code><encoding-type><element-data><element-tot-len>

encoding-type indicates the data type, element-data holds the actual value, and element-tot-len records the length of the entire entry except for itself. The most‑significant bit of each byte in element-tot-len signals whether the length continues (1) or ends (0); the remaining 7 bits contribute to the size value. Example: if the previous entry’s element-tot-len is 00000001 10000100 , the two bytes represent a total size of 132 bytes (binary 0000001 0000100 ).

Summary

The compressed list is a memory‑saving data structure in Redis that tightly packs list elements. Understanding ZIPLIST’s layout, encoding, query, and update characteristics is essential, while LISTPACK addresses ZIPLIST’s chain‑update performance issue, offering a more stable and efficient implementation.