Redis Internals: Data Structures, Skip Lists, Dictionaries, Streams, and Thread Model

This article provides an in‑depth technical overview of Redis internals, covering the implementation of its core data structures, the skip‑list used for sorted sets, integer sets, hash tables, ziplist, listpack, the radix tree (RAX), the stream data type, and the evolution of Redis' threading model.

1. String storage

Redis stores strings using a custom SDS (simple dynamic string) structure to achieve O(1) length calculation, binary safety, and efficient concatenation. The SDS header is defined as:

struct sds{  
    int len; // used length
    int free; // free space
    char buf[]; // actual string data
}

Different SDS header variants (sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64) are selected based on the string length, allowing small strings to avoid excessive overhead.

2. Skip list (used for sorted sets)

The skip list provides O(log N) search, insertion and deletion while keeping memory usage low. Its node structure is:

typedef struct zskiplistNode {  
    sds ele;               // element
    double score;          // sorting score
    struct zskiplistNode *backward; // backward pointer
    struct zskiplistLevel {        // per‑level forward pointer and span
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Key operations such as zslInsert and zslDeleteNode are implemented with careful span updates and level adjustments. The random level generator uses a probability p = 0.25 , giving an expected height of 1/(1‑p) ≈ 1.33 .

3. Integer set (intset)

Intset stores ordered integers in a compact array. Its definition is:

typedef struct intset {  
    uint32_t encoding; // element size (16/32/64 bits)
    uint32_t length;  // number of elements
    int8_t contents[]; // flexible array of integers
} intset;

Search, insertion and deletion are performed with binary search and possible re‑encoding when the required integer size grows.

4. Hash table (dict)

Redis' hash table is similar to Java's HashMap but uses incremental rehashing to avoid long pauses. The core structures are:

typedef struct dictht {  
    dictEntry **table;   // bucket array
    unsigned long size; // total slots (power of two)
    unsigned long sizemask; // size‑1 for fast modulo
    unsigned long used; // number of entries
} dictht;

typedef struct dictEntry {  
    void *key;           // key pointer
    union {              // value union
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // collision chain
} dictEntry;

Incremental rehashing moves entries bucket by bucket, limiting the number of empty bucket visits to n*10 per rehash step.

5. Ziplist (compressed list)

Ziplist stores small strings and integers in a compact byte array. Each entry contains a previous‑entry length, an encoding byte, and the payload. The decoding macros ZIP_DECODE_PREVLEN and ZIP_DECODE_LENGTH illustrate how the format is interpreted.

6. Listpack

Listpack is a newer, more efficient serialization format used by streams. It stores a sequence of elements with a back‑length field that allows reverse traversal. The entry header encodes the type (string or integer) and length.

7. Radix tree (RAX)

RAX is a compact prefix tree used for fast key lookup. Nodes can be compressed (storing a string of characters) or uncompressed (one child per character). The node definition is:

typedef struct raxNode {  
    uint32_t iskey:1;   // does node hold a key?
    uint32_t isnull:1;  // is associated value NULL?
    uint32_t iscompr:1; // compressed node?
    uint32_t size:29;   // length of compressed string or number of children
    unsigned char data[]; // payload (children pointers or string)
} raxNode;

Lookup walks the tree, handling compressed nodes by matching the whole substring, and uncompressed nodes by scanning child characters.

8. Stream data type

Redis streams combine a radix tree for indexing messages and listpacks for storing the actual entries. A stream is defined as:

typedef struct stream {  
    rax *rax;            // key → listpack mapping
    uint64_t length;     // total number of entries
    streamID last_id;    // ID of the last entry
    rax *cgroups;        // consumer groups
} stream;

Adding a message uses streamAppendItem , which creates a new listpack entry and updates the radix tree. Consumer groups and consumers are stored as separate RAX trees, and pending entries are tracked with per‑consumer PEL (pending entry list) structures.

9. Thread model evolution

Redis 3.0 used a single‑threaded event loop (file event handler). Starting with Redis 4.0, background threads were introduced for auxiliary tasks such as connection cleanup and incremental rehashing. Redis 6.0 added true multithreading for I/O, allowing read/write operations to be processed in parallel while the main thread continues to execute commands.

Overall, the article demonstrates how Redis achieves high performance through carefully designed data structures, memory‑efficient encodings, and a progressive threading model.