Concepts

One idea at a time, each with a working demo you can step through.

  • Caching (Storage, 14 min): Keep recent answers in memory so the database only does each piece of work once. Then deal with the three ways that goes wrong: stale data, a full cache, and a stampede.
  • Load balancing (Networking, 15 min): One address in front of many servers. Follow one shopper’s request on sale day through DNS, the balancer’s choice of server, a crash, and back.
  • Database indexes (Storage, 13 min): Find one user among a million by reading 4 pages instead of 12,500. Build the index by hand, then see what it costs and why column order matters.
  • Replication (Distributed systems, 13 min): A copy of your database is not a live mirror. Copies run behind, so you can read old data, and a crash can lose a save you were told was safe.
  • CAP theorem (Distributed systems, 15 min): When the network between two copies of your data breaks, each side must either refuse some requests or risk a wrong answer. You choose which, ahead of time.
  • Sharding (Distributed systems, 14 min): Split one table across many database machines. It buys room and speed, and makes every query and transaction that crosses machines harder.
  • Message queues (Distributed systems, 15 min): Let the fast part of your app reply now and the slow part catch up later. Nothing is lost in a rush, but any job may run twice, so make twice harmless.
  • TCP (Networking, 10 min): Follow one page load from Enter to pixels and see how TCP turns a network that loses things into a connection that never does, and what that costs in round trips.
  • Server-Sent Events (Networking, 16 min): Build a live score page from one HTTP response that never ends: a few lines of plain text per event, a browser that reconnects by itself, and an id that lets it catch up on what it missed.
  • WebSockets (Networking, 15 min): Turn one HTTP request into a pipe that stays open, so the server can push a chat message the moment it arrives. Then pay for it: memory per user, heartbeats, reconnects and pub/sub.
  • HTTPS (Security, 16 min): Follow one password typed on café Wi-Fi, first over plain HTTP, where anyone nearby can read it, then over HTTPS: a secret agreed in public, a certificate that proves who the server is, and encryption for everything after.
  • HyperLogLog (Data structures, 10 min): Count 10 million different visitors in 12 KB, to within about 1%, without storing a single ID.
  • Network layers (Networking, 11 min): Build a real packet by hand: 42 bytes of HTTP inside three envelopes, and which boxes on the way open which one.
  • Bloom filter (Data structures, 9 min): Answer “have I seen this before?” for a hundred million names in about 10 bits each. It never wrongly says no.
  • Count-Min Sketch (Data structures, 11 min): Count 500 million hashtags a day in about half a megabyte. It may overcount a little, but it never undercounts.
  • Consistent hashing (Distributed systems, 11 min): Why adding one cache server can take a database down, and the ring that makes it move only about 1 key in 5 instead of 4 in 5.
  • Merkle tree (Distributed systems, 13 min): Two copies of a million rows find the few that differ by comparing about 41 short fingerprints, not a million rows.
  • Segment tree (Algorithms, 12 min): Build a tree of totals over a ramen shop’s daily sales, then answer any “days l to r” question and absorb any change in about 20 steps for a million days.
  • Bit tricks and bitmasks (Algorithms, 11 min): Store “which cities have I visited?” as one number, and the shortest round trip through 20 stops drops from years of work to under a second.
  • Square-root decomposition (Algorithms, 11 min): Keep one total per block of about √n numbers, so both “change one number” and “add up a stretch” stay cheap.
  • LSM tree (Storage, 12 min): Follow one write through Cassandra- or RocksDB-style storage: append it to a log, sort it in memory, write whole files, and clean up old copies later.
  • Raft consensus (Distributed systems, 14 min): Five servers hold copies of the same settings. Raft’s four rules stop them from ever disagreeing, even when the network splits them in two.
  • Token bucket (Distributed systems, 10 min): A rate limit with two knobs: how fast permits come back, and how many can pile up. Set both and a real app’s burst gets through while a flood does not.
  • Skip list (Data structures, 14 min): Keep a million-player leaderboard in score order and find any score in about 40 steps, using a linked list, some extra lanes and a coin.
  • Fenwick tree (Algorithms, 11 min): Running totals that stay fast while the numbers keep changing, in one plain array the same size as the data. The binary of each position does the work.
  • Geohash (Data structures, 13 min): Build a short code like xn76fg for any spot on Earth, so “ramen near me” becomes “codes that start with xn76fg”, one read on an ordinary database index.
  • OAuth grant types (Security, 13 min): How an app gets a limited key to your data without ever seeing your password, and which of the handover routes to use for a website, a TV or a server job.
  • PKCE (Security, 12 min): A phone app can’t keep a password of its own, so a stolen login code used to be as good as your account. PKCE ties each code to a secret that stays in the app until the very last step.