Listpack and quicklist

The compact encodings used for small lists, sets, hashes, sorted sets, and stream nodes.

Source layout

File	Role
src/listpack.c	Listpack: a length-prefixed packed byte array of typed entries. ~122 KB.
src/listpack.h	Listpack API.
src/listpack_malloc.h	Allocation hooks, overridable for tests and modules.
src/quicklist.c	Quicklist: a doubly-linked list of listpacks with optional LZF compression of middle nodes. ~145 KB.
src/quicklist.h	Quicklist API.
src/ziplist.c, src/ziplist.h	Legacy ziplist encoding. Not created for new objects since Redis 7.0 but kept around for old RDB compatibility.
src/zipmap.c, src/zipmap.h	Even older small-hash encoding. Kept only for RDB compatibility.

Listpack

A listpack is a contiguous byte buffer that stores a sequence of typed entries with O(1) insertion at either end and O(N) lookup by index. Each entry has:

• An encoding byte (or two) that identifies the type and length.
• The payload (integer or string).
• A back-pointer length so iteration can go in either direction.

Header layout:

+---------+---------+---------+--------------------+---+
| total   | num     | entries (variable-encoded)   |\xFF|
| bytes   | entries |                              |    |
+---------+---------+---------+--------------------+---+
   4 B       2 B                                     EOF

The \xFF byte at the end makes truncation detectable.

Why listpack and not the older ziplist?

• Ziplist used a previous-entry-length field that updated on insertion, causing cascading reallocations in pathological cases.
• Listpack uses a back-jump length (a constant per-entry overhead) instead, removing the cascade.

API highlights

unsigned char *lpNew(size_t capacity);
unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, unsigned char *p, int where, unsigned char **newp);
unsigned char *lpAppend(unsigned char *lp, unsigned char *ele, uint32_t size);
unsigned char *lpPrepend(unsigned char *lp, unsigned char *ele, uint32_t size);
unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp);
unsigned char *lpFirst(unsigned char *lp);
unsigned char *lpLast(unsigned char *lp);
unsigned char *lpNext(unsigned char *lp, unsigned char *p);
unsigned char *lpPrev(unsigned char *lp, unsigned char *p);
unsigned long lpLength(unsigned char *lp);
int64_t lpGetInteger(unsigned char *p);
unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf);

Listpacks store integers in 7/13/16/24/32/64-bit packed form (depending on magnitude) and strings with a length-byte plus payload. For very small integers the entire entry fits in one byte.

Listpack-EX and listpack-HFE

Two variants used for hashes with field TTLs:

• OBJ_ENCODING_LISTPACK_EX — fields and values interleaved, with a TTL slot inserted after each value.
• OBJ_ENCODING_LISTPACK_HFE — the "hash-field-expiration" variant.

The TTL slot uses a special encoding so it can be 0 (no TTL) without ambiguity. See src/t_hash.c for the read/write helpers.

Quicklist

A quicklist is a doubly-linked list of listpack nodes. The list as a whole supports O(1) head/tail push/pop; iteration jumps from listpack to listpack via the linked-list pointers.

graph LR
    Head[head] -->|next| N1[Node 1<br/>listpack 8 KiB]
    N1 -->|next| N2[Node 2<br/>compressed listpack]
    N2 -->|next| N3[Node 3<br/>compressed listpack]
    N3 -->|next| N4[Node 4<br/>listpack 8 KiB]
    N4 -->|next| Tail[tail]
    Tail -.prev.-> N4
    N4 -.prev.-> N3
    N3 -.prev.-> N2
    N2 -.prev.-> N1
    N1 -.prev.-> Head

Each node has:

• A pointer to its listpack (or to an LZF-compressed buffer for non-edge nodes).
• The listpack's byte size and entry count.
• The compression flag (encoding == QUICKLIST_NODE_ENCODING_LZF).

The list-max-listpack-size config controls per-node size:

• Negative values (e.g. -2) mean "max bytes" — -1=4 KiB, -2=8 KiB, -3=16 KiB, -4=32 KiB, -5=64 KiB.
• Positive values mean "max entries per node".

list-compress-depth N keeps the first and last N nodes uncompressed; everything in the middle is LZF-compressed. Reads/writes that touch a compressed node decompress it temporarily.

API highlights

quicklist *quicklistCreate(void);
void quicklistPushHead(quicklist *ql, void *value, size_t size);
void quicklistPushTail(quicklist *ql, void *value, size_t size);
int  quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry, void *data, size_t size);
int  quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
int  quicklistPopCustom(quicklist *ql, int where, ...);

quicklistIter *quicklistGetIterator(const quicklist *ql, int direction);
int   quicklistNext(quicklistIter *iter, quicklistEntry *entry);
unsigned long quicklistCount(const quicklist *ql);

Quicklists are the only encoding for large lists. Every list mutation in src/t_list.c ultimately calls into quicklist.

Embedded tests

Both have substantial tests under #ifdef REDIS_TEST. Run with ./redis-server test listpack and ./redis-server test quicklist.

Where to start modifying

• Add a listpack entry encoding — extend the encoding byte parser in src/listpack.c. Bump RDB compatibility checks.
• Tune compression depth defaults — list-compress-depth in src/config.c.
• Improve listpack-with-TTL — src/listpack.c's lpInsertEx family + src/t_hash.c's field-TTL paths.

Related pages

• robj — the value wrapper that holds the listpack/quicklist pointer.
• Data types — which types use which encoding.