LRU list LRU extended with dataless “ghost” entries Trausti

Trausti Saemundsson
Reykjavik University
Hjortur Bjornsson
University of Iceland
Gregory Chockler
University of London,
Royal Holloway
Ymir Vigfusson
Emory University
Dynamic Performance Profiling of Cloud Caches
Cache server
MIMIR
Item-to-bucket
mapping
Get/Set(e)
Replacement
algorithm
Hit(e)
HRC estimator
Ghost list/ghost filter
Miss(e)
Set(e)
Export-HRC()
𝒆𝟏 𝒆𝟐 ⋯ 𝒆𝑵
Aging policy
Evict(e)
ROUNDER
Hit rate of
current
allocation
Cumuluate hit rate
Hit rate curve (CDF)
1
STACKER
0,5
0
0
5000
10000
Cache size (items)
(answers “what if” questions)
B Buckets
1
2
g,h,u
f
e,r,t
Estimated # of hits
LRU list
Bucket #0
LRU extended with dataless “ghost” entries
3
b,c,d,a
(i) LRU list before
hit on item e
(ii) PDF update
Hit rate curve
(PDF)
Stack distance
e
e,g,h,u
f
g,h,u
f
r,t
b,c,d,a
r,t,b,c,d,a
(iii) After request
(iv) After aging
>96%
accuracy
using
standard
traces
Buckets (B) MAE
8 1.2%
16 0.6%
32 0.4%
64 0.3%
128 0.3%
>98% accuracy on
memcached YCSB
High throughput in
memcached

Download Report