System design: going deeper

Lesson 8 keeps the payments ledger (Design 3) and notifications (Design 6) in full. These five designs moved here whole, with their figures, code and Operate-it blocks; a one-page card for each is in "Design cards". Section names such as "consistency" and "rate limiter" refer to lesson 8. Every volume, price and count is invented.

Design 1: a URL shortener

Goal. By the end of this section you can design a service that turns a long URL into a short code and redirects the code, justify each box with a number, and name the one product decision (301 or 302) that changes what the service can measure.

Requirements (agreed in the first five minutes). Create a short code for a long URL; redirect a code to its URL; optionally take a custom alias and an expiry; delete a link. A code, once issued, is never reused for another URL. Redirect p99 under 100 ms is an assumption and is said as one. Out of scope, said aloud: click analytics, abuse scanning, login.

Estimate. Assumption: 100 million new links a month and a hundred reads per write. Computed: 38.6 writes a second average, 116 at peak (factor three); 3,858 reads a second average, 11,574 at peak. Five years of links is 6.0 billion rows; at an assumed 500 bytes a row that is 3.0 TB. So: reads dominate by a hundred to one, a cache in front pays for itself, and the data is small enough for a few shards.

Interface and data. POST /v1/urls takes the long URL and optional alias and expiry and returns 201 with the code; a client that retries sends an idempotency key. GET /{code} returns a redirect with a Location header. DELETE /v1/urls/{code} returns 204. One table, urls(code, long_url, owner_id, created_at, expires_at), keyed and sharded by code.

The architecture figure shows every box. The CDN, the rate limiter and the expiry sweeper are dashed because they are optional extensions, not needed to meet the numbers.

The code. Take a number from a counter and write it in base 62 (digits and upper and lower case letters). Python gives the key space: 6 characters hold 56.8 billion codes, 7 hold 3.52 trillion, 8 hold 218 trillion. At 6.0 billion links in five years, six characters would be about 11% full and seven are very comfortable. Sequential codes can be enumerated: anyone can walk the codes in order and read every link, including private ones. If links must not be guessable, use random 7-character codes from a secure random source with an insert-if-absent check (at 6.0 billion links out of 3.52 trillion codes, one random guess hits a live link with probability 0.17%, so rate-limit repeated misses), or pass the counter through a keyed permutation so consecutive IDs look unrelated and still never collide. Either costs the plain ordering of IDs. Do not hash the long URL to make the code: two users shortening the same address would share a code, and any collision needs a retry path. Nor hand out one number per request from one counter: an ID block service gives each app server a block, say 1,000 numbers, so a short outage of it does not stop creates.

The redirect, step by step. The next figure follows one redirect. The row is checked for expiry on every read, not only by a sweeper, so an expired link cannot be served in the gap before the sweep.

Components and failures (SDE-2). A stateless app tier behind the load balancer; a Redis cache keyed by code, with a time-to-live of the lesser of a day and the link's expiry; a key-value store sharded by code on a consistent-hash ring, replicated. Cache down: every read goes to the store, and the cache can die at the peak, so size the store for 11,574 a second, not the 3,858 average, and say so; the six shards below are sized for exactly that. ID service down: creates fail, redirects keep working, and prefetched blocks cover a short outage. A viral link: one code takes most reads, the cache absorbs it, and a small in-process cache on each app server stops that one key from loading the cache node. Delete: the app deletes the row, then the cache key; a reader that misses just after reads a replica that still has the row. The mitigation is a short TTL and writing the delete as a tombstone, a marker that replicas honour.

Senior depth (adds). Consistency: a create must be visible to the next redirect in the same region. R + W > N does not give that (lesson 8, consistency), so return the code only after the shard's primary has committed it, and when a replica read misses, check the primary before answering 404; cache a 404 for a few seconds at most. A stale replica then costs one extra primary read and never a wrong "not found". Abuse: a token bucket on creates per user (lesson 8, rate limiter) and a blocklist check on create. Capacity: if one shard serves 2,000 reads a second (an assumption, not a measured figure), the 11,574 peak needs 11,574 / 2,000 = 5.8, so six shards, each a primary and two replicas: 18 nodes. At ten times the traffic, reads reach 115,741 a second at peak; the cache has to hold the working set, and the ID block service is the next bottleneck.

Next stop: Design 2: a news feed, 6 min

Design 2: a news feed

Goal. By the end of this section you can design a feed, compute why pushing every post to every follower is the bottleneck, and explain the push/pull split that follows from the numbers.

Requirements. Authors post text and media; followers see posts newest first (ranking is out of scope, said aloud). Feed read p99 under 300 ms is an assumption; the Dynamo paper's 300 ms at the 99.9th percentile is its own service target, not a rule. A user's own post shows in their feed at once (read-your-writes). Delivery to followers within seconds is acceptable.

