Design a Key-Value Store — System Design Interview Practice

Interview prompt

Design a DynamoDB- or Cassandra-like distributed key-value store with partitioned storage, replication, tunable consistency, conditional writes, failure recovery, and predictable low-latency access.

• Define partition-key and sort-key access patterns, item limits, conditional writes, versioning, and consistency levels.
• Use replication, quorum reads/writes, hinted handoff or repair, and membership protocols without making one node authoritative forever.
• Handle hot partitions, tombstones, compaction, rebalancing, read repair, and cross-region conflict policy.
• Explain durability acknowledgements, overload behavior, encryption, quotas, backups, and operational repair.

Requirements and scale assumptions

• Create tables and indexes, put/get/update/delete items, scan bounded partitions, and issue conditional or batch operations.
• Support strong or eventual reads, TTL, optimistic versions, transactions within a defined partition scope, and backups.
• Expose capacity, throttling, replica health, repair progress, hot keys, consistency errors, and request tracing.
• Target p99 reads and writes below 10 ms within a region at the configured consistency level.
• Store billions of records by hashing partition keys, splitting hot keys, and limiting per-partition throughput.
• Never acknowledge a write below its durability contract; make conditional retries and repair idempotent.
• Throttle rather than overload, serve eventual reads when allowed, and preserve quorum safety during failures.
• Support 10 billion items, 1 million requests per second, and multi-region replicas with uneven tenant traffic.
• Partition by application key and hash prefix; isolate hot tenants, celebrity keys, and large item collections.
• Retain durable replicas, tombstones, snapshots, and repair logs while bounding caches and hinted handoff.

• Stored items: 10B items — Scale drives partition distribution, replica capacity, compaction, and repair bandwidth.
• Key-value latency: p99 <=10ms — Regional single-key access target at the selected consistency level.
• Durable boundary: Committed before async — The source of truth is Store and retrieve key-value pairs; Support CRUD operations.
• Async boundary: At-least-once workers — Keep Consistent hashing for data distribution, Replication for availability, Quorum-based consistency off the synchronous path.

Key entities

• ResourceSpecresourceId, tenantId, desiredState, version, policyVersion, updatedAt

  Versioned desired state for a key value store managed resource.

• OperationoperationId, resourceId, requestHash, step, attempt, status

  Durable key value store reconciliation operation with per-step progress.

• PolicyVersionpolicyId, scope, version, rules, effectiveAt, status

  Auditable key value store policy evaluated before provisioning or mutation.

• ReconciliationCheckpointresourceId, provider, observedVersion, cursor, lastError, updatedAt

  Provider-specific key value store observation and recovery cursor.

Data flow

1. 1. Accept a desired-state commandThe key value store control plane authenticates the tenant, validates policy and quotas, checks the expected version, and records the desired state.
2. 2. Plan a safe operationA planner turns key value store desired state into ordered, bounded steps with dependency checks, blast-radius limits, and rollback metadata.
3. 3. Reconcile providers asynchronouslyWorkers apply key value store operations through provider adapters, persist checkpoints, rate-limit calls, and treat unknown outcomes as observable state.
4. 4. Publish observed healthThe serving projection joins desired and observed key value store state with operation status, policy version, freshness, and actionable errors.
5. 5. Recover and auditRetries, dead letters, drift detection, and operator approvals repair key value store resources without losing the original command or provider evidence.

Deep dives and trade-offs

• Desired versus observed stateKeep key value store desired state separate from provider-observed state and show both to operators. Make every reconciliation step conditional and resumable so a worker crash does not restart unsafe effects. Version policy and resource state so old operations cannot overwrite newer intent.
• Provider failures and unknown outcomesUse provider-specific idempotency tokens and query-after-timeout behavior for key value store operations. Bound retries with exponential backoff, circuit breakers, and per-provider quotas. Route irreconcilable drift to an approval or quarantine path instead of retrying forever.
• Blast radius and operationsPartition key value store work by tenant, region, cluster, or resource class and cap concurrent mutations. Audit who changed desired state, which policy allowed it, and what provider evidence was observed. Alert on drift age, operation backlog, failed steps, policy denials, and stale observations.
• Push versus pull reconciliationUse event triggers for fast response and periodic scans for missed events, drift, and recovery. A push-only key value store controller silently misses changes when a provider event is lost.
• Central control plane versus provider-native controllersKeep policy, intent, and audit centralized while isolating provider-specific application logic behind adapters. A monolithic controller becomes hard to scale and couples unrelated provider failure domains.
• Automatic repair versus approvalAutomate low-risk, reversible key value store changes and require approval for destructive or high-blast-radius operations. Full automation without policy or blast-radius controls can turn a transient signal into a widespread outage.