BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210808T235336Z
LOCATION:Room A
DTSTART;TZID=America/Chicago:20210810T114500
DTEND;TZID=America/Chicago:20210810T120000
UID:icpp_ICPP 2021_sess113_pap397@linklings.com
SUMMARY:Efficient Modeling of Random Sampling-Based LRU
DESCRIPTION:Conference Paper\n\nEfficient Modeling of Random Sampling-Base
d LRU\n\nYang, Wang, Wang\n\nThe Miss Ratio Curve (MRC) is an important me
tric and effective tool for caching system performance prediction and opti
mization. Since the Least Recently Used (LRU) replacement policy is the de
facto policy for many existing caching systems, most previous studies on
efficient MRC construction are predominantly focused on the LRU replacemen
t policy. Recently, the random sampling-based replacement mechanism, as op
posed to replacement relying on the rigid LRU data structure, gains more p
opularity due to its lightweight and flexibility. To approximate LRU, at r
eplacement times, the system randomly selects K objects and replaces the l
east recently used object among the sample. Redis implements this approxim
ated LRU policy. We observe that there can exist a significant miss ratio
gap between exact LRU and random sampling-based LRU under different sampli
ng size K, therefore existing LRU MRC construction techniques cannot be di
rectly applied to random sampling based LRU cache without loss of accuracy
.\n\nIn this work, we present a new probabilistic stack algorithm named KR
R which can be used to accurately model random sampling based-LRU under ar
bitrary sampling size K. We propose two efficient stack update algorithms
which reduce the expected running time of KRR from O(N*M) to O(N*log^2M) a
nd O(N*logM) respectively, where N is the workload length and M is the num
ber of distinct objects. Furthermore, we adopt spatial sampling which furt
her reduces the expected running time of KRR by several order of magnitude
, and enables practical, low overhead online application of KRR.
END:VEVENT
END:VCALENDAR