Why Is Redis So Fast? Unveiling Its Core Data Structures

Redis Speed: The Role of Data Structures

Beyond being an in‑memory database, Redis’s speed largely stems from the sophisticated data structures that underpin its core types, enabling efficient insert, delete, update, and query operations.

1. How Redis Stores Key‑Value Pairs

Keys are always string objects. Values can be strings, lists, hashes, sets, or sorted sets (zsets). Example commands:

> SET name "xiaolincoding"
OK
> HSET person name "xiaolincoding" age 18
0
> RPUSH stu "xiaolin" "xiaomei"
(integer) 4

Redis keeps all key‑value pairs in a hash table, giving O(1) average lookup time. Each dictEntry stores void *key and a union for the value, plus a next pointer for chaining in case of hash collisions.

2. Simple Dynamic String (SDS)

Redis implements its own string type called SDS to overcome C‑string limitations (null‑termination, O(N) length calculation, unsafe functions). An SDS header stores len (string length), alloc (allocated space), flags (type), and the actual buffer buf[]. This allows O(1) length retrieval and binary‑safe storage.

struct __attribute__((packed)) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[]; };
struct __attribute__((packed)) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[]; };

Different header variants (sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64) are chosen based on the maximum string length to save memory.

3. Linked List Implementation

Redis’s list type uses a custom doubly‑linked list. The node structure:

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

The list wrapper adds head/tail pointers, length, and optional dup, free, match callbacks:

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

Advantages: O(1) access to head, tail, and length; flexible value storage. Drawbacks: non‑contiguous memory hurts CPU cache performance and each node adds overhead.

4. Compressed List (ziplist)

A ziplist is a compact, contiguous memory structure used for small lists or hashes. It stores three header fields ( zlbytes, zltail, zllen) and a series of entries, each with prevlen, encoding, and data. Length lookup for the first/last element is O(1), but searching other elements is O(N).

When inserting a large element, the ziplist may need to reallocate and adjust prevlen fields of following entries, causing a "chain reaction" (连锁更新) that degrades performance.

5. Integer Set (intset)

Used for sets that contain only integers and are small. The structure stores an encoding (int16, int32, or int64), a length, and a contiguous contents array whose element type matches the encoding. When a larger integer is added, the intset upgrades its encoding, expanding the array while preserving order.

6. Hash Table Details and Rehashing

The hash table consists of an array of dictEntry pointers (buckets). Collisions are resolved with chaining (linked list of entries). Redis maintains two hash tables ( ht[2]) to perform incremental rehashing: new entries go to the second table while the first is gradually migrated, avoiding long pauses.

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

7. Skiplist (used by Zset)

Zsets combine a hash table for O(1) score lookup and a skiplist for O(log N) range queries. A skiplist node stores the element ( sds ele), its score, a backward pointer, and an array of levels, each with a forward pointer and a span (used to compute rank). Nodes are assigned random levels with a 25% probability of increasing the level, up to a maximum of 64.

typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;

8. Quicklist (Redis 3.2+ List Implementation)

Quicklist combines a doubly‑linked list of nodes, each node holding a ziplist. This limits the size of any single ziplist, reducing the impact of chain updates. The structures:

typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; unsigned long len; } quicklist;

typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *zl; unsigned int sz; unsigned int count:16; } quicklistNode;

9. Listpack (Redis 5.0+ Replacement for Ziplist)

Listpack removes the prevlen field that caused chain updates. It stores a total byte length, element count, and a series of entries, each with an encoding, the actual data, and the entry’s total len. Because only the current entry’s length is stored, inserting a new element never forces updates to subsequent entries.

Conclusion

The article provides a comprehensive walkthrough of Redis’s internal data structures—SDS, ziplist, quicklist, listpack, intset, hash tables, and skiplists—explaining how each design choice balances memory efficiency, speed, and complexity, and how newer structures (quicklist, listpack) address the shortcomings of earlier implementations.