website statistics

S3-FIFO

Scalable and Efficient Cache Eviction

Efficient: up to 72% lower miss ratio than LRU

Robust: evaluated on 6594 workloads from 12 companies

Scalable: NO locking

Simple: FIFO queues only

Flash-friendly: sequential writes only

Published at SOSP ’23

Learn More Paper Watch Video Slides

How does S3-FIFO work?

Simple and Scalable caching with three Static FIFO queues

Animation of S3-FIFO: requests enter a small FIFO queue; objects requested again move to the main queue, the rest are evicted and remembered in a ghost queue.
  1. New objects enter a small FIFO queue that holds about 10% of the cache.
  2. When the small queue is full, its oldest object moves to the main queue if it was requested again; otherwise it is evicted, and only its key is kept in a ghost queue.
  3. A miss on a key in the ghost queue inserts the object straight into the main queue.
  4. The main queue evicts from its tail but gives objects that were reused another pass. A hit only bumps a small counter, so nothing is locked or moved on the hot path.

How good is S3-FIFO?

S3-FIFO reduces your LRU cache size by 46% and improves the throughput by 6x

* target miss ratio 10%, 16 threads

How to use

# 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

In your language

Production cache libraries that implement S3-FIFO.

Why does S3-FIFO work?

A huge number of objects accessed once (called one-hit wonders) calling for quick demotion:
S3-FIFO quickly removes objects that will not be accessed in the future

Figure shows that most of the objects evicted by LRU spend long time in the cache without reuse.

Adoption

Systems running S3-FIFO

Running S3-FIFO-like eviction through quick_cache — its README names S3-FIFO; its docs call it a Clock-PRO variant “very similar to” S3-FIFO

In progress upstream — open pull requests and proposals

Designs inspired by S3-FIFO

More implementations

Discussed and written about

Shipped S3-FIFO somewhere? Tell us — we would love to list you, and to hear how it went.

Acknowledgement

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


Dataset source:
Twitter, Meta, Tencent, Microsoft, Wikimedia, CloudPhysics

Contact Us

More from cacheMon: SIEVE · libCacheSim · cachemon.org

Home