Adaptive Hybrid Eviction (AHE)

A self-tuning cache eviction algorithm that blends recency, frequency, and TTL urgency into a single score — and adapts its own weights from live hit-ratio feedback.

• Status: Adaptive hybrid algorithm, shipped since v0.3
• Source: src/storage/eviction.rs
• Related: Whitepaper §9.5

---

Abstract

Classic cache eviction policies force a fixed trade-off. LRU reacts fast to bursty traffic but is defenceless against scan pollution and cannot recognise long-lived hotspots. LFU protects stable hot keys but suffers a cold-start penalty: a freshly arrived hot key has a low frequency and is evicted before it ever warms up. Neither adapts when the access pattern shifts mid-run.

AHE (Adaptive Hybrid Eviction) resolves this by scoring every candidate with a single Eviction Priority Score (EPS) that fuses three signals:

• recency — how long since the key was last touched (LRU intuition),
• infrequency — how rarely the key is accessed (LFU intuition),
• TTL urgency — whether the key is about to expire anyway.

The blend weight alpha between recency and frequency is not a tunable knob the operator must set — it is driven by a feedback controller that watches the engine's observed hit ratio and nudges alpha toward whatever the current workload rewards. The result is one eviction policy that behaves like LRU under bursts and like LFU under stable热度, without any human intervention.

---

1. Motivation

Workload	LRU	LFU	Problem
Bursty hotspot (flash sale)	✅	❌	LFU cold-starts the new hot key and evicts it
Stable hot key	❌	✅	LRU drops a long-lived hot key after one idle read
Scan pollution (full table scan)	❌	✅	LRU lets cold scan keys evict hot data
Key about to expire	❌	❌	Neither is TTL-aware; a dying key wastes a slot
Shifting access pattern	❌	❌	A fixed policy cannot follow the change

Core idea. For each sampled candidate compute a unified score; the key with the highest score is the most evictable. Separately, a controller adjusts the recency/frequency weight from observed hit ratio.

---

2. The Eviction Priority Score (EPS)

EPS = alpha · recency + (1 − alpha) · infrequency + ttl_penalty

Higher EPS ⇒ more evictable. Each term is normalised to [0, 1] so the three signals are directly comparable.

Term	Definition	Meaning
recency	min((now − last_access) / 600s, 1.0)	Higher for keys untouched for longer
infrequency	1 − lfu_counter / 255	Higher for colder keys (shared Morris counter)
ttl_penalty	+0.2 if remaining TTL ≤ 30s or already expired; else 0	Lets AHE prefer keys that are doomed anyway
alpha	adaptive weight, clamped to [0.05, 0.95]	→ 1.0 favours LRU, → 0.0 favours LFU

recency uses a 600-second horizon (RECENCY_HORIZON): a key idle for 10 minutes is maximally "stale" and scores 1.0 regardless of how much longer it waits. infrequency reuses the same lfu_counter that powers the *-lfu policies (Morris counter, 0..=255), so AHE adds zero extra per-key memory.

Design note. An earlier draft used a log2 frequency normalisation and a 1/(1+elapsed) time decay. The shipped version instead shares the LFU Morris counter and a linear recency gradient — this keeps AHE's metadata footprint at exactly zero and ties it directly to Redis-compatible structures.

---

3. Adaptive Weight Controller (alpha)

alpha lives in AdaptiveHybridState, a 1-dimensional gradient search driven by the engine's hit ratio. The engine calls observe(hits, misses) after each successful eviction; once window_size (default 64) samples accumulate, the controller updates alpha.

Field	Default	Role
alpha	0.5	Current recency/frequency blend
step	0.05	Magnitude of each adjustment
direction	+1.0	Sign of the last move; flipped on regression
last_hit_ratio	0.0	Previous window's hit ratio (regression detector)
window_size	64	Samples between adjustments (noise filter)
window_count	0	Samples seen in the current window

observe(hits, misses):
    window_count += 1
    if window_count < window_size:
        return                       # still gathering samples

    ratio = hits / (hits + misses)
    if ratio + 1e-4 < last_hit_ratio:
        direction = -direction       # hit ratio dropped → reverse course
    alpha = clamp(alpha + direction · step, 0.05, 0.95)
    last_hit_ratio = ratio
    window_count = 0

Properties

• Objective is hit ratio, not access distribution. No per-key skew metrics are needed; keyspace_hits / (keyspace_hits + keyspace_misses) is the target.
• Flip-on-regression gradient search. Only the last move's sign is stored; when the hit ratio retreats, the sign flips — a lightweight stand-in for estimating the gradient.
• Guard rails. alpha is clamped to [0.05, 0.95], so AHE never degenerates into pure LRU or pure LFU.
• Self-paced. Because observe fires per eviction, the adaptation rate tracks write pressure naturally.

---

4. Complexity & Memory

Step	Cost	Notes
Per-candidate score	O(1)	recency + infrequency + ttl_penalty, all inline
Victim selection	O(k)	k = maxmemory-samples (default 5)
Extra per-key memory	0 bytes	reuses lfu_counter and last_access
Controller update	O(1) amortised	once per window_size evictions

This matches Redis' sampling-based approach (Redis 6+ also samples maxmemory-samples random keys instead of maintaining a global heap/list) while adding adaptivity at no memory cost.

---

5. Comparison with Classic Policies

Dimension	LRU	LFU	AHE (FerrumKV)
Score compute	O(1)	O(1) (Morris)	O(1)
Selection	O(k) sample	O(k) sample	O(k), k = samples
Extra memory	—	—	— (reuses LFU fields)
Burst hotspot	✅	❌	✅ alpha → LRU
Stable hotspot	❌	✅	✅ alpha → LFU
Scan resistance	❌	✅	✅ frequency floors it
TTL-aware	❌	❌	✅ ttl_penalty
Pattern shift	❌	❌	✅ adapts live
Tunable params	none	lfu-log-factor, lfu-decay-time	alpha init, step, window, samples

---

6. Convergence Behaviour

Under a workload that switches from a burst (favouring recency) to a stable hotspot (favouring frequency), the controller walks alpha toward LRU first, then reverses toward LFU, oscillating in a shrinking band around the value the current mix rewards. The trace below is illustrative — the exact path depends on the hit-ratio signal, which you can watch live via INFO memory (ahe_alpha, ahe_last_hit_ratio).

The flat line is a fixed-weight policy for reference; AHE's line shows the self-tuning excursion and settle.

---

7. Configuration & Observability

Enable AHE with a single flag — no algorithm-specific tuning required:

./ferrum-kv --maxmemory 256mb --maxmemory-policy allkeys-ahe
# or the TTL-scoped variant:
./ferrum-kv --maxmemory 256mb --maxmemory-policy volatile-ahe

Knob	Default	Notes
maxmemory-policy	noeviction	set allkeys-ahe / volatile-ahe to enable
maxmemory-samples	5	candidates sampled per eviction (shared with *-lru/*-lfu)
step / window_size / direction	0.05 / 64 / +1	internal, via AdaptiveHybridState::default()

Watch the controller converge in real time:

$ redis-cli -p 6380 INFO memory
# Memory
used_memory:268435456
maxmemory:268435456
maxmemory_policy:allkeys-ahe
ahe_alpha:0.71
ahe_last_hit_ratio:0.94

---

8. Further Reading

• Implementation: src/storage/eviction.rs — eps_score, pick_victim_ahe, AdaptiveHybridState
• Full design discussion: Whitepaper §9.5
• Try it live: the built-in dashboard plots ahe_alpha as the workload changes.