Target Duration: 4–5 minutes (~650–800 spoken words)
Goal: Deliver an end-to-end architectural explanation covering the single-threaded reactor, low-level socket protocol handling, progressive rehashing, intrusive data layouts, augmented AVL trees, and asynchronous background deallocations. Plant deep-dive hooks along the way.
"To understand how low-latency in-memory databases achieve predictability under heavy concurrent traffic, I built MyRedis from first principles in C++.
Like production Redis, MyRedis is built on a fundamental architectural premise: a single-threaded reactor eliminates synchronization overhead, locks, and context switching, provided that no single operation ever blocks the event loop.
To uphold this guarantee across network I/O, memory resizing, and expiration, I structured the system around four foundational subsystems: 1. Non-blocking Event Loop & Framing Protocol 2. Progressive Rehashing Hash Table 3. Dual-Indexed Augmented AVL Sorted Sets 4. Active Multi-Timer Eviction & Async Thread Pool Deallocation"
"For network I/O, I implemented a single-threaded event loop driven by Linux poll(). All client and server file descriptors are configured with O_NONBLOCK via fd_set_nb() (server.cpp:32).
Each client connection is represented by a struct Conn (server.cpp:48) containing explicit application intent flags (want_read, want_write, want_close) and dedicated input and output byte buffers.
- When POLLIN fires, handle_read() (server.cpp:149) reads data into incoming and loops over try_one_request() (server.cpp:703).
- To prevent stream framing ambiguities over TCP, requests use a 4-byte length-prefixed binary framing protocol parsed in parse_req() (server.cpp:643).
- A crucial feature here is TCP pipelining: when multiple commands arrive packed in a single read call, the server parses and executes each command in a loop, appends responses sequentially to outgoing, and consumes only the parsed slice via buf_consume() (server.cpp:74) rather than wiping the buffer.
- When responses are queued, the connection transitions to want_write and immediately attempts a synchronous flush via handle_write() (server.cpp:189) before yielding back to poll(), minimizing latency."
(Hook: Deep dive into topic_01_event_loop_and_nonblocking_io or topic_02_framing_pipelining_and_serialization)
"In standard hash tables, doubling table size requires rehashing all keys at once—causing severe millisecond-scale latency spikes that violate real-time SLAs.
To solve this, I built a two-table progressive rehashing engine struct HMap (hashtable.h:22):
- Storage consists of a newer and an older table, using FNV-1a hashing with power-of-two slot masks in h_init() (hashtable.cpp:7).
- When the load factor exceeds 8, rehashing is triggered: newer becomes older, and a double-sized newer table is allocated.
- Crucially, migration is incremental: every lookup, insert, or delete migrates a bounded chunk of up to 128 non-empty slots (k_rehashing_work in hashtable.cpp:7) from older to newer via hm_trigger_rehashing() (hashtable.cpp:48). This guarantees strict $O(1)$ amortized operations and constant-time latency.
Furthermore, I used intrusive data structures modeled after the Linux kernel. Node structures like struct HNode (hashtable.h:8) and struct AVLNode (avl.h:7) are embedded directly inside data payloads (struct Entry in server.cpp:276) rather than allocated as separate wrapper objects. Using the container_of macro (common.h:8) and offsetof arithmetic, we compute parent container pointers with zero indirection and zero heap overhead."
(Hook: Deep dive into topic_03_progressive_rehashing_hashtable or topic_04_intrusive_data_structures_and_memory_layout)
"Beyond simple string key-values, I implemented high-performance Sorted Sets (struct ZSet in zset.h:7) supporting range queries, score updates, and rank-based lookups.
I engineered a dual-index architecture:
1. An intrusive hash map (HMap) indexes member names to provide $O(1)$ key lookups for ZSCORE and membership checks via zset_lookup() (zset.cpp:97).
2. A self-balancing AVL tree orders elements by (score, name) tuples for sorted traversal, rebalanced via avl_fix() (avl.cpp:72).
To support efficient pagination and ranking, I augmented each struct AVLNode (avl.h:7) with a cnt field tracking the subtree size, maintained during tree rotations via avl_update() (avl.cpp:10). This augmentation transforms the AVL tree into an order-statistic tree:
- ZQUERY can seek to a score/name bound using binary search (zset_seekge() in zset.cpp:131) in $O(\log N)$.
- It can then jump forward or backward by arbitrary numeric rank offsets via avl_offset() (avl.cpp:151) in $O(\log N)$ time, avoiding linear cursor scans."
(Hook: Deep dive into topic_05_dual_indexed_sorted_sets_and_avl)
"Finally, managing expirations and resource reclamation without blocking the single-threaded reactor required three specialized designs:
Active TTL Eviction with Bidirectional Min-Heap:
Passive eviction (only checking on access) wastes memory, while linear scans waste CPU. I built a binary min-heap (struct HeapItem in heap.h:7) storing absolute expiration timestamps (expire_at). To allow keys with existing TTLs to be updated or deleted in $\mathcal{O}(\log N)$ time without full heap scans, each heap element maintains a reverse pointer (size_t *ref) back to the key's heap_idx in Entry. In each event loop tick, process_timers() (server.cpp:771) evicts expired keys in bounded batches of up to 2,000 items.
Idle Connection Pruning via Circular Doubly-Linked List (DList):
All client connections share a 5-second inactivity timeout. Rather than scanning all descriptors, I link active connections into an intrusive circular doubly-linked list (struct DList in list.h:7). Whenever a connection has read/write activity, it is moved to the tail in $\mathcal{O}(1)$. The head is always the least-recently-used connection, allowing $\mathcal{O}(1)$ LRU expiration checks. Furthermore, next_timer_ms() (server.cpp:745) computes the minimum deadline across both the TTL min-heap and the idle connection list, passing it directly as the poll() timeout to eliminate busy-wait CPU spinning.
Async Deallocation via Worker Thread Pool:
Deleting a container holding hundreds of thousands of items can take dozens of milliseconds in free() calls. If executed synchronously, this freezes the server. When any container exceeds 1,000 items, entry_del() (server.cpp:296) hands off the unlinked task via thread_pool_queue() (thread_pool.cpp:40) to a 4-thread worker ThreadPool (thread_pool.h:9) and worker() (thread_pool.cpp:25), completely removing memory deallocation latency from the reactor loop."
(Hook: Deep dive into topic_06_ttl_cache_eviction_and_thread_pool)
"In summary, MyRedis gave me rigorous, hands-on experience designing systems software: mastering event-driven asynchronous networking, developing cache-conscious intrusive memory layouts, eliminating tail latencies via incremental rehashing, and coordinating thread-pool concurrency alongside a single-threaded reactor."
In low-latency in-memory databases, time complexity cannot merely be analyzed on "average case"—it must be strictly bounded to eliminate p99 tail latency jitter. Below is the complete time complexity specification for every user-facing command and internal subsystem in MyRedis:
| Command | Syntax | Time Complexity | Data Structure(s) Used | Microarchitectural Rationale & Guarantees |
|---|---|---|---|---|
| GET | get <key> |
$\mathcal{O}(1)$ amortized | Intrusive HMap (FNV-1a) |
Bitmask lookup in newer table; falls back to older table if rehashing is active. Progressively migrates up to 128 non-empty buckets in the same pass. |
| SET | set <key> <val> |
$\mathcal{O}(1)$ amortized | Intrusive HMap |
Looks up key; updates existing value or allocates Entry and prepends embedded HNode to the newer bucket chain. Triggers progressive rehashing if load factor > 8. |
| DEL | del <key> |
$\mathcal{O}(1)$ on main thread | HMap + Worker ThreadPool |
Unlinks HNode from hash chain in $\mathcal{O}(1)$ using pointer-to-pointer indirection. If container > 1,000 items, physical deallocation ($\mathcal{O}(M)$) is offloaded to background threads. |
| KEYS | keys |
$\mathcal{O}(N)$ | newer + older tables |
Full linear scan across all hash buckets in both tables to collect all active keys, where $N$ is the total key count. |
| PEXPIRE | pexpire <key> <ttl_ms> |
$\mathcal{O}(\log K)$ | HMap + Binary Min-Heap |
$\mathcal{O}(1)$ hash lookup to locate Entry. If key already has a TTL, it uses the embedded reverse pointer size_t *ref = &ent->heap_idx to update the heap in $\mathcal{O}(\log K)$ sift-up/down without an $\mathcal{O}(K)$ scan. If new TTL, appends and sifts up in $\mathcal{O}(\log K)$ ($K$ = active TTL keys). |
| PTTL | pttl <key> |
$\mathcal{O}(1)$ | HMap + Min-Heap array |
$\mathcal{O}(1)$ hash lookup. If heap_idx == -1, returns -1. Otherwise reads heap[heap_idx].val in $\mathcal{O}(1)$ and subtracts the monotonic clock. |
| ZADD | zadd <zset> <score> <name> |
$\mathcal{O}(\log M)$ | Dual-Index: HMap + Augmented AVL |
$\mathcal{O}(1)$ lookup in ZSet hash table. If updating score, detaches node from AVL in $\mathcal{O}(\log M)$, updates score, and reinserts into AVL with balance rotations in $\mathcal{O}(\log M)$ ($M$ = ZSet member count). Subtree counts (cnt) updated in $\mathcal{O}(1)$ per visited ancestor. |
| ZREM | zrem <zset> <name> |
$\mathcal{O}(\log M)$ | Dual-Index: HMap + Augmented AVL |
$\mathcal{O}(1)$ lookup and unlinking from ZSet HMap; $\mathcal{O}(\log M)$ detachment and rebalancing rotations in AVL tree. |
| ZSCORE | zscore <zset> <name> |
$\mathcal{O}(1)$ | ZSet Intrusive HMap |
Direct hash lookup in the ZSet's internal dictionary. The embedded ZNode stores the score directly—the AVL tree is never touched! |
| ZQUERY | zquery <zset> <score> <name> <offset> <limit> |
$\mathcal{O}(\log M + L)$ | Augmented AVL Tree (Order-Statistic) | $\mathcal{O}(\log M)$ binary search to find starting bound via zset_seekge(); $\mathcal{O}(\log M)$ jump over offset elements via avl_offset() using subtree counts (avoids linear cursor scans); $\mathcal{O}(L)$ in-order traversal to emit $L$ items ($L = \text{limit}$). Total: $\mathcal{O}(\log M + L)$. |
| Subsystem Operation | Function / File | Time Complexity | Operational Mechanism & Guarantee |
|---|---|---|---|
| Event Loop Multiplexing | poll() in server.cpp |
$\mathcal{O}(C)$ | Monitors $C$ active client and server file descriptors with O_NONBLOCK. Timeout dynamically computed by next_timer_ms() to prevent busy-wait CPU spinning. |
| TCP Pipelining & Slicing | try_one_request() / buf_consume() |
$\mathcal{O}(B)$ | Processes multiple length-prefixed requests in a single read buffer. 4-byte header decoding is $\mathcal{O}(1)$; byte slice shifting via memmove is $\mathcal{O}(\text{remaining bytes})$. |
| Progressive Rehashing | hm_trigger_rehashing() in hashtable.cpp |
$\mathcal{O}(1)$ amortized ($\le 128$ buckets) | Migrates a bounded batch of up to 128 non-empty buckets per query. Table doubling ($\mathcal{O}(N)$) is amortized across $N/128$ queries, eliminating stop-the-world pauses. |
| Active TTL Expiration | process_timers() in server.cpp |
$\mathcal{O}(E \log K)$ | Inspects min-heap root in $\mathcal{O}(1)$. If expired, pops up to $E \le 2000$ keys in $\mathcal{O}(\log K)$ per key. Bounded batch size prevents reactor stalls. |
| Idle Connection Pruning | dlist_detach() / next_timer_ms() |
$\mathcal{O}(1)$ | Connections linked in circular DList. Activity moves node to tail in $\mathcal{O}(1)$. Head is always least-recently-used, allowing $\mathcal{O}(1)$ timeout checks and pruning. |
| Async Background Deallocation | thread_pool_queue() / worker() |
Main: $\mathcal{O}(1)$ Worker: $\mathcal{O}(M)$ |
Main thread detaches container in $\mathcal{O}(1)$ and enqueues task to 4 POSIX worker threads. Deep recursive deallocation ($\mathcal{O}(M)$) runs concurrently in background. |
ZSCORE queries the internal hash table directly by member name in $\mathcal{O}(1)$ without touching the tree. ZQUERY queries the AVL tree to seek to (score, name) in $\mathcal{O}(\log M)$, uses subtree counts to skip offset items in $\mathcal{O}(\log M)$ without traversing them, and iterates $L$ items in $\mathcal{O}(L)$.HeapItem stores a reverse pointer size_t *ref = &ent->heap_idx. When elements swap, *a[pos].ref = pos updates the entry's index immediately, allowing direct $\mathcal{O}(\log K)$ sift-up/down.free() calls, freezing the event loop for 50+ ms. In MyRedis, any container with >1,000 items is unlinked from the hash table in $\mathcal{O}(1)$ on the main thread and pushed to a 4-thread worker pool for asynchronous cleanup.graph LR
DetailedSpeech[4-5 Min Detailed Speech] --> T1[topic_01: Event Loop & Non-Blocking IO]
DetailedSpeech --> T2[topic_02: Framing, Pipelining & Serialization]
DetailedSpeech --> T3[topic_03: Progressive Rehashing Hashtable]
DetailedSpeech --> T4[topic_04: Intrusive Structures & Memory Layout]
DetailedSpeech --> T5[topic_05: Dual-Indexed AVL Sorted Sets]
DetailedSpeech --> T6[topic_06: TTL Min-Heap & Async Thread Pool]