Design a Key-Value Store
& Distributed Cache

A key-value store question arrives in two flavours: "design a cache" (think Redis, Memcached, speed is everything, durability is optional) and "design a persistent key-value store" (think DynamoDB, Cassandra, RocksDB, durability is non-negotiable). The first question you should ask is which one the interviewer wants. Both share the same distribution primitives, but their tradeoff trees diverge immediately.

What makes this question deceptively hard is that the core operation, put(key, value) / get(key), is trivially solved with a single hash table. The interview is really asking: what happens when one machine isn't enough? How do you partition 10 TB of data across 50 nodes? How do you handle node failure without service disruption? How do you deal with one key receiving 100× the traffic of any other?

Before drawing anything, nail down whether this is a cache (latency-first, data loss acceptable) or a persistent store (durability-first). These two constraints drive almost every subsequent decision.

Functional requirements

Non-functional requirements

The numbers below are working assumptions for this design, 10 TB of total data and 1M peak QPS. The estimator in §3 is calibrated to these defaults.

Caches are almost entirely read-dominated. The write rate matters because it determines replication pressure and invalidation fan-out. The storage number tells us how many nodes we need and whether in-memory storage is economically viable. Cache sizing is derived from the working set, not total data.

Clients are services, web browsers, or mobile apps, anything that issues get/put calls. They connect through a load balancer that distributes requests evenly across API server instances.

API servers hold a small in-process (L1) cache per server. This is the first stop, a read that hits here costs zero network round-trips. The L1 is intentionally small (a few hundred MB) and short-lived, acting as a micro-cache for the hottest keys.

Cache cluster (in-memory key-value store, e.g. Redis or Memcached) is the L2 layer. All L1 misses land here. It holds the working set of the data, the 10–20% of keys receiving 80–90% of traffic. Nodes are partitioned using consistent hashing so that adding or removing a node remaps only a small fraction of keys.

Persistent store (e.g. RocksDB, Cassandra, or a relational database) is the source of truth. Cache misses fall through to this layer. For the pure cache variant, this is the upstream database; for a persistent KV store, this is the storage engine itself.

Coordinator (e.g. Zookeeper, etcd) manages cluster membership, leader election, and failure detection. Nodes heartbeat to the coordinator; when a node goes silent, the coordinator triggers automatic failover to a replica.

Architectural rationale

Real-world comparison

Once the dataset outgrows a single machine, you need a rule for deciding which node holds which key. The rule must be stable enough that adding or removing a node doesn't remap everything, fast enough to compute on every request, and balanced enough that no single node carries a disproportionate share of the load.

The core idea of consistent hashing is placing both nodes and keys on a circular hash ring (0 to 2³²). Each key is assigned to the first node clockwise from its position on the ring. When a node is added, only the keys between the new node and its predecessor need to move. When a node is removed, only its keys move to its successor.

Virtual nodes solve the load imbalance problem. With a small number of physical nodes, the ring partitions unevenly, one node might hold 40% of the keyspace and another 10%. By mapping each physical node to hundreds of virtual positions on the ring (e.g., hash("nodeA:0"), hash("nodeA:1"), ...), the load distributes much more evenly. It also makes rebalancing smoother: adding a node with 150 virtual nodes redistributes load from every existing node proportionally.

The interface surface area for a KV store is intentionally small. Each operation needs a clear ownership of the key, explicit TTL semantics, and a defined behaviour for non-existent keys.

Core endpoints

GET /v1/keys/{key}

// Request (no body, key in path)
GET /v1/keys/user:1234:session HTTP/1.1

// Response, hit
HTTP/1.1 200 OK
X-Cache: HIT
X-TTL-Remaining: 3542
{
  "key": "user:1234:session",
  "value": "eyJhbGciOiJIUzI1NiJ9...",
  "expires_at": "2026-03-29T12:00:00Z"
}

// Response, miss
HTTP/1.1 404 Not Found
{ "error": "key_not_found" }

PUT /v1/keys/{key}

// Request
PUT /v1/keys/user:1234:session HTTP/1.1
Content-Type: application/json
{
  "value": "eyJhbGciOiJIUzI1NiJ9...",
  "ttl_seconds": 3600,          // optional; 0 = no expiry
  "if_not_exists": false         // atomic set-if-absent
}

// Response
HTTP/1.1 200 OK
{ "status": "ok", "version": 42 }

