Distributed Cache System — System Design Interview Practice

Interview prompt

Design a distributed cache like Redis or Memcached that serves key-value reads and writes with predictable low latency, bounded memory, replication, and recovery.

• Define key ownership, TTL behavior, eviction policy, and the consistency contract for reads, writes, and deletes.
• Use partitioning and hot-key isolation to serve 10M operations per second over a 1TB working set without a single-node bottleneck.
• Separate cache operations from replication, rebalancing, eviction telemetry, and warmup so background work cannot stall requests.
• Explain node failure, quorum or primary-replica choices, cache stampede protection, security, and degraded behavior.

Requirements and scale assumptions

• Store, retrieve, overwrite, and delete values by namespace and key.
• Support per-entry TTL, explicit expiration, and an observable miss or expired result.
• Provide atomic compare-and-set and increment operations for callers that need coordination.
• Distribute entries across cache nodes and replicate selected partitions for failure recovery.
• Expose node, partition, memory, eviction, and replication health to operators.
• Allow authenticated clients to use namespaces, quotas, and encryption in transit.
• Keep the normal GET, SET, and DELETE path below p99 5ms inside a region.
• Handle 10M cache operations per second and a 1TB working set with horizontal partitioning.
• Keep a node failure from losing acknowledged writes beyond the declared durability contract.
• Bound memory, queue depth, replication lag, and recovery work so overload is visible and controlled.
• Degrade predictably during a partition, backing-store failure, or hot-key event.
• Serve 10M operations per second at peak over approximately 1TB of active values.
• Assume a roughly 90:10 read-to-write ratio, with a small set of keys capable of becoming extremely hot.
• Partition by a hash of namespace and key; keep replicas in separate failure zones and reserve headroom for rebalancing.
• Treat the cache as the serving layer unless the product explicitly requires durable writes to a backing database.

• Peak throughput: 10M operations/second — Capacity assumption that drives shard count, connection limits, and backpressure.
• Working set: 1TB active values — Memory and replica capacity must include metadata, fragmentation, and failover headroom.
• Operation latency: p99 < 5ms — Budget for the regional cache path, excluding optional asynchronous telemetry.
• Replica freshness: p99 lag < 1s — Operational target for asynchronous replicas when the chosen consistency mode permits it.
• Cache effectiveness: >= 95% hit rate for hot working set — A product-specific target that must be measured by namespace and key class, not only globally.

Key entities

• CacheEntrynamespace (PK), key (SK), value or valuePointer, version, expiresAt, sizeBytes, lastAccessedAt

  The serving record returned by a cache read. Version and expiry travel with the value so stale replicas and expired entries can be rejected.

• CacheNodenodeId, zone, endpoint, capacityBytes, usedBytes, status, membershipEpoch

  A cache process or shard host that owns partitions and reports capacity, health, and membership state.

• PartitionpartitionId, hashRange, primaryNodeId, replicaNodeIds, epoch, state

  The routing and failover unit. Its epoch prevents an old owner from accepting writes after rebalancing.

• ReplicapartitionId, nodeId, role, replicationOffset, lastHeartbeatAt, status

  Replication state for a partition copy, including whether it can be promoted and how far it has caught up.

• EvictionRecordrecordId, namespace, key, reason, bytesFreed, evictedAt

  Bounded telemetry for TTL and memory-pressure evictions; it is not part of the cache read critical path.

Data flow

1. 1. Route the key to a partitionThe gateway authenticates the namespace, hashes namespace plus key, and uses a versioned partition map to select the primary or an eligible replica.
2. 2. Serve a cache hitThe cache node checks the entry version and expiresAt in memory, returns the value immediately, and increments bounded local hit telemetry.
3. 3. Read or write the primaryA miss reads the current partition owner and fills the local entry; a SET, DELETE, or atomic operation updates the primary with a conditional version check.
4. 4. Replicate the partition changeThe primary appends the mutation to a per-partition replication log and acknowledges after the selected consistency boundary, while replicas apply mutations in order.
5. 5. Evict, rebalance, and recover asynchronouslyBackground workers expire or evict entries, move hash ranges, warm replicas, and promote a caught-up copy after failure without blocking healthy cache operations.

