Distributed Database

Same startup, same engineer #4. Seventeenth Monday.

Your CTO drops by. "Every service we've built either uses a distributed database (Cassandra, DynamoDB, Spanner, Vitess) or wishes it did. Time to understand how distributed databases ACTUALLY work — sharding, replication, consistency guarantees, cost math. Ship a design in 12 weeks."

She pauses. "For context — DynamoDB stores petabytes for Amazon.com itself. Slack runs Vitess on top of sharded MySQL at 2.3M QPS peak. Cassandra powers Netflix's watch history at exabyte scale. Spanner runs Google's Ads system with globally-consistent transactions. If you don't understand how these databases handle replication factor + quorum + partition tolerance, you'll design systems that either lose data OR reject writes during network partitions. Both are career-ending outcomes."

Here's the paradigm shift:

MySQL + Postgres are single-master relational databases. They scale by adding read replicas (fast) or sharding (slow, painful). Their consistency model is easy: strong, transactional, ACID.

Distributed databases are fundamentally different:
- Sharding is baked in from Day 1, not bolted on. DynamoDB automatically splits partitions. Cassandra distributes tokens across nodes. Spanner shards by primary key ranges.
- CAP theorem is a lived experience, not academic. Cassandra chose AP (available + partition-tolerant, eventually consistent). Spanner chose CP (consistent + partition-tolerant, uses TrueTime GPS-atomic clock synchronization). DynamoDB gives you both options per-request.
- Replication factor + read/write quorums are configurable primitives. RF=3, W=2, R=2 = quorum consistency with 1 node failure tolerance. Getting these wrong = silent data loss.
- Costs at scale are counterintuitive. DynamoDB at 100 PB = $25M+/month in storage alone. Cassandra self-hosted = 10x cheaper but requires ops team. This is the Slack story — Slack migrated from Vitess to a hybrid model for cost reasons.

Google's answer was Spanner with atomic clocks + TrueTime API for globally-consistent transactions. Reference: Spanner OSDI 2012 paper. Amazon's answer was DynamoDB — invented the "distributed key-value store" category and made it managed. Reference: DynamoDB SOSP 2007 paper. Facebook's answer was Cassandra — originally for Inbox Search, now open-source and used by Netflix + Instagram + Discord. Reference: Cassandra LADIS 2009 paper.

The real 2024 numbers

• DynamoDB single-table hard limit: unlimited (originally 10 GB, removed) — AWS DynamoDB developer guide
• DynamoDB pricing at 100 PB: ~$25M/month in storage alone at $0.25/GB/month On-Demand
• Netflix Cassandra: exabyte-scale for watch history + user preferences (Netflix Tech Blog: Cassandra)
• Slack Vitess: 2.3M QPS peak on top of sharded MySQL (Slack Engineering blog on Vitess)
• Spanner: Google Ads system + AdSense at global consistency with sub-10ms commit latency
• Cassandra typical: 100K writes/sec per node with RF=3 + W=2 quorum
• RF=3 with W=2 R=2 quorum: survives 1 node failure (not 2 — that requires RF=5). Common tutorial mistake.

Interview soundbite: "Distributed databases at Slack/Netflix scale are 4 primitives: (1) sharding topology (Cassandra tokens, DynamoDB partitions, Vitess vindexes), (2) replication factor + quorum (RF=3 W=2 R=2 = quorum with 1-failure tolerance), (3) CAP choice per-query (Cassandra tunable, Spanner strong), (4) global consistency (Spanner TrueTime, DynamoDB Global Tables async). DynamoDB at 100 PB is $25M/mo storage — Slack migrated off Vitess partly for cost. Naming these + the RF=3-survives-1-not-2 correction signals L6+ preparation."

The whole journey at a glance

Every 10× in dataset size surfaces different bottlenecks:

