Framing
An inference server serves an embedding cache to many worker threads at once. The design goal is: reads (the hot path, one per inference request) should almost never block, writes (a cache miss that computes a new embedding, or an eviction) can be a little slower, and the eviction policy has to stay approximately correct under concurrent access without a single global lock serializing every request.
Sharded structure
Split the keyspace into N shards (a power of two, say 64), each shard owning:
- its own hash map from key to embedding vector
- its own bounded LRU (least recently used) list, or a segmented LRU (a "probationary" segment for first-time hits and a "protected" segment for keys accessed more than once, which resists single-hit cache pollution better than plain LRU)
- its own lock, sized so that under N worker threads the odds of two threads wanting the same shard at once stay low:
shard = hash(key) & (N-1), with the hash pre-mixed (e.g. a 64-bit multiply-xor) so keys with similar prefixes don't collapse onto the same shard.
Sharding turns one global lock into N independent locks, so throughput scales close to linearly with shard count until the workload becomes skewed toward a few hot keys.
Lock-free read path
Within a shard, a full mutex around every read is often still too expensive at inference QPS (queries per second). Two ways to make reads effectively lock-free:
- Immutable value + atomic reference swap. Each embedding vector is immutable once published. A read is just
AtomicReference.get() (Java), std::atomic<std::shared_ptr<T>>::load() (C++20), or in Rust a load from an ArcSwap<T> (the arc-swap crate). Rust's standard library deliberately offers no generic Atomic<T>, only atomics over integers, bools and raw pointers (AtomicPtr): atomically publishing a reference-counted handle has to adjust the refcount at the same instant it swaps the pointer, which a single machine-word swap cannot do on its own, so ArcSwap (or a Mutex<Arc<T>> if you can tolerate the lock) is what actually provides that operation. A write publishes a brand-new vector by swapping the pointer with a compare-and-swap (CAS), never mutating in place. Readers never see a torn (partially-written) vector because the object they read is never mutated after publication.
- Read-copy-update (RCU) style epochs for the LRU metadata itself: readers bump a lightweight "recency" counter (or just log the access to a small per-thread ring buffer that a background thread periodically drains into the real LRU list) instead of taking a lock to reorder the list on every hit. This trades slightly stale recency information for zero read-side locking, which is the right trade for eviction bookkeeping (being a few hundred milliseconds stale about which key is "most recent" almost never matters; blocking a read path for it does).
Memory consistency
The subtle bug to avoid is publishing a reference to an object before its fields are fully written (unsafe publication). In Java that means either making the vector's backing array final and assigning it in the constructor, or publishing through a volatile/AtomicReference write, both of which establish a happens-before edge so any thread that reads the reference also sees every write that happened before the publish. In C++, the equivalent is std::atomic<std::shared_ptr<T>> (or a raw pointer published with memory_order_release, read with memory_order_acquire). Skipping this is a real, hard-to-reproduce bug class: a reader can otherwise observe a vector object whose float array is still zero-filled.
Worked example
64 shards, 10,000 embeddings per shard (640,000 total, roughly 2 KB per 512-dim float32 vector plus key overhead, so about 1.3 GB resident). A batch of 256 concurrent inference requests hashes almost uniformly across shards, so the expected number of requests contending for the same shard's lock at once is about 256/64 = 4, versus 256 with one global lock. Combined with lock-free reads inside the shard, the only threads that actually block each other are the rare pair that both miss on the same key in the same shard at the same moment.
Trade-offs and edge cases
- Segmented/sharded LRU is only approximately globally-LRU-correct: a key that's genuinely least-recently-used across the whole cache might not be the least-recently-used within its own shard. This is normally an acceptable approximation (Redis's own eviction sampling makes the same trade).
- A single embarrassingly hot key (e.g. a popular query re-embedded by every request) still serializes on its one shard's lock. Mitigate by giving very hot keys a small per-thread or per-core "L0" cache in front of the shared cache, invalidated on write.
- On miss, use a per-key mutex or single-flight/coalescing so 50 threads that miss on the same key at once trigger one embedding computation, not 50 (this also protects the origin embedding model from a cache-stampede-style pile-on).
- Resizing the shard count later requires a full rehash; plan capacity up front or accept a migration window.
