Architectural Evolution of Redis: 2009 to Present¶

Level: Principal Distributed Systems Architect & Kernel Engineer
Scope: Cellular Anatomy & Paradigm Shifts from Redis 1.0 (2009) to Redis 7.2/8.0 (2024+)

Executive Architectural Chronology¶

Redis was born in 2009 when Salvatore Sanfilippo (antirez) needed a high-performance real-time log analyzer for his Italian startup LLOOGG. Relational databases (MySQL) could not sustain the write throughput without immense locking overhead. Antirez realized that if data fit into RAM, removing all disk serialization on the critical execution path and relying on a single-threaded multiplexed event loop would produce orders of magnitude higher throughput while eliminating all race conditions, lock contention, and cache coherence penalties.

2009: Redis 1.0 ──────► In-memory key-value, epoll/kqueue event loop, basic RDB snapshots
2010: Redis 2.0 ──────► VM (Virtual Memory) introduced (later deprecated), Multi-bulk protocol
2011: Redis 2.4 ──────► jemalloc allocator integrated; COW memory optimization
2012: Redis 2.6 ──────► Lua 5.1 Scripting runtime embedded; millisecond precision TTLs
2013: Redis 2.8 ──────► Partial Resync (PSYNC), Sentinel 2.0 HA monitoring, Pub/Sub rewrite
2015: Redis 3.0 ──────► Redis Cluster (16,384 Hash Slots, gossip protocol, zero single-point)
2016: Redis 3.2 ──────► Quicklists (ziplist + linkedlist hybrid), GEO spatial commands
2017: Redis 4.0 ──────► C Dynamic Modules API, Async UNLINK/FLUSHALL, PSYNC2, LFU Eviction
2018: Redis 5.0 ──────► Streams data type (Radix tree + PEL consumer groups), HyperLogLog upgrade
2020: Redis 6.0 ──────► Threaded I/O (epoll worker threads), fine-grained ACLs, RESP3 protocol
2022: Redis 7.0 ──────► Multi-Part AOF (base+incr+manifest), Listpack default, Functions API
2024: Redis 7.2/8.0 ──► Dual-channel replication, engine-level vector search, enhanced sharding

1. Paradigm Shift 1: The Single-Threaded Philosophy vs. Multi-Core SMP¶

The Core Problem in 2009¶

Classical databases assigned a dedicated thread or process per connection (e.g., MySQL connection threads, Postgres fork). At thousands of concurrent connections: 1. Thread context switching consumed up to 40% of CPU cycles (switch_mm, register state thrashing). 2. Locks (latches, mutexes, spinlocks) generated huge CPU cache coherence bus storms (MESI protocol invalidations across CPU cores). 3. Memory allocator fragmentation in multi-threaded heaps forced aggressive lock contention on ptmalloc bins.

Antirez's Architectural Axiom¶

In-memory operations take nanoseconds (L1/L2 cache reads take 1–4 ns; main memory RAM fetches take 50–100 ns). In contrast, inter-core thread synchronization (pthread_mutex_lock) takes 25–100 ns even without contention, and hundreds of nanoseconds under contention.

Therefore: Lock-free single-threaded CPU execution is fundamentally faster for pure memory retrieval than multi-threaded execution with synchronization primitives.

Multi-Threaded Engine (Contention Bottleneck):
[Core 0: Worker] ───► [ Mutex Lock ] ◄─── [Core 1: Worker]
       │                    │                     │
       ▼                    ▼                     ▼
CPU Cache Line Invalidation (MESI Bus Storm: Modified -> Shared -> Invalid)

Redis Single-Threaded Engine (Pure Cache Locality):
[Client A] ──┐
[Client B] ──┼──► [aeEventLoop: Epoll] ──► [Single Worker Thread] ──► [L1/L2 Cache RAM]
[Client C] ──┘                               (No Locks, Zero Contention)

2. Paradigm Shift 2: Memory Allocators (Glibc Ptmalloc to Jemalloc)¶

The Fragmentation Crisis (2010–2011)¶

In early Redis versions using glibc malloc, high mutation workloads suffered catastrophic memory fragmentation. When millions of short keys were created and deleted, glibc could not release memory back to the Linux OS because the memory allocator held onto fragmented pages (the "glibc brk/mmap fragmentation trap"). A 4GB dataset would consume 16GB of resident set size (RSS), triggering the Linux Out-Of-Memory (OOM) Killer.

The Jemalloc Integration (Redis 2.4+)¶

Redis standardized on Jason Evans' jemalloc allocator (used by FreeBSD and Facebook). Jemalloc organizes memory into size classes (bins): - Small bins: Exact power-of-two and quantum sizes (8, 16, 32, 48, 64, 80, 96, 112, 128... bytes) eliminating internal fragmentation. - Arenas: Separation of allocations into distinct memory pools. - Dirty Page Purging: Proactive release of unused memory pages to the kernel via madvise(MADV_DONTNEED) or madvise(MADV_FREE).

