Why Is Redis So Fast? A Deep Dive into Its Core Data Structures and Optimizations

Redis Performance Overview

Redis is a high‑performance key‑value cache server that surpasses Memcached by supporting a richer set of data types. The most common interview answer cites two reasons: data resides entirely in memory and Redis runs on a single thread, eliminating disk I/O and context‑switch overhead.

Beyond these basics, Redis achieves speed through several deeper mechanisms:

Pure memory operations

Single‑threaded execution

Highly efficient internal data structures

Smart data encoding

Additional low‑level optimizations

Common Redis Data Types

String : cache, counters, distributed locks

List : linked list, queue, timeline feeds

Hash : user profiles, hash tables

Set : deduplication, likes, mutual friends

Zset : ranking lists, score‑based leaderboards

1. Simple Dynamic String (SDS)

Redis implements strings with a custom structure called SDS instead of plain C strings. The structure stores the length, free space, and the actual buffer.

struct sdshdr {
    int len;
    int free;
    char buf[];
}

Fields:

len : length of used buffer space

free : length of unused space

buf[] : actual content

2. SDS vs. C Strings

O(1) length access : SDS stores length, so retrieving it is constant‑time, unlike C strings which require O(n) traversal.

Buffer‑overflow protection : SDS checks available space before modification and reallocates if needed, preventing accidental overwrites.

Fewer reallocations : SDS uses pre‑allocation and lazy free strategies to reduce the number of memory reallocations during frequent updates.

Binary safety : SDS can store arbitrary binary data because the length field, not a terminating '\0', defines the end of the string.

3. Dictionary Implementation

Redis dictionaries are similar to Java’s HashMap but include two hash tables to support incremental rehashing.

typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2];
    int trehashidx;
}

typedef struct dictht{
    dectEntrt **table;   // hash table array
    unsigned long size;  // table size
    unsigned long sizemask;
    unsigned long used; // number of entries
}

Key fields ht[0] and ht[1] hold the current and next tables; trehashidx tracks the rehash progress.

Rehash Process

Allocate space for ht[1] (size = next power‑of‑two greater than ht[0].used*2 for expansion, or greater than ht[0].used for contraction).

Move entries from ht[0] to ht[1].

When all entries are migrated, free ht[0], promote ht[1] to ht[0], and allocate a fresh ht[1] for the next rehash.

Progressive Rehash

During normal operations, Redis increments trehashidx and rehashes a small batch of buckets each time, ensuring the operation does not block the server.

4. Skip‑List (used by Zset)

Zsets store ordered elements using a skip‑list (zkiplist) combined with a dictionary for O(1) member lookup and O(log N) range queries.

typedef struct zskiplistNode {
    robj *obj;          // member object
    double score;       // score
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer
        unsigned int span;              // distance to next node
    } level[];
} zskiplistNode;

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

typedef struct zset {
    zskiplist *zsl;
    dict *dict;
} zset;

The skip‑list provides fast forward traversal, backward pointers for occasional back‑steps, and a span field indicating the distance between nodes.

5. Zip‑List (Compressed List)

Zip‑list is a compact sequential structure used for small lists, hashes, and sorted sets when element count and size stay below configurable thresholds.

list-max-ziplist-entries 512
list-max-ziplist-value 64

When thresholds are exceeded, Redis converts the zip‑list to a regular linked list or hash table.

6. Object Encoding Conversions

Redis objects ( redisObject) contain a type, an encoding, and a pointer to the underlying data structure.

typedef struct redisObject{
    unsigned type:4;      // object type (string, list, hash, set, zset)
    unsigned encoding:4;  // encoding (int, raw, ziplist, linkedlist, intset, hashtable, zskiplist)
    void *ptr;            // pointer to actual data
} robj;

String Encoding

127.0.0.1:6379> set str 1
OK
127.0.0.1:6379> object encoding str
"int"

127.0.0.1:6379> set str 1a
OK
127.0.0.1:6379> object encoding str
"raw"

List Encoding

List uses ziplist when all elements are < 64 bytes and the list contains fewer than 512 items; otherwise it becomes a linkedlist. The limits are configurable via list-max-ziplist-entries and list-max-ziplist-value.

Set Encoding

Set uses intset when all members are integers and the set size is < 512; otherwise it switches to a hashtable. Configurable limit: set-max-intset-entries 512.

Hash Encoding

Hash uses ziplist when both field names and values are < 64 bytes and the hash contains fewer than 512 entries; otherwise it becomes a hashtable. Configurable limits: hash-max-ziplist-entries 512 and hash-max-ziplist-value 64.

Zset Encoding

Zset uses ziplist when the number of elements is < 128 and each member is < 64 bytes; otherwise it uses a zkiplist. Configurable limits: zset-max-ziplist-entries 128 and zset-max-ziplist-value 64.

7. Expiration Deletion Strategies

Redis provides three ways to delete expired keys:

Timer‑based deletion : a timer fires exactly when a key’s TTL expires and removes the key immediately.

Lazy deletion : the key is removed only when it is accessed after expiration.

Periodic deletion : Redis scans the expiration dictionary every so often, sampling a small number of keys (default 20) and deleting those that are expired. The scan runs at most 25 ms per cycle and occurs ten times per second.

These strategies balance CPU usage and memory reclamation, ensuring that expiration handling does not become a performance bottleneck.

Conclusion

Redis’s high performance stems from a combination of pure in‑memory operations, a single‑threaded event loop, carefully engineered data structures (SDS, dictionaries, skip‑lists, zip‑lists), adaptive encoding, and thoughtful expiration handling. Understanding these internals helps developers tune Redis for their specific workloads.