tinyufo

Active contributors: yuchen

Purpose

The cache admission and eviction algorithm behind pingora-memory-cache. A TinyLFU/S3-FIFO-flavored design — small, fast, and good at handling skewed access patterns without admitting one-off keys.

This is the only crate in the workspace not prefixed with pingora-.

Directory layout

tinyufo/src/
├── lib.rs              TinyUfo top-level API
├── buckets.rs          Storage buckets
└── estimation.rs       Frequency sketch (count-min variant)

Key abstractions

Type	File	What it is
TinyUfo<K, V>	tinyufo/src/lib.rs	The cache structure
Estimation	tinyufo/src/estimation.rs	Frequency sketch — admission filter
Buckets	tinyufo/src/buckets.rs	Three-tier bucket storage (small / main / ghost)

How it works

graph LR
    incoming[Get/Insert]
    estimator[Frequency sketch<br/>estimation.rs]
    small[Small queue]
    main[Main queue]
    ghost[Ghost queue]
    incoming --> estimator
    estimator --> small
    small -->|admitted| main
    small -->|evicted| ghost
    main -->|evicted| ghost
    ghost -->|seen again| main

A frequency sketch tracks "how often have I seen this key" cheaply. New keys go into a small queue; only keys with enough frequency get promoted to the main queue. When the main queue evicts, the key goes to a ghost queue (just a key, no value); if a ghost-listed key is requested again, it gets promoted directly back to the main queue. This keeps churn-y access patterns out of the main store.

The crate ships criterion benchmarks under benches/ and shows competitive numbers against moka and standard LRUs.

Integration points

• Used by pingora-memory-cache.
• Standalone-usable; the README's "Notable crates" calls it out specifically.

Entry points for modification

• Bucket sizing → lib.rs constants.
• Different sketch implementation → estimation.rs.

Key source files

File	Purpose
tinyufo/src/lib.rs	TinyUfo API
tinyufo/src/buckets.rs	Three-tier storage
tinyufo/src/estimation.rs	Frequency sketch
tinyufo/benches/	Criterion benchmarks