Learning Relaxed Belady for Content Distribution Network Caching
summary
A machine‑learned cache replacement called Relaxed Belady approximates Belady’s MIN by treating all items beyond a chosen time boundary equally and evicting a random sample among them; implemented as Learning Relaxed Belady (LRB) with gradient‑boosted trees, a sliding memory window, 64‑candidate sampling, and online incremental training. Simulator and Apache Traffic Server prototype show 5–24% WAN traffic reduction versus production CDN policies, 30K predictions/sec, 11.7 Gbps throughput, and ~1–3% extra memory overhead; evaluation uses six production traces and a fast good decision ratio metric.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:10Caching Remains Challenging
- 2:28General Overview of our Approach
- 3:22Generate Online Training Data
- 4:26Solutions: Relaxed Belady Algorithm & Good Decision Ratio
- 4:57Challenge: Hard to Mimic Belady (Oracle) Algorithm
- 6:08Introducing the Relaxed Belady Algorithm
- 7:44Good Decision Ratio: Directly Measures Eviction Decisions
- 8:53Evaluate Design Decisions wlo Simulation
- 9:37Past Information
- 9:52Track Objects within a Sliding Memory Window
- 10:33Sample Training Data & Label on Access or Boundary
- 11:18ML Architecture
- 11:36Solution 3: Feature & Model Selection
- 12:26Eviction Candidates
- 13:52Implementation
- 14:15Evaluation Setup
- 16:58Conclusion
related talks
15m3L-Cache: Low Overhead and Precise Learning-based Eviction Policy for Caches
16mGL-Cache: Group-level learning for efficient and high-performance caching
19mLearning Production-Optimized Congestion Control Selection for Alibaba Cloud CDN
11mLearning Cache Replacement with CACHEUS
31mFifty Shades of Caching and How LLMs Paint It Blαck
16mCredence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions
17mCacheSlide: Unlocking Cross Position-Aware KV Cache Reuse for Accelerating LLM Serving
16mHALP: Heuristic Aided Learned Preference Eviction Policy for YouTube Content Delivery...