The University of Arizona

Events & News

CS Colloquium

DateThursday, February 4, 2016
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 10:45am, Gould-Simpson, 9th floor atrium.

Faculty Host: Dr. David Lowenthal
SpeakerYmir Vigfusson
AffiliationAssistant Professor of Mathematics and Computer Science at Emory University

Dynamic Performance Profiling of In-Memory Caches

Large-scale in-memory object caches such as memcached are widely used to accelerate popular web sites and to reduce burden on backend databases. Yet operators still have limited visibility into how these caches should be set up to optimally accommodate the workloads at hand. How much would the cache performance improve from additional cache space, or by adding more cache servers to the pool? Resources come at a cost, so to what extent would user request latency deteriorate if cache memory is repurposed for a different service?

In this talk, I'll focus on several research questions pertaining to large-scale distributed caches. In particular, I'll home in on the challenge of providing online monitoring of the cost and benefits of memory space in a large-scale cache, enabling cache operators to answer these questions without requiring trace collection and manual offline tuning. In our work, we introduce general and efficient algorithms for dynamically estimating hit rate curves -- histograms of cache hit rate as a function of memory size -- which can be plugged into cache replacement policies such as LRU.

Extensive simulations on cache benchmarks indicate that our methods provide accurate estimates of hit rate at different cache sizes. Our experiments on an implementation of our methods in memcached showed that hit rate curves were dynamically estimated at over 98% accuracy with only a small drop in throughput. The results are encouraging and suggest that exposing hit rate curves can be a practical method for improving provisioning and metering of large-scale caches.

This is joint work with Trausti Saemundsson at CloudPhysics and Gregory Chockler at the University of London, Royal Holloway.


Ymir Vigfusson is Assistant Professor of Mathematics and Computer Science at Emory University since 2014, Assistant Professor at the School of Computer Science at Reykjavik University since 2011, and a co-founder and Chief Science Officer of the offensive security company Syndis since 2013. Ymir completed his Ph.D. in Computer Science at Cornell University (2010) with focus on Distributed Systems and minor in music composition, where his dissertation was nominated for the ACM Doctoral Dissertation Award. His work is partially supported by an NSF CAREER award and grants from the Icelandic Center for Research. Ymir's primary research interests are on distributed data replication, data science and security. His website is