## Problem Statement > Design a horizontally scalable, fault-tolerant key-value store supporting simple get/put/delete operations with tunable consistency and availability guarantees. ## Interview Context - **Company:** xAI - **Duration:** 45 minutes - **Frequency:** Commonly reported (December 2025 cycle) - **Product-specific note:** xAI operates large-scale ML infrastructure (training data, feature stores, caching layers for Grok). Interviewers may probe on how this store could back low-latency feature lookups or model metadata — emphasize throughput, tail latency, and operational simplicity over rich query features. ## Timing Breakdown (45 min) | Phase | Time | Focus | |---|---|---| | Requirements | ~5 min | Scope API, consistency model, scale targets | | High-Level Design | ~15-20 min | Partitioning, replication, request routing | | Deep Dives | ~15 min | Consistent hashing, replication/quorum, failure detection, conflict resolution | | Wrap-up | ~5 min | Trade-offs, bottlenecks, future extensions | ## Clarifying Questions | Question | Why it matters | |---|---| | What's the API surface — just get/put/delete, or also range scans, TTL, batch ops? | Determines partitioning strategy (hash vs range) and schema complexity | | What consistency model is required — strong or eventual? | Drives replication protocol (quorum, leader-based, or gossip) | | What's the expected scale (QPS, dataset size, value size)? | Determines partition count, sharding strategy, memory vs disk tiering | | Should the system tolerate node failures automatically, or is manual failover acceptable? | Impacts need for failure detection, replica re-routing, hinted handoff | | Do we need multi-datacenter replication? | Adds cross-region latency and conflict resolution complexity | **Likely Scope:** In scope — single-region deployment, simple get/put/delete API, tunable consistency (eventual by default, optional strong read), automatic failure detection and re-replication. Out of scope — multi-region active-active replication, complex query language, transactions across keys. ## Requirements ### Functional | Feature | Description | |---|---| | Put(key, value) | Write/overwrite a value for a key | | Get(key) | Read the value(s) for a key (may return multiple versions on conflict) | | Delete(key) | Remove a key (implemented as tombstone) | | Replication | Each key stored on N nodes for durability/availability | | Failure detection & recovery | Detect failed nodes, re-route traffic, re-replicate data | ### Non-Functional | Requirement | Target | |---|---| | Availability | 99.9%+, writes/reads succeed despite node failures | | Latency | p99 < 10ms for get/put on cache-resident data | | Scale | Millions of keys, 100K+ QPS, horizontally scalable | | Consistency | Tunable — eventual by default, read-your-writes / strong optional via quorum | | Storage | Values up to ~1MB, total dataset in TBs, replicated 3x | | Durability | No data loss after write acknowledged to client (survives 1-2 node failures) | ## High-Level Architecture ```mermaid flowchart TD Client[Client / SDK] Coordinator[Coordinator Node
Request Router] Ring[[Consistent Hash Ring
+ Virtual Nodes]] NodeA[Storage Node A
replica 1] NodeB[Storage Node B
replica 2] NodeC[Storage Node C
replica 3] Repl[Replication Manager
Quorum R/W/N] Vector[Vector Clocks
Version Store] CacheA[(In-Memory Cache)] CacheB[(In-Memory Cache)] CacheC[(In-Memory Cache)] LSMA[(LSM-Tree Store A)] LSMB[(LSM-Tree Store B)] LSMC[(LSM-Tree Store C)] Gossip[[Gossip Protocol
Membership + Failure Detection]] Merkle[Anti-Entropy
Merkle Tree Repair] Ack[Quorum Ack
Delivered to Client] Client --> Coordinator Coordinator --> Ring Ring --> NodeA Ring --> NodeB Ring --> NodeC NodeA --> Repl NodeB --> Repl NodeC --> Repl Repl --> Vector NodeA --> CacheA --> LSMA NodeB --> CacheB --> LSMB NodeC --> CacheC --> LSMC NodeA --> Gossip NodeB --> Gossip NodeC --> Gossip LSMA --> Merkle LSMB --> Merkle LSMC --> Merkle Vector --> Ack ``` | Component | Responsibility | |---|---| | Client SDK | Hashes key, knows ring topology (or asks coordinator), sends requests to correct replicas directly or via coordinator | | Coordinator | Any node receiving a request; determines replica set via consistent hashing, forwards to N replicas, collects quorum responses | | Consistent Hash Ring | Maps keys to nodes; supports virtual nodes for load balancing and smooth rebalancing on node add/remove | | Storage Node | Owns a partition range; stores data in-memory (cache) + on-disk (LSM-tree); serves reads/writes for its partitions | | Replication Manager | Ensures each key is written to N replicas; supports quorum reads/writes (R, W, N) | | Gossip / Failure Detector | Nodes exchange heartbeats and membership state; detects failed nodes, propagates ring changes | | Anti-Entropy (Merkle Trees) | Background process comparing replica data to detect and repair divergence | | Vector Clocks / Version Store | Tracks causal versions per key to detect and resolve write conflicts | ## APIs ``` PUT /kv/{key} Request: { "value": "", "context": "" } Response: 200 OK { "version": "" } GET /kv/{key} Response: 200 OK { "values": [ { "value": "", "version": "" } ] } // multiple entries returned if concurrent conflicting writes exist (client/app resolves) DELETE /kv/{key} Request: { "context": "" } Response: 200 OK // internally writes a tombstone GET /admin/ring/status Response: { "nodes": [...], "partitions": [...], "health": [...] } ``` ## Schema **Per-node local store (LSM-tree based, e.g., RocksDB/LevelDB style):** - Key: `user_key` (raw bytes, hashed to determine partition placement) - Value: serialized blob containing: - `value_bytes` - `vector_clock` (map of node_id -> counter) - `timestamp` (for tombstone GC and read-repair tie-breaking) - `tombstone_flag` - Access pattern: point lookups only (get/put/delete by key) — no range or secondary index needed for core KV semantics - Write path: append to in-memory memtable + WAL, flush to sorted SSTables on disk, background compaction merges/removes tombstones **In-memory cache layer (per node):** - Key: `user_key` - Value: `value_bytes + version` - Eviction: LRU/LFU, sized to hot working set - Purpose: absorb read traffic before hitting LSM-tree disk store **Cluster metadata store (small, replicated via gossip or a coordination service like a Raft-backed KV):** - Ring topology: node_id -> hash range(s), virtual node mappings - Membership: node_id -> {status: alive/suspect/dead, last_heartbeat} ## Core Flows **1. Put(key, value)** 1. Client (or coordinator) hashes `key` to find its position on the ring. 2. Coordinator identifies N replica nodes (the node owning that ring position + next N-1 nodes clockwise). 3. Coordinator sends write to all N replicas in parallel, attaching an updated vector clock. 4. Each replica appends to its WAL/memtable and acknowledges. 5. Coordinator waits for W acknowledgments (write quorum, e.g., W=2 of N=3); returns success to client once W is met. 6. Slow/failed replicas catch up later via hinted handoff or anti-entropy repair. **2. Get(key)** 1. Coordinator determines the N replicas for the key via the ring. 2. Sends read request to all N (or a fast subset) in parallel. 3. Waits for R responses (read quorum, e.g., R=2 of N=3). 4. Compares vector clocks: if one version dominates, return it; if concurrent/conflicting, return all versions to the client (or auto-merge with a policy like last-write-wins). 5. If replicas disagree, trigger read-repair: write the latest version back to the stale replica asynchronously. **3. Node failure & failure detection** 1. Nodes gossip heartbeats periodically with peers. 2. If a node misses heartbeats beyond a timeout, peers mark it "suspect," then "dead" after further confirmation (phi-accrual or simple timeout-based detector). 3. Ring is updated: the failed node's partitions are temporarily owned by the next node clockwise. 4. Writes destined for the dead node are stored elsewhere as "hints" (hinted handoff). 5. When the node recovers, hints are replayed to it; if permanently dead, an operator/auto-scaler adds a replacement and data streams in from remaining replicas. **4. Adding/removing a node (rebalancing)** 1. New node joins the ring at a computed position (or requests one via virtual nodes for even load). 2. Ownership of a contiguous key range transfers from neighbor(s) to the new node. 3. New node bulk-streams data for its range from existing replicas. 4. Once caught up, it starts serving live traffic; old replicas can garbage-collect data outside their new range. 5. Consistent hashing + virtual nodes ensures only ~1/N of data moves, not a full reshuffle. **5. Anti-entropy repair (background)** 1. Each replica periodically builds a Merkle tree over its key range. 2. Replicas exchange tree roots/branches with peers to find divergent sub-ranges (O(log n) comparison instead of scanning all keys). 3. Divergent keys are synced — newest version (by vector clock/timestamp) wins or conflict is surfaced. ## Deep Dive Notes **1. Partitioning strategy — consistent hashing with virtual nodes** - Naive modulo hashing (`key % N`) causes massive reshuffling when N changes. Consistent hashing bounds data movement to ~1/N of keys on node add/remove. - Virtual nodes (each physical node owns many small ring segments) smooth load distribution and make heterogeneous hardware (different capacities) easier to support by assigning more/fewer virtual nodes proportionally. - Trade-off: more virtual nodes = better balance but more metadata and gossip overhead. **2. Replication & consistency — tunable quorum (N, R, W)** - N = replica count, R = read quorum, W = write quorum. R + W > N guarantees strong (read-your-write) consistency; R + W ≤ N favors availability/latency at the cost of staleness. - Common defaults: N=3, R=2, W=2 (balanced), or R=1/W=1 for max availability (eventual consistency), or R=N/W=N for max consistency at cost of availability during partitions. - This directly implements the CAP trade-off: under a network partition, you must choose between rejecting requests (favor C) or serving possibly-stale data (favor A). **3. Conflict resolution — vector clocks vs last-write-wins** - LWW (timestamp-based) is simple but can silently drop concurrent writes if clocks are skewed — acceptable for caches, risky for critical data. - Vector clocks track causal history per key across replicas; detect true concurrent writes vs causally ordered ones, surfacing genuine conflicts to the application (like Dynamo) instead of silently discarding data. - Trade-off: vector clocks add metadata size (grows with number of writers) and push conflict resolution complexity to the client/application layer. **4. Failure detection accuracy — timeout vs phi-accrual** - Simple fixed timeouts cause false positives under transient network jitter (flapping nodes) or slow detection under real failures. - Phi-accrual failure detection computes a continuous suspicion level from heartbeat inter-arrival history, adapting to network conditions — reduces false positives while keeping detection latency low. - Trade-off: more complex to implement/tune than fixed timeouts; most systems (Cassandra) use phi-accrual for this reason. **5. Storage engine — LSM-tree vs B-tree for the local store** - LSM-trees (used by Cassandra, RocksDB) optimize for high write throughput: writes are sequential appends to memtable/WAL, later compacted — ideal for KV stores with heavy write load. - B-trees give better read latency for random point lookups but suffer write amplification under high write throughput and random I/O patterns. - Given KV stores are typically write-heavy at scale (and reads can be absorbed by cache), LSM-tree is the standard choice; compaction tuning (leveled vs size-tiered) becomes the operational lever. ## Trade-offs Summary | Decision | Trade-off | Why | |---|---|---| | Consistent hashing + virtual nodes over modulo hashing | More metadata/gossip overhead | Bounds data movement to ~1/N on membership change, enables smooth scaling | | Tunable quorum (N, R, W) over fixed strong/eventual | Requires careful client-side tuning per use case | Lets same system serve latency-sensitive and consistency-sensitive workloads | | Vector clocks over last-write-wins | More metadata, app must handle conflicts | Avoids silently dropping concurrent writes; correctness-critical data needs this | | Phi-accrual failure detection over fixed timeout | More implementation complexity | Reduces false positives/negatives from network jitter | | LSM-tree over B-tree for storage engine | Read amplification, background compaction cost | Optimizes for high write throughput typical of KV workloads | | Gossip-based membership over centralized coordinator | Eventually-consistent membership view | Avoids single point of failure/bottleneck for cluster metadata | ## One-Page Cheat Sheet **Architecture in 3 lines:** Clients hash keys onto a consistent-hash ring with virtual nodes; any node can coordinate a request to the N replicas owning that key; each node persists via LSM-tree + WAL, gossips membership/heartbeats, and repairs divergence via Merkle trees and read-repair. **Key APIs:** `PUT /kv/{key}`, `GET /kv/{key}`, `DELETE /kv/{key}` (tombstone), `GET /admin/ring/status`. **Key tables/stores:** Local LSM-tree (key → value+vector_clock+tombstone), in-memory LRU cache, cluster metadata (ring topology + membership via gossip). **Key numbers:** N=3 replicas, R=2/W=2 default quorum, p99 < 10ms cache-resident reads, 100K+ QPS, TB-scale dataset, ~1/N data movement on rebalance. **Opening Statement:** "I'll design a horizontally-scalable key-value store using consistent hashing with virtual nodes for partitioning, and tunable N/R/W quorums for replication so we can trade off consistency and availability per use case. Data is persisted locally via LSM-trees for write throughput, with gossip-based failure detection, hinted handoff, and Merkle-tree anti-entropy for resilience — this mirrors the Dynamo/Cassandra design lineage that underlies most production KV stores at scale."

Problem

Problem Overview

Self-assessment rubric

Requirements & Scope

Core Architecture

Deep Dives & Trade-offs

Communication & Structure

Solution