The Taub Faculty of Computer Science Events and Talks

In this talk, I introduce a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate.

Realizing this concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and light-weight as it builds upon Bloom filter theory.

I will present a study of the properties of TinyLFU through simulations of both synthetic workloads as well as multiple real traces from several sources. These simulations exhibit the performance boost obtained by enhancing various replacement policies with the TinyLFU eviction policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU will be prese nted. W-TinyLFU will be demonstrated to obtain equal or better hit-ratios than other state of the art replacement policies (including ARC and LIRS) on these traces. It is the only scheme to obtain such good results on all traces. An open source implementation of TinyLFU and W-TinyLFU is available as part of the Caffeine Java 8 high performance caching library.

* Joint work Gil Einziger and Ben Manes.

Bio:
Roy Friedman is an associate professor in the department of Computer Science at the Technion - Israel Institute of Technology. His research interests include Distributed Systems and Networking with emphasis on Fault-Tolerance, Consistency, Caching and Mobile Computing. Roy Friedman serves as associate editor for IEEE TDSC and has served as PC co-chair for ACM DEBS, ACM SYSTOR and Autonomics, as well as vice chair for IEEE ICDCS and EuroPar. Formerly, Roy Friedman was an academic specialist at INRIA (France) and a researcher at Cornell University (USA). He is a founder of PolyServe Inc. (acquired by HP) and holds a Ph.D. and a B.Sc. from the Technion.