Skip to content

ahe.md

Latest commit

 

History

History
316 lines (265 loc) · 17.7 KB

ahe.md

File metadata and controls

316 lines (265 loc) · 17.7 KB
Raw

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.

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.
Adaptive alpha controller one lightweight feedback loop, updated every eviction window observe(hits, misses) per eviction window >= 64? ratio = hits / (hits + misses) ratio regressed? flip direction alpha = clamp(alpha + direction·step) keep alpha yes no yes no

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.

Sampling-based eviction path Redis-style random sampling, plus adaptive scoring maxmemory exceeded sample k random keys score candidates EPS(alpha, key, now) argmax(EPS) victim key evict + observe adjust if full

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).

AHE alpha under a shifting workload illustrative convergence path: LRU bias first, then LFU bias 0.0 0.5 1.0 Eviction window (×64 evictions) alpha AHE self-tuning fixed weight

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