Distributed Key-Value Store (Amazon Dynamo & Cassandra)

A distributed key-value store exposes operations such as PUT(key, value), GET(key), and DELETE(key) while spreading data across machines. The hard questions are not the method names: who owns a key, how many replicas acknowledge an operation, what a read may return during failure, how conflicting versions are resolved, and how replicas converge afterward.

Given 500,000 operations/s at peak, 70% reads, 30% writes, 1 KiB values, replication factor 3, and a target of 60% steady-state utilization, derive a starting point. These numbers are illustrative and must be benchmarked with the chosen consistency level and value distribution.

Background compaction, anti-entropy repair, streaming, tombstones, and read repair compete with foreground requests. A node count based only on client QPS will fail during recovery—the exact moment the system has fewer healthy nodes.

1. 01Partitioner: hashes the key into a token range; virtual nodes or an equivalent placement scheme distribute ownership.
2. 02Preference list: selects N replicas across failure domains, not merely the next N processes on one rack.
3. 03Coordinator: accepts any client request, forwards it to replicas, and waits for the requested consistency level.
4. 04Storage engine: appends writes to a commit log and memtable, then flushes immutable sorted tables.
5. 05Repair mechanisms: hints shorten inconsistency after brief outages; read repair fixes replicas observed by reads; scheduled anti-entropy repair covers the full dataset.
6. 06Membership and topology: expose node state, token ownership, rack/zone placement, and safe bootstrap/decommission workflows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function put(key, value, consistency):
  replicas = placement.preferenceList(hash(key), N=3)
  version = nextVersion(readContextOrClock())
  send mutation(key, value, version) to every replica
  wait until consistency.requiredAcks arrive
  return success(version) or timeout(unknownOutcome=true)

function get(key, consistency):
  replicas = placement.preferenceList(hash(key), N=3)
  responses = read enough replicas for consistency
  versions = reconcile(responses)
  if one version dominates: return it and repair stale participants
  if versions are concurrent: apply documented merge or return siblings
  return result

A write timeout is an unknown outcome, not proof of failure: some replicas may have stored it. Clients retry with an idempotency token or version precondition. Reads compare version metadata, not arrival time at the coordinator.

Track latency and errors by operation and consistency level, not one cluster average. Add coordinator timeouts, unavailable responses, replica divergence, oldest unrepaired range, hint age/volume, tombstone scans, compaction backlog, disk imbalance, and cross-zone bytes. An availability number without the requested consistency level is incomplete.