# AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network ### Presentation * CDN Caching Architecture * Users, content providers, CDN is a layer in between (caching servers which store the popular objects) * Two caching levels * Disk Cache (DC): slower * Hot Object Cache (HOC): in memory, faster * HOC performance metric: object hit ratio = # of reqs served by HOC / tot # reqs * Goal: maximize OHR * Prior approaches to cache management * Frequent decisions required * What to admit * Admit all the requests into the cache * What to evict: most of the prior work * LRU * Mixtures of LRU / LFU * Concurrent LRU (boost caching system throughput) * We are missing a key issue * Not all objects are the same (object size distribution) * 9 orders of magnitude of variability * Should we admit every object? * HOC is small. Favor what? How to do it well? * Academic works (equal sizes) * Size-aware admission * Fixed size threshold: admit if size < Threshold c * How to pick c? Pick c to maximize OHR * The c is different at different times (morning, noon, evening) * The best threshold changes with the traffic mix * Probabilistic admission * High admission probability for small objects, low admission probability for large objects * But many curves, which curve makes big difference (adapt c) * The AdaptSize Caching System: focus on admission to the cache, and continuously adapts the parameter of size-aware admission * Adapt with traffic, adapt with time * Take traffic measurements --> calculate the best c --> enforce admission control * Red, green, and blue curve in the evening * Delta interval, fnid the best c within each delta interval * Traditional approach * Hill climbing: local optima on OHR-vs-c curve * AdaptSize approach: Markov model to predict the curve, enables speedy global optimization * How AdaptSize gets the OHR-vs-c curve * Markov chain * Track IN/OUT for each object * IN: hit, OUT: miss * Algorithm * For every delta interval and for every value of c * Use Markov chain to solve for OHR(c) * Find c to maximize OHR * Why hasn't this been done? too slow with exponential state * New technique: approximation with linear state space * Implementing AdaptSize * Incorporated into Varnish * Highly concurrent HOC system, 40+ Gbits / s * Take traffic measurements --> calculate the best c --> enforce admission control * Challenges * 1\) Concurrent write conflicts: 40% requests concentrate on 1% object * 2\) Locks too slow * AdaptSize: producer/consumer + ring buffer, lock-free implementation * AdaptSize: admission is very simple * Given c, and the object size * Admit with P(c, size): probability * Enables lock free & low overhead implementation * Testbed * Clients: replay Akamai requests trace * HOC systems: 1.2 GB, 16 threads * Evaluate * unmodified Varnish: admit everything, evict based on concurrent LRU * NGINX cache: frequency filter to admit, LRU to evict * AdaptSize * Also evaluate robustness of AdaptSize * Artificial traffic mix changes * Compare * Size-aware OPT: offline parameter tuning * AdaptSize: our Markovian tuning model * HillClimb: local-search using shadow queues Conclusion: * Goal: maximize OHR of the Hot Object Cache * Approach: size-based admission control * Key insight: need to adapt parameter c * AdaptSize: adapts c via a Markov chain * Result: 48-92% higher OHRs * Paper: throughput, disk utilization, byte hit ratio, request latency --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sliu583.gitbook.io/blog/specific-work/wisr-group/cache/index/adaptsize-orchestrating-the-hot-object-memory-cache-in-a-content-delivery-network.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.