The system design path

Lessons are short reads with an exercise and a recap. Labs put several lessons together into one design.

25 modules · 205 lessons · 34 system labs · ~33 hours

Part 1 · Foundations

Part 2 · Distributed systems

Part 3 · Algorithms and internals

19

Algorithms behind big systems

Clocks, hashing, sketches, consensus and storage structures, traced by hand.

  1. 19.1Lamport clocksOrdering events without trusting wall clocks.Read 8m
  2. 19.2Vector clocksTelling "happened before" from "happened at the same time".Read 8m
  3. 19.3The consistent hash ringVirtual nodes and how much data moves.Read 8m
  4. 19.4Rendezvous hashingHighest random weight, a simpler alternative to the ring.Read 7m
  5. 19.5Bloom filters"Definitely not" or "maybe", in very little memory.Read 8m
  6. 19.6Count-min sketchApproximate counts for millions of keys.Read 8m
  7. 19.7HyperLogLogCounting unique visitors in 12 KB.Read 9m
  8. 19.8Percentile sketchesp99 latency across a fleet in a few kilobytes, and why you can't average percentiles.Read 11m
  9. 19.9Top-K heavy hittersTrending items from an endless stream.Read 9m
  10. 19.10Merkle treesFinding which data differs between two replicas.Read 8m
  11. 19.11Gossip protocolsSpreading news through a cluster like a rumour.Read 8m
  12. 19.12Failure detectionHeartbeats and the phi accrual detector.Read 9m
  13. 19.13Raft: leader electionTerms, votes and randomised timeouts.Read 9m
  14. 19.14Raft: log replicationHow a majority commits an entry.Read 9m
  15. 19.15Write-ahead logsHow databases survive a crash mid-write.Read 9m
  16. 19.16B-treesThe index inside almost every relational database.Read 9m
  17. 19.17LSM treesFast writes with memtables, SSTables and compaction.Read 10m
  18. 19.18Geohashes and quadtreesFinding everything near a point.Read 10m
  19. 19.19Unique IDs at scaleUUIDs, Snowflake IDs and ticket servers.Read 9m
  20. 19.20CRDTsData types that merge without conflicts.Read 10m
  21. 19.21PaxosThe original consensus algorithm, and how it relates to Raft.Read 10m
  22. 19.22Tries and FSTsPrefix search for autocomplete and dictionaries, without a database.Read 9m

Part 4 · Going deeper