DLS Talk by Kai Li (Princeton)

Speaker: Dr. Kai Li, Professor, Department of Computer Science, Princeton University

Title:  Designing A Practical Learned Cache

Abstract:

Cache is one of the most important components in hardware, storage and network systems. The key to a cache’s performance is its replacement algorithm to decide which objects to evict to reduce its miss ratio. Current practical algorithms are based on heuristics (e.g. LRU); they work well for some access patterns and poorly for others. Even with five decades of extensive study, there is still a large gap between the heuristic algorithms and an offline optimal algorithm such as Belady’s MIN. A research challenge is to use Machine Learning (ML) to design a learned cache to substantially close this gap.

ML considers the cache replacement as a prediction problem to minimize cache ratios based on past access patterns. To design a practical learned cache system, we must solve several challenging problems. The first is how to train and update an ML model to achieve good prediction accuracies as the cache system runs. The second is how to reduce the prediction overhead for each eviction to be on par with a heuristic algorithm. The third is to find a good tradeoff between the space for ML model and that for cached data, as large model will takes space away from data. The overall goal is to achieve better miss ratios than previous state-of-the-art (SOTA) approaches.

In this talk, I will describe how our group solves these problems in designing two learned cache systems. Both systems achieve substantially lower miss ratios than the SOTA heuristic algorithms with different production workloads. Their prototype implementations achieve similar throughputs to those based on the heuristic algorithms with modest increases in CPU utilizations. We have collaborated with the industry to deploy learned caches to a large content distribution network.

Bio:

Kai Li received his doctorate from Yale University in 1986 and joined Princeton University the same year. He has worked on a wide variety of topics in computer science. In the area of distributed systems, he pioneered techniques that allow users to program using a shared-memory programming model on a cluster of computers. In the area of computer architecture, he developed an efficient protected communication mechanism which evolved into an industry standard, called Infiniband, for efficient data center networking and has been deployed in almost all hyperscale data centers. In the area of storage systems, he co-founded Data Domain, Inc. and pioneered deduplication storage systems for efficient backup and data replication for disaster recovery. The Data Domain’s product line has been the leader (over 60%) of its market segment since 2006. The deduplication technology has allowed the industry to build new generation storage systems. In the area of machine learning and computer vision, he co-led the development of ImageNet knowledge base, which propelled deep learning as the mainstream machine learning method for computer vision as well as numerous application domain. He won seven most influential or test-of-time paper awards in seven different areas in computer science. He was elected as an ACM Fellow, an IEEE Fellow, and a member of the US National Academy of Engineering. Li co-founded Asian American Scholar Forum, a nonprofit organization, which is the leading voice of Asian American scholar community to promote academic belonging, openness, freedom and equality for all.

Host:  Dr. Mark Greenstreet, UBC Computer Science