Inside Redis: Ziplist, Skiplist, Quicklist & Stream – Memory & Performance Secrets

Ziplist

The ziplist is a specially encoded doubly linked list designed for extreme memory efficiency. It stores strings and integers, encoding integers as native values. Push and pop operations run in O(1) time, but each modification triggers a memory reallocation, making the actual cost proportional to the total size of the ziplist.

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

Creation API shows that a ziplist is just an unsigned char * buffer:

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

Key fields:

zlbytes – total bytes used by the ziplist (uint32_t).

zltail – offset of the tail entry from the start (uint32_t).

zllen – number of entries; if it exceeds 65534 it is capped at 65535 and must be counted by traversal.

entry – each node stores <prevlen> <encoding> <entry‑data>. The prevlen field is 1 or 5 bytes depending on the previous entry size, and encoding encodes type and length.

Skiplist

A skiplist provides an ordered data structure with multiple forward pointers per node, offering O(log n) search while being simpler to implement than balanced trees. Redis uses it for sorted sets.

typedef struct zskiplistNode {
    sds ele;                     // member string
    double score;               // sorting score
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;        // number of elements (excluding header)
    int level;                   // max level of any node
} zskiplist;

Nodes are allocated with a random level (1‑32) based on a probability p (default 1/4). The structure enables O(1) access to head/tail and O(log n) range queries.

Intset

Intset stores a set of unique integers in a compact array. It adapts its encoding (int16, int32, int64) based on the largest element, allowing efficient memory use for small sets.

typedef struct intset {
    uint32_t encoding;   // INTSET_ENC_INT16 / INTSET_ENC_INT32 / INTSET_ENC_INT64
    uint32_t length;     // number of elements
    int8_t contents[];   // actual integer values, size depends on encoding
} intset;

When inserting a larger integer, the set is upgraded: allocate a new buffer with the larger encoding, copy existing values, and insert the new element at the appropriate position. Downgrades are not performed because future larger inserts would require another upgrade.

Quicklist

Quicklist replaces the old ziplist‑based list implementation (pre‑3.2) by chaining multiple ziplist nodes. Each node can be stored raw or compressed with LZF, balancing memory usage and modification cost.

typedef struct quicklistNode {
    struct quicklistNode *prev, *next;
    unsigned char *zl;               // pointer to ziplist or compressed data
    unsigned int sz;                  // ziplist size in bytes (original size if compressed)
    unsigned int count : 16;          // number of entries in this ziplist
    unsigned int encoding : 2;        // RAW==1 or LZF==2
    unsigned int container : 2;       // NONE==1 or ZIPLIST==2
    unsigned int recompress : 1;      // was previously compressed?
    unsigned int attempted_compress : 1;
    unsigned int extra : 10;
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head, *tail;
    unsigned long count;              // total entries in all ziplists
    unsigned long len;                // number of quicklist nodes
    int fill : QL_FILL_BITS;          // list‑max‑ziplist‑size value
    unsigned int compress : QL_COMP_BITS; // list‑compress‑depth value
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

Configuration parameters:

list‑max‑ziplist‑size – controls the maximum number of entries (positive) or maximum byte size (negative, –1 to –5) per quicklist node.

list‑compress‑depth – number of nodes at each end that remain uncompressed (0 disables compression).

Zipmap

Zipmap is a compact string‑based map used for very small hash objects (pre‑2.6). It stores key‑value pairs in a contiguous byte array with minimal overhead (as little as three extra bytes per pair).

unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);
    zm[0] = 0;               // length byte
    zm[1] = ZIPMAP_END;      // 255 terminator
    return zm;
}

Encoding of a pair looks like:

<zmlen><len>"foo"<len><free>"bar"...

Fields:

zmlen – number of key/value pairs (direct if < 254, otherwise requires traversal).

len – length of a key or value, stored in 1 or 5 bytes.

free – unused bytes after a value, allowing in‑place updates without immediate reallocation.

Stream

Introduced in Redis 5.0, streams implement a persistent message queue using a radix tree (rax) for indexing and listpack for entry storage.

typedef struct streamID {
    uint64_t ms;   // milliseconds timestamp
    uint64_t seq;  // sequence number
} streamID;

typedef struct stream {
    rax *rax;                 // radix tree of listpacks
    uint64_t length;          // total entries
    streamID last_id;         // last generated ID
    rax *cgroups;             // consumer groups dictionary
} stream;

Each listpack (the actual entry container) follows the format:

+-------+--------+------------+---------+--/--+---------+---------+-+
| count | deleted| num‑fields | field_1 | ... | field_N |0|

Message IDs consist of a 64‑bit timestamp and a 64‑bit sequence, guaranteeing monotonic ordering even if the server clock moves backwards (the last_id is used to adjust).

Overall Insights

Redis’s internal data structures are meticulously crafted to squeeze every byte and minimize operation latency. Ziplist, intset, and zipmap favor memory density for tiny collections, while skiplist and quicklist trade a modest amount of extra memory for faster range queries and reduced reallocations. Configurable thresholds such as list‑max‑ziplist‑size and list‑compress‑depth let developers tune the balance between space and speed for their specific workloads.