Why Is Redis So Fast? Unveiling Its Core Data Structures

Besides being an in‑memory database where all operations happen in RAM, Redis’s speed largely comes from the data structures it uses to store and manipulate data.

In this article we dive into the Redis data structures that are frequently asked about in interviews.

Redis data structures do not refer to the high‑level types String, List, Hash, Set, and Zset; those are the data types of values stored in key‑value pairs, whose underlying implementations rely on lower‑level data structures.

I have drawn a diagram showing the correspondence between Redis object types (the "Redis objects") and their underlying data structures; the left side reflects Redis 3.0 (as described in the book Redis Design and Implementation ), while the right side shows the latest code on GitHub.

The underlying data structures have changed across versions. For example:

In Redis 3.0 the List object is implemented by a doubly‑linked list or a ziplist; from version 3.2 onward it uses a quicklist.

In the newest (unreleased) Redis code the ziplist has been replaced by a listpack.

There are nine core data structures: SDS, doubly‑linked list, ziplist, hash table, skip list, integer set, quicklist, and listpack.

Let’s start with the key‑value implementation.

How Does a Key‑Value Database Work?

In Redis a key is always a string object, while the value can be a string object or a collection object such as List, Hash, Set, or Zset.

Example commands for adding key‑value pairs:

> SET name "xiaolincoding"
OK

> HSET person name "xiaolincoding" age 18
0

> RPUSH stu "xiaolin" "xiaomei"
(integer) 4

These commands illustrate:

The first command creates a string key because the value is a string object.

The second command creates a hash key because the value is a hash object containing two fields.

The third command creates a list key because the value is a list object with two elements.

Redis stores all key‑value pairs in a hash table, giving O(1) lookup time. Each hash bucket holds a pointer (dictEntry*) to the actual key‑value data. The dictEntry stores void *key and void *value pointers, so the value can point to any object type.

The following diagram shows the structures involved in storing a key‑value pair:

Key structures include:

redisDb : the database structure, containing a pointer to a dict.

dict : contains two hash tables (ht[0] and ht[1]) used during rehashing.

dictht : the hash table itself, holding an array of pointers to dictEntry nodes.

dictEntry : each node stores void *key and void *value pointers; the value can point to a string object or a collection object.

redisObject : every object in Redis is represented by this structure, which includes type (String, List, Hash, Set, Zset), encoding (the underlying data structure), and ptr (pointer to the actual structure).

Now let’s explore each underlying data structure.

SDS (Simple Dynamic String)

Strings are heavily used in Redis; keys are strings and values are often strings as well. Redis does not use raw C char* arrays; instead it defines its own SDS structure.

C String Drawbacks

C strings are null‑terminated character arrays. Functions like strlen must scan the array until they encounter \0, giving O(N) time complexity. The null terminator also prevents storing binary data that contains \0, and standard string functions are unsafe because they assume the destination buffer is large enough, leading to buffer overflows.

These drawbacks motivate the design of SDS.

SDS Design

The Redis 5.0 SDS layout (simplified) is:

struct sdshdr {
    unsigned int len;   // length of the string
    unsigned int alloc; // total allocated space
    unsigned char flags; // type flags
    char buf[];          // actual data (can hold binary)
}

Key fields:

len : stores the string length, allowing O(1) length retrieval.

alloc : total allocated space; alloc - len tells how much free space remains, enabling automatic expansion when needed and preventing buffer overflows.

flags : indicates which of the five SDS header types (sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64) is used.

buf : the character array that can store text or binary data.

Because len is stored, strlen ‑like operations become O(1). The structure is binary‑safe (no reliance on \0) and avoids overflow by checking available space before modifications.

Memory‑Saving Header Types

Each header type uses different integer sizes for len and alloc (uint8, uint16, uint32, uint64), allowing small strings to use minimal overhead.

Compiler Packing

Redis uses __attribute__((packed)) to prevent padding, ensuring the structure occupies exactly the needed bytes.

Linked List

Redis List objects are implemented with a custom doubly‑linked list.

Node Structure

typedef struct listNode {
    struct listNode *prev; // previous node
    struct listNode *next; // next node
    void *value;           // stored value
} listNode;

List Structure

typedef struct list {
    listNode *head;               // first node
    listNode *tail;               // last node
    void *(*dup)(void *ptr);      // optional duplicate function
    void (*free)(void *ptr);      // optional free function
    int (*match)(void *ptr, void *key); // optional compare function
    unsigned long len;            // number of nodes
} list;

Advantages:

Prev/next pointers give O(1) access to neighboring nodes.

Head/tail pointers give O(1) access to list ends.

Length is stored for O(1) size queries.

Void* values allow storing any object type.

Drawbacks:

Nodes are not stored contiguously, hurting CPU cache locality.