Estimate. Assumptions: 300 million daily users, five feed reads each, 50 million posts a day, 200 followers per author on average. Computed: feed reads 17,361 a second average, 52,083 at peak; post writes 578.7 a second (50,000,000 / 86,400); if every post is pushed to every follower, 578.7 x 200 = 115,741 writes a second on the mean and 347,222 at a peak factor of three. Both are too kind. Posting peaks harder than three times (events and time zones bunch it): 578,704 a second at 5 times, 1,157,407 at 10 (the author's what-ifs). And the mean hides the tail, because follower counts are heavy-tailed. In an invented split the top 1% of authors hold 60% of follow edges: 12,000 followers each (0.6 x 200 / 0.01), everyone else about 81 (0.4 x 200 / 0.99 = 80.8). Pushing only the 99% costs 578.7 x 0.99 x 80.8 = 46,296 writes a second on the mean (the same as 578.7 x 200 x 0.4, since the 99% hold 40% of the edges), 138,889 at three times and 462,963 at ten times, while one post by a 20-million-follower account would be 20,000,000 writes, 1,000 seconds at 20,000 a second. Timeline memory: 800 post IDs at 8 bytes is 6.4 KB a user, 1.92 TB for 300 million users, but that is raw payload only. In-memory lists carry per-element overhead, taken here as 1.5 to 2.5 times the payload, and 2 to 3 copies are kept for failover, so 1.92 x 1.5 x 2 = 5.8 TB at the low end and 1.92 x 2.5 x 3 = 14.4 TB at the high end: about 6 to 15 TB, an author's estimate. At an assumed 64 GB of usable memory per node that is 90 to 225 nodes, and keeping lists only for users active in the last 30 days (state it) shrinks it in proportion. So: the bottleneck is the fan-out write under peak and skew, not the post write, and the timeline cache is a real cost line, not a footnote.

The decision the numbers force. Push (fan-out on write) for ordinary authors: when they post, a worker adds the post ID to each follower's timeline list, so a read is one list fetch. Pull (fan-out on read) for accounts with very many followers: their posts stay in their own list and are merged in when a follower reads. The threshold, for example 10,000 followers, is an assumption and can move. Workers also read the follower list a page at a time, so one large author does not hold a worker for minutes (the author's reading of the design, not a published figure).

Interface and data. POST /v1/posts returns 201 and a post_id. GET /v1/feed?cursor=...&limit=20 returns items and a next cursor. The cursor is an opaque position (post ID, or time plus ID), never an offset, so a new post arriving mid-scroll does not shift pages. PUT and DELETE /v1/follows/{user_id} manage follows. Tables: posts(post_id, author_id, created_at, text, media_key) sharded by post_id; follows(follower_id, followee_id) with a second index on followee for fan-out; and the timeline, a list of at most 800 post IDs per user in Redis (the cap is an assumption).

The architecture figure draws both paths. The write path is the top chain, ending in the timeline cache; the read path is the bottom chain; media goes around both, direct to blob storage, and is read through a CDN.

Failures (SDE-2). Fan-out lag: a follower sees a post late. The requirements allow seconds; measure the lag as the SLO. A duplicate from the queue pushes the same post ID twice; the timeline list dedupes by post ID. A deleted post still in timelines: the read path hydrates by ID and filters what no longer exists. Loss of the timeline cache: rebuild a user's list by pulling, expensive once, then pushed again. The author's own post is written to the author's list synchronously, which is how read-your-writes holds without waiting for the queue.

The next figure shows the decision itself, and the read path that makes it work.

Senior depth (adds). The deep dive is the threshold, as in the example. Consistency: a cursor must survive a new post landing mid-scroll, and a timestamp tie is broken by post ID so the sort is stable. A celebrity's post body is read by millions, so cache bodies by post ID and serve media through the CDN. At ten times the load, peak feed reads reach 520,833 a second; the timeline cache is the scaling question, and fan-out workers scale by partitioning the queue. A ranking service, if added, is a separate call from the feed service; say what happens when it is down (fall back to newest first).

Next stop: Design 4: a chat service, 8 min

Design 4: a chat service

Goal. By the end of this section you can design one-to-one and group chat with delivery states, per-conversation ordering, presence and offline sync, and say why the hard parts are the connection tier and the sequence number, not the message store.

Requirements. Send text to a person or to a group of up to 256 members (an assumption). Each message shows sent, delivered and read. Everyone sees one conversation in the same order. A user who was offline gets what they missed on reconnect. Presence shows online or last seen. Out of scope, said aloud: media (a message that carries a blob key), end-to-end encryption, search, voice.

Estimate. Assumptions, all invented: 500 million daily users, 40 messages sent each a day, 20% of messages go to groups averaging 10 members, and 20% of users connected at the busiest hour. Computed: 20 billion messages a day is 231,481 a second on average and 694,444 at a peak factor of three. A one-to-one message is one delivery and a group message nine, so the mean is 0.8 x 1 + 0.2 x 9 = 2.6 deliveries a message: 52 billion a day, 601,852 a second on average, 1,805,556 at peak. Connected sockets at peak: 100 million. At an assumed 100,000 sockets and about 10 KB of memory each, a gateway holds 1 GB for sockets, so 1,000 gateways. At an assumed 200 bytes a message (body and metadata) storage is 4 TB a day, 120 TB for 30 days kept on the server and 360 TB with three copies. If every delivery produced a delivered event and a read event, that would add 1.2 million events a second on average. So: the load is 100 million open connections and 1.8 million deliveries a second, not the store (139 MB a second inbound at peak); receipts must be cumulative and batched, and order must be settled without a global lock.

Interface and data. Over a WebSocket: send(conversation_id, client_msg_id, body), ack(conversation_id, kind, up_to_seq) with kind delivered or read, and sync(conversation_id, last_seq). Plain HTTP is for login and paging old history. Tables: messages(conversation_id, seq, sender, client_msg_id, body, sent_at), partitioned by conversation_id (plus a month bucket for very busy groups) and sorted by seq; members(conversation_id, user_id); cursors(conversation_id, user_id, delivered_seq, read_seq). A registry maps user to gateway, with an expiry.

