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: only FIFO queues

Flash-friendly: to come

* To appear in SOSP'23 and SNIA SDC'23

How does S3-FIFO work?

Simple and Scalable caching with three Static FIFO queues

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


from cachemonCache import S3FIFO

# Create a cache backed by DRAM
cache = S3FIFO(size=10) # or cache=LRU(size=10)         

# Add an object to the cache
cache.put("key", "value", ttl=10)

# Get an object from the cache
cache.get("key")
print(value) # Outputs: "value" or None

# Remove an object from the cache
cache.delete("key")

# Check if an object is in the cache
cache.has("key")
print(exists)  # Outputs: False


const { S3FIFO } = require('cachemonCache');           

// Create a cache backed by DRAM
const cache = new S3FIFO({ size: 10 }); 

// Add an object to the cache
cache.put("key", "value", { ttl: 10 });

// Get an object from the cache
const value = cache.get("key");
console.log(value); // Outputs: "value"

// Remove an object from the cache
cache.delete("key");

// Check if an object is in the cache
const exists = cache.has("key");
console.log(exists); // Outputs: false

More languages to come!

Why does S3-FIFO work?

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

Adoption

To come ...

Acknowledgement

Sponsors:
Carnegie Mellon University Parallel Data Laboratory Emory University SimBioSys Lab
Meta, Google, AWS, Microsoft, CloudLab, NSF

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

Home