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?

The CTO's brief is one sentence. Your job as engineer is to translate that into 7 quantified requirements that any distributed-DB architecture MUST satisfy. Miss one → wrong architecture.

Functional requirements

FR-1: Schema flexibility. Some services need relational (join across users + orders + invoices — Postgres/Vitess). Some need key-value at scale (session store — DynamoDB/Redis). Some need wide-column time-series (metrics/logs — Cassandra/ScyllaDB). Some need document (product catalog with variable attributes — MongoDB/DynamoDB). You cannot pick ONE database and serve all four workloads efficiently. Every distributed-DB has an optimal shape and 3 anti-shapes.

FR-2: Multi-region reads. Product catalog reads happen in every region. Latency budget: <50ms p99 from any user, any continent. This forces regional read replicas — either async replication (Cassandra, DynamoDB Global Tables) with eventual consistency, OR synchronous Paxos (Spanner) with 100-150ms write latency due to cross-region quorum. Pick one.

FR-3: Regional writes with cross-region visibility. User writes a review in Tokyo. The user in São Paulo should see it — eventually is fine, sub-second is not. This is the replication lag budget: Cassandra CROSS_REGION replication runs 100-500ms typically. DynamoDB Global Tables: 1-2 seconds. Spanner: synchronous, but writes are 100ms+. If you need <100ms cross-region write visibility, you cannot use eventual consistency — full stop.

FR-4: Transactional guarantees for money. Payments, ledger, inventory decrements — these need ACID transactions. Cassandra + DynamoDB support single-partition transactions only (fast). Cross-partition transactions require coordinators (Spanner Paxos groups, DynamoDB TransactWriteItems with 25-item limit). Design the schema so 95% of transactions fit in a single partition.

Non-functional requirements

NFR-1: Availability. 99.99% (52 minutes downtime/year) is table-stakes for consumer apps. 99.999% (5 minutes/year) is table-stakes for payment/ledger. Achieved via replication factor + quorum tuning: RF=3 W=2 R=2 survives 1 node failure per replica set. RF=5 W=3 R=3 survives 2 failures but doubles storage cost. For 99.999%: multi-region + automatic failover + no manual intervention. Reference: Cassandra multi-DC docs.

NFR-2: Latency p99. DynamoDB On-Demand: 5-10ms p99 for single-key reads. Cassandra with LOCAL_QUORUM: 10-25ms p99. Spanner: 10ms p50 reads, 100ms p99 writes (cross-region Paxos). Choose based on your write:read ratio. Read-heavy (100:1) → Cassandra/DynamoDB. Write-heavy transactional → Spanner or hybrid (Vitess for OLTP + Cassandra for feed).

NFR-3: Cost bound. CTO said "we can afford $50K/month for DB infra at year 2". At 10 TB active data:
- DynamoDB On-Demand: $2,500/mo storage + $1.25/M reads → ~$25K/mo at 100M requests/day. Simple, no ops.
- DynamoDB Provisioned: ~$12K/mo with reserved capacity, but requires forecasting.
- Cassandra self-hosted (24 nodes r6i.2xlarge + EBS gp3): ~$8K/mo compute + $2K/mo storage → $10K/mo total. But requires 1 FTE ops engineer ($200K/yr fully loaded = $17K/mo).
- Aurora Postgres (Vitess-style sharding at app layer): ~$15K/mo for 24 shards on db.r6g.large + storage.
- Spanner: ~$50-100K/mo at this scale — pays for itself only when global consistency is business-critical (Ads, payments).

The right answer depends on team maturity. 3-engineer team → DynamoDB On-Demand (higher $ per unit but zero ops). 20-engineer team → self-hosted Cassandra (lower $ per unit but 1-2 FTEs on ops).

Consistency requirements — the STRICT hierarchy

Not all data needs strong consistency. Map each entity to its minimum consistency requirement:

STRONG (linearizable, read-your-writes): Payments, inventory, session tokens, auth. Use Spanner, DynamoDB with ConsistentRead=true, or Cassandra with QUORUM+LOCAL_SERIAL.

BOUNDED STALENESS (X seconds max lag): Newsfeed rankings, product catalog, user profile. Use Cassandra QUORUM, DynamoDB Global Tables (1-2s lag OK).

EVENTUAL (best-effort, may be minutes): Analytics, aggregates, denormalized counters. Use Cassandra ONE, DynamoDB single-region.

Getting the mapping wrong = either latency crisis (over-strong on things that don't need it) or data corruption (under-consistent on things that do).