Design an In-Memory Key-Value Store

A key-value store is infrastructure other code reads and writes constantly, often from multiple threads at once — a utility where concurrency is a core design concern, not an afterthought. The design must keep the store consistent when two writers arrive at the same instant: a concurrent write that corrupts the LRU structure produces silent wrong results.

See It in Action

The demo shows insertion, capacity eviction, TTL expiry, and lazy removal on the next get.

Clarifying Requirements

"Design an in-memory key-value store" leaves the eviction and expiry policies open, so surface them before writing code. Functional requirements we commit to: put(key, value, ttl) stores a string value with an optional time-to-live; get(key) returns the value if present and not expired, or a sentinel indicating absence; delete(key) removes the key immediately. The store is bounded by a capacity; when a put would exceed capacity, the least-recently-used entry is evicted. Expiry is lazy — expired entries are removed on the next access rather than by a background sweeper, making the logic deterministic and testable without controlling a real clock. The TTL is per-key; a TTL of zero means the entry never expires.

The two core operations follow distinct decision paths. The flowchart below captures both so you can verify your implementation handles every branch before writing a line of code.

Core Entities

Scanning the requirements for nouns that carry state or enforce rules gives a short list: the stored value with its expiry, the access-order bookkeeping that drives eviction, and the store itself. A tempting shortcut is to fold all three into one KeyValueStore class that holds a dict and a list and does everything inline. Before reading on, decide whether the access-order tracking earns its own class, or whether it belongs inside the store.

The list resolves into three entities, each owning a single concern.

An Entry is a value object: the stored string plus an optional absolute expiry timestamp. Its only behaviour is is_expired(now) — compare the expiry to the supplied timestamp and return a boolean. Keeping expiry logic inside Entry means the store never checks expiry inline with raw arithmetic; it asks the entry.

An LRUList tracks access order and nothing else. It is a doubly-linked list wired to a hash map so that every operation — add, touch, remove, evict-oldest — runs in O(1). It knows nothing about values or expiry; it only knows which key was used most recently and which was used least recently. Separating order bookkeeping from value storage gives each concern one place to live and one reason to change.

A KeyValueStore is the public facade. It holds the entry dictionary, delegates order tracking to LRUList, enforces capacity, and performs lazy expiry. It is the only class the outside world talks to.

The ownership relationships between the three entities are straightforward: KeyValueStore composes both LRUList and the entry dictionary, while Entry is a pure value object with no back-references.

Designing the Classes

Step 3 of the delivery framework says: for each entity, derive its state (fields) directly from requirements, then derive its behavior (method signatures) from what callers need to ask it. Add nothing that no requirement demands.

Entry

The requirements say: store a string value, optionally expiring at an absolute timestamp. That is exactly two fields — value: str and expiry: Optional[int], where None means never expires. The TTL input is a duration; Entry stores the pre-computed absolute timestamp (timestamp + ttl) so every expiry check is a single comparison rather than recomputing the deadline on each call.

The only behavior the store needs from Entry is: "are you expired at time now?" A boolean method is_expired(now: int) -> bool satisfies this. The store never reads the expiry field directly — it asks Entry. That is Tell, Don't Ask: the rule lives where the data lives.

LRUNode and LRUList

The capacity requirement demands evicting the least-recently used entry when the store is full. That means the store must track access order across all keys. The state required is an ordered sequence of keys that supports four mutations in O(1): add a new key at the MRU end, promote an existing key to MRU, remove an arbitrary key, and pop the key at the LRU end.

Before reading the answer, decide what data structure backs that ordered sequence so all four mutations stay O(1).

A plain list cannot promote in O(1) — scanning to find the key is O(n). A hash set cannot preserve order. The classic solution is a doubly-linked list paired with a hash map: the list preserves order and allows O(1) splice at any node; the map maps each key to its node for O(1) lookup. This is why the design introduces LRUNode as a first-class object — you cannot splice in O(1) without a direct pointer to the node.

Two sentinel nodes — dummy head/tail nodes that are never real entries, so every splice always has a node on each side and needs no null check — _head (MRU end) and _tail (LRU end), eliminate all edge-case checks for empty lists and boundary splices. Every real node lives between the sentinels. The LRUList exposes exactly four operations: add(key), touch(key), remove(key), evict_lru() -> str. No caller ever sees a node; the list is completely encapsulated.

KeyValueStore

The store must: hold entries (a dict[str, Entry]), enforce a maximum count (_capacity: int), and delegate order tracking (_lru: LRUList). Those three fields are its complete state — nothing else. The public surface is exactly three methods derived from the functional requirements: put, get, delete. All eviction and lazy-expiry logic lives inside these methods. No raw field is ever accessed from outside.

One decision remains: when does an expired entry actually get removed? Either a background thread sweeps the store on a timer, or expiry is resolved on access. Before reading on, decide which keeps the design testable.

TTL expiry and LRU eviction happen in different places. TTL expiry is lazy, inside get: an expired entry is treated as absent and cleaned from both _store and _lru the moment it is first accessed after its deadline. LRU eviction is not lazy — it runs in put, when the store is already at capacity: the least-recently-used key is removed to make room before the new entry goes in. Lazy expiry keeps the store single-threaded-correct without any background timer and makes tests deterministic: the caller controls the clock by supplying timestamps explicitly.

Entry is a pure value object with no references back to the store. LRUList is a helper owned by KeyValueStore; it has no life outside its store. KeyValueStore composes both.

The public surface of KeyValueStore is three methods. Everything else is private. LRUList exposes four operations and no more. This small surface is what makes the design safe to extend: adding a TTL-refresh-on-put policy, for example, touches only KeyValueStore.put and LRUList.touch — nothing else needs to change.

Try It Yourself

Before reading the implementation, build it. Implement key_value_store(capacity, instructions) that replays a command stream and returns one output line per get or delete.

Each instruction is a list of strings. Three commands are supported:

["put", key, value, timestamp, ttl] — store the value. Expiry is timestamp + ttl; a ttl of "0" means the entry never expires. If the store is already at capacity, evict the LRU entry first. Counts as a use for LRU purposes. Produces no output line.

["get", key, timestamp] — if the entry exists and timestamp < expiry (or no expiry), append the value and mark the entry as most-recently used. If the entry is absent or expired, append "null". Expired entries are lazily removed.

["delete", key] — remove the key. Append "deleted" if it existed, "absent" if not.

Timestamps in the input are non-decreasing. Run your solution against the test cases. The reference implementation follows.