website statistics
SOSP ’23 FIFO queues are all you need for cache eviction

S3-FIFO

Simple and Scalable caching with three Static FIFO queues

Most objects in a cache are never requested again. S3-FIFO lets them go soon after they arrive, so the space goes to objects that are reused, and a hit only bumps a two-bit counter, with no lock.

See it run Paper Talk Slides Code
72%
lower miss ratio than LRU, at best
6×
the throughput of optimized LRU at 16 threads
6,594
traces from 14 datasets in the evaluation
10 of 14
datasets where it has the lowest mean miss ratio

S3-FIFO runs in

  • Cloudflare
  • Google
  • VMware
  • Amazon Dynamo
  • Redpanda
  • InfluxDB
  • RisingWave
  • Apache Traffic Server
  • YDB
See every adopter

How it works

Filter new objects first, then keep the ones that are reused

New objects wait in a small queue. Most are never requested again and leave quickly. Objects that are reused move on to the main queue, which keeps them for as long as they keep getting hits.

Next requests
    Hits
    0
    Misses
    0
    Miss ratio
    –
      Objects enter each queue on the left and leave on the right. The dots under a letter count its hits, up to three. The demo uses tiny queues, and gives S a larger share than the usual 10%, so that every move is easy to follow.
      1. S

        New objects start small

        S holds about 10% of the cache. An object hit twice while in S moves to M; the rest are evicted as soon as S needs room. This is quick demotion.

      2. G

        Evicted keys are remembered

        G keeps only the keys of objects evicted from S, as many as M holds. A key requested again while it is in G goes straight into M.

      3. M

        Reused objects go around again

        When M needs room, it checks its oldest object: with a counter above zero, it is reinserted with the counter lowered by one (lazy promotion); otherwise it is evicted.

      4. 2 bits

        Hits touch two bits

        A hit increments a counter capped at 3 with one atomic update. Nothing moves and nothing locks on the hot path, so S3-FIFO scales with threads.

      Results

      Fewer misses, smaller caches, more throughput

      We compared S3-FIFO with 12 state-of-the-art algorithms on 6,594 traces from 14 datasets. It has lower miss ratios overall, and the lowest mean miss ratio on 10 of the 14 datasets.

      Mean miss ratio

      Five datasets, lower is better.

      Data table

      Up to 46% less cache

      Cache space saved compared with LRU

      For the same 10% miss ratio.

      Data table

      Scales with threads

      Throughput, in million operations per second

      A hit never takes a lock, so more threads give more throughput.

      Data table

      Why it works

      Most objects are never reused

      Cache workloads are skewed, and a cache only ever sees a short stretch of requests. In that stretch, most objects are requested once: with a cache at 10% of a trace’s footprint, about 72% of objects are not reused before they are evicted.

      LRU keeps each of these one-hit wonders for a full trip through the queue. S3-FIFO’s small queue lets them go after a short stay, which leaves the main queue to the objects that earn their place.

      Objects LRU evicts without a single reuse

      Share of evicted objects, by cache size as a fraction of the objects in the trace.

      Data table

      Use it

      Try it in a few lines

      Experiment with the Python package, pick a production library in your language, or replay your own traces in libCacheSim.

      example.py
      pip install cachemonCache 
      from cachemonCache import S3FIFO

# A cache that holds up to 1,000 objects
cache = S3FIFO(cache_size=1000)

# Add an object; it expires after 60 seconds
cache.put("key", "value", ttl_sec=60)

# Look it up
print(cache.get("key"))   # value
print("key" in cache)     # True

# Remove it
cache.delete("key")
print(cache.get("key"))   # None

# It also behaves like a dict
cache["answer"] = 42
print(cache["answer"])    # 42

      Production libraries

      libCacheSim Compare S3-FIFO with other eviction algorithms on your own traces.

      Adoption

      Running in real systems

      S3-FIFO and close variants of it run in proxies, databases, storage engines and stream processors. Each entry links to the code, pull request or docs that show it.

      Systems running S3-FIFO 19

      Running S3-FIFO-like eviction through quick_cache 20

      Its README names S3-FIFO; its docs call it a Clock-PRO variant “very similar to” S3-FIFO.

      In progress upstream 5

      Open pull requests and proposals.

      Designs inspired by S3-FIFO 2

      Their own designs, built on its ideas.

      More implementations 12

      Discussed and written about 12

      Supported by

      Carnegie Mellon University, Parallel Data Laboratory, Emory University, SimBioSys Lab, Meta, Google Cloud, AWS, Microsoft Azure, CloudLab, the Sloan Foundation, VMware and NSF.

      Traces from

      Twitter, Meta, Tencent, Microsoft, Wikimedia and CloudPhysics.

      Shipped S3-FIFO, or have a question?

      We would love to list you, and to hear how it went.

      Email us Slack X / Twitter GitHub

      More from cacheMon: SIEVE · libCacheSim · cachemon.org

      Home