04QuestionsDistributed cache

04 · Worked prompt

Distributed cache

Design partitioning, replication, eviction, consistency, hot-key protection, and node rebalancing.

35 minInterview blueprint

INTERVIEW RUBRIC

What a passing answer must show

100 points · 45 minutes

20pts
Scope the problem
0–5 min
Prioritize the core flows, state the scale, and name the non-goals.
15pts
Define contracts
5–10 min
Identify durable entities, APIs, idempotency, and the source of truth.
30pts
Complete the diagram
10–25 min
Trace one write path and one read path. Label the commit boundary and async work.
20pts
Lead one deep dive
25–38 min
Choose the highest-risk trade-off and explain the mechanism, alternative, and cost.
15pts
Prove reliability
38–45 min
Walk a failure, recovery, metric, bottleneck, and evolution path.

DRAW THIS FIRST

One complete box-and-arrow design

Design partitioning, replication, eviction, consistency, hot-key protection, and node rebalancing.

Distributed cache system architecture. A ring epoch assigns ownership; versions and quorum policy make replication and rebalancing explicit. Request path: Application clients to Cache router to Primary owner to Primary memory shard. Asynchronous path: Replication stream to Replica owners. Read path: Read coordinator to Eligible replicas. External dependency: Membership service. Delivery path: Eviction channel. — Distributed cache · system architecture

DEFEND THE DIAGRAM

Explain every boundary before adding more boxes.

A ring epoch assigns ownership; versions and quorum policy make replication and rebalancing explicit.

INTERVIEW CONTRACT

Design partitioning, replication, eviction, consistency, hot-key protection, and node rebalancing.

CAPACITY QUESTIONS TO QUANTIFY

Millions QPS · sub-ms target · memory capacity · Zipfian popularity. State average and peak load, stored bytes, bandwidth or open connections, and the growth horizon before choosing a partitioning strategy.

End-to-end walkthrough

Trace the architecture in this order.

01
Enter and classify the request
Application clients → Cache router
GET / SET / DELETE enters over HTTPS / RPC. Cache router handles identity, admission, routing, and request context; it deliberately does not own domain truth.
02
Validate, then cross the commit boundary
Cache router → Primary owner → Primary memory shard
Primary owner receives the command, checks invariants and retry identity, then uses write owner to update Primary memory shard. The user-visible mutation is accepted only after this boundary succeeds.
03
Move replayable work off the request path
Primary owner → Replication stream → Replica owners → Eligible replicas
Primary owner emits publish after commit; Replica owners uses consume and replicate to build Eligible replicas. Consumers must tolerate duplicate delivery and stale retries because this path is asynchronous.
04
Serve reads from the right authority
Cache router → Read coordinator → Eligible replicas / Primary memory shard
Read coordinator uses quorum / nearest for the common, read-optimized path and strong read when correctness or repair requires authoritative state. The API must state the freshness promise instead of hiding it.
05
Contain the dependency boundary
Primary owner → Membership service
watch epoch crosses into Membership service. Treat timeouts as ambiguous, use a deadline and idempotent retry or reconciliation, and keep the core state recoverable when the dependency is unavailable.
06
Deliver without changing the source of truth
Replica owners → Eviction channel → Application clients
Replica owners uses fan-out; Eviction channel returns updates over stream / push. Sequence IDs, reconnect cursors, and backpressure make delivery resumable without turning a socket into durable state.

Ownership ledger

Why each box exists—and what it must defend.

Component	Owns	Why it exists	Interviewer probe
Cache routerHash key + ring epoch	Identity, admission, routing	Protects the system edge and attaches trusted context before domain work begins.	Timeout budgets, quotas, regional routing
Primary ownerVersion + TTL + CAS	Write invariants and retry identity	Serializes or conditionally applies state changes before acknowledging success.	Concurrent writes, deduplication, hot ownership
Primary memory shardCurrent value + version	Authoritative durable state	Provides the one record used to resolve disputes, recover, and rebuild projections.	Partition key, replication, consistency
Replication streamOrdered mutations	Durable asynchronous handoff	Absorbs bursts and lets slow or optional work retry independently of the request.	Ordering key, lag, retention, dead letters
Replica ownersApply + acknowledge	Replayable processing	Runs expensive, fan-out, or side-effecting work with leases and bounded retries.	Idempotency, poison work, autoscaling
Eligible replicasVersioned resident copy	Rebuildable query state	Shapes data for the dominant reads without weakening the write-side invariant.	Freshness, versioning, rebuild time
Read coordinatorPrimary/replica policy	Read composition and freshness policy	Chooses authoritative or derived state and returns a stable client contract.	Fan-out, cache policy, partial results
Membership serviceNodes + ring epochs	External capability, not local truth	Keeps a specialized or third-party concern behind a replaceable contract.	Ambiguous timeout, circuit breaking, fallback
Eviction channelInvalidation metadata	Connection and delivery state	Separates open connections and fan-out pressure from durable domain state.	Reconnect, ordering, slow consumers

Physical design

Name the database, shard key, indexes, and guarantees.