text
    ═══════════ DISTRIBUTED DATABASE ACROSS 4 SCALES ═══════════

    L4 (100 GB)        L5 (10 TB)         L6 (1 PB)                L7 (100 PB Netflix/Amazon)
    Postgres primary   Sharded MySQL      Cassandra / Vitess       Spanner / DynamoDB
    12 weeks · $500/mo 6 months · $50K/mo 18 months · $500K/mo     ongoing · $25M+/mo

    ┌────────┐         ┌────────┐         ┌── App tier ────────┐  ┌── App tier ──────────┐
    │  App   │         │  App   │         │  100+ services     │  │  1000+ services      │
    │ pods   │         │ pods   │         └─┬──┬──┬──┬─────────┘  └──┬──┬──┬──┬──────────┘
    └───┬────┘         └───┬────┘           │  │  │  │              │  │  │  │
        │                  │              ┌─▼──▼──▼──▼─────┐    ┌───▼──▼──▼──▼──────────┐
     ┌──▼───┐           ┌──▼──┐           │ Client library  │    │ Client library        │
     │ SQL  │           │Client                              │    │ + connection pool     │
     │client│           │lib   │          └───┬──────┬─────┘    └──┬──┬──┬──┬───────────┘
     │      │           │+ retry              │      │              │  │  │  │
     └──┬───┘           └──┬──┘           ┌───▼──────▼───┐        ┌──▼──▼──▼──▼──────────┐
        │                  │              │  Cassandra   │        │ Spanner (Google)      │
        │                  │              │  cluster     │        │ + TrueTime API        │
        │                  │              │  RF=3, W=2   │        │ + globally-consistent │
        │              ┌───▼──┐           │  R=2 quorum  │        │   transactions        │
        │              │Vitess│           │  ~30 nodes   │        │ OR                    │
        │              │VTGate│           │  ~100 GB/node│        │ DynamoDB              │
        │              │      │           └───┬───────────┘        │ + Global Tables       │
        │              └───┬──┘           ┌───▼──────────┐         │ + auto-partitioning   │
     ┌──▼───┐          ┌───▼─┐            │ Cassandra    │         │ + $25M/mo at 100 PB  │
     │Postgr│          │Sharded            │ multi-DC     │         └──┬──┬──┬──┬──────────┘
     │Multi-│          │MySQL │           │ replication  │            │  │  │  │
     │AZ    │          │+ Vit │           │              │         ┌──▼──▼──▼──▼──────────┐
     │Single│          │ess   │           └───┬──────────┘         │Regional replicas      │
     │region│          │      │           ┌───▼──────────┐         │(Cassandra multi-DC   │
     │      │          │(YouTube            │Kafka event   │         │ or Spanner regions)  │
     │      │          │origin  │         │pipeline for  │         │+ Kafka event pipeline│
     │      │          │)     │           │downstream    │         │+ downstream analytics│
     └──────┘          └──────┘           │analytics     │         └──────────────────────┘
                                          └──────────────┘

    Bottleneck        Bottleneck          Bottleneck                Bottleneck
    Single primary    Cross-shard         Multi-DC consistency      Cost at 100 PB:
    write cap ~10K    aggregation queries  vs latency vs cost.       DynamoDB = $25M+/mo.
    writes/sec.       are painful.        Choose your CAP.          Spanner ~$50M/yr.
                      Rebalance is slow.                            Custom = 10x cheaper.

   Chapter 5      Chapters 6+6.5      Chapter 7+7.5              Chapter 8
   walks          walks through       walks through Cassandra    walks through Spanner
   through        Vitess sharding     RF=3 W=2 R=2 quorum         TrueTime, DynamoDB
   L4 MVP         + read replicas    + multi-DC replication      Global Tables, and 100
                                                                  PB cost tradeoffs

  Key insight: Distributed databases are 4 primitives, not 1 monolith. Sharding
  topology + replication factor + CAP per-query + global consistency. Cassandra
  gives you AP + tunable consistency. Spanner gives you CP + strong consistency
  via TrueTime. DynamoDB gives you both options per-request but at $25M/mo at
  100 PB. If you name these 4 primitives + the RF=3-survives-1-not-2 correction
  (common tutorial mistake) you're L6+. If you cite Spanner's TrueTime or
  DynamoDB's SOSP paper you signal L7 preparation.

