Learning Relaxed Belady

for Content Delivery Network Caching

NSDI 2020

CDN Caching Goal: Minimize WAN Traffic

2

Wide Area Network (WAN)

traffic is expensive

Key metric byte miss ratio:

Caching Remains Challenging

Heuristic-based algorithms (1965–): LRU, LRUK, GDSF, ARC, ...

• Work well for some workloads, but work poorly for other

ML-based adaptation of heuristics (2017–): UCB, LeCAR, ...

• Also work well for some workloads, but poorly for others

Belady’s MIN algorithm (1966)

• Oracle: requires future knowledge
• Large gap in byte miss ratio between state-of-the-art and Belady:

• 20–40% on production traces

3

Introducing Learning Relaxed Belady (LRB)

​

New approach: mimic Belady using machine learning

​

​

4

General Overview of our Approach

5

Challenge 1: Past Information

6

What past information to use?

Past information

ML architecture

Training data

Eviction candidates

More data improves training but increases mem overhead

Challenge 2: Generate Online Training Data

7

What past information to use?

Generate online training data?

Past information

ML architecture

Training data

Eviction candidates

Challenge 3: ML Architecture

8

What past information to use?

Generate online training data?

What ML architecture to select?

Past information

ML architecture

Training data

Eviction candidates

Large design space: �features, model, prediction target, loss function

​

Challenge 4: Eviction Candidates

9

Past information

ML architecture

Training data

Eviction candidates

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Challenge 5: Quickly Evaluate Design Decisions

10

End-to-end evaluation: days

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Past information

ML architecture

Training data

Eviction candidates

Solutions: Relaxed Belady Algorithm & Good Decision Ratio

11

End-to-end evaluation: days

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Relaxed Belady algorithm

Good decision ratio

Solutions: Relaxed Belady Algorithm & Good Decision Ratio

12

Relaxed Belady algorithm

Good decision ratio: mins

End-to-end evaluation: days

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Solutions: Relaxed Belady Algorithm & Good Decision Ratio

13

End-to-end evaluation: days

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Relaxed Belady algorithm

Good decision ratio: mins

Challenge: Hard to Mimic Belady (Oracle) Algorithm

Mimicking exact Belady is impractical

• Need predictions for all objects → prohibitive computational cost
• Need exact prediction of next access → further prediction are harder

Belady: evict object with next access farthest in the future

14

Introducing the Relaxed Belady Algorithm

Observation: many objects are good candidates for eviction

Relaxed Belady evicts an objects beyond boundary

• Do not need predictions for all objects → reasonable computation
• No need to differentiate beyond boundary → simplifies the prediction

15

Good Decision Ratio: Directly Measures Eviction Decisions

Insight: relaxed Belady enables evaluating eviction decisions

Good decision ratio:

16

Challenge 5: Quickly Evaluate Design Decisions

17

End-to-end evaluation: days

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Past information

ML architecture

Training data

Eviction candidates

Evaluate Design Decisions w/o Simulation

Evaluate designs on log using good decision ratio in minutes

18

Challenge 1: Past Information

19

ML architecture

Training data

Eviction candidates

More data improves training but increases mem overhead

Past information

What past information to use?

Track Objects within a Sliding Memory Window

Per object features

Only track objects within memory window

Window size is LRB’s main hyperparameter

​

20

Sliding memory window mimics Belady boundary

Challenge 2: Training Data

21

What past information to use?

Generate online training data?

Past information

ML architecture

Training data

Eviction candidates

Sample Training Data & Label on Access or Boundary

Per object features

Unlabeled training data

Labeled training data

22

Sliding memory window

Challenge 3: ML Architecture

23

Large potential design space

What past information to use?

Generate online training data?

What ML architecture to select?

Past information

ML architecture

Training data

Eviction candidates

Solution 3: Feature & Model Selection

Gradient boosting decision trees

Lightweight & high good decision ratio

Training ~300 ms, prediction ~30 us

Use good decision ratio to evaluate new designs

24

Challenge 4: Eviction Candidates

25

Past information

ML architecture

Training data

Eviction candidates

How to select evict candidates?

What past information to use?

Generate online training data?

What ML architecture to select?

Solution 4: Random Sampling for Eviction

Can mimic relaxed Belady if we can�find 1 object beyond the boundary

k=64 candidates; more does not improve �good decision ratio

26

Learning Relaxed Belady

27

Implementation

• Simulator implementation
• LRB + 14 other algorithms
• Prototype implementation
• C++ on top of production system (Apache Traffic Server)
• Many optimizations

28

Evaluation Setup

• Q1: Learning Relaxed Belady (LRB) traffic reduction vs state-of-the-art
• Q2: overhead of LRB vs CDN production system
• Traces: 6 production traces from 3 CDNs
• Hyperparameter (memory window/model/...) tuned on 20% of trace

29

LRB Reduces WAN Traffic

30

20% traffic reduction over B-LRU

10% reduction over the best SOA

Wikipedia trace

LRB Consistently Improves on the State of the Art

31

Wikipedia

LRB Overhead Is Modest

Throughput: 11.7 Gbps vs 11.7 Gbps (unmodified)

Memory overhead=1‒3% cache size

Peak CPU: 16% vs 9% (unmodified)

32

Conclusion

• LRB reduces WAN traffic with modest overhead
• Key insight: relaxed Belady

→ Simplifies machine learning & reduces system overhead

→ Good decision ratio enables fast design evaluation & design iteration

Code & Wikipedia trace: https://github.com/sunnyszy/lrb

33

34

Learning Relaxed Belady

35