Unlocking Redis Speed: A Deep Dive into Its Core Data Structures

Why Redis Is So Fast

Beyond being an in‑memory database, Redis achieves high performance by implementing highly optimized data structures for every key‑value operation, allowing constant‑time (O(1)) inserts, deletes, and lookups.

What "Redis Data Structures" Actually Mean

The term refers to the underlying C structs that implement the logical types (String, List, Hash, Set, Zset), not the abstract data types themselves. The article compares the old Redis 3.0 implementation (as described in "Redis Design and Implementation") with the latest GitHub source, highlighting the evolution of these structures.

Key‑Value Storage Overview

In Redis, a key is always a String object . The value can be a String, List, Hash, Set, or Zset object. Example commands:

SET name "xiaolincoding"
HSET person name "xiaolincoding" age 18
RPUSH stu "xiaolin" "xiaomei"

These commands illustrate that:

The first command creates a string key whose value is a string object.

The second creates a hash key whose value is a hash object containing two fields.

The third creates a list key whose value is a list object with two elements.

All key‑value pairs are stored in a global hash table ( dict) where each entry ( dictEntry) holds void *key and void *value pointers.

Redis Object Layout

Every Redis object is represented by redisObject:

type : identifies the logical type (String, List, …).

encoding : indicates which low‑level data structure backs the object.

ptr : points to the actual structure (e.g., an SDS, a list, a hash table).

SDS – Simple Dynamic String

Redis replaces the C char * string with SDS to solve three major C‑string problems:

O(N) length calculation → O(1) because SDS stores len.

Zero‑termination prevents binary data → SDS stores length, allowing embedded \0 bytes.

Unsafe standard functions cause buffer overflows → SDS tracks allocated space ( alloc) and checks it before modifications.

The SDS struct (Redis 5.0) looks like:

typedef struct sdshdr {
    unsigned int len;   // used length
    unsigned int alloc; // total allocated size
    unsigned char flags; // type of SDS (5 variants)
    char buf[];         // actual bytes (binary‑safe)
} sdshdr;

Because len is stored, strlen ‑like operations become O(1). The alloc‑len check prevents overflow, and the structure can hold arbitrary binary data.

Linked List Implementation

Redis implements its List object with a custom doubly linked list:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
} list;

Advantages:

O(1) access to head, tail, and length.

Node values can be any object via void * and custom dup/free/match callbacks.

Drawbacks:

Non‑contiguous memory hurts CPU cache locality.

Each node incurs extra allocation overhead.

Ziplist – Compact Sequential List

Ziplist stores elements in a single contiguous memory block, making it cache‑friendly. Header fields: zlbytes: total bytes. zltail: offset of the tail entry. zllen: number of entries. zlend: 0xFF terminator.

Each entry contains prevlen, encoding, and data. The prevlen field varies in size (1 or 5 bytes) depending on the previous entry’s length, which leads to the "chain update" problem when inserting a large entry that forces earlier entries to expand their prevlen fields.

Hash Table

Redis uses a hash table ( dictht) to store all key‑value pairs. The table is an array of pointers to dictEntry buckets. Each dictEntry holds void *key, a union for the value, and a next pointer for chaining.

Collision resolution is done via chaining. When the load factor (used/size) reaches 1 (or 5 in extreme cases), Redis triggers a rehash.

Rehash Mechanism

Redis maintains two hash tables ( ht[2]) during rehash. The process:

Allocate a new table roughly twice the size.

Gradually move entries from the old table to the new one.

When migration finishes, the old table is freed and the new table becomes ht[0].

To avoid long pauses, Redis performs "progressive rehash": each regular operation (insert, delete, lookup) also migrates a small batch of entries, spreading the cost over many client requests.

Intset – Integer Set

Intset stores only integer values in a contiguous array. The encoding field determines whether the array holds int16_t, int32_t, or int64_t. When a larger integer is added, the set upgrades its encoding (e.g., from 16‑bit to 32‑bit) by reallocating the array and preserving order. Downgrades never occur, ensuring memory is never reclaimed after an upgrade.

Skiplist – Used by Zset

Zset objects combine a hash table (for O(1) score lookup) and a skiplist (for O(log N) range queries). A skiplist node contains:

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

The skiplist itself holds pointers to the header and tail, the total length, and the current maximum level.

Node levels are chosen randomly: a new level is added with probability 0.25 until a random number exceeds that threshold, capping at 64 levels. This randomization yields an average 2:1 ratio of nodes between adjacent levels, giving O(log N) search complexity.

Quicklist – List + Ziplist Hybrid

Introduced in Redis 3.2, quicklist replaces the pure doubly linked list with a list of ziplist nodes. Each quicklistNode contains pointers to the previous and next node and a pointer to an embedded ziplist ( zl) plus its size and element count. By limiting the size or element count of each ziplist, quicklist mitigates the chain‑update issue of a single massive ziplist while still benefiting from its compact memory layout.

Listpack – Ziplist Replacement

Redis 5.0 introduced listpack to finally replace ziplist. Listpack stores entries in a contiguous block with three fields per entry: encoding, data, and len. Crucially, it no longer stores the previous entry’s length, eliminating the chain‑update problem entirely.

The header records total bytes ( bytes) and number of entries ( count), followed by a 0xFF terminator.

Conclusion

The article walks through each of Redis’s nine core data structures, explains why they were introduced, how they improve performance or memory usage, and shows the evolution from older implementations (linked list, ziplist) to newer, more efficient ones (quicklist, listpack). Understanding these internals helps developers reason about Redis’s speed, memory footprint, and the trade‑offs involved in choosing data types for specific workloads.

References

"Redis Design and Implementation" (the classic book)

"Redis Source Code Analysis and Practice"

Redis GitHub repository (latest master branch)