4–5 Minute Detailed Architecture: MyRedis (In-Memory Key-Value Database)

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.


🎙️ Spoken Script & Section Walkthrough

1. High-Level Architectural Thesis (30s)

"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"


2. Pillar 1: Non-Blocking Reactor & TCP Pipelining (60s)

"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)


3. Pillar 2: Progressive Rehashing & Intrusive Memory Layout (60s)

"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)


4. Pillar 3: Dual-Indexed Augmented AVL Sorted Sets (75s)

"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)


5. Pillar 4: Dual-Timer Eviction & Background Thread Pool (60s)

"Finally, managing expirations and resource reclamation without blocking the single-threaded reactor required three specialized designs:

  1. 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.

  2. 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.

  3. 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)


6. Summary & Wrap-up (30s)

"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."


⚡ Algorithmic Time Complexity Analysis by Operation

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:

1. User-Facing Command Operations

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)$.

2. Internal Subsystem & Reactor Operations

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.
💡 Interview Defense — The 4 Critical Complexity Guarantees:

🧭 Interviewer Follow-Up Mapping

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]