The same 4 tiers as clean architecture diagrams

L4 · 100 GB · Postgres primary + replicas · $500/mo · 12 weeks:

L5 · 10 TB · Sharded MySQL + Vitess · $50K/mo · 6 months:

L6 · 1 PB · Cassandra RF=3 W=2 R=2 · $500K/mo · 18 months:

L7 · 100 PB · Spanner / DynamoDB · $25M+/mo · custom silicon:

Why every 10× breaks the architecture

1. Sharding enters at L5. Single MySQL/Postgres caps at ~10K writes/sec (fsync bound). Vitess is the industry answer for sharding on top of MySQL — invented at YouTube ~2010, now runs at Slack, GitHub, HubSpot, Etsy. Reference: Vitess adopters.

1. RF=3 W=2 R=2 survives 1 failure, NOT 2. Common tutorial mistake. Formula: W + R > RF for quorum consistency. To survive 2 failures with quorum you need RF=5, W=3, R=3. Reference: Cassandra consistency levels docs.

1. DynamoDB at 100 PB = $25M/mo storage alone. This is why Slack migrated PARTIALLY off Vitess for cost reasons. Below ~10 PB, managed wins; above ~100 PB, self-hosted Cassandra + custom ops team is 10x cheaper. Reference: Slack Engineering: Scaling Datastores with Vitess.

The 3 senior insights before we start Chapter 1

1. CAP theorem is a per-query choice, not a database property. DynamoDB lets you pick strong or eventual per-request. Cassandra is tunable via consistency level (ONE, QUORUM, ALL). Spanner is always strong (via TrueTime). Naming which mode your workload needs signals L6+ awareness.

1. Spanner's TrueTime is Google's most influential distributed-systems contribution. GPS + atomic clock synchronization gives ordered timestamps across datacenters, enabling globally-consistent transactions with sub-10ms commit. Reference: Spanner OSDI 2012 paper. Every candidate says "we use consistent hashing" — L7 candidates cite TrueTime.

1. Cost is a first-class design constraint at 100 PB. DynamoDB Global Tables at 100 PB = $25M+/mo. Spanner similar. Cassandra self-hosted = ~$2-3M/mo but needs a 10-engineer team. The decision curve crosses at ~100 PB. Reference: Dropbox Magic Pocket break-even story.

Chapter map for the journey ahead

• Chapter 1 — Requirements (schema, consistency, availability, latency, cost)
• Chapter 2 — Capacity estimation (Netflix Cassandra reference, DynamoDB pricing)
• Chapter 3 — API design (KV vs SQL, consistency level per-request)
• Chapter 4 — Data model (partition key, sort key, secondary index)
• Chapter 4.5 — Sharding topology: consistent hash vs range vs Vitess vindexes
• Chapter 5 — L4 MVP: Postgres single primary. Works to 100 GB
• Chapter 6 — L5: Vitess sharded MySQL. Works to 10 TB
• Chapter 6.5 — Vitess deep-dive: VTGate + VTTablet + vindexes
• Chapter 7 — L6: Cassandra RF=3 W=2 R=2 quorum + multi-DC
• Chapter 7.5 — CAP + quorum math: W+R > RF for strong consistency
• Chapter 8 — L7: Spanner TrueTime OR DynamoDB Global Tables (cost tradeoffs)
• Chapter 9 — Failure modes: split-brain, RF=3 during 2 failures, secondary index lag
• Chapter 10 — Trade-off matrix (Cassandra vs DynamoDB vs Spanner vs Vitess vs CockroachDB)
• Chapter 11 — Interview masterclass: 45-min mock, questions to ask
• Chapter 12 — Defense: the 20 hardest interview questions on distributed databases

Ready? Chapter 1 next: what did the CTO actually ask for?