"Designing efficient and scalable cache management systems"

Abstract

Software-managed caches have been ubiquitously deployed in today's system infrastructure. From personal devices to servers on the edge and the cloud, these caches speed up data access, reduce data movement, and avoid repeated computation. However, they consume a huge amount of resources, i.e., DRAM and CPUs. 
 
In this talk, I will discuss how to design efficient and scalable cache systems. In the first part, I will demonstrate that the efficiency of a key-value cache is not only determined by the eviction algorithm but also by other components, e.g., storage layout and expiration design. I will then describe how I designed Segcache to reduce memory footprint by up to 60% and increase throughput by 8x compared to state-of-the-art systems. Segcache has been adopted for production at Twitter and Momento. 
In the second part, I will introduce a surprising new finding from our largest-scale eviction algorithm study: FIFO queues are all we need for cache eviction. I will then describe S3-FIFO, a new cache eviction algorithm that is simpler, more scalable, and more efficient than state-of-the-art algorithms. S3-FIFO has been adopted for production at Google, VMWare, Redpanda, and several others. 
Finally, I will describe my future work on building efficient, performant, and robust data systems. 

 
Biography

Juncheng Yang (https://junchengyang.com) is a 6th-year Ph.D. student in the Computer Science Department at Carnegie Mellon University. His research interests broadly cover the efficiency, performance, reliability, and sustainability of large-scale data systems.
 
Juncheng's works have received best paper awards at NSDI'21, SOSP'21, and SYSTOR'16. His OSDI'20 paper was recognized as one of the best storage papers at the conference and invited to ACM TOS'21. Juncheng received a Facebook Ph.D. Fellowship in 2020, was recognized as a Rising Star in machine learning and systems in 2023, and a Google Cloud Research Innovator in 2023.

His work, Segcache, has been adopted for production at Twitter and Momento. The two eviction algorithms he designed (S3-FIFO, SIEVE) have been adopted for production at Google, VMware, Cloudflare, Redpanda, and many others with over 20 open-source libraries available on GitHub. Moreover, the open-source cache simulation library he created, libCacheSim, has been used by almost 100 research institutes and companies.

"Simpler Machine Learning Models for a Complicated World"

Abstract

While the trend in machine learning has tended towards building more complicated (black box) models, such models have not shown any performance advantages for many real-world datasets, and they are more difficult to troubleshoot and use. For these datasets, simpler models (sometimes small enough to fit on an index card) can be just as accurate. However, the design of interpretable models is quite challenging due to the "interaction bottleneck" where domain experts must interact with machine learning algorithms.

I will present a new paradigm for interpretable machine learning that solves the interaction bottleneck. In this paradigm, machine learning algorithms are not focused on finding a single optimal model, but instead capture the full collection of good (i.e., low-loss) models, which we call "the Rashomon set." Finding Rashomon sets is extremely computationally difficult, but the benefits are massive. I will present the first algorithm for finding Rashomon sets for a nontrivial function class (sparse decision trees) called TreeFARMS. TreeFARMS, along with its user interface TimberTrek, mitigate the interaction bottleneck for users. TreeFARMS also allows users to incorporate constraints (such as fairness constraints) easily.

I will also present a "path," that is, a mathematical explanation, for the existence of simpler-yet-accurate models and the circumstances under which they arise. In particular, problems where the outcome is uncertain tend to admit large Rashomon sets and simpler models. Hence, the Rashomon set can shed light on the existence of simpler models for many real-world high-stakes decisions. This conclusion has significant policy implications, as it undermines the main reason for using black box models for decisions that deeply affect people's lives.

This is joint work with my colleagues Margo Seltzer and Ron Parr, as well as our exceptional students Chudi Zhong, Lesia Semenova, Jiachang Liu, Rui Xin, Zhi Chen, and Harry Chen. It builds upon the work of many past students and collaborators over the last decade.

Here are papers I will discuss in the talk:

Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, Cynthia Rudin

Exploring the Whole Rashomon Set of Sparse Decision Trees, NeurIPS (oral), 2022.

https://arxiv.org/abs/2209.08040

Zijie J. Wang, Chudi Zhong, Rui Xin, Takuya Takagi, Zhi Chen, Duen Horng Chau, Cynthia Rudin, Margo Seltzer

TimberTrek: Exploring and Curating Sparse Decision Trees with Interactive Visualization, IEEE VIS, 2022.

https://poloclub.github.io/timbertrek/

Lesia Semenova, Cynthia Rudin, and Ron Parr

On the Existence of Simpler Machine Learning Models. ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT), 2022.

https://arxiv.org/abs/1908.01755

Lesia Semenova, Harry Chen, Ronald Parr, Cynthia Rudin

A Path to Simpler Models Starts With Noise, NeurIPS, 2023.

https://arxiv.org/abs/2310.19726

 
Biography

Cynthia Rudin is the Earl D. McLean, Jr. Professor of Computer Science and Engineering at Duke University. She directs the Interpretable Machine Learning Lab, and her goal is to design predictive models that people can understand. Her lab applies machine learning in many areas, such as healthcare, criminal justice, and energy reliability. She holds degrees from the University at Buffalo and Princeton. She is the recipient of the 2022 Squirrel AI Award for Artificial Intelligence for the Benefit of Humanity from the Association for the Advancement of Artificial Intelligence (the “Nobel Prize of AI”). She received a 2022 Guggenheim fellowship, and is a fellow of the American Statistical Association, the Institute of Mathematical Statistics, and the Association for the Advancement of Artificial Intelligence.

Zoom: https://northwestern.zoom.us/j/95918818964?pwd=TFAzbFVENE9KWXlNYkRNZzI1MXROUT09

CS Department Events

Tuesday, April 9, 2024 & Wednesday, April 10, 2024
8:45AM - 4:30PM 

Mudd 3514
2233 tech Drive, Evanston, IL

Thursday, May 30, 2024
3:00PM - 5:00PM

TBA

Other Events & Opportunities

VentureCat 2024 Applications are Open

Northwestern Medicine Healthcare AI Forum

CS News

NU News