Efficient admission policies for cache management and heavy hitter detection

26/10/2017 - 12:00
Speaker: 
Seminar: 
מיקום: 
Abstract: 

In this talk, I introduce the often overlooked concept of cache admission policies. Once the cache is full, in order to admit a new item, we need to evict one of the stored items. An admission policy decides if the new item should be admitted to the cache. I will present two admission policies that enhance performance in different fields. The TinyLFU cache admission policy uses past frequency to estimate the benefit of data items. This policy is implemented in the Caffeine high-performance Java library and is used by many open source projects such as Apache Cassandra, Apache Accumulo, JBoss Infinispan, Druid, Neo4J, Spring, to name a few. It is also used in industry by companies such as Google, Netflix, and Linkedin. Alternatively, the RAP admission policy is a randomized streaming algorithm for finding the most frequent items. In RAP, we use a coin flip to decide if a new item should be admitted to the cache. This approach improves the space to accuracy ratio of state of the art algorithms by up to x32 on real traces and up to x128 on synthetic ones.