Database + storage: Use an in-memory Redis/Memcached-style key-value engine; the origin database remains authoritative. An append log is optional only for warm restart.
Partitioning / sharding: Consistent or rendezvous hashing with many virtual nodes limits movement. Hash full keys; replicate or L1-cache extreme hot immutable keys.
Indexes: Hash-table key lookup, TTL timing wheel, frequency sketch for admission, and per-tenant memory counters are the important structures.
Replication + consistency: Use two or three zone replicas. Per-key versions/CAS prevent lost updates; replica reads are allowed only under an explicit staleness contract.
Cache, queue + recovery: Request coalescing, negative cache, stale-while-revalidate, versioned invalidation, and rate-limited rebalance protect the origin.
Capacity math: Estimate resident bytes, GET:SET, hit target, TTL churn, network Gbps, hottest-key QPS, and origin capacity during cold start.
Alternative rejected: Modulo sharding remaps most keys after membership change; consistent/rendezvous hashing is worth the ownership complexity.

Deep-dive candidates

Pick one risk and explain the mechanism, alternative, and cost.

Membership

Version the ring and move bounded ranges with shadow reads before cutover

A node join should not remap the entire cache

Hot keys

Replicate or locally memoize popular immutable values and apply request coalescing

More shards do not solve one key

Consistency

Use per-key versions and define whether reads may fall back to replicas

A cache is allowed to be stale only if the product contract says so

Failure pressure test

Show detection, containment, recovery, and evidence.

Node loss

Promote a replica under a new ring epoch and rate-limit refills

ownership changes and origin QPS

Rebalance storm

Move ranges gradually with per-node bandwidth budgets

migration throughput and miss ratio

Stampede

Grant one fill lease and serve stale when safe

coalesced waiter count

Before you finish, explicitly cover

Functional requirements and non-goals
Peak traffic, storage, bandwidth, and growth
Entities, APIs, idempotency, and pagination
Source of truth and consistency promise
Partition key, replicas, caches, and hot spots
Retries, backpressure, failover, and reconciliation
Latency, saturation, correctness, and recovery metrics
Security, migration, cost, and multi-region evolution

SAY THIS WHILE YOU DRAW

A four-part talk track

Scope
“I’ll prioritize serve get/set/delete at sub-millisecond latency and scale capacity by adding nodes.”
Scale
“The design changes around millions qps · sub-ms target · memory capacity · zipfian popularity.”
Decision
“Client-side hashing removes a hop; a routing tier centralizes membership and policy.”
Risk
“The first failure I want to pressure-test is: Node loss and rebalancing can create an origin-crushing miss storm.”

Reference details

Open these only after you can explain the diagram above without reading.

01Requirements and state lifecycle4 requirements

Serve get/set/delete at sub-millisecond latency
Scale capacity by adding nodes
Survive node loss with bounded inconsistency
Prevent hot keys and rebalancing from crushing the origin

Distributed cache · state lifecycle

state lifecycle

Each transition must be durable, observable, and safe to retry.

absent

filling

resident

stale

evicted

02Data model and APIs4 entities · 3 interfaces

Core entities

CacheEntrykey, value, version, expires_atOwner: Cache shard

HashRangestart, end, primary, replicas, epochOwner: Membership service

NodeStatenode_id, capacity, health, epochOwner: Cluster manager

FillLeasekey, owner, deadlineOwner: Origin shield

External interfaces

PUT /v1/cache/{key}

Store a versioned value with optional TTL

GET /v1/cache/{key}

Read value, version, and freshness metadata

DELETE /v1/cache/{key}

Write a tombstone that survives replica races

03Deep dives and trade-offsChoose one

Membership

Version the ring and move bounded ranges with shadow reads before cutover

A node join should not remap the entire cache

Hot keys

Replicate or locally memoize popular immutable values and apply request coalescing

More shards do not solve one key

Consistency

Use per-key versions and define whether reads may fall back to replicas

A cache is allowed to be stale only if the product contract says so

04Failures, recovery, and evidence3 scenarios

Node loss

Promote a replica under a new ring epoch and rate-limit refills

ownership changes and origin QPS

Rebalance storm

Move ranges gradually with per-node bandwidth budgets

migration throughput and miss ratio

Stampede

Grant one fill lease and serve stale when safe

coalesced waiter count

05What makes the answer seniorInterviewer signals

The origin-protection story matters more than naming Redis
Explain what the client does with two ring epochs during transition
Tie consistency to the cached data, not to a universal cache rule
Primary trade-off: Client-side hashing removes a hop; a routing tier centralizes membership and policy.

BEFORE THE NEXT QUESTION

Can you redraw it from memory?

Name the source of truth.
Trace the write and read paths.
Defend one trade-off.
Recover from one failure.

Scope the problem

Define contracts

Complete the diagram

Lead one deep dive

Prove reliability

Write

Propagate

Read

Trace the architecture in this order.

Enter and classify the request

Validate, then cross the commit boundary

Move replayable work off the request path

Serve reads from the right authority

Contain the dependency boundary

Deliver without changing the source of truth

Why each box exists—and what it must defend.

Name the database, shard key, indexes, and guarantees.

Pick one risk and explain the mechanism, alternative, and cost.

Membership

Hot keys

Consistency

Show detection, containment, recovery, and evidence.

Node loss

Rebalance storm

Stampede

Reference details

Core entities

External interfaces

Membership

Hot keys

Consistency

Node loss

Rebalance storm

Stampede

Can you redraw it from memory?