Faculty Recruiting Support CICS

Design and analysis of caching systems

02 Sep
Friday, 09/02/2022 2:00pm to 4:00pm
Hybrid - CS 303 & Zoom
PhD Dissertation Proposal Defense
Speaker: Anirudh Sabnis

Abstract: Caching -- a simple yet powerful technique -- has played a pivotal role in improving the performance of a myriad of computer systems from Internet content delivery to CPUs to domain name systems to database systems. A cache improves the performance by storing frequently accessed data locally so that future requests for that data can be served faster. For instance, a Content Delivery Network (CDN) like Akamai deploys hundreds and thousands of edge caches across the globe so that end-user requests are served from a nearby cache and not a remote origin server, thus providing a significant reduction in latency.  The CPU stores recently accessed data and instructions in L1, L2, and L3 caches that provide considerably faster access as compared to the RAM. The efficient use of CPU cycles has enabled CPUs to operate at speeds closer to their potential. Given the prevalence and importance of caches in computing systems, caching has remained an active research area in computer science over the last several decades. In this thesis, we make the following contributions to caching research.

In the first part of the thesis, we identify that the state-of-the-art fault-tolerance mechanism in a CDN cache cluster -- object replication -- is neither efficient nor effective. We develop techniques that harness erasure codes to build a Coded-CDN cache cluster called C2DN that provides efficient and effective fault-tolerance. C2DN obtains a 11\% lower byte miss ratio (efficient) and eliminates unavailability-induced miss ratio spikes (effective).

In the second part of the thesis, we develop synthetic trace generation tools TRAGEN and JEDI that generate synthetic traces that are ``similar" to the original production traces obtained from live Internet caching proxies. The synthetic traces have the same object-level and cache-level properties as the production traces and can substitute the production traces for cache simulations. The production traces are seldom available to the public as they are considered private and proprietary, and the lack of publicly-available production traces has made it difficult for system designers and researchers to test and validate new caching algorithms and architectures. Thus, by developing tools that generate realistic synthetic traces, we overcome a major obstacle in caching research. 

In the last part of this thesis, we design and implement domain-aware cache algorithms that are cognizant of the properties of the content in the cache. We show that a domain-aware cache algorithm performs better than the currently deployed one-size-fits-all cache algorithms such as LRU, FIFO. Specifically, we design and implement two domain-aware cache algorithms GRADES and MM-CACHE that are tailored for recommendation systems and multimedia content delivery, respectively.  A recommendation system responds with a conforming recommendation for a given user profile. However, the recommendation need not be perfect. In such a scenario, the cache can respond with an alternate similar recommendation that matches the user profile rather than fetching the most appropriate recommendation from a remote server. We develop a gradient descent based approximate-caching algorithm that exploits this relaxation to find the most appropriate content to store in the cache. Looking forward, we aim to design and implement cache algorithms for a multimedia delivery system. The cache can perform super-resolution and down-sampling on locally available media content on-the-fly to serve a request rather than obtaining the requested content from a remote server.  

Advisor: Ramesh Sitaraman

Join via Zoom