SYSTEM DESIGN:Lesson 11: The Simplest Database Interviewers Love

"Design a key-value store" — the interview that never goes away

"The interviewer drew a box on the whiteboard and said: clients on the left, storage on the right. Forty-five minutes. Go."

It sounds vague. It is also one of the most repeated system design prompts at Indian product companies and FAANG offshore loops — because almost everything reduces to get, put, and delete under the hood.

Redis, DynamoDB, Memcached, RocksDB, etcd — different names, same primitive. This chapter builds the single-node mental model. No replication, no consistent hashing ring (you already have that from the previous chapters). Just: what happens when code calls get("user:9182736450")?

Previous chapters: Consistent Hashing in Production covered where keys live in a cluster. This chapter covers what storage engine does with them on one machine.

GET, PUT, DELETE — the whole database in three buttons

Interviewers love this problem because the answer is simple until it is not.

The three operations that define everything

That is the whole API surface for the core interview. Extensions — TTL, compare-and-swap, batch get — are seasoning, not the dish.

interface KeyValueStore {
  get(key: string): Promise<{ value: Buffer; found: boolean }>
  put(key: string, value: Buffer): Promise<void>
  delete(key: string): Promise<boolean>  // true if key existed
}

Notice values as Buffer, not JSON strings. Production KV stores are byte blobs — serialization is the client's job. A Swiggy service might store protobuf; a session service might store JSON; the store does not care.

Single-node architecture

Before distributing anything, nail the single-box design. Every distributed KV (Dynamo, Riak, Redis Cluster) is a collection of single-node engines with a routing layer on top.

Single-node key-value store architecture

Client → HTTP/gRPC API → Storage engine → Disk (and/or RAM)

Layers:
  1. API server     — auth, rate limits, request validation
  2. In-memory index — hash map or cache of hot keys
  3. Storage engine  — B-tree or LSM, WAL, compaction
  4. Disk            — SSD/NVMe, sequential writes preferred

Interview tip: draw this diagram in 90 seconds. Label the write path (append to WAL, update memtable) separately from the read path (check memtable, then SSTable/B-tree). Interviewers use it to decide whether to go deep on storage or jump to distribution.

In-memory vs on-disk

Most real systems use both. Redis in front of Postgres is the textbook pattern from the data layer scaling chapter. The KV interview often asks you to design the durable layer — not just the cache.

When to say in-memory in an interview:

• Strict latency SLA (< 5 ms p99)
• Data can be rebuilt from another source (cache-aside)
• Working set fits in RAM (or hot subset does)

When to say on-disk:

• Durability required (payment idempotency keys, audit logs)
• Dataset >> RAM (billions of UPI transaction IDs)
• Cost sensitivity — NVMe is cheaper than DRAM per GB

Write-ahead log: durability before speed

Any durable KV store writes to a WAL (write-ahead log) before acknowledging a PUT. Append the operation to a sequential log file on disk, fsync (or group fsync), then update in-memory structures.

PUT("order:88421", {...})
  1. Append {op: PUT, key, value, ts} to WAL on disk
  2. fsync WAL (or batch fsync every N ms)
  3. Update in-memory hash map / memtable
  4. Return 200 OK to client

Crash after step 2 → replay WAL on restart, no lost acked writes

This is why Redis AOF and Postgres WAL rhyme — same durability pattern. If an interviewer asks "how do you not lose writes on crash?", WAL is the first sentence.

LSM vs B-tree: sixty-second version

Storage engines organize on-disk data differently. You do not need to implement either — you need to name the trade-off.

B-tree (MySQL InnoDB, PostgreSQL, SQLite)

• Updates happen in place on disk pages
• Reads are predictable — tree lookup, few I/Os
• Writes can be random I/O — fine on SSD, painful on HDD
• Good default mental model for "general purpose database"

LSM-tree (RocksDB, LevelDB, Cassandra, ScyllaDB)

• Writes append to memtable, flush to immutable SSTables
• Writes are sequential — very fast ingest
• Reads may check memtable + several SSTable levels
• Background compaction merges SSTables — disk amp, write amp trade-offs

For a write-heavy event log ("store every UPI callback payload"), lean LSM in the interview. For mixed read/write user profiles, B-tree or "Postgres is fine" is honest and defensible.

API design: what to expose over HTTP

A minimal REST API for the single-node store:

PUT /v1/keys/user:9182736450
  Body: raw bytes or base64 JSON wrapper
  Headers: Content-Type, optional If-None-Match for CAS
  Response: 204 No Content

GET /v1/keys/user:9182736450
  Response: 200 + body, or 404

DELETE /v1/keys/user:9182736450
  Response: 204 (deleted) or 404 (not found)

Design choices interviewers probe:

