AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network

https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/berger

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