The architecture figure shows where each job lives. The gateway only holds sockets; the chat service is stateless and does the appending; the registry tells it which gateway to push through.

One message, and its states. Figure A8.6 follows a message. The chat service appends it to the conversation log and assigns the next sequence number (step 2), then tells the sender "sent" (step 3). Pushing to the receiver is separate: if the registry shows a gateway, the frame goes there (steps 4 and 5); if not, a push notification wakes the device and it syncs later. The state words are cursors: "delivered up to 41" covers every message up to 41. Group state is then cheap: a message is delivered to all when the smallest recipient cursor has passed it. For a 256-member group with 100 messages a day, per-message per-member rows would be 25,600 rows a day; cursors are 256 x 2 numbers in total.

The ordering rule is one writer per conversation: the partition that owns the conversation assigns the next number, and client clocks are never used. A client that sees 40 and then 42 asks for the gap with sync. A retry carries the same client_msg_id and receives the same number. The block below is that logic, run with java --source 21 ConversationLog.java with checks for a retry, a late old acknowledgement, the slowest-cursor rule and gap sync.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class ConversationLog {
  record Message(long seq, String clientMsgId, String sender, String body) {}

  private final List<Message> log = new ArrayList<>();
  private final Map<String, Long> seqByClientId = new HashMap<>();
  // member -> highest seq acknowledged
  private final Map<String, Long> delivered = new HashMap<>();
  private final Map<String, Long> read = new HashMap<>();

  // One writer per conversation: the partition owner assigns seq.
  synchronized long append(String clientMsgId, String sender, String body) {
    Long seen = seqByClientId.get(clientMsgId);
    if (seen != null) return seen;             // a retry gets the same seq
    long seq = log.size() + 1;
    log.add(new Message(seq, clientMsgId, sender, body));
    seqByClientId.put(clientMsgId, seq);
    return seq;
  }

  // A cursor only moves forward: "delivered up to seq n" covers 1..n.
  synchronized void ack(Map<String, Long> cursors, String member, long seq) {
    cursors.merge(member, seq, Math::max);
  }
  synchronized void delivered(String m, long seq) { ack(delivered, m, seq); }
  synchronized void read(String m, long seq) { ack(read, m, seq); }

  // A reconnecting device sends its last seq and gets the gap.
  synchronized List<Message> after(long lastSeq) {
    return List.copyOf(log.subList((int) lastSeq, log.size()));
  }

  // The sender sees "delivered to all" when the slowest cursor passes seq.
  synchronized boolean deliveredToAll(List<String> members, long seq) {
    return members.stream()
        .allMatch(m -> delivered.getOrDefault(m, 0L) >= seq);
  }

  public static void main(String[] args) {
    var c = new ConversationLog();
    long a = c.append("c1", "ann", "hi");
    long b = c.append("c2", "ann", "yo");
    check(a == 1 && b == 2, "seq assigned in order");
    check(c.append("c1", "ann", "hi") == 1, "retry gets same seq");
    check(c.after(0).size() == 2, "log has two messages");
    c.delivered("bob", 2);
    c.delivered("bob", 1);               // late old ack
    check(c.delivered.get("bob") == 2, "cursor never moves back");
    var members = List.of("bob", "cy");
    check(!c.deliveredToAll(members, 2), "slowest cursor blocks");
    c.delivered("cy", 2);
    check(c.deliveredToAll(members, 2), "all passed seq 2");
    check(c.after(1).size() == 1 && c.after(1).get(0).seq() == 2,
        "gap sync returns the missing message");
    System.out.println("conversation ok: log=" + c.after(0).size());
  }

  static void check(boolean ok, String what) {
    if (!ok) throw new AssertionError(what);
  }
}

Presence. Heartbeats from 100 million sockets every 30 seconds would be 3.3 million writes a second. Do not store heartbeats. The gateway writes the registry only when a socket connects or disconnects: at an assumed 30-minute session, 100 million sockets give about 111,000 transitions a second, 30 times fewer. The gateway refreshes its sockets' expiry in batches (1,000 gateways, one batch each every 30 seconds, is about 33 calls a second). "Last seen" is a timestamp written on disconnect. Send presence changes only to people who have that conversation open, not to every contact.

Failures (SDE-2). A gateway dies: its 100,000 clients reconnect. Without jitter that is 100,000 connects at once; spread over 30 seconds it is 3,333 a second. Each reconnect runs sync, so nothing is lost, because the append happens before any delivery. The registry points at a dead gateway: the push times out, the recipient is treated as offline, and the message waits in the log. The chat service crashes after the append and before the "sent": the client retries and gets the same number. A very busy group is a hot partition: add the month bucket and cache its last page.

