Low-level design: key-value store with TTL

An in-memory key-value store with a time to live (TTL) keeps values under keys inside one process, forgets each key when its time is up, and lets a client group changes into transactions. In a low-level design (LLD) round it comes down to four classes. A Store maps each key to an Entry: the value, an optional deadline and a version number, behind one lock. Expiry has two halves: an operation that finds a key past its deadline deletes it, and a periodic cycle deletes expired keys that nobody reads. A Session runs one client’s commands, and its nested transactions are a stack of change sets: a read looks in the innermost set first, a delete writes a tombstone, ROLLBACK drops the top set and COMMIT merges it into the one below. Time comes from a Clock the store is given.

The prompt, the requirements and the first design

The prompt: “Design an in-memory key-value store for an app’s login sessions and one-time codes, with SET, GET, DEL, EXPIRE and TTL, keys that expire, and nested transactions with BEGIN, ROLLBACK and COMMIT.” Five questions shape it:

1. Values and units? Strings, and times to live in milliseconds.
2. What does a read inside a transaction see? Its own writes first; other clients see them after COMMIT.
3. COMMIT inside a nested transaction? It merges outwards; only the outermost reaches the store.
4. Many clients? Yes, each with its own session.
5. Memory? Expired keys must not pile up unread.

The answers become numbered requirements:

• K1 SET stores a value and replaces any old value and its expiry.
• K2 GET returns the value, or nothing for a missing or expired key.
• K3 DEL removes a key; EXPIRE gives a key a new time to live, and 0 or less deletes it.
• K4 TTL answers the milliseconds left, -1 for a key without expiry and -2 for a missing key.
• K5 An expired key is never returned, and its memory comes back even if nobody reads it.
• T1 to T4 Transactions nest; a read sees the innermost change first; ROLLBACK discards the innermost transaction and COMMIT merges it outwards; the outermost COMMIT applies everything at once, or nothing.
• N1 Time comes from a clock the store is given; N2 every operation and every commit is atomic.

Expiring keys only when someone reads them looks enough, until the keys that nobody reads again are counted:

"""Why a store cannot expire keys only when they are read.

A store keeps 10,000 login sessions, each with a time to live of 30 minutes, and removes an expired entry only when a
read finds it. An hour later, 200 of those users come back.
"""

MINUTE = 60_000


class LazyOnlyStore:
    def __init__(self):
        self.entries = {}  # key -> (value, deadline in ms)

    def set(self, key, value, ttl_ms, now):
        self.entries[key] = (value, now + ttl_ms)

    def get(self, key, now):
        entry = self.entries.get(key)
        if entry is not None and entry[1] <= now:
            del self.entries[key]  # expired: removed, but only because someone asked
            return None
        return None if entry is None else entry[0]


store = LazyOnlyStore()
for user in range(10_000):
    store.set(f"session:{user}", "token", ttl_ms=30 * MINUTE, now=0)

now = 60 * MINUTE
expired = sum(1 for _, deadline in store.entries.values() if deadline <= now)
print(f"after an hour:  {len(store.entries):,} entries held, {expired:,} of them expired")
answers = [store.get(f"session:{user}", now) for user in range(0, 10_000, 50)]
print(f"200 reads later: every read answered {set(answers)}; {len(store.entries):,} entries held, all expired")

after an hour:  10,000 entries held, 10,000 of them expired
200 reads later: every read answered {None}; 9,800 entries held, all expired

An hour later all 10,000 entries had expired, and 200 reads removed only the 200 they touched. The design names these options:

• Lazy expiry: an operation that finds a key past its deadline deletes it and answers as if it were missing.
• Sampling: a periodic cycle tests a few random keys that have a deadline and deletes the expired ones.
• A deadline heap: a min-heap of deadlines pops every key whose time has come, exactly on time.
• Tombstone: a marker in a change set that says “deleted here”, so an older value below stays hidden.
• Change sets: each open transaction keeps only what it wrote, and reads fall through to the store.
• Copy at BEGIN: a transaction starts with its own copy of the whole store.
• Version check: a commit fails when a key it read has changed since.

Redis documents the same two halves for its EXPIRE command, a passive way on access and an active way that tests a few random keys with an expiry.

The deep dives that decide whether this design holds:

1. How do the Store, its Entries and a Session look in code, and what does one session print?
2. What do lazy expiry, sampling and a heap cost in memory and work, measured?
3. Why do deletes inside a transaction need tombstones, and what must a rollback restore?
4. What happens when two sessions change the same key, and how does a commit notice?
5. How do locks, shards and snapshots fit, and what changes in five other languages?

An answer is judged on the requirements, the split between store, sessions and clock, the expiry policy and its numbers, transactions that keep their promises, and concurrency.

The store and a session in code Pro: opens with a Pro, Premium or Ultimate pass