pingora-lru

Active contributors: yuchen, fdeng

Purpose

A sharded, fixed-capacity LRU cache. Used internally by pingora-pool and exposed for direct use. The standard lru crate has a single-mutex hot path; this implementation shards by key hash so concurrent gets/puts on different keys don't contend.

Directory layout

pingora-lru/src/
├── lib.rs              Lru, sharded API
└── linked_list.rs      Intrusive doubly-linked list used per shard

Key abstractions

Type	File	What it is
Lru<K, V>	pingora-lru/src/lib.rs	The sharded LRU
LinkedList	pingora-lru/src/linked_list.rs	Index-based intrusive list

How it works

Keys hash to one of N shards. Each shard owns a HashMap and a LinkedList<Node>. Standard LRU operations (get, insert, evict) happen entirely within one shard, holding only that shard's mutex. The result is roughly N-fold throughput improvement under contention compared to a single-mutex LRU.

The intrusive doubly-linked list (linked_list.rs) avoids per-node allocation — nodes are slab-allocated in the shard and reference each other by index.

The bench_lru benchmark (in benches/, updated d41a66b Apr 2026) was rewritten using production-scale data to be more representative. There's a promote_top_n warning in the docs noting that promoting every hit is expensive and the prod system uses an "only promote occasionally" heuristic.

Integration points

• Used by pingora-pool for its idle-connection LRU.
• Used by pingora-cache's eviction modules.
• Standalone-usable.

Entry points for modification

• Number of shards → constructor.
• Different LRU policy (e.g. SLRU, MQ) → would need a new module here or in pingora-cache/eviction.

Key source files

File	Purpose
pingora-lru/src/lib.rs	Lru<K, V> and shard logic
pingora-lru/src/linked_list.rs	Intrusive list