Doctoral Thesis Oral Defense - Juncheng Yang

— 5:00pm

Location:
In Person and Virtual - ET - Traffic21 Classroom, Gates Hillman 6501 and Zoom

Speaker:
JUNCHENG YANG, Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~juncheny/

Designing Efficient and Scalable Cache Management Systems

Software caches have been widely deployed at scale in today's computing infrastructure to improve data access latency and throughput. These caches consume PBs of DRAM at many companies, which necessitates high efficiency --- achieving the same miss ratio with less DRAM consumption. Meanwhile, modern servers have hundreds of cores, making scalability a critical requirement for designing software caches. This thesis explores different approaches to improving the efficiency and scalability of software caches. 

This thesis has two parts. The first part focuses on system designs that allow caches to store more objects in the cache to achieve a low miss ratio. In this part, I will describe three works. First, I will discuss what key-value cache workloads at Twitter look like using a large-scale workload analysis. Second, drawing on insights from the workload study, I will describe the design of Segcache, a TTL-indexed segment-structured key-value cache that quickly removes expired objects, provides tiny object metadata, and enables close-to-linear scalability. Third, I will present C2DN to demonstrate a fault-tolerant CDN cache cluster using erasure coding for low-overhead redundancy. 

The second part focuses on algorithms that allow the cache to store more useful objects in the cache, which is also critical for cache efficiency. First, I will investigate the design of a low-overhead learned cache. Existing caches using machine learning often incur significant storage and computation overheads. I will show that learning on the group level amortizes overheads and accumulates more information for better learning. While GL-Cache is faster than existing learned caches, it is still more complex compared to simple heuristics. In the following chapter, I will discuss two techniques, lazy promotion and quick demotion, which enable us to design simple yet effective eviction algorithms. In the third chapter, I will discuss an example using the two techniques, S3-FIFO, a new eviction algorithm only composed of FIFO queues. In the last chapter, I will present SIEVE, a new eviction algorithm that uses one queue to achieve lazy promotion and quick demotion. SIEVE is simpler than LRU, but achieves state-of-the-art efficiency and scalability.

Thesis Committee: 

Rashmi Vinayak (Chair)
Greg Ganger
Phillip Gibbons
Vijay Chidambaram (University of Texas at Austin)
Ion Stoica (University of California, Berkeley)
 

n Person and Zoom Participation.  See announcement.

Event Website:
https://csd.cmu.edu/calendar/doctoral-thesis-oral-defense-juncheng-yang