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

Redis, a key‑value cache server, is renowned for its high performance and richer data types compared with Memcached.

When I first interviewed after graduation, interviewers often asked why Redis is fast; I could only mention two reasons: data stored in memory and Redis being single‑threaded.

Data resides in memory, eliminating disk I/O.

Single‑threaded execution avoids context‑switch overhead.

These are only a small part of the story. The article outlines the main factors behind Redis’s speed:

Pure in‑memory operations

Single‑threaded design

Efficient data structures

Smart data encoding

Other optimizations

Redis’s five core data structures and typical use cases are:

String – cache, counters, distributed locks

List – linked list, queue, timeline feeds

Hash – user profiles, hash tables

Set – deduplication, likes, mutual friends

Zset – ranking, leaderboards

SDS (Simple Dynamic String)

Redis is written in C but uses its own SDS structure for strings.

<code>struct sdshdr {
    int len;
    int free;
    char buf[];
}
</code>

SDS fields:

len – length of used buffer

free – length of unused buffer

buf[] – actual content

When executing

SET key value

, both key and value are stored as SDS objects.

Differences Between SDS and C Strings

1. Constant‑time length retrieval

C strings require O(n) traversal to find the terminating '\0', while SDS stores length in

len

, giving O(1) access.

2. Buffer‑overflow protection

SDS checks available space before modification and reallocates if needed, preventing adjacent strings from being overwritten.

3. Fewer reallocations on modifications

SDS employs pre‑allocation and lazy free space strategies:

When expanding, it allocates extra unused space (equal to current length if

len < 1M

, otherwise 1 MB).

When shrinking, it records freed bytes in

free

for future appends, avoiding immediate deallocation.

4. Binary safety

SDS can store binary data containing '\0' because length is tracked by

len

, not by a terminator.

Dictionary Implementation

Redis’s internal hash table (similar to Java’s HashMap) is defined as:

<code>typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2];
    int rehashidx;
} dict;

typedef struct dictht{
    void **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
</code>

The fields

ht

and

rehashidx

are crucial for the rehash process.

Rehash

1. Rehash Procedure

Redis keeps two hash tables

ht[0]

and

ht[1]

. When resizing, it allocates

ht[1]

, moves entries from

ht[0]

to

ht[1]

, then swaps them.

2. Incremental Rehash

For large datasets, Redis performs incremental rehashing: each regular dictionary operation also migrates a bucket from

ht[0]

to

ht[1]

until completion, limiting CPU spikes.

Note: During rehash, memory usage temporarily increases because both tables coexist.

Skip‑list (used by Zset)

Zset’s ordered set is implemented with a skip‑list:

<code>typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

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

Forward pointer : traverses from head to tail.

Backward pointer : moves one node backward; forward pointers can skip multiple nodes.

Span : distance to the next node, indicating how many elements are skipped.

Compressed List (ziplist)

Ziplist is a memory‑efficient sequential structure used for small lists and hashes.

When the number of elements exceeds a threshold, Redis converts the ziplist to a regular linked list or hash table.

Object Encoding

Redis objects (

redisObject

) store type, encoding, and a pointer to the underlying data:

<code>typedef struct redisObject{
    unsigned type:4;
    unsigned encoding:4;
    void *ptr;
    // ...
} robj;
</code>

Different data types have multiple encodings (e.g.,

int

vs.

raw

for strings,

ziplist

vs.

linkedlist

for lists,

intset

vs.

hashtable

for sets, etc.). The article lists the conditions under which each encoding is chosen and shows example CLI commands.

Expiration Deletion Strategies

Redis provides three ways to delete expired keys:

Timed deletion : a timer removes the key exactly at its expiration time (CPU‑intensive).

Lazy deletion : the key is removed only when accessed after expiration (memory‑intensive).

Periodic deletion : a hybrid approach that scans a subset of expired keys every few milliseconds, limiting CPU impact.

By combining these strategies, Redis balances memory usage and CPU load while maintaining high throughput.

Overall, Redis’s performance stems from pure in‑memory storage, a single‑threaded event loop, carefully designed data structures, adaptive encoding, and thoughtful expiration handling.