# 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