Build a wide-column store (Cassandra / DynamoDB family)

About Build a wide-column store (Cassandra / DynamoDB family)

One server is not enough — disk fills, throughput maxes, the box dies. Build a multi-node store from first principles: hash sharding, the consistent-hash ring, vnodes, replication, eventual consistency, tunable W+R quorum, hinted handoff, read repair. Every modern Dynamo-style store is a point in this design space.

Difficulty
beginner
Time
about 90 minutes
Stages
9
Topic
Storage Engines & Databases

How this problem is worked

Nine stages, from what the thing is for to how it compares with the real implementations. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.

  1. 01Purpose & invariantsWhat is this for, and what must always be true of it?
  2. 02Workload characterizationWho writes, who reads, and in what shapes?
  3. 03Data model & on-disk formatWhat does the data look like at rest?
  4. 04Core algorithmsHow do the write path and the read path actually work?
  5. 05Distribution & replicationHow does this scale out and survive losing a machine?
  6. 06Consistency & correctnessUnder concurrency and failure, what is guaranteed?
  7. 07Failure modes & recoveryWhat actually happens when each part fails?
  8. 08Operational characteristicsCan a human run this at three in the morning?
  9. 09Trade-offs & comparisonWhere does this sit against the alternatives?

Primary sources for this problem

  • DeCandia et al. — Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)
  • Chang et al. — Bigtable: A Distributed Storage System for Structured Data (OSDI 2006)
  • Cassandra documentation — cassandra.apache.org/doc/ (Architecture, Operations, Data Modeling)
  • Sivasubramanian et al. — Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (USENIX ATC 2022)
  • Aphyr — Jepsen reports on Cassandra and DynamoDB (jepsen.io/analyses)
  • Kleppmann — Designing Data-Intensive Applications, Chapters 5–9

More in Storage Engines & Databases

Open the box every design diagram labels "DB": pages, logs, LSM trees, wide-column, documents, graphs and columnar scans, built from scratch.

Browse the full problem catalog, or see what the simulator does and does not model.