LRU Eviction & Memory: The Infinite Workload

Redis is often used as a cache, which means it handles workloads larger than its physical RAM. When the memory is full, Redis doesn't just crash—it becomes a Bouncer. It chooses which data is least important and kicks it out. This is Eviction.

1. Intuition: The VIP Club

Why this exists in Redis

RAM is expensive and limited. If you try to store 20GB of data in a 16GB server, the process will be killed by the OS (OOM Killer). Redis prevents this by enforcing a maxmemory limit.

Real-world problem it solves: Preventing server crashes while ensuring that the most frequently used ("hot") data stays in memory and only "cold" data is removed.

The Analogy (The Busy Cafe)

A cafe has only 10 tables. When a new customer arrives and all tables are full, the manager looks for the person who has been sitting the longest and hasn't ordered a refill recently. They are asked to leave to make room for the new customer.

2. Internal Architecture

How Redis designs this feature

Redis offers several Policies (like allkeys-lru) to manage memory. It doesn't use a global lock for eviction; instead, it checks memory limits before every write command.

Components Involved

maxmemory: The user-defined limit.
LRU Clock: A 24-bit timestamp updated every 100ms.
Eviction Pool: A candidate list used to refine the random sampling.

Trade-offs: True LRU vs. Approximated LRU

True LRU: $O(1)$ but requires massive memory (two pointers per key) and causes CPU contention on every read.
Approximated LRU: Uses only 24 bits in the robj. It samples $N$ random keys and evicts the oldest. Uses almost zero extra memory and CPU.

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

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

Client: Sends SET newkey value.
Command Engine: Before executing, it checks if used_memory > maxmemory.
Eviction Loop:

Sample: Pick 5 random keys from the main dictionary.
Compare: Find the key with the smallest (oldest) LRU timestamp.
Evict: Delete that key from memory.
Check Again: Is memory still over the limit? If yes, repeat.

Execution: Once memory is below the limit, the SET command finally executes.

4. Internals Breakdown

The LRU Clock

In the robj structure, 24 bits are reserved for the lru field. Redis updates a global server.lruclock every 100ms. When an object is accessed, it copies this global clock.

Memory Fragmentation

Even if you DEL a key, the memory might not return to the OS immediately. This is Fragmentation. Redis uses jemalloc to manage this. In Node.js, we are at the mercy of the V8 Garbage Collector.

5. Node.js Reimplementation (Hands-on)

Step 1: Memory Monitoring

We'll use process.memoryUsage() to simulate the maxmemory check.

const MAX_MEMORY = 100 * 1024 * 1024; // 100MB
 
function isOverLimit() {
 return process.memoryUsage().heapUsed > MAX_MEMORY;
}

Step 2: The Approximated LRU Logic

function performEviction() {
 const keys = Array.from(dictionary.keys());
 const SAMPLES = 5;
 
 while (isOverLimit()) {
 let oldestKey = null;
 let oldestTime = Infinity;
 
 // Sample N random keys
 for (let i = 0; i < SAMPLES; i++) {
 const randomKey = keys[Math.floor(Math.random() * keys.length)];
 const obj = dictionary.get(randomKey);
 
 if (obj.lru < oldestTime) {
 oldestTime = obj.lru;
 oldestKey = randomKey;
 }
 }
 
 // Evict the winner
 if (oldestKey) {
 console.log(`Evicting key: ${oldestKey}`);
 dictionary.delete(oldestKey);
 // Refresh key list for next loop iteration
 keys.splice(keys.indexOf(oldestKey), 1);
 }
 }
}

Step 3: Integrating with the Pipeline

function executeCommand(cmd, args) {
 if (isWriteCommand(cmd) && isOverLimit()) {
 performEviction();
 }
 return runLogic(cmd, args);
}

6. Performance, High Concurrency & Backpressure

High Concurrency Behavior

Under high load, Redis doesn't just evict one key. It calculates how much memory must be freed to reach the limit and evicts in Batches.

Bottlenecks & Backpressure Handling

Bottleneck: If the Eviction Policy is too aggressive (sampling 20 keys instead of 5), the CPU cost of FINDING a victim overwhelms the cost of SERVIVING requests.
Backpressure: When Redis hits maxmemory, every incoming SET command must wait for a successful EVICTION before it can proceed. This slows down all writers.

7. Redis vs. Our Implementation: What we Simplified

Eviction Pool: Redis uses a "Best candidates" pool to make its random sampling more accurate over time. Our Node implementation uses simple Array.from() which is far slower and less smart.
Virtual Memory: Older versions of Redis swapped to disk. Modern Redis (and our project) is strictly In-Memory.

8. Why Redis is Optimized

Redis is optimized for Predictable Deletion. By using Approximated LRU, it ensures that "taking out the trash" (eviction) takes a fixed amount of time ($O(1)$) regardless of whether you have 100 or 100 million keys.

Allocation: Redis (C) allocates exactly what it needs. Node.js (V8) allocates large "pages" of memory and might show high usage even after we delete keys because the GC hasn't reclaimed them yet.
Clock Resolution: Redis LRU clock has a resolution of 1 second. Since commands execute in nanoseconds, many keys might have the same timestamp.

9. Edge Cases & Failure Scenarios

The "Eviction Thrashing" Loop: If your data is arriving faster than you can evict, Redis stays in a loop constantly sampling and deleting, causing 100% CPU usage and massive latency spikes.
Lazy Freeing Latency: While background freeing helps, if the background thread is overwhelmed by a 10GB deletion, the memory "reclaim" might not happen fast enough to prevent an OOM crash.
Sampling Bias: Approximated LRU might accidentally evict a "Hot" key if it happens to be in a sample of even hotter keys. This causes a temporary cache miss spike.

8. Summary & Key Takeaways

Approximation is Efficiency: In high-speed systems, a "good enough" algorithm is often better than a perfect one that is slow.
Eviction is a Write-Time cost: Every write potentially triggers an eviction, which can lead to latency spikes if memory is constantly full.

Next Step: Eviction is about survival. Now let's look at Transactions & Signals: Ensuring Multi-Command Atomicity.

Objects, Encodings & INFO Transactions & Signals