Active Defragmentation (Redis 4.0+)¶

Even with jemalloc, uneven key lifetime distributions caused external fragmentation. Redis 4.0 added active-defrag: an internal background scan inside activeDefragCycle() that uses jemalloc's introspective allocator APIs (je_mallctl) to inspect whether an allocation is located in a fragmented memory page. If fragmented, Redis reallocates the pointer into a dense page and frees the old pointer, compacting RAM live in production without downtime.

3. Paradigm Shift 3: Evolution of String Encodings (C Strings to SDS)¶

Standard C strings are null-terminated (\0), which presents fatal architectural limitations: 1. Cannot store binary data containing arbitrary bytes or \0. 2. Calculating length requires an \(O(N)\) traversal via strlen(). 3. String concatenations require multiple malloc() / realloc() allocations, causing memory churn.

Simple Dynamic String (SDS) Internals¶

Antirez created SDS. An SDS string is binary-safe because it explicitly tracks byte length in a header preceding the buffer pointer.

In Redis 3.2+, SDS was re-engineered with specialized headers to eliminate header padding overhead:

/* Redis 3.2+ SDS Header Definitions */
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;         /* Current string byte length (0 to 255) */
    uint8_t alloc;       /* Total allocated space excluding header and null */
    unsigned char flags; /* 3 bits for type (SDS_TYPE_8), 5 bits unused */
    char buf[];          /* Variable-length binary buffer + '\0' */
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;        /* 0 to 65,535 */
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};

Why `attribute ((packed))`?¶

The GCC packed attribute instructs the compiler not to insert 4-byte or 8-byte alignment padding bytes between flags and buf[]. Thus, the actual pointer returned to the engine is s = sh->buf. Redis can inspect the flag byte at offset s[-1] using direct pointer arithmetic in \(O(1)\) time with zero pointer dereference hops.

SDS Memory Layout in RAM:
┌─────────────────┬───────────────────┬───────────────┬───────────────────────────────┬──────┐
│ len (uint8_t: 5)│ alloc (uint8_t: 8)│ flags (1 byte)│ 'H'  'E'  'L'  'L'  'O'      │ '\0' │
└─────────────────┴───────────────────┴───────────────┴───────────────────────────────┴──────┘
▲                                     ▲               ▲
│ [sdshdr8 base pointer]              │ flags = s[-1] │ Pointer returned to engine (s)

4. Paradigm Shift 4: From Ziplists to Listpacks (Cascading Updates Solved)¶

The Ziplist Architecture (Redis 2.6 to 6.2)¶

To save memory when storing small hashes, lists, and sorted sets, Redis avoided pointers (which take 8 bytes each on 64-bit systems) and encoded collections as contiguous byte arrays called Ziplists. Each entry in a ziplist stored: [prevlen | encoding | entry-data]

The Fatal Vulnerability: Cascading Updates (\(O(N^2)\) Catastrophe)¶

The prevlen field stored the byte length of the preceding entry. - If the preceding entry was \(< 254\) bytes, prevlen consumed 1 byte. - If the preceding entry was \(\ge 254\) bytes, prevlen expanded to 5 bytes.

If a developer mutated an entry from 253 to 254 bytes, the next entry's prevlen grew from 1 to 5 bytes. This expansion caused the entry to grow beyond 254 bytes, triggering an expansion in the next entry, cascading through all \(N\) entries in the list. This resulted in \(N\) memory reallocations and memmoves, locking the main thread for hundreds of milliseconds.

Ziplist Cascading Update Chain Reaction:
[Entry 0: expanded to 254B] ──► [Entry 1: prevlen expands 1B->5B] ──► [Entry 2: prevlen expands] ──► CPU Stalled!

The Listpack Solution (Redis 7.0+)¶

Redis replaced Ziplist with Listpack (src/listpack.c). A Listpack entry stores its own length at the end of the entry, encoded in reverse: [encoding + data | entry-length-encoded-backwards]

Because an entry never stores the length of its predecessor, modifying an element NEVER cascades to subsequent elements. Cascading updates are structurally impossible.

5. Paradigm Shift 5: The AOF Revolution (From Fork Rewrite Races to Multi-Part AOF)¶

The Classical AOF Dilemma (Redis 1.0 to 6.2)¶

The Append-Only File (AOF) logs every mutating command. Over time, the log grows indefinitely. Redis rewrote the AOF via BGREWRITEAOF: 1. The main thread calls fork() to create a child process. 2. The child writes a compact snapshot of all current keys to a temporary AOF file. 3. Simultaneously, mutating commands continue arriving at the parent process. The parent buffers them into an AOF Rewrite Buffer in RAM. 4. When the child finishes writing, the parent main thread must synchronously write the entire AOF Rewrite Buffer to disk before swapping file descriptors.