Each node incurs memory overhead.

Because of these drawbacks, Redis 3.0 uses a ziplist for small lists.

Ziplist (Compressed List)

A ziplist is a compact, contiguous memory block that stores a sequence of entries. It begins with three header fields:

zlbytes : total byte size of the ziplist.

zltail : offset of the tail entry.

zllen : number of entries.

Each entry consists of:

prevlen : length of the previous entry (1 byte if < 254, otherwise 5 bytes).

encoding : type and length of the current entry (different sizes for integers vs. strings).

data : the actual payload.

Accessing the first or last entry is O(1) using the header fields, but locating arbitrary entries requires linear scanning (O(N)).

When inserting or updating, if the new entry does not fit, the ziplist may need to reallocate memory. If the new entry is large, the prevlen field of the following entry may need to expand from 1 to 5 bytes, which can trigger a cascade of updates ("chain reaction") across subsequent entries, degrading performance.

Because of these issues, ziplist is only used when the number of elements is small and the elements themselves are short.

Hash Table

Redis uses hash tables to store key‑value pairs with O(1) average lookup.

Hash table structure ( dictht) contains: dictEntry **table: array of bucket pointers. unsigned long size: number of buckets. unsigned long sizemask: mask for computing bucket index. unsigned long used: number of stored entries.

Each bucket points to a linked list of dictEntry nodes to resolve collisions (chaining).

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // next entry in the same bucket
} dictEntry;

When the load factor (used/size) grows, Redis performs rehashing. It maintains two hash tables (ht[0] and ht[1]) and migrates entries incrementally (gradual rehash) to avoid long pauses.

Rehashing

Rehashing steps:

Allocate a new, larger hash table (usually double the size).

Gradually move entries from the old table to the new one during normal operations.

Once all entries are moved, free the old table and make the new table the primary one.

Rehash is triggered when the load factor ≥ 1 (and no RDB/AOF background save is running) or when the load factor ≥ 5 regardless of background saves.

Integer Set (intset)

Used as the underlying representation for small Set objects that contain only integers. The structure is:

typedef struct intset {
    uint32_t encoding; // 16, 32 or 64 bits per element
    uint32_t length;  // number of elements
    int8_t contents[]; // actual integer array (type depends on encoding)
} intset;

When a new element larger than the current encoding is added, the intset is upgraded (e.g., from 16‑bit to 32‑bit) by reallocating the array and converting existing elements, preserving order. Downgrading never occurs.

Skip List

Used for Zset objects, providing O(log N) range queries while a parallel hash table gives O(1) exact lookups.

typedef struct zskiplistNode {
    sds ele;               // element value
    double score;          // score for ordering
    struct zskiplistNode *backward; // reverse pointer
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer for this level
        unsigned long span;             // number of nodes skipped
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length; // number of elements
    int level;             // current max level
} zskiplist;

Search starts from the highest level of the header and moves forward while the next node’s score is less than the target or, if scores are equal, the element string is lexicographically smaller. When forward pointers become NULL or the condition fails, the algorithm drops one level and continues.

Node levels are chosen randomly: each additional level is added with probability 0.25, up to a maximum of 64, yielding an average 2:1 ratio between consecutive levels and O(log N) search complexity.

Quicklist

Introduced in Redis 3.2, quicklist replaces the plain doubly‑linked list for List objects. It combines a doubly‑linked list of nodes, each node containing a ziplist (or later a listpack). This limits the size of any single ziplist, reducing the impact of chain‑reaction updates.

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;   // pointer to the ziplist (or listpack)
    unsigned int sz;    // ziplist byte size
    unsigned int count:16; // number of entries in the ziplist
    // ... other flags omitted
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count; // total number of entries across all nodes
    unsigned long len;   // number of quicklist nodes
    // ... other fields omitted
} quicklist;

When inserting, Redis checks whether the target node’s ziplist can accommodate the new element; if not, a new node is created.

Listpack

Redis 5.0 introduced listpack to replace ziplist entirely. Like ziplist, it stores data in a contiguous memory block, but each entry records only its own length (no prevlen), eliminating the chain‑reaction problem.

Listpack header stores total byte size and element count, followed by a series of entries. Each entry contains an encoding byte (or bytes) that determines how the following data is interpreted, the data itself, and the total len of the entry.

Because entries do not depend on the size of the previous entry, adding or enlarging an entry never forces updates to subsequent entries, providing stable performance.

Summary

This article has detailed the nine core data structures used inside Redis—SDS, doubly‑linked list, ziplist, listpack, quicklist, integer set, hash table, skip list, and the overall object layout—explaining their designs, advantages, and the evolution that mitigates earlier shortcomings such as O(N) operations, memory waste, and chain‑reaction updates.