Helping out the middle class (in the cache) with the MITHRIL prefetching algorithm

Seminar | 020 | 15:00

Ymir Vigfusson,

Emory University


The growing pressure on cloud application scalability has accentuated storage performance as a critical bottleneck. Although cache replacement algorithms have been extensively studied, cache prefetching – reducing latency by retrieving items before they are actually requested – remains an underexplored area. Existing approaches to history-based prefetching, in particular, provide too few benefits for real systems for the resources they cost.
My talk will detail MITHRIL: a prefetching layer that efficiently exploits historical patterns in cache request associations.
MITHRIL is inspired by sporadic association rule mining and only relies on the timestamps of requests. Through evaluation of 135 block-storage traces, we show that MITHRIL is effective, giving an average of a 55% hit ratio increase over LRU and PROBABILITY-GRAPH, and a 36% hit ratio gain over AMP at reasonable cost. Finally, I’ll demonstrate the improvement comes from MITHRIL being able to capture mid-frequency blocks.


Ymir Vigfusson is Assistant Professor of Mathematics and Computer Science at Emory University since 2014, Adjunct Assistant Professor at the School of Computer Science at Reykjavik University since 2011, co-founder and Chief Science Officer of the offensive security company Syndis since 2013, and co-founder of the cybersecurity training company since 2017. Ymir completed his Ph.D. in Computer Science at Cornell University in 2010 where his dissertation on “Affinity in Distributed Systems” was nominated for the ACM Doctoral Dissertation Award.
His primary research interests are on distributed systems and caching, having worked on cache replacement in the IBM Websphere eXtreme Scale at IBM Research (2009-2011), and more recently as part of his NSF CAREER program on “Rethinking the Cache Abstraction”. He has published at conferences that include ACM SOCC, USENIX ATC, VLDB and EuroSys, as well as ACM TOCS. Ymir has been the general chair of LADIS (2010-2018), and has served on the program committees of ACM SOCC; ICDCS, EuroSys and P2P, along with others.
When not pondering questions about how to make distributed caching systems on the Internet better, or training hackers and figuring out how to somehow make the world more secure as a result, Ymir spends his time thinking about how to improve disease surveillance (malaria, influenza, food-borne illnesses, funded by the CDC), and how to best write text about himself in third person without coming off as overly ostentatious (even for our times).

For more information: