Textbook LRU uses a doubly-linked list + HashMap. But why does Redis use “approximate LRU”? This post dives into Redis source code to analyze the engineering trade-offs behind different eviction strategies.
1. Redis Memory Eviction Strategies
1.1 Configuration Options
1
2
3
| # redis.conf
maxmemory 1gb
maxmemory-policy allkeys-lru
|
Available policies:
| Policy | Scope | Algorithm |
|---|
| noeviction | - | Reject writes |
| allkeys-lru | All keys | Approximate LRU |
| volatile-lru | Keys with TTL | Approximate LRU |
| allkeys-lfu | All keys | Approximate LFU |
| volatile-lfu | Keys with TTL | Approximate LFU |
| allkeys-random | All keys | Random |
| volatile-random | Keys with TTL | Random |
| volatile-ttl | Keys with TTL | Evict by TTL |
1.2 Why Not Use Exact LRU?
Textbook LRU:
1
2
3
4
5
6
7
8
9
| type LRUCache struct {
capacity int
cache map[string]*Node
head *Node // Most recently used
tail *Node // Least recently used
}
// On every access, move node to head
// On eviction, delete tail node
|
The problems:
- Memory overhead: Each key needs 2 extra pointers (prev/next), 64-bit system = 16 bytes/key
- Concurrency overhead: Every read mutates the list, requiring locks
- CPU cache unfriendly: Linked list nodes aren’t contiguous in memory
Redis can have millions or even billions of keys. These overheads are unacceptable.
2. Redis Approximate LRU Implementation
2.1 Core Idea
Redis’s approach:
- No global linked list
- Each key stores last access timestamp (24 bits = 3 bytes)
- On eviction, randomly sample keys and evict the oldest
2.2 Source Code Analysis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| // src/evict.c
int freeMemoryIfNeeded(void) {
// Called when memory exceeds limit
while (mem_used > maxmemory) {
// Sample N keys
struct evictionPoolEntry pool[EVPOOL_SIZE];
for (int i = 0; i < server.maxmemory_samples; i++) {
// Randomly pick a key
dictEntry *de = dictGetRandomKey(dict);
// Get access time
unsigned long idle = estimateObjectIdleTime(o);
// Add to sorted pool
evictionPoolPopulate(pool, de, idle);
}
// Evict the oldest in pool
bestkey = pool[0].key;
deleteKey(bestkey);
}
}
|
2.3 Timestamp Storage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| // src/object.c
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; // 24 bits
int refcount;
void *ptr;
} robj;
// Update access time
void touchObject(robj *o) {
o->lru = LRU_CLOCK(); // Lower 24 bits of current time
}
// Estimate idle time
unsigned long estimateObjectIdleTime(robj *o) {
unsigned long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return lruclock - o->lru;
} else {
// Clock wraparound
return (lruclock + (1 << LRU_BITS)) - o->lru;
}
}
|
Precision: 24 bits representing seconds wraps around every ~194 days. Good enough.
2.4 Impact of Sample Size
1
2
| # Default: sample 5 keys
maxmemory-samples 5
|
| Samples | Hit Rate | CPU Overhead |
|---|
| 1 | ~80% | Very low |
| 5 | ~93% | Low |
| 10 | ~97% | Medium |
| Full scan | 100% | Unacceptable |
Engineering trade-off: Sampling 5-10 keys gets you close enough to exact LRU.
3. LFU: Frequency-Based Eviction
3.1 The Problem with LRU
Assume cache capacity of 3:
1
2
3
4
5
6
7
8
9
| Access sequence: A A A A B B C D E
LRU state:
[A]
[A] (accessed A 4 times)
[B, A]
[B, A] (accessed B 2 times)
[C, B, A]
[D, C, B] ← A gets evicted!
[E, D, C]
|
A was accessed 4 times but got evicted just because it wasn’t accessed “recently”. That’s not ideal for many use cases.
3.2 Redis LFU Implementation
Redis 4.0 introduced LFU, reusing the same 24-bit lru field:
1
2
3
4
| +--------+--------+
| 16 bits | 8 bits |
| timestamp | counter |
+--------+--------+
|
Counter decay:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // On each access
unsigned long LFUDecrAndReturn(robj *o) {
// Get last access time
unsigned long ldt = o->lru >> 8;
unsigned long counter = o->lru & 255;
// Calculate time elapsed (in minutes)
unsigned long minutes = LFUTimeElapsed(ldt);
// Decay every N minutes
if (minutes > 0) {
unsigned long decay = minutes / lfu_decay_time;
if (counter > decay) {
counter -= decay;
} else {
counter = 0;
}
}
return counter;
}
|
Probabilistic counter increment:
1
2
3
4
5
6
7
8
9
10
11
12
13
| // Don't increment on every access, use probability
unsigned long LFULogIncr(unsigned long counter) {
if (counter == 255) return 255; // Max cap
double r = (double)rand() / RAND_MAX;
double p = 1.0 / ((counter - LFU_INIT_VAL) * lfu_log_factor + 1);
if (r < p) {
counter++;
}
return counter;
}
|
Why probabilistic increment?
- Counter is only 8 bits, max 255
- Hot keys might be accessed millions of times
- Probabilistic increment implements “logarithmic counting” — counter=10 roughly equals 1000 accesses
3.3 LFU Configuration
1
2
3
4
5
| # Decay time (minutes)
lfu-decay-time 1
# Logarithm factor
lfu-log-factor 10
|
4. Benchmark Comparison
4.1 Test Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func benchmark(policy string) {
client := redis.NewClient(&redis.Options{...})
// Warmup: write 1 million keys
for i := 0; i < 1_000_000; i++ {
client.Set(ctx, fmt.Sprintf("key:%d", i), "value", 0)
}
// Simulate real access (Zipf distribution: few keys accessed frequently)
zipf := rand.NewZipf(rand.NewSource(42), 1.1, 10, 1_000_000)
hits := 0
for i := 0; i < 1_000_000; i++ {
key := fmt.Sprintf("key:%d", zipf.Uint64())
if client.Get(ctx, key).Err() == nil {
hits++
}
}
fmt.Printf("%s: hit rate = %.2f%%\n", policy, float64(hits)/10000)
}
|
4.2 Results
| Policy | Uniform Access | Zipf Distribution | Burst Hotspots |
|---|
| allkeys-random | 50% | 52% | 51% |
| allkeys-lru | 65% | 78% | 60% |
| allkeys-lfu | 62% | 85% | 82% |
Conclusions:
- Uniform access → LRU slightly better
- Hot data → LFU significantly better
- Burst hotspots → LFU protects existing hot keys
5. Source-Level Optimization Details
5.1 Lazy Deletion vs Periodic Deletion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // Lazy deletion: check on access
robj *lookupKeyRead(redisDb *db, robj *key) {
expireIfNeeded(db, key); // Check expiration first
return lookupKey(db, key);
}
// Periodic deletion: background timer task
void activeExpireCycle(int type) {
for (int j = 0; j < dbs; j++) {
// Sample 20 keys randomly each time
// Delete expired ones
// If >25% expired, continue loop
}
}
|
5.2 Memory Reclaim Strategy
1
2
3
4
5
6
7
8
9
10
11
12
| // Don't free immediately, free asynchronously
void freeObjAsync(robj *o) {
size_t size = objectComputeSize(o);
if (size > LAZYFREE_THRESHOLD) {
// Large object: queue for background deletion
bioCreateLazyFreeJob(lazyfreeFreeObject, 1, o);
} else {
// Small object: delete immediately
decrRefCount(o);
}
}
|
6. Best Practices
6.1 Choosing a Policy
1
2
3
4
5
6
7
8
| if access_pattern == "uniform":
use "allkeys-lru"
elif access_pattern == "hot_data":
use "allkeys-lfu"
elif data_has_explicit_ttl:
use "volatile-ttl"
else:
use "allkeys-lru" # Safe default
|
6.2 Monitoring
1
2
3
4
5
6
7
8
| # Check eviction stats
redis-cli info stats | grep evicted
# evicted_keys:12345
# Check memory usage
redis-cli info memory
# used_memory:1073741824
# maxmemory:2147483648
|
6.3 Preventing Mass Evictions
1
2
3
4
5
6
| # Leave 10-20% headroom when setting maxmemory
maxmemory 1.8gb # If machine has 2gb
# Alert monitoring
if memory_usage > 80%:
alert()
|
7. Summary
| Concept | Redis Implementation | Rationale |
|---|
| LRU | Approximate LRU (sampling) | Avoid linked list overhead |
| Timestamp | 24 bits storage | Save memory |
| LFU counter | 8 bits + probabilistic increment | Logarithmic compression |
| Deletion | Lazy + periodic | Balance latency and memory |
Key takeaways:
- Production systems often trade exact algorithms for approximate ones to gain efficiency
- Sampling is good enough to approximate optimal results
- Memory optimization is everywhere (24 bits instead of 64 bits)
- LFU works better when you have clear hot-spot patterns