Redis Internal Data Structures: Ziplist, Skiplist, Intset, Quicklist, Zipmap, and Stream

In the previous article we introduced the three low‑level data structures of Redis. This article continues the series by describing the remaining internal structures and explaining how they are implemented.

Ziplist

The ziplist is a specially encoded doubly linked list designed for high memory efficiency. It stores both strings and integers, encoding integers as native binary values. Push and pop operations on either side run in O(1) time, but each operation requires a memory reallocation, so the actual cost depends on the total size of the ziplist.

The ziplist layout (as shown in the source comments) is:

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

It is represented simply as an unsigned char * pointer. The creation API illustrates this:

// 创建一个新的压缩列表
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;
}

The header fields are:

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

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

zllen – number of entries (uint16_t, capped at 65535).

entry – the actual data nodes.

zlend – a constant 255 marking the end.

Each entry consists of three parts:

<prevlen> <encoding> <entry‑data>

prevlen stores the length of the previous entry (1 or 5 bytes). encoding encodes the type (string or integer) and length. When the encoding itself contains the value (e.g., small integers), the format reduces to <prevlen> <encoding> .

Chain Update

If a newly inserted entry changes the size of prevlen from 1 byte to 5 bytes, a cascade update may occur, leading to O(n²) complexity. In practice this situation is rare because it requires many consecutive entries whose lengths lie between 250 and 253 bytes.

Use Cases

Ziplist is used as the underlying representation for hash objects with few fields and short strings or small integers. Prior to Redis 3.2 it also backed list objects, but was replaced by quicklist.

Skiplist

A skiplist is an ordered data structure that maintains multiple forward pointers per node to achieve fast search. It is simpler to implement than balanced trees and offers comparable performance for most workloads.

// 跳跃表节点实现
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

Skiplist nodes are ordered by score (and by ele for equal scores). Insertion chooses a random level (1‑32) based on a probability factor (commonly p = 1/4).

Quicklist

Quicklist, introduced in Redis 3.2, combines a doubly linked list of ziplist “chunks”. Each quicklist node stores a ziplist (or a compressed LZF version) and metadata:

// 快表节点
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;               // pointer to ziplist or compressed data
    unsigned int sz;                // size of the ziplist (uncompressed)
    unsigned int count : 16;        // number of entries in the 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;        // future use
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz;                // LZF size in bytes
    char compressed[];              // compressed ziplist bytes
} quicklistLZF;

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

Quicklist reduces memory fragmentation compared with a plain linked list while keeping O(1) access to head/tail. The list‑max‑ziplist‑size configuration controls the maximum number of entries per ziplist (positive values) or the maximum byte size (negative values). The list‑compress‑depth parameter determines how many nodes at each end remain uncompressed; middle nodes are compressed with LZF.

Intset

Intset stores a set of unique integers in sorted order. Its layout is:

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 array (size depends on encoding)
} intset;

When an element of a larger integer type is added, the intset is upgraded to the larger encoding, reallocating memory and preserving order. Downgrades are not performed because they would be costly and rarely beneficial.

Zipmap

Zipmap is a compact string‑based map used for very small hash objects (pre‑Redis 2.6). Its structure is:

/* Create a new empty zipmap. */
unsigned char *zipmapNew(void) {
    unsigned char *zm = zmalloc(2);
    zm[0] = 0;            /* Length */
    zm[1] = ZIPMAP_END;   /* End marker */
    return zm;
}

A key‑value pair is stored as:

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

Fields:

zmlen – number of entries (direct if < 254, otherwise requires traversal).

len – length of key or value (1 or 5 bytes).

free – unused bytes in a value slot, used for in‑place updates.

Zipmap was replaced by ziplist in later Redis versions.

Stream

Redis 5.0 introduced the stream data type, implemented as a radix tree ( rax ) of listpack entries. The core structures are:

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

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

Each node in the radix tree is defined as:

typedef struct raxNode {
    uint32_t iskey:1;
    uint32_t isnull:1;
    uint32_t iscompr:1;
    uint32_t size:29;
    unsigned char data[];
} raxNode;

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

Stream entries are stored in listpack objects, a compact serialization format similar to zipmap. A newly created listpack looks like:

unsigned char *lpNew(void) {
    unsigned char *lp = lp_malloc(LP_HDR_SIZE+1);
    if (lp == NULL) return NULL;
    lpSetTotalBytes(lp,LP_HDR_SIZE+1);
    lpSetNumElements(lp,0);
    lp[LP_HDR_SIZE] = LP_EOF;
    return lp;
}

When adding a message, Redis finds the appropriate radix‑tree node, checks whether the current listpack can accommodate the new fields, and either appends to it or creates a new listpack. The listpack header encodes the number of fields, deleted entries, and the actual field/value pairs.

Conclusion

The article demonstrates how Redis meticulously designs each low‑level data structure to maximize memory efficiency and operation speed. By carefully encoding lengths, using variable‑size fields, and combining structures (e.g., quicklist = linked list + ziplist), Redis achieves a balance between low memory footprint and high performance, which is crucial for an in‑memory, single‑threaded database.