Machine coding · not HLD

In-memory key-value store

Imagine treating this store as "just a HashMap." Callers iterate a public field, mutate entries, and you cannot prove a ten-second without Thread.sleep. Jumping to Cassandra (replication, consistent hashing, quorum) leaves the machine-coding round.

The design goal is a testable : inject for expiry, hide the map, return on get, and handle concurrent puts safely. Process-local get/put/delete with optional TTL lives here. Cluster verbs belong on the related System Design note: Key-value store .

Seams to keep

get, put, delete, and maybe put-with-TTL. Values can be bytes or a generic V.

Freeze and advance time in tests. Never call System.currentTimeMillis.

Hide the map. Return Optional on get so callers never iterate entries.

On get, if Clock says dead, remove the entry and return empty.

What actually happens on get and put

The HashMap story above is the default if you skip the seams. A public map lets callers iterate and mutate, so expiry and concurrency leak. The stays at get, put, delete, and maybe put-with-. The implementation owns a private map. Values can be bytes or a generic V.

Expiry is a policy checked on read. Each Entry holds the value and an optional expiresAt. dead(now) is a query, not a background job. If says the entry is dead, removes it and get returns . put without TTL stores expiresAt null (forever). Null TTL on the overload means the same. Zero or negative TTL rejects at put. delete removes regardless of TTL. Overwrite put replaces the whole Entry, including a new TTL: a fresh expiry is a new Entry, not a mutated field without a happens-before (the visibility guarantee between writes).

Independent keys use . Compound actions need : get-then-put ifAbsent is the same race as parking occupy, just on a map key. Expiry remove should use remove(key, expectedEntry) so a concurrent put of a fresh value survives. Keep serialization out unless they ask. String to String is enough; a ValueSerializer strategy is the seam if they add JSON later. See repository: a port you can fake in tests.

Simple rule of thumb

Once the is tiny, three questions keep the round on the in-process store instead of a cluster sketch or a public map.

1. Can this stay in process? Replication, consistent hashing, and quorum belong on the related System Design note (see the hero link). Mention that boundary, then implement get/put.

2. Can tests freeze expiry? Inject . A test that needs Thread.sleep is coupled to the wall clock.

3. Is capacity in scope? When the map grows huge, eviction can reuse the LRU idea. Compose a KvStore that delegates eviction, or the reverse. Do not merge the pages.

In simpler terms

Write the four-method port and hide the map. Prove TTL with a frozen clock. Stay off Cassandra-scale design until the in-process contract works.

From problem to mechanism

Here is the "just a HashMap" story again, slowed down so you can see where the naive map fails and what the seams change.

Problem. Interviewers want a process-local store with optional . The must stay tiny so fakes stay easy, and get must return rather than a leaked Entry.

Naive system. A public HashMap, System.currentTimeMillis inside get, and get-then-put ifAbsent as two calls. There is no injected , so expiry is untestable without sleep.

Break it. Callers iterate and mutate. An expired get still returns the value (a zombie TTL). Two threads both insert a default. A late lazy-delete can wipe a fresher put if you remove(key) instead of remove(key, expectedEntry).

Mechanism. Hide the map behind InMemoryKvStore. Use for independent keys and for get-or-create. on read is enough for machine coding; a background sweeper (a heap of due keys, like a task scheduler) is a follow-up, not minute five. Scanning every key on each get is acceptable here.

Worked example: freeze time, then get

The mechanism names an injected and ; this is the test that is the whole design. Write these sentences on the board before trivia.

FakeClock at T. put("k", "v", 10 seconds). get → v. Advance 11 seconds. get → empty, and the map no longer holds a zombie entry. get never treats a forever entry (expiresAt null) as dead.

Numbers to know

Ten-second TTL, then advance eleven seconds: get must return empty.
Waiting eleven real seconds in CI is not a design.
Forty-five minutes: port first, TTL by minute 32, cluster talk last.

Java API sketch

java

interface KvStore<K, V> {
  Optional<V> get(K key);
  void put(K key, V value);
  void put(K key, V value, Duration ttl);
  void delete(K key);
}

final class Entry<V> {
  final V value;
  final Instant expiresAt; // null = forever
  boolean dead(Instant now) {
    return expiresAt != null && !now.isBefore(expiresAt);
  }
}

class InMemoryKvStore<K, V> implements KvStore<K, V> {
  private final Clock clock;
  private final ConcurrentHashMap<K, Entry<V>> map = new ConcurrentHashMap<>();

  public Optional<V> get(K key) {
    Entry<V> e = map.get(key);
    if (e == null) return Optional.empty();
    if (e.dead(clock.instant())) {
      map.remove(key, e);
      return Optional.empty();
    }
    return Optional.of(e.value);
  }

  public void put(K key, V value) {
    put(key, value, null); // null TTL = forever
  }

  public void put(K key, V value, Duration ttl) {
    if (ttl != null && (ttl.isZero() || ttl.isNegative()))
      throw new IllegalArgumentException("TTL must be positive or null");
    Instant exp = ttl == null ? null : clock.instant().plus(ttl);
    map.put(key, new Entry<>(value, exp));
  }

  public void delete(K key) { map.remove(key); }
}

Responsibility walk

The sketch above names four types. Here is who owns what, so a later box can point here instead of restating the .

Type	Owns
KvStore	The port is intentionally tiny: get/put/delete. No cluster or quorum verbs.
InMemoryKvStore	Owns the map and an injected Clock. Expiry is checked lazily on get.
Entry	Holds the value and optional expiresAt. dead(now) is a query, not a background job.
Clock	Injected Clock so tests can freeze and advance time.

Invalid cases, and what still breaks after the fix

The table names the owners. These are the answers that fail the round, the concurrency habit that saves them, and the follow-ups that still go wrong after the seams are in.

Invalid cases

Public map field: callers iterate and mutate; hide expiry and concurrency.
Expired get returning a value: skip , and FakeClock tests must fail.
put of a null key: reject it; may allow a policy you do not want.
Drawing a cluster: shards and gossip are System Design; implement put/get here.
get-then-put ifAbsent as two calls: use so two threads cannot both insert.

Concurrency

Independent keys: ConcurrentHashMap (see above). Compound actions: compute / computeIfAbsent. Expiry remove should use remove(key, expectedEntry) so you do not delete a fresher put. See thread safety.

Still fails when…

Zombie TTL: an expired get still returned the value; you forgot lazy delete on read.
Lost put: get-then-put ifAbsent as two calls lets both threads insert.
Expiry needs Thread.sleep: the store is still coupled to the wall clock.

Trade-offs

Lazy expiry on get is enough; a sweeper heap is faster but later.
Scan-on-get is fine here; an expiry heap is not minute five.
Max size is LRU-cache territory: compose, do not merge those pages.

How to spend forty-five minutes

After the failure list, this is the board order. Write the first; prove with before cluster talk (see Numbers to know).

0–8Write the four-method port and keep the map private.
8–20Wire ConcurrentHashMap and Clock; implement put/get without TTL.
20–32Add TTL with FakeClock advance and lazy delete on get.
32–40Show computeIfAbsent; mention the LRU cousin if capacity appears.
40–45Name the related System Design note, then return to the in-process port.

Wrap-up

You have the seams, the FakeClock test (see Numbers to know), and the forty-five-minute order. Use these checks, then follow the related pages.

Tests that prove the seams

This test is the whole design: injected , then get returns after the advance.