The Failure Mode: Under high write load (e.g., 50,000 writes/sec), the AOF rewrite buffer accumulated gigabytes of memory in RAM (provoking OOM crashes) and caused the main thread to freeze for seconds while flushing gigabytes to disk during the final swap phase.

Classical AOF Rewrite:
[Parent Process] ─── Writes mutations to ───► [AOF Rewrite Buffer in RAM (Gigabytes!)]
       │                                                         │
  fork() child                                                   ▼
       ▼                                         Parent MUST synchronously write
[Child Process] ──► Writes new AOF file ────────► this entire buffer at the end! (Freeze)

Multi-Part AOF (Redis 7.0+)¶

Multi-Part AOF splits the single AOF file into an orchestrated directory of files tracked by an appendonly.aof.manifest: 1. Base File: Snapshot of data at the time of rewrite (either raw RESP or RDB format). 2. Incremental Files: Append-only deltas recording new mutations during and after rewrite. 3. Manifest: Atomic state table tracking active base and incremental generations.

When BGREWRITEAOF runs in Redis 7.0: 1. Redis simply opens a new incremental AOF file for incoming writes. 2. The child process writes the new base file. 3. When the child finishes, the parent updates the manifest file in a single atomic rename() system call. 4. Old base and previous incremental files are deleted asynchronously by background threads. Result: Zero AOF rewrite buffer in RAM, zero main-thread disk flush stall.

6. Paradigm Shift 6: Distributed Consensus (From Sentinel to Redis Cluster)¶

Feature	Redis Sentinel (v2.8+)	Redis Cluster (v3.0+)
Architectural Model	Active-Passive Master-Replica with External Monitors	Master-Replica Distributed Sharding (Peer-to-Peer)
Max Capacity	Bound by single-node RAM (e.g., 64GB)	Horizontally scalable across hundreds of nodes (Terabytes)
Data Partitioning	None (full replica on all nodes)	16,384 Hash Slots distributed across master nodes
Client Routing	Client queries Sentinel to discover Master IP	Smart client calculates `CRC16(key) mod 16384` directly
Failover Mechanism	Sentinel quorum votes on leader to promote replica	Master nodes gossip via Cluster Bus; elect replica directly
Brain-Split Mitigation	`min-replicas-to-write` + `min-replicas-max-lag`	Epoch-based quorum fencing + node isolation timeout

7. Paradigm Shift 7: I/O Concurrency (Threaded I/O in Redis 6.0+)¶

Why Not Multi-Threaded Execution?¶

Users frequently requested multi-threaded Redis. Antirez resisted multi-threading the execution engine because memory pointer lookups are fast, and synchronizing hash table buckets would decimate simple key lookups.

The True Bottleneck: Kernel Network I/O¶

Profiling modern 10Gbps/100Gbps network cards revealed that Redis spent 60% of its CPU time on: 1. read() syscalls reading bytes from network sockets into user-space memory buffers. 2. Parsing the RESP protocol into Redis command structures. 3. Formatting responses and issuing write() syscalls back to sockets.

The Solution: Threaded Network I/O¶

In Redis 6.0+, the architecture isolates network parsing while maintaining single-threaded deterministic execution:

[Network Sockets]
   │    │    │
   ▼    ▼    ▼
[I/O Thread 1]  [I/O Thread 2]  [I/O Thread 3]  <--- Read & Parse RESP from Sockets
   │         │         │
   └─────────┼─────────┘
             ▼
   [MAIN ENGINE THREAD]                         <--- Executes Commands Atomically
             │                                       (Strictly Single-Threaded!)
   ┌─────────┼─────────┐
   ▼         ▼         ▼
[I/O Thread 1]  [I/O Thread 2]  [I/O Thread 3]  <--- Formats & Writes Responses to Sockets

Key Invariant: During the execution phase, I/O worker threads are locked out. The main thread executes all commands with zero locks on the dictionary. Once execution finishes, worker threads resume in parallel to push bytes down the network cards.

Summary Matrix of Architectural Evolution¶

Dimension	Redis 1.0 (2009)	Redis 4.0 (2017)	Redis 7.2 / 8.0 (2024+)
Memory Allocator	`glibc malloc`	`jemalloc` + Active Defrag	`jemalloc 5.3` + listpacks everywhere
String Header	Fixed 8-byte header	Variable packed SDS headers	Optimized compact SDS (`sdshdr5/8/16`)
Internal Lists	Linked list of C nodes	Quicklist of Ziplists	Quicklist of Listpacks (zero cascade)
I/O Engine	Single-threaded multiplexing	Single-threaded multiplexing	Threaded socket I/O + async offload
AOF Engine	Monolithic append + rewrite buffer	Monolithic + RDB preamble	Multi-Part AOF (Base + Incremental)
Security	Single global plaintext password	Renamed commands, basic auth	Role-Based ACLs, TLS, Key-level restrictions
Clustering	Manual client-side sharding	16,384 Hash Slot Gossip Cluster	Auto-rebalancing, slot migration, cluster bus