Store a deadline, then expire two ways
Each entry holds its value and an absolute deadline: now + ttl at write time. A countdown per key would need something to decrement it, which is a timer per key and a lot of wasted work. Read the time from an injected clock so tests can advance it without sleeping.
Lazy expiry is the cheap half. get compares the deadline with the clock, and if it has passed, returns nothing and removes the entry. Lazy expiry alone is a leak, though. A session key written once and never read again stays in memory forever. Active expiry covers that: a scheduled task walks or samples the keys and removes the stale ones. Redis combines both ideas, removing an expired key when it is accessed and also running a periodic job over a sample of keys that carry a TTL.
A priority queue ordered by deadline is the other active option. It finds the next key to expire without scanning, but a key whose TTL is extended leaves a stale queue entry behind. Store the entry object in the queue and remove the key only if the map still holds that exact entry. Whichever you choose, the removal must be conditional, so the sweep never deletes a value somebody rewrote a moment ago.
Why copying a ConcurrentHashMap is not a snapshot
The obvious key-value store snapshot is new HashMap<>(live), or iterating a ConcurrentHashMap. It is safe, in that it never throws, but its iterators are weakly consistent: each key is read at whatever moment the scan reaches it. Suppose the scan reads x (old value). A client then writes x, then writes y. The scan reaches y and reads the new value. The copy now holds the new y and the old x, a state that never existed, since x was changed first. A restore from that copy is quietly wrong.
A consistent snapshot must equal the store at a single instant, the cut. There are three honest ways to get one. Stop all writes and copy, which pauses writers for the whole O(n) copy. Keep versions per key and read every key at the cut's version, which needs version chains and their garbage collection. Or copy each key just before its first change after the cut, which is copy-on-write at key granularity. The third suits a machine-coding round, and it is the same idea Redis gets from fork(), where the operating system copies a memory page only when the parent process writes to it.
Copy-on-write per key
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.function.LongSupplier;
import java.util.function.UnaryOperator;
public final class TtlStore {
private record Entry(String value, long expiresAt) {}
private static final Entry ABSENT = new Entry(null, 0);
private final ConcurrentHashMap<String, Entry> live = new ConcurrentHashMap<>();
private final ReentrantReadWriteLock cut = new ReentrantReadWriteLock();
private volatile ConcurrentHashMap<String, Entry> before;
private final LongSupplier nowMillis;
public TtlStore(LongSupplier nowMillis) { this.nowMillis = nowMillis; }
public void put(String key, String value, ttlMillis) {
(value, nowMillis.getAsLong() + ttlMillis);
mutate(key, old -> e);
}
{ mutate(key, old -> ); }
Optional<String> {
live.get(key);
(e == ) Optional.empty();
(e.expiresAt() <= nowMillis.getAsLong()) {
mutate(key, old -> old == e ? : old);
Optional.empty();
}
Optional.of(e.value());
}
{
cut.readLock().lock();
{
ConcurrentHashMap<String, Entry> saved = before;
live.compute(key, (k, old) -> {
change.apply(old);
(saved != && next != old) {
saved.putIfAbsent(k, old == ? ABSENT : old);
}
next;
});
} { cut.readLock().unlock(); }
}
Map<String, String> {
ConcurrentHashMap<String, Entry> saved = <>();
at;
cut.writeLock().lock();
{ before = saved; at = nowMillis.getAsLong(); } { cut.writeLock().unlock(); }
{
Map<String, Entry> image = <>();
live.forEach((k, e) -> {
saved.get(k);
image.put(k, old != ? old : e);
});
saved.forEach(image::put);
Map<String, String> out = <>();
image.forEach((k, e) -> {
(e != ABSENT && e.expiresAt() > at) out.put(k, e.value());
});
out;
} {
before = ;
}
}
}
Why the order of two reads is the proof
The correctness argument fits in three sentences, and saying it is most of the score. The cut takes the write lock, so every write either finished before the cut or will see the new before map. After the cut, a writer saves a key's old value before the live map changes, and putIfAbsent keeps only the first, which is the value at the cut. The scan reads the live value first and then checks saved; if a write slipped in between, the saved copy is already there and overrides it, so the scan can never keep a post-cut value.
Reverse either order and it breaks. If the writer changed the live map first, the scan could read the new value before the old one was saved. If the scan checked saved first, a write could land between the two reads.
Expiry needs one more line of thought. Lazy and active expiry both go through mutate, so expiring a key during a snapshot saves its old entry like any other change. The snapshot then filters by at, the time of the cut, and keeps any key that was still live at that moment.
What it costs
In this key-value store, writers pay a shared read-lock acquisition and, only while a snapshot runs, one putIfAbsent per key touched. The cut blocks writers only while it swaps a reference and reads the clock. Memory overhead is at most one saved entry per key modified during the snapshot, which is the same bound fork-based snapshots have at page granularity. A write-heavy store can therefore need up to twice its memory during a long snapshot, so say so before the interviewer asks. For the eviction side of in-memory stores, LRU in O(1) covers the structure.
A snapshot is a claim about one instant, and a concurrent iterator makes no such claim. Cut once, save each key's old value before its first change, and read live before saved. Those two orderings are the whole proof.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).