On this page

Landmark Systems

A handful of systems, most of them described in papers between 2003 and 2012, set the patterns that almost every modern database, data platform and cloud service still uses. When an interviewer says "partition it with consistent hashing and replicate with quorums", they are describing Dynamo. "A sorted map on an LSM tree" is Bigtable. "Externally consistent transactions across regions" is Spanner.

Each page here reads one system as a case study:

  • the problem it was built to solve;
  • its architecture;
  • its read and write paths;
  • the exact guarantees it gives, and the caveats its authors admitted;
  • how it handles faults;
  • what its successors changed.

How They Fit Together

graph LR
    GFS["GFS / HDFS"] --> MR["MapReduce / Spark"]
    GFS --> BT["Bigtable / HBase"]
    CH["Chubby / ZooKeeper"] --> BT
    CH --> ZK["ZooKeeper recipes"]
    BT --> SP["Spanner"]
    DY["Dynamo"] --> CS["Cassandra, Riak, DynamoDB"]
    BT --> CS
    SP --> CR["CockroachDB, YugabyteDB"]
    CA["Calvin"] --> FA["FaunaDB"]
    DL["Distributed Ledgers"]
SystemEraKey ideaRead it to learn
GFS & HDFS2003Single master, large chunks, relaxed consistencyMetadata/data separation, leases, re-replication
MapReduce & Spark2004 / 2012Re-execution as fault tolerance, then lineageBatch processing, shuffles, stragglers
Bigtable & HBase2006Sorted sparse map on SSTablesLSM storage, tablets, row-level atomicity
Amazon Dynamo2007Always writable, leaderlessConsistent hashing, sloppy quorums, vector clocks
ZooKeeper2010Coordination kernel, not a lock serviceZnodes, watches, sessions, lock and election recipes
Spanner & TrueTime2012Bounded clock uncertainty + commit waitExternal consistency, 2PC over Paxos groups
Calvin & FaunaDB2012Order first, then execute deterministicallyAvoiding 2PC, deterministic locking
Distributed Ledgers2008 →Shared state among mutually distrusting partiesNakamoto vs BFT consensus, permissioned ledgers

Before You Read

These pages assume the theory from the Distributed Systems Course: replication and quorums, clocks and causality, consensus, and distributed transactions. They are the course's final module.