Senior depth (adds). The deep dives are sequence assignment through an owner failover (the example above, fenced as in lesson 8's consistency section), cursors instead of per-message flags, and the connection tier: sticky load balancing by connection, reconnect storms, and draining a gateway before a deploy. Multi-device: each device has its own delivered cursor and the user has one read cursor. A group above a few hundred members becomes a fan-out problem like the feed's, so cap its size or push through a queue.

Next stop: Design 5: ride-hailing matching, 8 min

Design 5: ride-hailing matching

Goal. By the end of this section you can design the matching core of a ride-hailing service: take driver locations at a high rate, find nearby drivers fast with a grid index, and assign each driver to at most one ride at a time.

Requirements. A driver app sends its position every 4 seconds while online. A rider requests a ride at a point. The system offers the ride to a good nearby available driver, who has 10 seconds to accept; if not, the next one. A driver is never on two rides, and a ride is never matched twice. The rider sees the driver approach. Out of scope, said aloud: pricing and surge, road routing and ETA (a separate service; this design uses straight-line distance as a first filter), payments.

Estimate. Assumptions, invented: 1 million drivers online at peak, one update per 4 seconds, 100 bytes an update, 20 million rides a day. Computed: 250,000 updates a second, 25 MB a second; storing every update would be 2.16 TB a day. The latest position of every driver is 1 million x 100 bytes = 100 MB. Rides are 231 a second on average, 694 at peak, and each match reads about nine cells. So: the write rate is the problem and the match rate is not. Keep the latest positions in memory, and write a sampled trail to cold storage.

The grid. A geohash names a rectangle by interleaving longitude and latitude bits and writing them in base 32. Length 6 is 30 bits, 15 for each axis, so a cell is 360 / 2^15 degrees wide and 180 / 2^15 high: 1.22 km by 0.61 km at the equator (the author's arithmetic from the bit layout; cells get narrower in width away from the equator). Length 5 is 4.89 km by 4.89 km, length 7 is about 153 m square. Two traps. Nearby points can sit in different cells, so a query reads the rider's cell and its eight neighbours, never the cell alone. And fixed cells ignore density: a stadium cell can hold thousands of drivers and a rural cell none. A quadtree, or the S2 library (cells on a space-filling curve in many sizes; the author's reading, its documentation was not opened for this lesson), adapts cell size to density. The code below is a simplified row-major grid with the same cell size, standing in for geohash cells; real geohash neighbour handling differs (neighbours need de-interleaving or a lookup table, and the +1 and -1 arithmetic used here does not apply to geohash strings). Choose the fixed grid when it is enough and say what you would change if one cell becomes too hot.

The next figure shows the query: the rider, a driver just across a border, and the ring read only if too few drivers are found.

Write path. Store the latest location by driver_id, so the 250,000 writes a second spread evenly and no city can make one shard hot. Keep a second, in-memory index from cell to drivers, and change it only when a driver crosses a cell border. At 30 km/h a driver moves 33 m in 4 seconds. A Java random-walk run (2 million trials, java --source 21 Cross.java) found 5.16% of steps change cell, matching the formula 33.3 x (2 / pi) x (1/1,223 + 1/611) = 5.2%. So the cell index takes about 13,000 writes a second, 19 times fewer than the location store. If an index node loses its memory, rebuild it from the next round of driver updates, about four seconds, with matching degraded in that time; nothing in the index needs to be durable.

Matching and the lock. The service reads the nine cells, widens to the 25-cell ring if it finds fewer than five available drivers (up to a radius cap), keeps the drivers marked available, ranks the nearest ten by straight-line distance, and makes an offer to the best. The claim must be atomic per driver, so it lives with the driver (the key driver_id), not with the cell: a compare-and-set from available to offered, with a lease that expires, so a driver who never answers returns to the pool. When two rides race for one driver, exactly one claim succeeds and the other moves to its next driver. An accept carries the ride id and succeeds only while the hold still names that ride; that check is the fencing token of lesson 8's consistency section. The block below is the cell grid and the hold, with checks: a driver in the next cell is found, a same-cell move writes nothing, eight threads race for one driver and exactly one wins, and the hold expires.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

class DriverIndex {
  record Hold(String rideId, long expiresAt) {}

  // Simplified grid standing in for geohash cells: 15 bits of x and
  // 15 of y, row-major. Not bit-interleaved, so not a real geohash.
  static long cell(double lat, double lon) {
    long y = (long) ((lat + 90) / 180 * 32768);
    long x = (long) ((lon + 180) / 360 * 32768);
    return (y << 15) | x;
  }

  private final Map<Long, Set<String>> cells = new ConcurrentHashMap<>();
  private final Map<String, Long> where = new ConcurrentHashMap<>();
  private final Map<String, Hold> holds = new ConcurrentHashMap<>();

  // Most updates stay in the same cell and leave the index untouched.
  boolean move(String driver, double lat, double lon) {
    long c = cell(lat, lon);
    Long old = where.put(driver, c);
    if (old != null && old == c) return false;
    if (old != null) cells.get(old).remove(driver);
    cells.computeIfAbsent(c, k -> ConcurrentHashMap.newKeySet()).add(driver);
    return true;
  }

  Set<String> nearby(double lat, double lon) {
    // No wrap at the date line: within one cell of lon 180, also
    // read the cells on the other side.
    long c = cell(lat, lon);
    var found = new HashSet<String>();
    for (int dy = -1; dy <= 1; dy++)
      for (int dx = -1; dx <= 1; dx++)
        found.addAll(cells.getOrDefault(
            c + ((long) dy << 15) + dx, Set.of()));
    return found;
  }

  // One driver, one ride: an atomic claim that expires if never accepted.
  boolean hold(String driver, String rideId, long now, long ttlMs) {
    Hold h = holds.compute(driver, (k, old) ->
        old == null || old.expiresAt() <= now
            ? new Hold(rideId, now + ttlMs) : old);
    return h.rideId().equals(rideId);
  }

  public static void main(String[] args) throws Exception {
    var ix = new DriverIndex();
    double lat = 12.9716, lon = 77.5946;
    check(ix.move("d1", lat, lon), "first move writes the index");
    check(!ix.move("d1", lat + 1e-6, lon), "same-cell move writes nothing");
    ix.move("d2", lat, lon + 0.0125);    // about 1.4 km east: next cell
    var near = ix.nearby(lat, lon);
    check(near.contains("d1") && near.contains("d2"), "next cell found");
    ix.move("d3", lat, lon + 0.5);       // far away
    check(!ix.nearby(lat, lon).contains("d3"), "far driver not found");
    var wins = new java.util.concurrent.atomic.AtomicInteger();
    var ts = new ArrayList<Thread>();
    for (int i = 0; i < 8; i++) {
      String ride = "r" + i;
      Thread t = new Thread(() -> {
        if (ix.hold("d1", ride, 0, 10_000)) wins.incrementAndGet();
      });
      ts.add(t);
      t.start();
    }
    for (Thread t : ts) t.join();
    check(wins.get() == 1, "exactly one ride wins the driver");
    check(!ix.hold("d1", "late", 9_999, 10_000), "hold still valid");
    check(ix.hold("d1", "late", 10_000, 10_000), "hold expired");
    System.out.println("index ok: winners=" + wins.get());
  }

  static void check(boolean ok, String what) {
    if (!ok) throw new AssertionError(what);
  }
}

Components and failures (SDE-2). A stale driver: no update for three intervals (12 seconds) removes them from the index. A rider who taps twice: the request id makes the second a no-op. The matcher crashes mid-offer: the hold expires in 10 seconds and the driver is available again. If the state shard for a driver is down, treat the driver as unavailable (fail closed): an offer you cannot lock is an offer you must not make. GPS jitter can flip a stationary driver between two cells; ignore moves under a few metres.

Senior depth (adds). Sharding the cell index: a geohash prefix of length 4 is a cell of about 39 km by 20 km, so a whole city is one shard and one hot spot; use length 5 or 6 for big cities and spread the prefixes over nodes with consistent hashing. A request then fans out to up to nine cells on several shards in parallel, and its latency is the slowest of them. Greedy versus batch matching: matching each request at once is simple; collecting requests for about 2 seconds and assigning drivers together lowers total pickup time but adds up to 2 seconds of waiting (the author's reading; state it as a trade).

Next stop: Design 7: e-commerce checkout and a flash sale, 10 min

Design 7: e-commerce checkout and a flash sale

Goal. By the end of this section you can design checkout for a shop that puts 1,000 units of one phone on sale at noon in front of 2 million people, never sell a unit it does not have, hand payment to the ledger's saga and outbox, and say what a buyer sees when payment fails or arrives late.

Context. Ticket booking holds a numbered seat. This design differs in one way that changes the answer: a unit has no identity, so the guard is a counter, and the counter's row becomes the hot spot.

Requirements. Browse and cart are ordinary: a cached catalogue and a cart per user. The hard path is "Buy now" on a sale item: reserve one unit for 10 minutes, take payment, confirm on success, release on failure or expiry. One unit per buyer for this sale. Never oversell. A buyer whose payment lands after the unit is gone gets an automatic refund. Out of scope, said aloud: search, recommendations, coupons and pricing, delivery slots, and the payment provider's internals; money belongs to the ledger in Design 3 (lesson 8).

Estimate. Assumptions, all invented: 1,000 units; 2 million people on the page at noon, each pressing Buy once in the first 10 seconds; an ordinary day's checkout of 3 orders a second. Computed: 200,000 attempts a second at noon against 1,000 units, so 199,000 of every 200,000 answers are "no", and the design is mostly about saying no cheaply. The stock row is the second number. Its lock is held until commit, and the commit waits for a synchronous standby; at an assumed 2 ms a transaction, one row serves about 500 holds a second. Even 2,000 admitted buyers on one row is 4 seconds of queue, with 2,000 database connections held while they wait. Split into 20 rows of 50 units the same 2,000 clear in 0.2 seconds, with room for ten times the sale. Payments are about 1,000 in 10 minutes, under 2 a second, nothing for the ledger. So: stop the crowd at the edge, admit about twice the stock, and spread the stock over rows.

Where to take the unit. There are three places, and the interviewer wants the trade said. At add-to-cart: carts are abandoned far more often than bought, so window-shoppers would hold the whole sale. At payment success: nothing is held, so all 2,000 admitted buyers pay and 1,000 are refunded; the oversell becomes a refund queue. At Buy now, with a hold that expires: the middle, at the price of a sweeper and a late-payment path. Take the third, and say on the cart page that a sale item is not reserved until Buy now.

Read the figure top to bottom: the crowd stops at the edge, the gate admits a few thousand, one transaction does the work, and every hold is ended by exactly one of two things.

The guard. One transaction does four writes: the conditional decrement UPDATE stock SET avail = avail - 1 WHERE sku = ? AND bucket = ? AND avail >= 1; the hold row with its expiry; the order as PENDING; and the outbox row that asks for payment, keyed by the order id. Zero rows updated means this bucket is empty; try the next. The decrement is safe without a read first, even at Read Committed. PostgreSQL 18's documentation (section 13.2.1, re-read 2 Nov 2026) says a second updater waits for the first to commit, and then "The search condition of the command (the WHERE clause) is re-evaluated to see if the updated version of the row still matches the search condition." So two buyers racing for the last unit cannot both see avail >= 1 pass. A CHECK (avail >= 0) on the column is a second wall (author's practice). One unit per buyer is a row keyed by sale and buyer, inserted in the same transaction and deleted on release.

The listing is an excerpt of a 169-line file and models the guard and the hold's life in memory: a compare-and-set loop stands in for the conditional UPDATE, and the comment above it gives the SQL. Its fields are an array of AtomicInteger stock rows (buckets), the hold lifetime (ttlMs), an AtomicLong id counter (ids), and three ConcurrentHashMaps: idempotency key to hold (byKey), buyer to hold id (buyer) and hold id to state (state).

enum State { RESERVED, CONFIRMED, RELEASED }
record Hold(long id, String user, int bucket, long expiresMs) {}

// UPDATE stock SET avail = avail - 1
//   WHERE sku = ? AND bucket = ? AND avail >= 1
boolean take(int b) {
  while (true) {
    int a = buckets[b].get();
    if (a < 1) return false;
    if (buckets[b].compareAndSet(a, a - 1)) return true;
  }
}

// Same key twice returns the same hold: the retry is free.
Hold reserve(String key, String user, long now) {
  return byKey.computeIfAbsent(key, k -> fresh(user, now));
}

private Hold fresh(String user, long now) {
  long id = ids.incrementAndGet();
  if (buyer.putIfAbsent(user, id) != null) return null; // 1 each
  int n = buckets.length, home = Math.floorMod(user.hashCode(), n);
  for (int i = 0; i < n; i++) {
    int b = (home + i) % n;                 // home row, then next
    if (take(b)) {
      state.put(id, new AtomicReference<>(State.RESERVED));
      return new Hold(id, user, b, now + ttlMs);
    }
  }
  buyer.remove(user, id);                   // sold out
  return null;
}

// Payment callback. False means: refund, the hold is gone.
boolean confirm(Hold h, long now) {
  return now < h.expiresMs() && state.get(h.id())
      .compareAndSet(State.RESERVED, State.CONFIRMED);
}

// Payment failed, or the sweeper found the hold expired.
boolean release(Hold h) {
  if (!state.get(h.id())
      .compareAndSet(State.RESERVED, State.RELEASED)) return false;
  buckets[h.bucket()].incrementAndGet();    // unit goes back
  buyer.remove(h.user(), h.id());
  return true;
}

Run with java --source 21 FlashSale.java on 2 Nov 2026 (OpenJDK 25), three times; each run printed flash ok: sold=1000 released=300 oversold=0, and the line prints only after every check has passed. The full file is 169 lines; the test around the excerpt sends 20,000 buyers on 8 threads at 1,000 units in 20 rows, each buyer retrying its key once and trying a second key; pays 7 holds in 10 and releases the rest; sends a second crowd that must buy exactly the 300 released units; refuses a payment after the sweeper has released its hold, and one on an expired hold the sweeper has not reached yet; and races confirm against release on 2,000 holds, requiring exactly one winner each. A check that fails inside a worker thread is caught there and rethrown on the main thread after the join, so it fails the run. Four mutants were run to check that the test can fail, and each threw its own AssertionError: without the stock guard, "stock left after a 20x crowd"; without the expiry check in confirm, "expired hold confirmed"; with an unconditional release, "confirm and release both won"; without one unit per buyer, "two holds for one user".

Failures (SDE-2). The checkout server dies after the commit and before the reply: the client retries with the same idempotency key and gets the same hold, which is the listing's first check. The payment provider times out: the hold stays RESERVED and the saga asks the provider for the order's status by its idempotency key before deciding; if the hold expires first, the sweeper releases it and a later success is refunded, never fulfilled. The outbox relay stops: holds wait unpaid and start to expire, so page on relay lag long before the 10 minutes run out. The inventory primary dies: a synchronous standby takes over with every committed decrement, the gate pauses admission for the seconds that takes, and no unit is sold twice. The edge flag is stale for up to 2 seconds: buyers in that window reach the gate and hear "sold out" from the database, which is the truth.

Senior depth (adds). Expect "why not a Redis counter?". A Lua script is atomic, so a Redis decrement cannot race. The trouble is failover: the Redis Cluster specification (read 2 Nov 2026) says "asynchronous replication is used" and "Usually there are small windows where acknowledged writes can be lost." A lost decrement is a unit sold twice. So Redis may say no early (the gate's tokens, the sold-out flag) and only the database says yes. Next, the rows: 20 rows of 50 drain unevenly, so the last units sit in scattered rows, and a buyer whose home row is empty scans the others; "sold out" means all 20 rows at zero, checked by summing them at most once a second. At ten times the crowd nothing inside changes: the edge absorbs it and the gate still admits 2,000, because tokens scale with stock, not with people. At ten times the stock, 10,000 units, admit 20,000 over 40 rows; 40 rows at about 500 holds a second clear them in about a second. One number I would not invent: the payment provider's rate limit. 1,000 payments in 10 minutes is far below any limit I would expect, but a 100,000-unit sale is not, so I would ask.

Next stop: Leases and fencing tokens, 3 min

Leases and fencing tokens

Context. A lease is a lock that expires, so a holder that dies cannot block everyone for ever. Expiry creates the opposite problem. Martin Kleppmann's essay "How to do distributed locking" (8 Feb 2016, read 1 Nov 2026) lists ways a holder can stop without knowing it: a garbage-collection pause, a page fault, slow disk, a delayed network packet (he cites a GitHub incident with packets delayed for about 90 seconds). The holder wakes after its lease has expired and another client holds the lock, then writes as if it still held it. Checking the clock before writing does not help, because the pause can fall between the check and the write.

The fix. The lock service hands out a fencing token, a number that increases with every grant. The client sends it with every write, and the storage remembers the highest token it has accepted and rejects a lower one. The protection lives in the resource, not in the client's sense of time. The essay notes that a ZooKeeper zxid or znode version can serve as the token, and that Redlock produces none. Figure A8.10 shows the race with tokens 7 and 8.

Worked example. The demonstration uses explicit times in milliseconds instead of sleeping, so every run is the same. Run with java --source 21 FencingDemo.java on 1 Nov 2026: it printed fencing ok: A=7 B=8 and passed every check, and with the token comparison removed the "stale A rejected" check fails.

import java.util.Optional;

public class FencingDemo {
  record Lease(String holder, long token, long expiresAtMs) {}

  static final class LockService {
    private long nextToken = 7;          // six grants happened earlier
    private Lease current;

    Optional<Lease> acquire(String who, long nowMs, long ttlMs) {
      if (current != null && nowMs < current.expiresAtMs()) {
        return Optional.empty();         // a live lease exists
      }
      current = new Lease(who, nextToken++, nowMs + ttlMs);
      return Optional.of(current);
    }
  }

  static final class Storage {
    private long highestToken = 0;
    private String value = "";

    boolean write(long token, String v) {
      if (token < highestToken) return false;   // stale holder
      highestToken = token;
      value = v;
      return true;
    }

    String value() { return value; }
  }

  public static void main(String[] args) {
    LockService locks = new LockService();
    Storage disk = new Storage();
    Lease a = locks.acquire("A", 0, 10_000).orElseThrow();
    check(locks.acquire("B", 5_000, 10_000).isEmpty(), "lease is live");
    // A stops (GC pause) past its TTL; B is granted the next token.
    Lease b = locks.acquire("B", 12_000, 10_000).orElseThrow();
    check(b.token() > a.token(), "tokens increase");
    check(disk.write(b.token(), "B wrote"), "B accepted");
    // A wakes, still believes it holds the lock, and writes.
    check(!disk.write(a.token(), "A wrote"), "stale A rejected");
    check(disk.value().equals("B wrote"), "B's write survives");
    System.out.println("fencing ok: A=" + a.token() + " B=" + b.token());
  }

  static void check(boolean ok, String what) {
    if (!ok) throw new AssertionError(what);
  }
}

Constraints. The token protects only resources that check it; a write path that skips the check is unprotected. Where the storage cannot compare tokens, a conditional write on a version column does the same job. This is the check in Design 4's owner failover and Design 5's driver hold.

Next stop: Leader election and split brain, 2 min

Leader election and split brain

Context. Many stores send every write through one leader so that writes have one order. When the leader goes quiet the others elect a new one, and they can judge "quiet" only by a timeout, which cannot tell a dead leader from a slow or cut-off one. If the old leader is alive on the far side of a partition, two nodes believe they lead. That is split brain: both accept writes and the histories diverge.

How consensus prevents it. The Raft paper (read 31 Oct 2026) numbers time in terms. A candidate needs votes from a majority to lead and a node votes once per term, so there is at most one leader per term. A message carrying an older term is rejected, and a leader that sees a newer term steps down. A leader commits an entry only once a majority has stored it, so an old leader on the minority side keeps its title but commits nothing; for reads, the paper has the leader confirm with a majority before answering. The term is a fencing token built into the protocol. Figure A8.11 shows five nodes split two and three.

Constraints. A majority needs an odd number of voters spread over at least three failure domains. With voters in only two data centres, losing the one that holds the majority stops writes. The usual answers are a small witness voter in a third zone, or fencing the old leader through an outside channel, such as cutting its power, before promoting another; practitioners call that STONITH, "shoot the other node in the head" (author's reading of common practice). Storage and clients should still check the term or epoch, because a deposed leader's messages can be in flight. This is the step "fence the old primary" in lesson 8's recovery table. An election also pauses writes for at least one election timeout (author's reading); say how long.

Next stop: An orchestrated saga, run, 4 min

An orchestrated saga, run

Lesson 8's section "Two-phase commit versus a saga" defines the saga and when to use it; this is the sketch that was run.

Worked example. The sketch is an orchestrated saga: one coordinator runs the steps, records a key for each, and on a failure runs the undos in reverse. The credit to B fails because B's account is frozen, so A's debit is refunded; a second saga then succeeds, and its retry under the same saga id moves no money. The step's effect and its key are committed together: once() snapshots the balances, runs the step, records the key, and on any exception restores the snapshot, which is what one local database transaction gives you. The test injects a crash after the debit of saga-3 has changed A but before its key is recorded; the debit is rolled back, the retry runs it once, and A ends at 0 rather than at minus 500. Run with java --source 21 SagaDemo.java on 2 Nov 2026 (OpenJDK 25): it printed saga ok: A=0 B=1000 log=9 and passed every check; with the key check removed the "moved once" check fails, with the rollback removed the "crash rolled the debit back" check fails, and without the compensated set the retry of saga-1 creates 500 in B. A retry of a compensated saga is refused; to try the transfer again, use a new saga id.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class SagaDemo {
  record Step(String name, Runnable action, Runnable undo) {}

  sealed interface Outcome permits Done, Compensated {}
  record Done() implements Outcome {}
  record Compensated(String failedStep) implements Outcome {}

  static final Map<String, Long> bal = new HashMap<>();
  static final List<String> log = new ArrayList<>();
  static final Set<String> applied = new HashSet<>();
  static final Set<String> compensated = new HashSet<>();
  static boolean bFrozen = true;

  static Outcome run(String sagaId, List<Step> steps) {
    // A compensated saga is finished: a retry must not run it again.
    if (compensated.contains(sagaId)) return new Compensated("retry");
    Deque<Step> done = new ArrayDeque<>();
    for (Step s : steps) {
      try {
        once(sagaId + "/" + s.name(), s.action());
        done.push(s);
        log.add("did " + s.name());
      } catch (IllegalStateException e) {
        log.add("failed " + s.name());
        while (!done.isEmpty()) {          // undo in reverse order
          Step d = done.pop();
          once(sagaId + "/undo " + d.name(), d.undo());
          log.add("undid " + d.name());
        }
        compensated.add(sagaId);
        return new Compensated(s.name());
      }
    }
    return new Done();
  }

  // The effect and its key commit together, as in one local database
  // transaction: a crash between them rolls the effect back.
  static class Crash extends RuntimeException {}
  static String crashAt = null;          // test hook: die before commit

  static void once(String key, Runnable r) {
    if (applied.contains(key)) return;   // a retry: already applied
    var before = new HashMap<>(bal);     // begin
    try {
      r.run();
      if (key.equals(crashAt)) { crashAt = null; throw new Crash(); }
      applied.add(key);                  // commit: effect + key together
    } catch (RuntimeException e) {
      bal.clear();
      bal.putAll(before);                // rollback
      throw e;
    }
  }

  static void add(String acct, long delta) {
    bal.merge(acct, delta, Long::sum);
  }

  static List<Step> transfer(long amt) {
    return List.of(
        new Step("debit A", () -> add("A", -amt), () -> add("A", amt)),
        new Step("credit B", () -> {
          if (bFrozen) throw new IllegalStateException("B frozen");
          add("B", amt);
        }, () -> add("B", -amt)));
  }

  public static void main(String[] args) {
    bal.put("A", 1_000L);
    bal.put("B", 0L);
    Outcome first = run("saga-1", transfer(500));
    check(first instanceof Compensated c
        && c.failedStep().equals("credit B"), "saga-1 compensated");
    check(bal.get("A") == 1_000 && bal.get("B") == 0, "money restored");
    check(log.equals(List.of("did debit A", "failed credit B",
        "undid debit A")), "log order");
    bFrozen = false;
    // Retrying the compensated saga under its id must move no money.
    check(run("saga-1", transfer(500)) instanceof Compensated,
        "compensated retry refused");
    check(bal.get("A") == 1_000 && bal.get("B") == 0, "no money created");
    check(run("saga-2", transfer(500)) instanceof Done, "saga-2 done");
    run("saga-2", transfer(500));        // client retries after timeout
    check(bal.get("A") == 500 && bal.get("B") == 500, "moved once");
    crashAt = "saga-3/debit A";          // die after the debit's effect
    try {
      run("saga-3", transfer(500));
      check(false, "crash expected");
    } catch (Crash e) {
      check(bal.get("A") == 500, "crash rolled the debit back");
    }
    check(run("saga-3", transfer(500)) instanceof Done, "saga-3 done");
    check(bal.get("A") == 0 && bal.get("B") == 1_000, "crash moved once");
    System.out.println("saga ok: A=" + bal.get("A")
        + " B=" + bal.get("B") + " log=" + log.size());
  }

  static void check(boolean ok, String what) {
    if (!ok) throw new AssertionError(what);
  }
}

Constraints. These rules are the author's reading of practice, not the 1987 paper. A compensation must be idempotent and must eventually succeed, so it is retried, never abandoned. A step that cannot be undone, such as money leaving for an outside bank, goes last. The in-between state is shown honestly, which is why the ledger says "pending". In the room: within one database, use a local transaction; across shards of a store that offers distributed transactions, its 2PC is acceptable if you name the blocking risk; across services or companies, use a saga.

Next stop: Idempotency keys and the outbox, 1 min

Idempotency keys and the outbox

Context. Lesson 8's building-block table gives the contract of an idempotency key; the implementation is where candidates slip. The key, a hash of the request and the stored result belong in the same database transaction as the effect, or a crash between them either forgets a completed payment or remembers one that never happened. A unique constraint on the key settles two copies that arrive together: one insert wins, and the other is answered from the stored row, or told to retry while the first is still running (author's reading).

The dual write. A service that updates its database and then publishes an event can crash between the two, so the state changes and nobody hears, or an event announces a change that rolled back. The outbox pattern (a practitioner pattern; author's reading, not from one source) writes the event as a row in an outbox table inside the same transaction as the business rows. A separate relay, polling that table or reading the database's change log (change data capture), publishes each row and marks it sent. The relay can crash after publishing and before marking, so delivery is at least once, and consumers drop repeats by event id, as in the queue row of that table. Design 3 (lesson 8) is this path: transfer, entries and outbox row in one transaction, then the relay to the bank gateway.

The failure to name. Do not promise exactly-once delivery end to end. Say "at least once, with an id the consumer deduplicates on", and say how long the dedupe record lives against the longest retry window.