Skip navigation
Please use this identifier to cite or link to this item:
Title: Unifying Caching Objectives with Learning Relaxed Belady
Authors: Cheng, Audrey
Advisors: Lloyd, Wyatt
Department: Operations Research and Financial Engineering
Certificate Program: Engineering and Management Systems Program
Class Year: 2020
Abstract: Caching is crucial to the end-to-end performance of distributed systems. By temporarily storing content that is commonly requested so that it can be served more quickly, this technique improves request latency and reduces load on backend servers. There are three objectives in caching: reducing object miss ratio, byte miss ratio, and miss ratio for unit-sized objects, with different objectives being important to different systems. Learning Relaxed Belady (LRB) is an existing machine learning (ML) caching algorithm that achieves substantially better byte miss ratios than other state-of-the-art approaches. In this thesis, we adapt LRB for the other two objectives: object miss ratio and caching for unit-sized objects. Object miss ratio is a crucial metric to a wide range of caches, including CDN in-memory caches and key-value caches for large storage systems. Decreasing object miss ratio translates directly into improved application performance. We apply a novel technique, byte sampling, to LRB that allows it to outperform other methods for object miss ratio. LRB also performs better than other policies for unit-sized traces, demonstrating the broad applicability of this algorithm. We evaluate LRB on 5 production traces and demonstrate its robustness in performance on varying workloads. LRB, enhanced with byte sampling, is the only algorithm we know of that can consistently outperform other state-of-the-art policies for all three caching objectives. We unify these objectives with this algorithm and simplify the method through which further advancements can be made.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Operations Research and Financial Engineering, 2000-2022

Files in This Item:
File Description SizeFormat 
CHENG-AUDREY-THESIS.pdf2.69 MBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.