TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design a Key-Value Store

    SD Mock · Design a Key-Value Store

    SD Mock · Design a Key-Value Store

    Overview

    Design a distributed key-value store like Dynamo or Cassandra on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design a key-value store

    A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.

    The API is two calls, so there is almost no product to negotiate. The signal sits in the machinery: how keys spread across machines, how copies stay in step, what a read returns when copies disagree, and what the cluster does while a node is dead. "Consistent hashing plus replication" is a phrase, not a design.

    Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):

    • Notepad. Shared notes. Requirements, capacity math, the storage-engine sketch and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    Build incrementally while you talk. Trace one put and one get end to end through your diagram, including the write that lands while one replica is down. Argue the tradeoff, not "that's what Cassandra does."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    Ask about consistency first

    Everything downstream depends on it. Must every read see the latest write, is "eventually" fine, or should each caller choose? Then the read and write mix, value size (kilobytes or megabytes), point lookups versus range scans, and one region versus several. A strong default: point lookups, small values, always writable, consistency tunable per request, one region across three zones.

    Partitioning: the ring, not mod N

    hash(key) mod N sends nearly every key somewhere new when N changes, and N will change. Put nodes and keys on a hash ring instead: a key belongs to the first node clockwise, and a new node takes over only the slice next to it, roughly one Nth of the data. Give each machine many ring positions (virtual nodes) so slices even out, bigger machines carry more, and a dead machine's load spreads over many survivors rather than one neighbour. Interviewers will ask what goes wrong without them.

    Replication: the walk and the preference list

    Store each key on N machines (usually three): walk clockwise from the key and take the first N distinct physical machines, skipping virtual nodes you already used, and ideally skipping until the copies land in different racks or zones. There is no leader: the node that receives a request acts as coordinator, finds the replicas and fans out. Expect "why no leader?" Answer: no single point of failure and the store stays writable, at the price of replicas that can disagree.

    Quorums: W + R > N

    W is how many replicas must confirm a write; R is how many must answer a read. When W + R > N, any write set and any read set share a replica, so a read reaches the latest acknowledged write. N = 3 with W = 2, R = 2 is the balanced default. W = 3, R = 1 favours reads; W = 1, R = 3 favours writes; W = 1, R = 1 gives up the overlap for speed. Make the numbers per request, and say the cost: the coordinator waits for the slowest of the replicas it needs. Strong candidates add the caveat that overlap is not linearizability: concurrent writes, partial failures and sloppy quorums can still surface stale or duplicate versions.

    Conflicts: last-write-wins or vector clocks

    Without a leader, two clients can update one key through different coordinators during a network blip. Last-write-wins keeps the newest timestamp: simple, but the other write vanishes silently and clocks drift. Good for caches and "last seen" fields. Vector clocks attach a counter per node to each version. If one clock is ahead or equal on every counter, it replaces the other; if each is ahead somewhere, the versions are concurrent siblings and the reader's application merges them (a cart takes the union). Costs: merge logic in the client, deleted items that come back after a union, clocks that grow and need trimming. CRDTs are the "data types that merge themselves" variant.

    Failure detection: gossip

    All-to-all heartbeats cost about n² messages per round. With gossip, each node bumps its own heartbeat counter and swaps its membership list with a few random peers every second; a peer whose counter stops rising past a timeout is suspected down, and more than one node must agree before the cluster acts on it.

    Failures: hints, read repair, Merkle trees

    • Temporary failure: a sloppy quorum writes to the first W healthy nodes on the ring; a stand-in keeps the write with a hint naming the real owner and hands it back when the owner returns (hinted handoff). The price: during the outage, W + R > N no longer promises overlap.
    • Drift on popular keys: read repair. The coordinator sees a stale version in the replies and pushes the newest one to that replica.
    • Long outages and cold keys: anti-entropy with Merkle trees. Hash buckets of keys, hash pairs of hashes up to a root, compare top-down, and transfer only the buckets that differ. Work follows the size of the difference, not the data.
    • A whole zone or data center lost: replicas placed in different zones or regions.

    Inside one node: the storage engine

    For a write-heavy store, an LSM tree: append to a commit log for durability, insert into a sorted in-memory memtable, acknowledge; flush full memtables as immutable SSTables, and compact them in the background. Reads check the memtable, then each SSTable's Bloom filter (never a false "no"; about one false "maybe" in a hundred at ten bits per key), then open only the files that might hold the key. Deletes write tombstones that must reach every replica before compaction drops them, or a deleted key can come back. A B-tree updates in place: steadier reads, more random writes.

    Reference solution

    One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.

    Requirements (lock these or take the defaults)

    • get(key), put(key, value), delete(key); values under about 10 KB; point lookups only
    • Holds far more than one machine: 40 TB today, growing
    • Always writable, even during node failures and network blips
    • Consistency tunable per request; low latency (single-digit milliseconds at p99 inside a region)
    • Scales by adding nodes, with automatic rebalancing; one region across three zones to start

    Capacity

    • 40 TB × 3 replicas = 120 TB stored
    • 8 TB usable per node → 15 nodes for disk alone; keep disks about two-thirds full so compaction has room → about 24 nodes
    • Peak 300,000 requests a second, 70% reads: 210 k reads × R=2 + 90 k writes × N=3 = 690 k replica operations a second, about 29 k per node
    • The bytes and the writes force partitioning. Read replicas would not help: every replica holds everything and sees every write.

    Components to put on the board

    How the graph works: callers use a client library that knows the ring (or go through a load balancer to any node). Every storage node is identical: it holds a slice of the ring, can coordinate any request, gossips membership, and runs the storage engine locally. A background repair worker compares Merkle trees between replicas.

    Web Client / Service (callers, ring-aware client library)
        → Load Balancer (optional: any node can take any request)
        → Storage Node tier (Service labelled "Storage node"; mark distributed)
            ↔ other Storage Nodes: replicate to N = 3 (label the edge), gossip membership (label)
            · Note: "Ring: consistent hashing, 256 vnodes/machine or fewer, N = 3, W = 2, R = 2"
            · Note: "Engine: commit log → memtable → SSTables + Bloom filters, compaction"
        ← Worker: anti-entropy repair (Merkle trees), on a schedule
        → Blob Store (optional: snapshots and backups)
    

    Walk one request: put("cart:42") while one replica is down

    1. The client hashes cart:42 onto the ring and sends the put to the nearest node, which becomes the coordinator.
    2. The coordinator walks clockwise to the first three distinct machines: A, B, C, in three different zones.
    3. Gossip already marked C down: its heartbeat stopped rising and several peers agreed.
    4. The coordinator writes to A and B and to D, the next healthy node, which stores the copy with a hint naming C.
    5. A and B append to their commit logs, update their memtables and acknowledge. W = 2 is met, so the client hears "ok" with the new version context.
    6. When C returns, D hands the write over and deletes its hint. If C had been gone for days, Merkle-tree repair would find and copy the missing buckets instead.

    The read: get("cart:42") with R = 2 asks two replicas, compares versions, returns the newest (or both siblings if their clocks are concurrent) and repairs any stale replica on the way out.

    Record layout

    key → [ (value, vector clock [node:counter,…], timestamp, tombstone?) … siblings ]
    ring state: node → (tokens, zone, status, heartbeat)       — gossiped, every node holds it
    hints: (target node, key, version, value)                    — kept by stand-ins until delivered
    

    Scaling and wrap-up

    • Add a node: it claims new ring positions and streams only those slices from neighbours; throttle streaming so it does not starve live traffic
    • Hot keys: one key hammers one replica set; cache it at the client, or split its value across subkeys
    • Multi-region: replicate to every region, use a local quorum per region for low latency, and accept cross-region conflicts (vector clocks or LWW)
    • Monitor: p99 latency per replica, pending hints, compaction backlog, repair lag, tombstone counts

    Equally defensible variants

    A leader per partition with Raft or Multi-Paxos (the way DynamoDB, Spanner and CockroachDB work) if the caller needs strong consistency and can tolerate a short pause on failover. Last-write-wins instead of vector clocks for data where losing a concurrent write is harmless. A B-tree engine for read-heavy workloads with range scans. What matters is that you can argue the tradeoff.

    More in System Design Interview Prep: AI Coach Edition

    • SD Mock · Design an API Rate Limiter
    • SD Coach · Event-Driven Systems and Notifications
    • SD Mock · Design a Notification System
    • SD Coach · Async Jobs, Schedulers and Crawlers
    • SD Mock · Design a Web Crawler
    • SD Coach · Distributed Storage
    • SD Coach · File Sync: Dropbox and Google Drive
    • SD Mock · Design Dropbox
    • SD Coach · Transactional Systems
    • SD Mock · Design Ticketmaster
    • SD Coach · Batch and Stream Pipelines
    • SD Coach · Real-Time Chat and Collaboration
    View the full course (43 sessions) →