Storage & TTL: The Mystery of Auto-Deletion

At its core, Redis is a key-value store. But what makes it a cache is its ability to hold data for a specific duration—the TTL (Time To Live). In this chapter, we'll design our internal data store and implement the sophisticated auto-deletion mechanisms that keep Redis lean.

1. Intuition: Why not just `setTimeout`?

Why this exists in Redis

Memory is the most expensive resource in a database. Storing a session token for 24 hours is great, but keeping it forever when the user never returns is a memory leak.

Real-world problem it solves: Automatic memory management without manual cleanup scripts.

The Analogy (The Library)

Imagine a library where every book has a "Return By" date.

Passive Cleanup: When a user tries to check out a book, the librarian looks at the date. If it's overdue, they throw it in the trash instead of handing it over.
Active Cleanup: Every hour, the librarian picks 20 random books. If they find overdue ones, they trash them. This prevents the shelves from overflowing with books no one ever asks for.

2. Internal Architecture

Components Involved

Main Dictionary: A Hash Table (Node.js Map) storing the actual keys and values.
Expiry Map: A separate Hash Table storing the key and its unix_timestamp_ms of death.

How Redis designs this feature

Redis uses a probabilistic expiration algorithm. It doesn't guarantee a key is deleted the exact millisecond it expires, but it guarantees it will eventually be deleted with very low CPU overhead.

Trade-offs

Accuracy vs. Performance: Perfect accuracy would require a timer for every key (expensive!). Redis chooses probabilistic accuracy to keep the event loop fast.

3. End-to-End Flow (VERY IMPORTANT)

Client → TCP → Event Loop → Command Queue → Parser → Execution → Data Store → Response

Client: Sends SETEX session 3600 "token123".
Parser: Breaks it into key: session, seconds: 3600, value: token123.
Command Engine:

Saves "token123" in the Main Dictionary.
Calculates now() + 3600000ms and saves it in the Expiry Map.

Time Event: Every 100ms, the background task samples the Expiry Map.
Client (2 hours later): Sends GET session.
Passive Check: The engine checks the Expiry Map. now() > expiry_time.
Deletion: The engine deletes from both Maps and returns $-1 (Null).

4. Internals Breakdown

Data Structures: The Dual Map

In C, Redis uses dict structures. Our implementation uses Map which is a highly optimized Hash Table in V8.

Algorithms

Passive: Check-and-delete on access.
Active: Sample $N$ random keys. If expired, delete. If $>25%$ of sample is expired, repeat immediately (up to a time limit).

5. Node.js Reimplementation (Hands-on)

Step 1: The Core Logic

const dictionary = new Map();
const expiryMap = new Map();
 
function handleSet(key, value, ttlSeconds) {
 dictionary.set(key, value);
 if (ttlSeconds) {
 expiryMap.set(key, Date.now() + (ttlSeconds * 1000));
 }
 return '+OK\r\n';
}

Step 2: Passive Expiration (The "Librarian Check")

function handleGet(key) {
 const expiry = expiryMap.get(key);
 
 if (expiry && expiry < Date.now()) {
 // Overdue! Delete and return Null
 dictionary.delete(key);
 expiryMap.delete(key);
 return '$-1\r\n';
 }
 
 const val = dictionary.get(key);
 return val ? `$${val.length}\r\n${val}\r\n` : '$-1\r\n';
}

Step 3: Active Expiration (The "Background Cycle")

function activeExpireCycle() {
 const keys = Array.from(expiryMap.keys());
 const sampleSize = Math.min(keys.length, 20);
 
 for (let i = 0; i < sampleSize; i++) {
 const randomKey = keys[Math.floor(Math.random() * keys.length)];
 if (expiryMap.get(randomKey) < Date.now()) {
 dictionary.delete(randomKey);
 expiryMap.delete(randomKey);
 }
 }
}
setInterval(activeExpireCycle, 100);

6. Performance, High Concurrency & Backpressure

High Concurrency Behavior

During the Active Expiration Cycle, Redis samples the keyspace. If more than 25% of keys are expired, it repeats the cycle to clear memory immediately. This ensures that even under millions of operations, the expired keys don't "clog" the system.

Bottlenecks & Backpressure

Bottleneck: The setInterval (or activeExpireCycle) is a blocking operation. If it takes too long (default limit 25ms), it delays the processing of actual GET/SET commands.
Scaling: As you add more keys, the Main Dictionary Hash Table grows. Redis performs "Incremental Rehashing" in the background so the resize doesn't block the server.

7. Redis vs. Our Implementation: What we Simplified

Probabilistic Efficiency: Redis uses dictGetRandomKey which is a true $O(1)$ random access. Our implementation uses Array.from(map.keys()) which is $O(N)$ and would crash a production server with millions of keys.
Time Resolution: Redis uses a specialized 24-bit LRU clock. We use Date.now(), which is more accurate but uses more memory per key.

8. Why Redis is Optimized

Redis is optimized for Predictable Latency. By choosing probabilistic algorithms (sampling random keys) over exact ones (sorting every key), it ensures that the CPU cost of "Housekeeping" is always fixed and never spikes based on the number of keys.

Randomization: Redis uses dictGetRandomKey which is $O(1)$. Our Array.from() is $O(N)$ and very slow for large Maps.
Time Limit: Redis limits the background cycle to 25ms (25% of the 100ms interval) to ensure it doesn't block the main thread too long.

9. Edge Cases & Failure Scenarios

Memory Spikes (Active Cycle): If you have 1 million keys expiring at the exact same second, your activeExpireCycle might take longer, slightly increasing latency for other commands.
Backpressure (Insertion Rate): In massive write-heavy systems, the expiration cycle might struggle to keep up with new keys, leading to memory exhaustion.
Replication Lag: In the real world, Redis replicas (slaves) don't expire keys themselves. They wait for a DEL command from the Master. If the link is slow, you might see expired data on the replicas.

8. Summary & Key Takeaways

TTLs are essential for memory health.
Passive + Active is the industry standard for high-performance expiration.
Node.js Maps are great, but randomized sampling needs better efficiency in production.

Next Step: Storage is great, but what if the power goes out? Let's implement Persistence: The AOF Internals.

Event Loop & IO Multiplexing Pipelining & AOF Internals