// Response, conflict (if_not_exists: true, key already exists)
HTTP/1.1 409 Conflict
{ "error": "key_exists", "current_version": 38 }

DELETE /v1/keys/{key}

HTTP/1.1 204 No Content  // success (idempotent)
HTTP/1.1 404 Not Found   // key didn't exist (acceptable, idempotent)

Optional endpoints by level

Conditional writes & Compare-and-Swap (CAS)

The version field in the entry schema (§7) enables optimistic locking. Two clients reading the same key both receive "version": 42. If both try to write, only the first succeeds, the second gets a 409 Conflict with the current version and must re-read and retry.

// Conditional write: only update if version matches
PUT /v1/keys/user:42:balance HTTP/1.1
{
  "value": "150",
  "if_version": 42        // fails with 409 if current version ≠ 42
}

// Response on conflict
HTTP/1.1 409 Conflict
{ "error": "version_mismatch", "current_version": 43, "hint": "re-read and retry" }

CAS is the standard answer to "how do you prevent lost updates when two clients write the same key concurrently?" without requiring distributed transactions. Redis offers two separate atomicity mechanisms for this: a Lua script (executes atomically, blocking other commands during its run, no WATCH needed or allowed) or the WATCH + MULTI + EXEC transaction pattern (optimistic locking, aborts the transaction if the watched key changed between WATCH and EXEC). These are mutually exclusive; do not combine them. DynamoDB implements the same guarantee natively via ConditionExpression.

Security & multi-tenancy

For a public or multi-tenant cache, three controls are non-negotiable at L6+. First, namespace isolation: prefix all keys with a tenant or service identifier (e.g., tenant_id:entity:id) and enforce this at the API layer, no cross-namespace reads should be possible at the key level. Second, authentication: Redis has historically shipped with no auth by default, leading to numerous high-profile exposure incidents; always enable Redis ACLs (since Redis 6.0) with per-service credentials. Third, value size limits: reject writes above a configured max (e.g., 1 MB) at the API tier to prevent a single key from monopolising a cache node's memory and triggering eviction avalanches.

The most important question in the read path is: what happens on a cache miss? The answer determines latency for cold or low-frequency keys, and also whether the system can defend itself against a cache stampede, where a popular key expires and thousands of requests simultaneously hit the backing store.

Cache stampede prevention

When a popular key expires, every concurrent request sees a miss simultaneously and races to query the database, a thundering herd. This is more destructive than it sounds: because the database is provisioned for only 10% of traffic (the 90% hit rate target from §3), a stampede that doubles or triples miss volume pushes it past its p99 latency SLO immediately. The tier we deliberately sized down becomes the failure point.

The standard mitigations are: (1) distributed mutex, use an atomic compare-and-set in the cache cluster to let only one request fetch from the database while others wait; (2) probabilistic early recompute (a.k.a. "XFetch"), before a key expires, randomly decide to recompute it based on how close the TTL is, spreading recomputations over time; (3) stale-while-revalidate, return the stale cached value immediately while triggering an asynchronous background refresh.

Write path

The write path is simpler but the tradeoff is between write latency and consistency. Write-through updates the cache and database synchronously on every write, cache is always fresh but every write pays a database round-trip. Write-behind acknowledges the write after updating the cache, then asynchronously flushes to the database, lower write latency but risk of data loss if the cache fails before the flush. Cache-aside leaves the cache population to read time, the simplest model but means every cold-start incurs a cache miss.

A key-value store is deceptively simple at the surface, a map from strings to blobs. The interesting design decisions live in what metadata accompanies each entry, how that metadata is stored efficiently, and what storage engine sits underneath.

Access patterns

Two things jump out from this table. First, point reads dominate overwhelmingly, O(1) hash map access is the right primary structure for an in-memory store, not a B-tree or skip list. Second, TTL expiry and LRU eviction both require efficient ordering by time, which a pure hash map doesn't support. The typical solution is to maintain a hash map for O(1) lookup alongside a doubly-linked list ordered by recency (for LRU) or by expiry time (for TTL), with the map storing pointers into the list.

Storage engine options

When memory fills up, the cache must decide what to throw away. The right eviction policy depends on the access pattern of the workload. Equally important is how the cache is populated, the caching strategy determines whether writes proactively fill the cache or leave it to reads.

Eviction policies

