Low-Level Design: An In-Memory Key-Value Store with TTL

A cache from first principles: a map plus a recency list, TTLs without a timer per key, LRU against sampled and random eviction measured on a Zipf workload, and the stampede that takes your database down.

Every service ends up with a cache in it. Most of them are a map with a mutex, a time.Time field and a hope. This part builds the real thing: a key-value store with expiry and eviction, then measures the design decisions that people argue about.

Three questions drive the whole design, and all three have answers you can measure: how do entries expire without a timer for each one, which entry do you throw away when you’re full, and what happens when a hundred callers miss the same key at once.

Try this first

You write 10,000 keys into a cache, each with a one-second time to live, and never read them again. A minute later, how much memory is the cache using?

Then: your cache holds 1,000 of 10,000 possible keys, and requests follow the usual pattern where a few keys are far more popular than the rest. How much worse is throwing away a random entry than the least recently used one? Write down a percentage.

The data structure

A cache needs two operations to be fast: find a key, and find the entry to evict. A hash map gives the first. For the second, the textbook answer is a doubly linked list in recency order: the most recently used entry at the front, the eviction candidate at the back. Each map value points at its list node, so both Get and Set are constant time.

Our lab’s Go version is exactly that, with the clock injected so expiry can be tested without sleeping:

type entry struct {
	key       string
	value     string
	expiresAt int64 // nanoseconds on the injected clock; 0 means no expiry
}

type Store struct {
	items    map[string]*list.Element
	order    *list.List // front = most recently used
	capacity int
	now      func() int64
	Hits     int
	Misses   int
	Evicted  int
	Expired  int
}

Each language has its own shortcut for the recency list:

• Java gets it free: LinkedHashMap with access order on, plus an override of removeEldestEntry. Ours extends it for brevity, which leaks put and get past the TTL logic; production code should wrap it, not inherit it (Part 8).
• C# has LinkedList<T> and Dictionary<TKey, LinkedListNode<T>>, which is the same structure written out.
• Rust can use a VecDeque or an index-based list; the lru crate does it properly, and takes a NonZeroUsize capacity, so “a cache of size zero” isn’t representable (Part 9).
• Go has container/list.

