Skip to content

lhd.md

Latest commit

 

History

History
32 lines (25 loc) · 1.35 KB

lhd.md

File metadata and controls

32 lines (25 loc) · 1.35 KB
Raw

LHD (Learning Hit Density)

Goal

Maximize value per byte by using a learned estimate of hit probability over remaining lifetime, especially when object sizes vary substantially.

Core Idea

LHD estimates each object's future hit density (roughly expected future hits per byte over a horizon) from observed reuse behavior. Eviction prefers entries with the lowest estimated hit density.

Compared to simple size-aware scoring, LHD adapts estimates from workload data instead of relying on fixed formulas.

Core Data Structures (Typical)

  • Hash index K -> EntryMeta
  • Size-aware entry metadata (size, age/timestamp, access stats)
  • Lightweight learned model/state (bucketized statistics tables)
  • Victim selector keyed by estimated hit density

Complexity & Overhead

  • Higher implementation complexity than GDS/GDSF
  • Additional memory for model tables and per-entry predictors
  • Runtime cost depends on estimator complexity (can be O(1) with table lookups)

Notes For CacheKit

  • High-value candidate for byte hit rate optimization and heterogeneous object sizes.
  • Start with coarse bucketed estimators to keep hot paths predictable.
  • Benchmark against GDS, GDSF, and Hyperbolic on mixed-size traces.

References

  • Beckmann et al. (2018): “LHD: Improving Cache Hit Rate by Maximizing Hit Density”, USENIX OSDI 2018 paper with follow-up implementations.