Caching strategies

Classic probes table

LRU (Least Recently Used) is the eviction policy asked about most in interviews. The data structure is a hash map for O(1) lookup, wired to a doubly-linked list ordered by recency. On every access, the node moves to the head. On eviction, the tail is removed. The challenge is doing this in O(1) for all three operations, get, put, and evict.

Why O(1) requires both structures

type Node struct {
    key, val    string
    prev, next  *Node
}

type LRUCache struct {
    cap        int
    m          map[string]*Node
    head, tail *Node  // sentinel nodes (never evicted)
}

func NewLRU(cap int) *LRUCache {
    h, t := &Node{}, &Node{}
    h.next, t.prev = t, h
    return &LRUCache{cap: cap, m: make(map[string]*Node), head: h, tail: t}
}

func (c *LRUCache) Get(key string) (string, bool) {
    n, ok := c.m[key]
    if !ok { return "", false }
    c.moveToFront(n)     // O(1), just pointer rewiring
    return n.val, true
}

func (c *LRUCache) Put(key, val string) {
    if n, ok := c.m[key]; ok {
        n.val = val
        c.moveToFront(n)
        return
    }
    if len(c.m) == c.cap {
        lru := c.tail.prev       // O(1), tail sentinel's prev is LRU node
        c.remove(lru)
        delete(c.m, lru.key)
    }
    n := &Node{key: key, val: val}
    c.m[key] = n
    c.insertFront(n)
}

func (c *LRUCache) remove(n *Node) {
    n.prev.next, n.next.prev = n.next, n.prev
}
func (c *LRUCache) insertFront(n *Node) {
    n.next, n.prev = c.head.next, c.head
    c.head.next.prev, c.head.next = n, n
}
func (c *LRUCache) moveToFront(n *Node) { c.remove(n); c.insertFront(n) }

Bloom filters have two complementary uses in a key-value system. Their primary role is inside storage engines: RocksDB, Cassandra, and LevelDB attach a Bloom filter to every SSTable level so that a point read can skip a disk seek if the filter says the key definitely isn't there, eliminating most unnecessary I/O in LSM-tree reads. Their secondary role is at the API layer: a miss that falls through to a database for a key that simply doesn't exist is pure waste, and a filter placed in front of the cache can short-circuit it immediately. This matters especially in public APIs where misbehaving or malicious clients probe arbitrary keys.

A Bloom filter is a probabilistic data structure: it can definitively say a key does not exist (no false negatives), but it may occasionally say a key might exist when it doesn't (false positives). The false positive rate is configurable and depends on the bit array size and number of hash functions.

False positive rate formula

For a Bloom filter with m bits, n inserted elements, and k hash functions, the false positive probability is approximately:

The optimal number of hash functions for a given m/n ratio is k = (m/n) × ln(2). In practice, using 10 bits per element with 7 hash functions achieves a false positive rate of roughly 1%. For a set of 100 million keys, that's 100 MB, orders of magnitude smaller than storing the keys themselves.

Interviewers frequently follow up "design a cache" with "would you use Redis or Memcached?" Both are in-memory key-value stores targeting sub-millisecond latency, but they are built for different workload profiles. The answer should come from requirements, not from brand familiarity.

Rate limiting with Redis atomic increment

One of the most common Redis-specific interview follow-ups is implementing a rate limiter. The simplest approach is a fixed-window counter using INCR + EXPIRE, the right first step to explain before graduating to sliding window or token bucket approaches.

-- Lua script (atomic execution in Redis)
-- Key pattern: ratelimit:{user_id}:{window_start}
-- window_start = floor(current_unix_sec / window_size)

local key    = KEYS[1]         -- e.g. "rl:user:42:1743200"
local limit  = tonumber(ARGV[1]) -- e.g. 100 (requests per window)
local window = tonumber(ARGV[2]) -- e.g. 60 (seconds)

local count = redis.call('INCR', key)
if count == 1 then
    redis.call('EXPIRE', key, window)  -- set TTL only on first request
end

if count > limit then
    return 0  -- rate limited
end
return 1      -- allowed

L6+ candidates are expected to own the system end-to-end. That includes knowing which signals to monitor, how to diagnose degradation, and how to change the system safely in production. The six signals to instrument on any cache cluster follow directly from the NFRs in §2.

Key metrics to monitor

Safe operations playbook