Deep dives and trade-offs

• Partitioning and consistent hashingHash namespace plus key into fixed slots or a consistent-hash ring so adding a node moves a bounded fraction of entries. Keep the partition map versioned. A request carrying an old epoch must refresh or fail rather than write to a previous owner. Use virtual nodes or fixed slots to spread uneven key sizes, and reserve capacity for a node or zone failure.
• Replication and consistencyPrimary-replica replication is simple for ordered writes; quorum acknowledgements improve durability but add latency and reduce availability during a partition. Offer an explicit consistency mode such as primary, session, or quorum read instead of hiding stale-read behavior in the client library. Replicate deletes as versioned tombstones so delayed data cannot resurrect after expiry or invalidation.
• TTL, eviction, and memory pressureEnforce expiresAt on reads even if lazy cleanup has not run; background TTL scans are storage maintenance, not correctness. Choose LRU, LFU, or a sampled hybrid based on workload, and reserve memory for metadata, replication buffers, and fragmentation. Expose eviction reason and namespace so a hit-rate drop is distinguishable from an origin or routing failure.
• Hot keys and cache stampedesA balanced hash ring does not prevent one viral key from overloading its owner; replicate hot entries and coalesce concurrent misses. Use jittered TTLs, request collapsing, stale-while-revalidate where allowed, and per-key rate limits to avoid synchronized expiry. Do not let warmup or repair consume the same connection and CPU budget as foreground requests.
• Failure recovery and rebalancingUse leases, heartbeats, and fencing epochs to decide when a replica can be promoted and to prevent split-brain owners. Rebalance gradually with per-partition checkpoints, admission control, and rollback or pause points. After a failover, mark freshness and missing ranges explicitly; do not claim that a cache hit is durable data unless the contract says so.
• Durability boundaryIf the cache is only a derived layer, a miss can reload from the backing store; if it is the source of truth, acknowledged writes need a durable log or replicated storage. Keep the product decision visible in the API and metrics because it changes whether node loss is a cache miss or data loss. Backups and snapshots should be asynchronous and rate-limited so they do not consume the foreground latency budget.
• Security and multi-tenancyAuthenticate clients, isolate namespaces, enforce maximum value size and TTL, and prevent one tenant from exhausting memory or connections. Encrypt traffic between clients and nodes, and avoid placing secrets or regulated data in a cache without an explicit retention policy. Audit administrative flush, failover, and topology operations separately from high-volume data operations.
• Degraded operationWhen a replica is stale, return a miss or a clearly bounded stale value according to the namespace contract; never silently turn a correctness-sensitive read into arbitrary stale data. Use circuit breakers and bounded retries for unavailable nodes, and protect the backing store from a miss storm. Alert on partition unavailability, replica lag, and origin load before the global cache hit rate makes the problem obvious.
• Cache-aside versus write-throughUse cache-aside when the backing store owns durability and write-through when a shared cache abstraction must coordinate writes consistently. Cache-aside can create stampedes and stale entries; write-through couples cache availability and write latency to the backing store.
• Primary-replica versus quorum replicationStart with primary-replica ordering and a documented acknowledgement mode; add quorum only for namespaces that need stronger durability or read guarantees. Quorum improves failure semantics but consumes latency and availability budget during network partitions.
• Fixed slots versus a hash ringUse fixed hash slots for predictable ownership and tooling, or a consistent-hash ring when incremental node movement is the dominant concern. Both need hot-key isolation, versioned membership, and a migration strategy; the hashing algorithm alone is not a rebalancing plan.
• LRU versus LFU evictionUse LRU for recency-heavy workloads and LFU or a sampled hybrid when long-lived popular keys should survive bursts of one-time traffic. An eviction policy can optimize memory but cannot repair a bad TTL, oversized value, or hot-key distribution.
• Stale reads versus fail-closed readsChoose per namespace: tolerate bounded stale data for feeds and metadata, but fail closed or reload from an authority for authorization and inventory decisions. A global fail-open or fail-closed policy makes unrelated workloads absorb each other’s failure semantics.