Here’s the Java version, which is the shortest of the four:

    static final class LruCache extends LinkedHashMap<String, Entry> {
        private final int capacity;
        private final Clock clock;
        int evicted;
        int expired;

        LruCache(int capacity, Clock clock) {
            super(16, 0.75f, true); // true: iteration and eviction order follow access
            this.capacity = capacity;
            this.clock = clock;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Entry> eldest) {
            if (size() > capacity) {
                evicted++;
                return true;
            }
            return false;
        }

The C# one writes the same structure out by hand, with TimeProvider as the clock:

var clock = new TestClock();
var cache = new LruCache(capacity: 3, clock);
cache.Set("a", "1", TimeSpan.FromMilliseconds(100));
cache.Set("b", "2", TimeSpan.Zero);
cache.Set("c", "3", TimeSpan.Zero);
Console.WriteLine($"get a: {cache.Get("a") ?? "miss"}");
cache.Set("d", "4", TimeSpan.Zero);          // over capacity: evicts the least recently used
Console.WriteLine($"get b: {cache.Get("b") ?? "miss"}");
clock.Advance(TimeSpan.FromMilliseconds(150));
Console.WriteLine($"get a after 150 ms: {cache.Get("a") ?? "miss"}");
Console.WriteLine($"entries: {cache.Count}, evicted: {cache.Evicted}, expired: {cache.Expired}");

sealed class TestClock : TimeProvider
{
    private long _ticks;

    public void Advance(TimeSpan by) => _ticks += by.Ticks;

    public override DateTimeOffset GetUtcNow() => DateTimeOffset.UnixEpoch.AddTicks(_ticks);
}

sealed class LruCache(int capacity, TimeProvider clock)
{
    private readonly Dictionary<string, LinkedListNode<Entry>> _items = [];
    private readonly LinkedList<Entry> _order = new();   // first = most recently used

    public int Count => _items.Count;
    public int Evicted { get; private set; }
    public int Expired { get; private set; }

    public string? Get(string key)
    {
        if (!_items.TryGetValue(key, out var node))
        {
            return null;
        }
        if (node.Value.ExpiresAt is { } expiry && clock.GetUtcNow() >= expiry)
        {
            Remove(node);
            Expired++;
            return null;
        }
        _order.Remove(node);
        _order.AddFirst(node);
        return node.Value.Value;
    }

    public void Set(string key, string value, TimeSpan ttl)
    {
        DateTimeOffset? expiresAt = ttl > TimeSpan.Zero ? clock.GetUtcNow() + ttl : null;
        if (_items.TryGetValue(key, out var existing))
        {
            Remove(existing);
        }
        var node = _order.AddFirst(new Entry(key, value, expiresAt));
        _items[key] = node;
        if (_items.Count > capacity)
        {
            Remove(_order.Last!);
            Evicted++;
        }
    }

    private void Remove(LinkedListNode<Entry> node)
    {
        _order.Remove(node);
        _items.Remove(node.Value.Key);
    }

    private sealed record Entry(string Key, string Value, DateTimeOffset? ExpiresAt);
}

It prints:

get a: 1
get b: miss
get a after 150 ms: miss
entries: 2, evicted: 1, expired: 1

And the read path, which is where expiry lives, in Rust. Its recency list is a Vec, so touch is O(n) rather than the O(1) a linked list gives; for a teaching example of the read path that’s fine, and for a real cache it isn’t:

fn get(&mut self, key: &str) -> Option<String> {
    let expired = match self.entries.get(key) {
        None => return None,
        Some(entry) => entry.expires_at.is_some_and(|at| self.now >= at),
    };
    if expired {
        // Lazy expiry: the entry is only noticed when someone asks for it.
        self.remove(key);
        self.expired += 1;
        return None;
    }
    self.touch(key);
    self.entries.get(key).map(|entry| entry.value.clone())
}

All four run the same scenario in our lab, and print the same thing:

get a: 1
get b: miss
get a after 150 ms: miss
entries: 2, evicted: 1, expired: 1

Three keys fit; writing a fourth evicted b, the least recently used, because a had just been read. Then the clock moved past a‘s TTL and the read that found it turned into a miss.

Expiry without a timer per key

The naive design gives every entry a timer. With a million keys that’s a million timers, and a scheduler doing nothing but firing them.

Nobody does this. The two real strategies, in Redis’s own words: “Redis keys are expired in two ways: a passive way and an active way. A key is passively expired when a client tries to access it and the key is timed out.” That’s lazy expiry: a read checks the timestamp and treats an expired entry as a miss.

Lazy expiry alone has a memory problem, which Redis states plainly: “However, this is not enough as there are expired keys that will never be accessed again.” So there’s a second mechanism, active expiry: “periodically, Redis tests a few keys at random amongst the set of keys with an expiration. All the keys that are already expired are deleted from the keyspace.”

Guava draws the distinction that makes a TTL API coherent: an expired entry “may be counted by Cache.size(), but will never be visible to read or write operations”. Logical expiry is a rule on the read path. Physical reclamation is a separate, lazier event.

.NET says the same about MemoryCache, in two sentences that sit oddly together on the same page: “Expiration doesn’t happen in the background. There’s no timer that actively scans the cache for expired items. Any activity on the cache (via Get, TryGetValue, Set, or Remove) can trigger a background scan for expired items.”

Our lab writes 10,000 keys with a 1 ms TTL, advances the clock by a second, and never reads them:

keys written with a 1 ms TTL: 10,000
clock advanced:              1s
still in memory (lazy only): 10,000
after one sampling cycle:    8,000
cycles until empty:          5

Lazy expiry alone reclaimed nothing, because nothing was read. The sampling cycle cleared them in five cycles. Read that number carefully: our cycle samples 20 keys, repeats while more than 10% of a sample was expired, and stops after 100 rounds, which stands in for the CPU budget Redis gives itself. Every key here was expired, so the stale threshold never stopped anything: the round cap did, at 2,000 keys a cycle.

The numbers everyone quotes for this are worth a closer look. The famous “20 random keys, 10 times a second, repeat while more than 25% were expired” comes from Redis’s old documentation repository, which GitHub archived, read-only, in March 2026. The live page has dropped the numbers entirely. And the archived text disagrees with the source: in current Redis, ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE is 10, and that’s the threshold compared against the share of the sample that was expired. The 25 in the source is ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC, “Max % of CPU to use”, which is a different quantity. redis.conf agrees with the code: the cycle tries “to avoid having more than ten percent of expired keys still in memory”.

What’s worth taking away isn’t the constants, which scale with a configuration knob anyway. It’s the shape of the guarantee: sampling bounds the waste rather than eliminating it. The old documentation put it as “the maximum amount of keys already expired that are using memory is at max equal to max amount of write operations per second divided by 4” — which is just arithmetic from that 25% threshold, so with the code’s 10% the bound is nearer a tenth of the write rate, and either way it assumes the sample represents the keyspace.

memcached is the other instructive case: its reworked LRU, crawler included, only became the default in version 1.5.0, and the crawler builds a histogram of TTLs and schedules its own next pass from it, rescanning busy slab classes in seconds and quiet ones at most hourly. Active expiry doesn’t have to run on a fixed interval.

Eviction: which entry goes?

When the cache is full, something has to go. The candidates:

• LRU: the least recently used. Cheap with a linked list, and it matches how caches are actually used.
• LFU: the least frequently used, which needs a counter per entry and a way to decay it.
• Random: pick any entry. Sounds terrible. Isn’t, quite.
• Sampled LRU: pick a handful at random, evict the oldest of those. This is what Redis does, and its documentation is careful to say so: its LRU is an approximation. Worth knowing before you copy it: Redis’s default maxmemory-policy is noeviction, so out of the box it isn’t a cache at all — it refuses writes when full.

Redis’s reason for approximating is instructive: a true LRU list means two pointers per entry, and the memory to store them, for a gain the sampling already captures. maxmemory-samples defaults to 5.

Our lab measures all three on a Zipf workload, the pattern where a few keys are hugely popular: 200,000 requests over 10,000 distinct keys, into a cache that holds 1,000.

Policy	Hit rate	Misses	Evictions
LRU (a true recency list)	75.06%	49,886	48,886
Sampled LRU (5 candidates)	74.45%	51,098	50,098
Random entry	71.05%	57,904	56,904

That’s the answer to the second question in “Try this first”. Random eviction isn’t catastrophic, it’s a few points worse, and sampling five candidates came within 0.6 of a point of true LRU. Which is the argument Redis makes for its design.

One honest caveat about our measurement: it shows how good a decision five candidates make, not how cheap the implementation is. Our sampler consults the real recency order to pick the oldest of its five; Redis instead keeps a coarse per-object clock with one-second resolution, which is where the memory saving comes from.

Two caveats before you take those numbers anywhere:

• They’re one workload. Zipf with those parameters, that capacity, that key count. Change the skew or the capacity and the gaps change. Modern policies in the TinyLFU family (Caffeine in Java documents W-TinyLFU; moka in Rust and Ristretto in Go document TinyLFU admission) beat plain LRU on many traces by admitting an entry only if it looks more valuable than the one it would replace.
• LRU’s cost isn’t the list, it’s touching it. Every read moves an entry to the front, which is a write to shared state on a read path. memcached’s fix is to rate-limit it: an item is “bumped once every 60 seconds” at most. Caffeine, moka and Ristretto all split the problem: a strongly consistent hash table, plus eviction bookkeeping that is batched and eventually consistent.

Thread safety: two structures, two problems

A cache is a map and a recency list. The map is easy to make concurrent. The list is the problem: every read mutates it, so the “read path” takes a write lock, and your cache serialises.

The options, from simplest:

1. One mutex around both. Correct, easy to review, and the bottleneck under load.
2. Shard the cache by key hash. Sixteen independent caches, each with its own lock, and a sixteenth of the contention. Eviction accuracy suffers slightly because each shard evicts its own.
3. Split the consistency models, which is what the modern libraries do: a lock-free concurrent map for the entries, and lock-guarded, batched structures for recency and frequency. moka documents exactly this split, and it explains why entry_count() can be stale.

Go’s sync.Map looks tempting and mostly isn’t: its documentation names two use cases, one of them “caches that only grow”, which is the opposite of a store with TTLs and eviction. It also warns about maintaining “other invariants along with the map content”, which is precisely the map-plus-recency-list problem.

One more from Part 11 that bites here: ConcurrentDictionary.GetOrAdd in .NET may run your factory more than once, because “delegates for these methods are called outside the locks”. Java’s computeIfAbsent runs it exactly once. If the factory loads from a database, that difference is the next section.

The stampede

A popular key expires. A hundred requests miss at the same instant. A hundred identical database queries leave at once, and the database that was comfortably serving a cached workload falls over.

Our lab demonstrates the shape with 50 callers missing the same key together, with and without duplicate suppression. It’s a demonstration rather than a measurement: without suppression every caller loads by construction, and the single call depends on all 50 arriving while the first load is still running.

callers missing the same key at once: 50
loader calls without single flight:   50
loader calls with single flight:      1

The fix is single flight: the first caller loads, everyone else waits for that result. Go’s singleflight package is the canonical version: “Do executes and returns the results of the given function, making sure that only one execution is in-flight for a given key at a time. If a duplicate comes in, the duplicate caller waits for the original to complete and receives the same results.”

Two things the documentation implies and beginners miss. The results are shared: if the loader returns a pointer, every caller gets the same pointer, and mutating it is a data race (Part 11). And the error is shared too: one slow failure is returned to everyone who joined. (Our lab’s version only makes the others wait; a real implementation hands them the loaded value, which is where that hazard comes from.)

.NET 9’s HybridCache ships the same guarantee, with its scope stated precisely: “A HybridCache instance ensures that only one concurrent caller for a given key calls the factory method, and all other callers using the same instance wait for the result of that call […] This coordination doesn’t extend to other HybridCache instances, even if they use the same secondary distributed cache.” Per instance, not per cluster.

Two other defences worth knowing:

• Jittered TTLs. A thousand entries written in the same second with the same TTL expire in the same second. Add a random few percent so they don’t.
• Probabilistic early recomputation. Refresh an entry slightly before it expires, with a probability that rises as expiry approaches, so one unlucky caller refreshes it while the rest still get the cached value. The VLDB 2015 paper on cache stampedes gives the formula, and the neat part is that it needs no configured rate: the window scales with how long the item took to compute last time.

Explain it like I’m ten

A small shelf by the door holds the things you use most: keys, wallet, a couple of books.

• The shelf is full. To put something new down, something has to go. You take the thing you haven’t touched in longest. That’s LRU.
• Milk has a date on it. You don’t check the fridge with a stopwatch; you notice when you reach for it. That’s lazy expiry.
• But nobody reaches for the thing at the back. So once in a while you check a few random items and throw out the off ones. That’s active expiry, and checking a few is much cheaper than checking everything.
• Everyone asks at once. If the whole family asks for milk the moment it runs out, you don’t want five people driving to the shop. One goes, the rest wait. That’s single flight.

The precise version

• The shelf is the capacity, and taking the longest-untouched thing is the eviction policy.
• Noticing on reach is lazy expiry; the occasional spot check is active expiry, and sampling is why it stays cheap.
• Five people driving to the shop is the cache stampede, and one person going is single flight.
• Where the analogy breaks: a real cache has to do all of this while several people reach for the shelf at once, which is why the recency list, not the map, is the hard part.

The API boundary

What the cache’s interface promises matters more than its internals:

• Get returns “present or not”, not “present or expired”. Expiry is invisible to the caller. Guava’s rule again: expired entries “will never be visible to read or write operations”. (Guava’s own page now opens by pointing at Caffeine instead; the rule is what matters here, not the library.)
• Set takes a TTL, and zero means forever. Make the “no expiry” case explicit rather than a magic number.
• A GetOrLoad(key, loader) is a different method, and it’s the one that needs single flight.
• Size means what? Entries, bytes, or “cost”? .NET’s MemoryCache makes you choose and provide it: “The cache size limit doesn’t have a defined unit of measure because the cache has no mechanism to measure the size of entries.”
• Stats are part of the API. Hits, misses, evictions and expiries are how anyone tunes the thing. Our lab’s store counts all four.
• Say what’s eventually consistent. If Count may include expired entries, document it, as Guava and moka do.

Trade-offs

• Bigger cache, better hit rate, until it isn’t. A Zipf workload means the tail is nearly uniform, so doubling the cache past the popular set buys very little.
• LRU is one write per read. If reads dominate and threads contend, that write is your bottleneck, not the eviction policy.
• Sampling trades a little accuracy for a lot of simplicity, which our measurements support: half a point of hit rate for no per-entry pointers.
• TTL is a correctness tool and a memory tool. A short TTL bounds staleness; it also bounds how much dead data you hold. Those two goals rarely want the same number.
• In-process caches are per instance. Ten replicas mean ten copies, ten misses on a cold key, and ten different staleness windows. That’s a distributed caching decision (Part 22).
• Eviction hides bugs. A cache that evicts aggressively makes a slow loader look fine until traffic shifts.

Common mistakes

• A timer per entry. It works at a thousand keys and collapses at a million. Expire on read, and sweep in the background.
• Reads that don’t check the TTL because “the sweeper will get it”. The sweeper is sampling; it may not reach that key for a while.
• Never sweeping at all. Lazily expired entries that are never read again are a memory leak with a nice name. Our lab held all 10,000.
• Evicting under the read lock. The read path now blocks on the eviction path. Batch the bookkeeping, or shard.
• One TTL for everything, written in one burst. They all expire together. Jitter them.
• No single flight on the load path. One popular key expiring becomes a thundering herd.
• Caching the error. A failed load stored with the normal TTL turns a blip into minutes of outage. Cache failures briefly, if at all.
• Unbounded caches. “It’s only small” is true until a key is derived from user input. Always set a capacity.

Interview questions

Try to answer each one before opening the model answer.

1. Design an in-memory cache with TTL and a size limit.

Show a strong answer

• Structures: a hash map for lookup and a doubly linked list in recency order for eviction, with map values pointing at list nodes, so Get and Set are O(1).
• Expiry: store an absolute expiry timestamp per entry, check it on read (lazy), and sweep a random sample periodically (active).
• Eviction: when over capacity, remove from the back of the list. Count entries, or bytes if the caller can supply a size.
• The clock is injected, so tests advance time instead of sleeping. Use a monotonic source for the arithmetic: System.nanoTime in Java, TimeProvider.GetTimestamp in .NET. A wall clock moves every TTL when NTP steps it.
• Concurrency: one lock to start, shard by key hash when it contends, and batch the recency bookkeeping if reads dominate.
• API: Get, Set(key, value, ttl), GetOrLoad(key, loader) with single flight, plus hit and miss counters.

Likely follow-up: “How do you test the expiry?” Inject the clock, advance it, and assert the entry is invisible to Get and eventually reclaimed by the sweeper.

2. How do you expire a million keys without a million timers?

Show a strong answer

• Lazy: a read that finds an expired entry treats it as a miss and removes it. Costs nothing until someone asks.
• Active: sample a few keys with expiries, delete the expired ones, and repeat while the sample looks stale, under a CPU budget. That’s Redis’s design.
• Why sampling works: it bounds the waste rather than eliminating it. Redis’s old documentation put the bound at “max amount of write operations per second divided by 4”.
• Alternatives: a timer wheel or a priority queue by expiry time, which is exact and costs a heap operation per write, and a per-entry timer, which nobody does.
• In libraries: Guava and Caffeine do maintenance on reads and writes; .NET’s MemoryCache scans on cache activity, not on a timer.

Likely follow-up: “What if memory matters more than CPU?” Raise the effort: sample more keys more often, or keep an expiry-ordered structure and pay on the write path.

3. LRU, LFU or random?

Show a strong answer

• LRU fits most workloads and is cheap with a list, but a scan of cold keys can flush it.
• LFU survives scans, needs a counter per entry, and needs decay or it remembers yesterday’s popularity forever. Redis’s LFU uses a probabilistic 8-bit counter with a decay period.
• Random is the cheapest and, in our measurement on a Zipf workload, only a few points worse than LRU.
• Sampled LRU gets most of LRU’s benefit with none of the pointers, which is why Redis defaults to sampling five candidates.
• W-TinyLFU (Caffeine, moka, Ristretto) adds an admission filter: a new entry only gets in if it looks more valuable than the victim.

Likely follow-up: “How would you choose in practice?” Measure hit rate on your own traffic. The policy matters far less than the capacity and the key design.

4. What is a cache stampede and how do you prevent it?

Show a strong answer

• What: a popular key expires, every concurrent request misses, and they all hit the backend at once.
• Single flight: one loader runs, the rest wait and share the result. Go’s singleflight, .NET’s HybridCache, or a per-key lock.
• The caveats: the shared result is shared, including pointers and errors, and the guarantee is usually per process, not per cluster.
• Jitter the TTLs so entries written together don’t expire together.
• Probabilistic early refresh: recompute slightly early with rising probability, so one caller refreshes while the others still read the cached value.
• Serve stale on failure where correctness allows it, rather than passing the outage through.

Likely follow-up: “What about across ten instances?” Ten loaders, not a hundred. If that still hurts, coordinate in the shared store with a lock key, and accept the round trip.

5. How would you make the cache thread-safe without killing throughput?

Show a strong answer

• Start with one mutex and measure. The critical section is tiny.
• Shard by key hash when it contends: N independent caches, N locks, and eviction decided per shard.
• Split the structures: a concurrent map for entries plus batched, eventually consistent recency and frequency bookkeeping, which is what Caffeine, moka and Ristretto do.
• Rate-limit the recency update: memcached only bumps an item once every 60 seconds.
• Be honest in the API about what’s eventually consistent, such as Count or hit statistics.

Likely follow-up: “Why not sync.Map in Go?” Its documented use cases don’t include a cache with eviction, and it can’t maintain the invariant between the map and the recency list.

6. What’s the difference between logical expiry and reclamation?

Show a strong answer

• Logical expiry is a predicate on the read path: past its expiry time, the entry is invisible.
• Reclamation is when the memory actually comes back, which may be much later.
• Guava states the consequence: an expired entry “may be counted by Cache.size(), but will never be visible to read or write operations”.
• Why it matters: your memory graph reflects reclamation, your correctness reflects logical expiry, and monitoring the wrong one leads to the wrong fix.
• Redis has a third case: replicas don’t expire keys themselves; the primary sends an explicit deletion, so a replica can hold a logically expired key.

Likely follow-up: “How do you report cache size, then?” Report both: entries present and entries live, or document which one your counter means.

7. Where does an in-process cache stop being the right answer?

Show a strong answer

• When instances multiply: each holds its own copy, so cold starts and stale windows multiply too.
• When the data must be consistent between instances, since there’s no invalidation channel without one.
• When entries are expensive to build and cheap to share, which is what a distributed cache is for.
• When the working set doesn’t fit in the memory you can afford per instance.
• The hybrid: a small in-process cache in front of a shared one, which is what .NET’s HybridCache is, with the stampede protection per instance.

Likely follow-up: “How do you invalidate across instances?” A pub/sub message or a version key, and accept a window where instances disagree.

8. Your cache hit rate dropped from 95% to 60% overnight. How do you investigate?

Show a strong answer

• Check the key shape first: a new field in the key (a user ID, a timestamp, a locale) multiplies the key space and shrinks the effective hit rate.
• Check capacity and evictions: a rise in evictions means the working set grew or the cache shrank.
• Check TTLs: a shortened TTL or a deployment that restarts instances hourly gives you permanent cold starts.
• Check traffic shape: a crawler or a scan flattens the popularity curve, which is what LFU-style admission is designed to survive.
• Check for stampedes: a spike in loader calls per miss means the single-flight path is broken.
• Then measure, don’t guess: log key samples, count distinct keys, and replay a trace against different capacities.

Likely follow-up: “What would you add to make this diagnosable next time?” Per-cache metrics for hits, misses, evictions, expiries and loader calls, plus a sampled log of the keys that miss most.

Sources

• Lab: system-design/checks/part15_kvstore/ (the store, the eviction-policy measurements on a Zipf workload, the expiry cycle and the stampede test); the C#, Java, Go and Rust programs above are run by the series’ code verifiers
• Redis: EXPIRE and its archived documentation, expire.c, redis.conf, key eviction
• memcached: the LRU wiki pages
• Java: Guava CacheBuilder, Caffeine’s wiki
• .NET: MemoryCache in ASP.NET Core, MemoryCacheOptions, HybridCache
• Go: sync.Map, singleflight, hashicorp/golang-lru and ristretto (community)
• Rust: std::collections::HashMap, the lru crate, moka (community)
• G. Einziger, R. Friedman, B. Manes, TinyLFU: A Highly Efficient Cache Admission Policy; A. Vattani, F. Chierichetti, K. Lowenstein, Optimal Probabilistic Cache Stampede Prevention, VLDB 2015

What to remember

• A cache is a hash map for lookup plus a recency structure for eviction. The recency structure is the hard part, because reads write to it.
• TTLs don’t need a timer per key: check on read, and sweep a random sample in the background.
• Lazily expired entries that nobody reads again are a memory leak. Our lab held all 10,000 until a sweeper ran.
• Sampled LRU came within half a point of true LRU on our workload, and random eviction was a few points behind. The policy matters less than the capacity.
• Make the stampede impossible on the load path: single flight, jittered TTLs, and early refresh for hot keys.
• Say in the API which numbers are exact and which are eventually consistent.

The cache’s job is to be wrong in cheap ways. Decide which ways before you ship it.