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 Radis from first principles in C++.
Like production Redis, Radis 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 two 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 $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.
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, Radis 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."
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]