• Key size limit — e.g., 256 bytes (prevent abuse)
• Value size limit — e.g., 1 MB default, 5 MB max (S3 for bigger blobs)
• Idempotent PUT — same key + value twice is fine
• Conditional writes — PUT if version = 3 for optimistic locking
• TTL — optional Expires-At header → background sweeper deletes key

Razorpay idempotency keys are a real-world PUT with TTL: store Idempotency-Key → response mapping for 24 hours, GET before processing duplicate POSTs. That is a KV store use case wearing a payment API costume.

Single-node data structures

The simplest implementation — enough for a coding round or MVP discussion:

class InMemoryKV {
  private map = new Map<string, Buffer>()

  get(key: string): Buffer | null {
    return this.map.get(key) ?? null
  }

  put(key: string, value: Buffer): void {
    this.map.set(key, value)
  }

  delete(key: string): boolean {
    return this.map.delete(key)
  }
}

Add durability: wrap every mutating call with WAL append. Add TTL: store { value, expiresAt } and lazy-delete on GET or periodic sweep.

For on-disk single node, you would not expose this Map — RocksDB or SQLite embeds the hard parts. The interview progression is: Map → WAL → B-tree/LSM → sharding (next chapter).

Capacity planning on one machine

Back-of-envelope for a single-node KV:

Assumptions:
  100M keys, avg value 2 KB → 200 GB data
  Peak: 50k reads/sec, 5k writes/sec
  NVMe SSD: 100k IOPS sustainable

LSM write path:
  Writes batched in memtable → mostly sequential flush
  5k writes/sec ≪ SSD sequential throughput → OK

Read path:
  50k reads/sec — bloom filters + block cache critical
  RAM for cache: 32–64 GB hot set

When numbers exceed one box — 500 GB data, 200k QPS — you say "shard across nodes using consistent hashing" and point to the previous chapters. Single-node math tells you when to distribute.

Worked example: feature flags for an IPL fantasy app

Store 10,000 feature flags (flag:double_points_enabled → true). Read on every API request. Writes rare (ops toggles during match).

Single-node design:

• In-memory hash map + snapshot to disk every 60 seconds
• GET served from RAM — < 1 ms
• PUT from admin console → update map + append WAL
• On restart: load latest snapshot + replay WAL tail

Why not Postgres? You could — but the interview wants KV trade-offs. Mention Postgres is fine at this scale; choose KV for predictable sub-ms reads and simple ops model.

If they ask scale: "10k keys fits one node until the end of time. If we stored per-user flags for 5 crore users, we shard by user_id hash — distributed chapter."

Common mistakes

Mistake 1 — jumping to distributed before single-node works.

Interviewers want the single-box PUT/GET path first. Sharding without a storage engine is architecture theater.

Mistake 2 — ignoring value size limits.

Letting clients PUT 50 MB values turns your KV into a bad object store. Cap values; use S3 for large blobs; store pointer in KV.

Mistake 3 — no durability story for writes.

"We use an in-memory map" without WAL loses data on crash. Say cache-aside explicitly if durability does not matter.

Mistake 4 — treating DELETE as trivial.

On LSM stores, deletes are tombstones until compaction. High delete churn creates read amplification. Mention tombstones if they go deep.

Mistake 5 — wrong engine for the access pattern.

B-tree lecture for a append-only metrics stream misses the point. Match LSM vs B-tree to read/write ratio.

Interview talking points

Structure for "design a key-value store":

1. Clarify — size, QPS, durability, value size, TTL needs
2. API — GET/PUT/DELETE (+ batch optional)
3. Single node — hash map + WAL + B-tree or LSM on disk
4. Capacity — napkin math, when one node breaks
5. Scale out — consistent hashing, replication (next chapter)
6. Trade-offs — CAP, quorum reads/writes if they push distributed

Opening line that works: "I'll start with a single-node durable store — WAL plus LSM for write-heavy ingest — then shard when we exceed one machine's disk or IOPS."

Depth questions to expect:

• How is DELETE implemented in LSM? → tombstone marker
• Compare to Redis → Redis optional persistence; this is durable-first
• Strong vs eventual consistency → single node is strong; distributed is next chapter
• Hot key → read replicas or client-side caching, not bigger hash map

Practice with hands-on labs

• Sharding Lab — after you understand single-node PUT/GET, see keys spread across shards
• Consistency Lab — compare read-your-writes on one node vs replicated nodes
• Mock Interview — "design a KV store" is a common prompt; practice the 45-minute arc

Implement a 50-line in-memory KV with WAL append in your language of choice. One evening of coding makes the whiteboard version feel automatic.

What comes next: distribution and replication

Single-node KV is the foundation. Production systems add partitioning (consistent hashing from Lessons 9–10), replication (leader-follower, quorum writes), and conflict handling (version vectors, last-write-wins).

The next chapter builds the distributed key-value store: multi-node routing, read repair, hinted handoff, and the CAP trade-offs interviewers expect after you nail GET/PUT/DELETE on one box.

Continue here: Key-Value Store Distributed.