Topic 06: Active Min-Heap TTL Eviction & Asynchronous Thread Pool

Target Duration: 2–4 minutes (~300–450 spoken words)
Focus: Pointwise verbal delivery covering multi-timer scheduling in the event loop, active TTL eviction via a binary min-heap with bidirectional tracking, idle connection pruning, and asynchronous deallocation via a background worker thread pool.

🎙️ Pointwise Spoken Speech (Word-for-Word Delivery)

• Opening & Scope:
  "In an in-memory database, memory reclamation and timeouts must happen proactively without stalling the single-threaded event loop. In Radis, I engineered an active eviction engine using a binary min-heap with bidirectional index tracking, paired with a background worker thread pool for asynchronous deallocations."

• Step 1: Multi-Timer Event Loop Scheduling (next_timer_ms):
  "First, the event loop must know how long poll() can sleep without missing deadlines. In next_timer_ms() (server.cpp:745-769), the server checks two timer sources: the oldest idle connection at the head of the intrusive idle_list, and the earliest TTL expiration at the root of the min-heap. It calculates the delta between the earliest expiration and monotonic time, passing the exact millisecond timeout to poll(). This eliminates busy-polling CPU waste and prevents timer drift."

• Step 2: Active TTL Tracking with a Binary Min-Heap:
  "Second, relying solely on passive expiration—checking TTL only when a key is accessed—causes dead keys to leak memory indefinitely. Instead, Radis uses an active binary min-heap stored in a std::vector<HeapItem> (struct HeapItem heap.h:7-11), ordered by monotonic expiration timestamps (val). The root item always represents the key expiring next, providing an instant $O(1)$ check for pending expirations."

• Step 3: Bidirectional Heap Index Tracking:
  "Third, a major limitation of standard priority queues like std::priority_queue is that updating or deleting an existing entry requires an $O(N)$ linear scan. To solve this, HeapItem stores a reverse pointer: size_t *ref = &ent->heap_idx. Whenever heap_up() (heap.cpp:16-36) or heap_down() (heap.cpp:38-53) swaps items during a rebalance, it immediately updates *ref with the new index. This allows any key to update its TTL or delete itself via heap_update() (heap.cpp:55-61) in strict $O(\log N)$ time."

• Step 4: Bounded Eviction Batches and Idle Connection Pruning:
  "Fourth, inside process_timers() (server.cpp:771-798), idle connections exceeding 5 seconds of inactivity are detached and destroyed via conn_done(). For TTL keys, if thousands of keys expire at the exact same millisecond, evicting them all synchronously would cause a latency spike for clients. To prevent this, the server caps eviction at k_max_works (2,000 keys per loop tick), yielding control back to client I/O before clearing subsequent batches."

• Step 5: Offloading Deallocations to a Background Thread Pool:
  "Finally, when a large data structure like a Sorted Set with 100,000 members is deleted, executing thousands of free() calls synchronously can freeze the reactor for 50 milliseconds. To prevent this tail latency spike, entry_del() (server.cpp:296-318) checks container size. If it exceeds 1,000 elements (k_large_container_size), the entry is unlinked synchronously from the database and queued via thread_pool_queue() (thread_pool.cpp:40-47) to a 4-thread background worker ThreadPool (thread_pool.h:9-21) and worker() (thread_pool.cpp:25-38). The worker destroys the memory off the critical path, keeping reactor response times sub-millisecond."

📋 Step-by-Step Summary (What, How & Why)

❓ Anticipated Interview Questions & Crisp Answers

Q1: Why combine an active min-heap and circular idle list instead of simple passive expiration or thread-per-timer?

Answer: Passive expiration (checking TTL only when a client queries a key) leaks memory if keys are written once and never touched again. Periodic whole-table scanning wastes massive CPU ($O(N)$ overhead). Active min-heap provides $O(1)$ earliest-expiration inspection and $O(\log N)$ updates. For idle socket timeouts, all connections share an identical 5-second deadline, meaning the intrusive circular doubly-linked list (idle_list) is naturally sorted by recency: bumping a connection on activity is $O(1)$ (dlist_detach + dlist_insert_before to tail), and checking expirations at head is $O(1)$. Combining both into next_timer_ms() calculates the exact millisecond poll() timeout, eliminating busy-wait CPU spinning entirely.

Q2: What concurrency bugs or race conditions can occur when offloading memory reclamation to background worker threads in an otherwise single-threaded engine?

Answer: Memory reclamation races happen if a background worker attempts to deallocate memory while the reactor still holds references, or if worker threads deallocate nodes back to the OS while the main thread's memory allocator experiences lock contention. To guarantee complete safety: (1) In entry_del(), the node is completely severed from the database hash table (h_del()), sorted set AVL tree, and TTL min-heap synchronously on the reactor thread before submitting to thread_pool_queue(). (2) The dispatched pointer is unreachable by any client lookup, giving the worker exclusive ownership. (3) Deletion is only offloaded for large structures (zset_del() with $>1000$ members) where recursive tree destruction would block the event loop for dozens of milliseconds. Smaller entries are deleted synchronously to avoid queue lock contention overhead.

Q3: How does the bidirectional HeapItem.ref pointer work during rebalances, and how did you verify it doesn't cause invalid memory writes?

Answer: In standard std::priority_queue, updating or deleting an element requires an $O(N)$ scan because items move during heapify without notifying their owners. In Radis, HeapItem embeds a pointer size_t *ref = &ent->heap_idx. Whenever heap_up() or heap_down() swaps array elements, it immediately executes *a[pos].ref = pos. When an entry is deleted or its TTL is extended via PEXPIRE, the code directly passes ent->heap_idx into heap_update(), performing an in-place reheapify in $O(\log N)$ without searching. To prevent invalid memory writes, whenever a key is removed from the heap, ent->heap_idx is set to (size_t)-1 (sentinel), and heap_update() asserts bounds before dereferencing ref. Validated under high-concurrency client mutations with AddressSanitizer.