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

* appear in SOSP'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 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

Google, VMware, Redpanda, Cloudflare, Risingwave, Deep Graph Library, MatrixOne, and uap-python,

mulitple large open-source libraries, such as otter (Golang), surrealkv (Rust), quick-cache (Rust), spica (Javascript), foyer (Rust),
and many other cache libraries in Golang [1], [2], Python [1], Rust [1], [2], [3], [4], C++ [1], [2], Java [1], [2], Zig [1], Javascript [1].

Discussed in Aleksey's Online Reading Group, UIUC CS525.

Covered in blog [1], [2], [3], [4] in Korean, [5] in Japanese, [6] in Russian, newsletters [1], [2], conference in Korea, [2]

let us know if you would like to be featured here.

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

Home