23 — Design A Hotel Reservation System

The problem: design the booking system for a hotel chain. Users search for rooms, see availability, and reserve.

A booking system has one central rule: a given room on a given night is sold to exactly one guest. The work is making that rule hold under simultaneous users, a payment provider that times out, a cache that lags the database, and four separate services that share no database.

This chapter covers:

• sizing the system’s traffic;
• the exact sequence of database operations that sells one room twice;
• the three standard fixes for that race, compared;
• a retry-safe payment path that cannot charge a card twice;
• why deliberate overselling is a number in a column rather than a bug.

What goes in and what comes out

The input is a single HTTP request: a hotel, a room type such as “king”, a check-in date, a check-out date, a guest, and an amount to charge.

The output is one of three things: a confirmed reservation with an id, a “sold out” error that names which night failed, or a declined payment with every briefly-held night given back.

Between input and output are exactly three effects:

1. the count of sold rooms goes up by one for each night of the stay;
2. one reservation row is written;
3. one charge is made at an outside payment company.

The chapter is about making those three effects happen exactly once each, in the right order, while requests are retried and machines crash.

Why this problem is different

The scale is small; correctness is the whole problem.

Do the estimate anyway, because it justifies spending the rest of the interview on transactions rather than on sharding. (A shard is one slice of a database split across several servers. Sharding is the standard answer to “too much traffic for one machine”, and part of this chapter’s job is to show that the question is never asked here.)

Three places candidates lose this round

Over-engineering. Proposing a system split across many database servers, fronted by caches and message queues, with copies of the data allowed to disagree for a while, all to absorb eight writes per second.

Vagueness. Saying “we take a lock” without naming the isolation level (the database setting that decides which concurrency mistakes are permitted), the lock’s scope, or how many bookings per second it can sustain.

A structural mistake. Placing the call to the outside payment company inside the database transaction that holds the room-count row, which multiplies the time that row is held by roughly six hundred.

What this chapter borrows from elsewhere

Three outside dependencies are worth naming now.

The 86,400 -> 1e5 rounding used in the arithmetic below — treating the 86,400 seconds in a day as 100,000, which makes per-second numbers a shift of the decimal point — comes from chapter 02.

Isolation levels, multi-version concurrency control (the technique that lets readers see a consistent older copy of a row while a writer changes it), lock modes and deadlock detection are derived in sql 03. This chapter restates each result it uses, in one line, where it uses it.

The durable retrying of long-running multi-service work rides on the message queue of chapter 20.

1. Framing: what decision, and what breaks

A reservation system exists to enforce one sentence: a room-night can be sold once.

A room-night is the unit being sold: one room, of one type, at one hotel, on one calendar night. It is the unit this chapter counts and locks throughout.

Everything else — search, ranking, pricing, loyalty points, cancellation policy — is commerce built on top of that single invariant, meaning a statement that must be true of the data before and after every operation, without exception.

The four properties the invariant trades against

The system is asked to be good at four things, and each one has a cost paid by a specific mechanism. Each mechanism has its own section later.

The terms in that table, in plain words

The table uses several terms of art, defined here before they recur.

• To walk a guest is hotel jargon for turning up a guest whose room does not exist and paying to put them elsewhere.
• Atomic means all-or-nothing: the step either happens completely or leaves no trace, with no state in between that another request can observe.
• To serialize work is to force it into single file, one at a time. That is what makes atomicity possible, and it is what caps throughput.
• A chargeback is the card network forcibly reversing a payment on the cardholder’s complaint. It costs a fee and counts against the merchant.
• An idempotency key is a string the caller attaches to a request so the server can recognise a retry of the same intent and return the first answer instead of doing the work again. “Idempotent” means running it twice has the same effect as running it once.
• Inventory, in this chapter, never means a warehouse. It is the count of room-nights available to sell.
• A distributed transaction is a single all-or-nothing operation spanning several independent databases.
• A saga is the practical replacement for one: a sequence of ordinary local steps, each with a compensation — a second operation that undoes the first after the fact (a refund undoing a charge) rather than rolling it back inside a transaction.

The sentence to say in the first minute

“The write rate here is single digits per second, so this is a data-integrity problem, not a throughput problem, and I am going to spend the time on the race condition.”

A race condition is a bug that appears only when two operations overlap in time and interleave in an unlucky order. That sentence reframes the round, and section 3 is the arithmetic that backs it.

What actually breaks in production

Four things, each with a section later.

• A flash sale. A promotion that compresses a month of demand for a single date into a single hour turns a quiet row into a contended one.
• A payment timeout. The provider times out, the client retries, and the same customer intent is now in flight twice.
• A stale cache. It serves “3 rooms left” for a date that sold out ninety seconds ago, so users are failed at the payment page rather than at the search page.
• A silently failed compensation. Room-nights stay held by a reservation nobody will ever pay for.

2. Requirements

Functional

• Search hotels by location and date range; show remaining availability per room type.
• Reserve a room type for a date range, atomically across every night of the stay.
• Pay, with a client-driven retry that cannot double-charge.
• Cancel, modify dates, and return the inventory.
• Admin: set inventory, rates, and a deliberate overbooking allowance per date.

Overbooking means accepting more reservations than there are physical rooms. Done by accident it is the central bug of this chapter; done on purpose it is standard practice, because a predictable share of guests never arrive, and section 12 derives the exact allowance.

Three things are out of scope, and stating that is part of the answer.

• Pricing and yield optimisation — deciding what to charge for a room tonight — is a forecasting model, not an architecture.
• Room assignment is excluded because hotels pick a physical room number at check-in rather than at booking. Section 5 leans on that fact.
• Synchronisation with outside travel agencies (Booking.com, Expedia and the like, collectively online travel agencies, or OTAs) through a channel manager is a whole integration product of its own.

Non-functional — the ones that settle the design

The two rows to watch are the latency ones: the p99 booking target is set by the payment provider, and the p99 read target is what justifies the cache.

Three pieces of shorthand in that table:

• p99 is the ninety-ninth percentile: the number that 99 out of 100 requests come in under. It describes the slow tail that users actually complain about, rather than the average, which hides it.
• A payment gateway is the outside company that talks to the card networks on your behalf. You call it over the network, it is slow by your standards, and you do not control it.
• Durability means that once the system has said yes, the data survives a crash. The data is on disk, not merely in memory.

The asymmetry worth naming: reads outnumber writes 400:1, and the reads are allowed to be stale while the writes are not allowed to be wrong.

Stale here means “correct a moment ago and possibly out of date now”. That split gives the system a cached read path and a small, strict write path, and the write path is where the interview lives.

3. Back of the envelope

A back-of-the-envelope estimate is a deliberately rough calculation, carried out in round numbers, whose purpose is to settle a design question rather than to be precise. Three of them follow: how much traffic there is, how much data there is, and how a date range must be interpreted so that two stays never collide. Each rules out a class of wrong answer.

3a. Demand, and why it is small

Three numbers come out of this estimate: the booking rate, the availability-read rate, and the ratio between them. QPS below means queries per second — how many requests of that kind the system handles each second.

Rates use 1e5 while you are estimating; every number reported as a result below is converted with the real 86,400.

The 86,400 -> 1e5 rounding of chapter 02 is a drill convention, not a reporting convention. Dividing by 100,000 instead of by 86,400 understates every rate by 13.6% (1 - 86,400/100,000 = 0.136). That error is invisible while deciding whether a number is big, and unacceptable in a reported number.

Ratios are exempt, because the divisor cancels. That is why the read:write ratio below comes out the same on either convention.

The block below runs in four stages. First the write side: rooms, then room-nights sold per day, then bookings per day, then bookings per second. Then the read side: detail-page views, then searches, then availability lookups. Then the two read rates added together, and finally the ratio between reads and writes.

assume  5,000 hotels, 200 rooms each, 70% occupancy, 3-night average stay,
        100 detail-page views per booking, 10 detail views per search,
        30 hotels scored per search, peak = 3x average

rooms in the system
  5,000 x 200                            =  1,000,000
room-nights consumed per day
  1,000,000 x 0.70                       =  700,000
bookings per day
  700,000 / 3                            =  233,333
booking QPS while estimating, at 86,400 -> 1e5
  233,333 / 100,000                      =  2.33
booking QPS as a REPORTED result, at the real 86,400
  233,333 / 86,400                       =  2.70
peak booking QPS
  2.70 x 3                               =  8.10
detail-page views per day
  233,333 x 100                          =  23,333,300
detail-page QPS at peak
  23,333,300 / 86,400 x 3                =  810
searches per day
  23,333,300 / 10                        =  2,333,330
availability lookups per second at peak, 30 hotels per search
  2,333,330 / 86,400 x 3 x 30            =  2,431
peak read QPS against availability
  810 + 2,431                            =  3,241
read to write ratio at peak -- and this one is structural, not measured:
100 detail views plus 10 searches x 30 hotels is 400 reads per booking
  3,241 / 8.10                           =  400

Eight writes per second. That is the number the whole chapter hangs on.

A single unremarkable Postgres primary — the one database server that accepts writes, as opposed to the read-only copies called replicas that follow it — handles thousands of small write transactions per second. Eight is three orders of magnitude below that.

So there is no sharding argument, no queue argument, and no NoSQL argument available on throughput grounds. (NoSQL is the family of non-relational databases that trade transactions and joins for horizontal scale. The trade is not worth making when one machine has a thousandfold of headroom.)

The 3,241 reads per second are a cache and two replicas. Nothing more.

State the consequence directly: at eight writes a second you can afford the most expensive correctness mechanism available. The question is which one, and what it costs when demand is not uniform.

3b. Inventory rows, and why the grain is a room type

This estimate answers two questions at once: how much data the availability table actually holds, and what it would cost to track each physical room individually instead. Grain is the unit one row of a table stands for.

The block below sizes the same table twice. The first half counts rows at a (hotel, room type, date) grain and multiplies by a per-row byte budget built up column by column. The second half redoes the row count at a per-physical-room grain, so the two totals can be compared directly. The last two lines size the reservation table, which is a different shape of problem — it grows with time rather than with the booking horizon.

assume  5 room types per hotel, 500-day booking horizon

inventory rows
  5,000 x 5 x 500                        =  12,500,000
row bytes: hotel_id 8 + room_type_id 8 + date 4 + total_inventory 2
           + total_reserved 2 + version 8 + index and row overhead 40
  8 + 8 + 4 + 2 + 2 + 8 + 40             =  72
inventory table, in bytes
  12,500,000 x 72                        =  900,000,000
the same table at a per-ROOM grain instead
  1,000,000 x 500                        =  500,000,000
per-room table, in bytes
  500,000,000 x 72                       =  36,000,000,000
reservation rows over 5 years
  233,333 x 365 x 5                      =  425,832,725
reservation table at 300 B/row, in bytes
  425,832,725 x 300                      =  127,749,817,500

The entire forward inventory of a 5,000-hotel chain is 900 MB. It fits in RAM on a laptop, index and all. That rules out every design that treats availability as a big-data problem.

The per-room grain is 40x bigger (36 GB against 900 MB) and — much more importantly — wrong.

Hotels do not sell room 412. They sell a king room, and the front desk assigns a physical room at check-in so it can group families, honour upgrades, and route housekeeping. Modelling inventory per physical room does three bad things: it forces an assignment decision months early, it converts every date change into a re-assignment, and it turns a one-row update into a search for a free room.

The unit of inventory is (hotel, room type, date). It is a domain fact, and worth stating and defending explicitly.

A 3-night stay therefore touches exactly 3 rows, and must take all 3 or none.

3c. The interval convention, and the night that is not sold

This is the smallest decision in the chapter, and it is one of the two ways to sell a room twice.

Every date range in this system is the half-open interval [check_in, check_out). The check-in night is sold; the checkout night is not. A half-open interval is a range that includes its start and excludes its end — the square bracket includes, the round bracket excludes — so 14th to 17th means the nights of the 14th, 15th and 16th, and not the 17th. Say it once, put it in the comment on the table definition, and make every database condition agree, because the alternative is not a style disagreement, it is a room-night sold twice.

The consequence is mechanical. The condition is always date >= check_in AND date < check_out, never date BETWEEN check_in AND check_out. SQL’s BETWEEN includes both ends, so it matches nights + 1 rows and marks the checkout night as sold — and that is the night the next guest is checking in on.

The code below turns a date pair into the list of nights it occupies, and then proves three things about it. Read it in four parts:

1. nights() itself — note the < in the loop and the co <= ci guard above it, which are the two comparisons the whole convention rests on;
2. the assertions that a 14th-to-17th stay is three nights, in both the date and the ISO-string form the API sends;
3. the boundary assertion — guest A checking out on the 17th and guest B checking in on the 17th share no night;
4. between(), the wrong version, which produces four nights and hands the 17th to both guests.

from datetime import date, timedelta

def _as_date(v) -> date:
    """The API of section 4 sends `start_date` and `end_date` as ISO strings.
    Accept either, so that `reserve()` in section 9b can be called on its own
    API's input instead of on a shape nothing ever sends it."""
    return v if isinstance(v, date) else date.fromisoformat(v)

def nights(check_in, check_out) -> list:
    """The nights a stay actually occupies, on [check_in, check_out)."""
    ci, co = _as_date(check_in), _as_date(check_out)
    if co <= ci:                             # the range guard: see below
        raise ValueError(f"end_date {co} must be strictly after start_date {ci}")
    out, d = [], ci
    while d < co:                            # `<`, not `<=`: the half-open guard
        out.append(d)
        d += timedelta(days=1)
    return out

# The section 4 example, 2026-11-14 -> 2026-11-17, is a THREE-night stay.
a = nights(date(2026, 11, 14), date(2026, 11, 17))
assert a == [date(2026, 11, 14), date(2026, 11, 15), date(2026, 11, 16)]
assert len(a) == 3
assert len(nights("2026-11-14", "2026-11-17")) == 3   # strings, as the API sends

# The boundary case that decides the predicate: guest A checks out on the 17th
# and guest B checks in on the 17th. That is not a conflict, and the night of
# the 17th must be decremented exactly once, by B.
b = nights(date(2026, 11, 17), date(2026, 11, 19))
assert set(a) & set(b) == set()

# A zero-night booking must not reach `rows != wanted` in section 9b, where
# `0 != 0` is False: the stay is confirmed and the card is charged with no
# room-night taken, which defeats the decrement-and-rowcount mechanism this
# whole chapter is built on. An inverted range is the same bug, backwards.
for bad in [("2026-11-14", "2026-11-14"), ("2026-11-17", "2026-11-14")]:
    try:
        nights(*bad)
        raise AssertionError(f"{bad} should not be bookable")
    except ValueError:
        pass

# What `date BETWEEN start AND end` does instead: 4 rows for a 3-night stay,
# and the 17th charged to both guests.
def between(check_in, check_out):
    out, d = [], check_in
    while d <= check_out:
        out.append(d)
        d += timedelta(days=1)
    return out

assert len(between(date(2026, 11, 14), date(2026, 11, 17))) == 4
assert set(between(date(2026, 11, 14), date(2026, 11, 17))) & \
       set(between(date(2026, 11, 17), date(2026, 11, 19))) == {date(2026, 11, 17)}

The range guard in that listing is not decoration. Without it, nights(d, d) and nights(d + 1, d) both return an empty list, so wanted is 0 in section 9b — and that function’s entire defence is if rows != wanted, which for 0 != 0 is False. A stay of no nights therefore passes every check, writes a reservation and charges the card, having taken no inventory at all. One missing comparison defeats the decrement-and-rowcount mechanism the rest of the chapter is built on, which is why the range is checked once, in the only function that turns a date pair into nights.

Note the shape of the damage. The closed condition does not merely over-count. On the boundary case it marks the 17th as sold for guest A and again for guest B, so one real room-night is consumed twice and the hotel walks a guest it never intended to oversell. That is the same outcome as the race in section 7, arriving through arithmetic rather than through concurrency — and because nothing about it involves two transactions overlapping, no database setting anywhere prevents it.

3d. Assumption ledger

Every number above rests on an assumption, and an interview goes badly when those are silently invented. The discipline is to sort each one into three buckets:

• state it — state it and move on, nobody will argue;
• ask it — the answer changes the design, so get it from the interviewer;
• load-bearing — if this number is wrong by an order of magnitude, some conclusion in this chapter collapses.

Keeping the ledger visible is what lets you say later “that follows from the 5% no-show rate I assumed; at 15% the same method gives an allowance in the mid-twenties instead of 7”.

Six rows below are marked load-bearing in the last column. Those are the ones to re-derive on the spot if the interviewer changes a number; the rest you can restate and move past.

The two to ask about are the no-show rate and the payment-gateway latency, because both are numbers the business already knows and both change a design decision rather than a digit.

4. API sketch

The contract makes the input and the output concrete: the exact request a client sends, the exact responses it can get back, and five choices the rest of the chapter has to honour.

Two things to know before reading the sketch.

The three-digit numbers are HTTP status codes. 2xx means it worked, 4xx means the caller’s request cannot be satisfied. 201 is “created”, 202 is “accepted, not finished yet”, 409 is “conflict”, 422 is “the request is well-formed but unprocessable”.

3-D Secure, named on the 202 line, is the card networks’ extra authentication step: the bank interrupts the payment to make the cardholder confirm, usually with a code sent by text. It takes minutes rather than milliseconds. That is why a booking has to be allowed to sit in pending instead of resolving in one round trip, and it is what section 11 sizes the pending-hold TTL against.

One write endpoint with its four possible responses, then the three supporting endpoints. The Idempotency-Key header appears on both write calls, and the 409 carries a date.

POST /v1/reservations
  Idempotency-Key: 0f3c9a...                 -- client generated, one per user intent
  {"hotel_id": 812, "room_type_id": 3,
   "start_date": "2026-11-14", "end_date": "2026-11-17",
   "guest_id": 99120, "rate_quote": "rq_7f2a", "amount_cents": 84000}
  201 {"reservation_id": "res_...", "status": "confirmed"}
  202 {"reservation_id": "res_...", "status": "pending"}   -- 3-D Secure in flight
  409 {"error": "sold_out", "night": "2026-11-15"}
  422 {"error": "idempotency_key_reused_with_different_body"}

GET  /v1/hotels/{id}/availability?start=&end=&guests=
     -> {"king": {"remaining": 3, "as_of": "2026-11-01T10:22:07Z"}, ...}
POST /v1/reservations/{id}:cancel   Idempotency-Key: ...
GET  /v1/reservations/{id}

Five choices in that contract carry weight, and each one is defended by a later section.

• start_date and end_date are the half-open interval of section 3c. 2026-11-14 to 2026-11-17 is three nights and three inventory rows, and the night of the 17th belongs to whoever checks in that day.
• Idempotency-Key is required on every call that changes data, not just on create. A retried cancellation that issues two refunds is the same double-charge bug in a different place.
• The 409 names the night that failed. A 3-night stay is 3 rows; “sold out” with no date attached gives the client nothing to act on, and its next move — offer two nights instead of three, or a different room type — depends on which night ran out.
• as_of is in the availability response. That number is a hint served from a cache, and putting its age in the response is how a caller decides whether to re-check the database before showing a “1 left!” badge.
• rate_quote is a token the server issued earlier, so the price is never chosen by the client and the quote can expire. The amount in the request body is checked against that quote rather than trusted.

There is deliberately no endpoint like PUT /availability/{date}/decrement. Publishing a “reduce the count by one” call would make all-or-nothing behaviour the client’s problem: a client that decremented two nights and then crashed would leave the third unbooked and the first two unsellable. The only public write is “reserve this stay”, and the all-or-nothing step happens on the server side of that boundary where it can be enforced.

5. Data model

The schema carries three choices an interviewer will push on: two counters instead of one, a rule enforced by the database rather than by code, and a uniqueness constraint that acts as a last line of defence.

Two bits of notation first. PK marks a table’s primary key, the column combination that identifies a row uniquely. UUID is a universally unique identifier — a 128-bit value any machine can generate on its own, with no central allocator and no coordination, and still be safe in assuming nobody else will ever generate the same one.

Seven tables follow. room_inventory is the one to read closely: it is the contended table, it carries the two counters, and its two CHECK lines are the invariant written where the database can enforce it. The rest are supporting cast — hotels and room_types are reference data, reservations is the record of sale, idempotency and saga_log are bookkeeping for retries, and rooms exists only so the front desk has somewhere to record a physical room number at check-in.

hotels          hotel_id PK, name, geo_cell, timezone
room_types      room_type_id PK, hotel_id, name, occupancy, base_rate_cents

room_inventory                                  -- the contended table
  hotel_id BIGINT, room_type_id BIGINT, date DATE,
  total_inventory SMALLINT NOT NULL,            -- includes any deliberate overbook
  total_reserved  SMALLINT NOT NULL DEFAULT 0,
  version         BIGINT   NOT NULL DEFAULT 0,
  PRIMARY KEY (hotel_id, room_type_id, date),
  CHECK (total_reserved >= 0),
  CHECK (total_reserved <= total_inventory)     -- the invariant, in the schema

reservations
  reservation_id UUID PK, hotel_id, room_type_id, guest_id,
  start_date, end_date,                         -- HALF-OPEN [start, end): section 3c
  status,                                       -- pending | confirmed | cancelled
  amount_cents, idempotency_key, created_at,
  UNIQUE (idempotency_key)

idempotency     key PK, request_hash, state, response_status, response_body, created_at
saga_log        saga_id PK, reservation_id, step, state, attempt, next_attempt_at
rooms           room_id PK, hotel_id, room_type_id, room_number   -- assigned at check-in

Three decisions in that schema are worth defending, because an interviewer will push on all three.

total_inventory and total_reserved, not a single remaining. One combined counter fails three ways. It cannot tell “sold out” apart from “an administrator set the room count to zero”. It cannot express a deliberate overbooking allowance without lying about how many rooms the hotel has. And it turns an inventory change such as taking a room out of service into a read-then-write against the very value that bookings are already fighting over.

With two columns, deliberate overbooking is a change to total_inventory alone and touches nothing else.

The CHECK lives in the table definition, not in the application. A CHECK constraint is a rule the database itself refuses to violate, on every write, from every caller.

It costs nothing at write time, because it is evaluated on a row the UPDATE statement is already holding. And it is the only guard that survives a new caller written by someone who never read this document. Section 8 prices all the guards side by side; this is the free one.

reservations.idempotency_key is UNIQUE. The separate idempotency table is the fast path that answers a retry quickly; this constraint is the truth. It means that even a bug in the idempotency layer cannot produce two reservation rows for one customer intent, because the database will reject the second insert.

If you ever shard this, shard on hotel_id

A shard key is the column whose value decides which machine a row lives on.

Here it is hotel_id. Every booking transaction touches rows for exactly one hotel, so partitioning on hotel_id keeps every write confined to a single machine, which means the correctness story in this chapter never has to become a transaction spanning two databases (shard-key selection).

But at 900 MB and 8 writes per second you would shard only for two reasons that have nothing to do with load: to limit blast radius — the amount of the business that one failure takes down — or to keep one large tenant’s data physically separate. Never for throughput. State that explicitly, so the interviewer sees you considered the option.

6. High-level architecture

Every component on one page. Nothing here is argued yet — this is a map, and every claim it makes has a section number attached.

The diagram splits at the gateway. The left-hand branch is the read path — search, cache, replicas — and the right-hand branch is the write path — reservation service, idempotency store, primary, then the saga. The two things to look for are that the primary is the only box the reservation service writes to inside a transaction, and that the payment service hangs off the saga orchestrator rather than off the primary.

flowchart TD
    U(["client"]) --> GW["API gateway<br/>auth, per-account rate limit"]
    GW --> SRCH["Search service<br/>geo + date filter"]
    GW --> RES["Reservation service"]
    SRCH --> CACHE[("Availability cache<br/>invalidated on write<br/>never TTL-expired")]
    CACHE -.->|"miss"| RO[("Read replicas<br/>availability only")]
    RES --> IDEM[("Idempotency store<br/>24 h TTL")]
    RES --> DB[("Primary<br/>room_inventory + reservations<br/>ONE transaction")]
    DB --> RO
    DB -->|"write-through invalidate"| CACHE
    RES --> SAGA["Saga orchestrator<br/>durable step log"]
    SAGA --> PAY["Payment service<br/>authorize, then capture"]
    SAGA --> LOY["Loyalty service"]
    SAGA --> MSG["Confirmation email<br/>irreversible, therefore last"]
    SAGA --> Q[["Retry queue<br/>ch 20"]]
    Q --> SAGA
    SWEEP["Expiry sweeper<br/>releases pending holds"] --> DB

    style DB fill:#1d3557,color:#fff
    style RO fill:#2d6a4f,color:#fff
    style CACHE fill:#bc6c25,color:#fff
    style SAGA fill:#40916c,color:#fff
    style MSG fill:#9d0208,color:#fff

Reading the colours

Colours follow ch 01’s key:

So the primary is blue, and the read replicas are green because they are the read capacity — the thing the 400:1 ratio buys.

The saga orchestrator is light green rather than green. It answers no reads at all, and its whole purpose is to move the payment, loyalty and mail steps off the request path.

The cache is orange rather than the green ch 01’s key would give it, and that deviation is deliberate rather than an oversight. Section 10 sizes it by memory and by how stale it is allowed to be, never by read volume, and its entire argument is about which direction it is allowed to be wrong in.

The confirmation email is red because it is the only step that cannot be undone. The key says red is the step you cannot undo, and the box’s label says “irreversible, therefore last”.

What each box does

Walking them in the order a request meets them:

• API gateway — authenticates the caller and applies a per-account rate limit, so one script cannot consume the booking path.
• Search service — answers “which hotels match” with a geo and date filter. It never writes anything.
• Reservation service — owns the write path and is the only component allowed to change room counts. One transaction on the primary’s room_inventory and reservations tables does the whole booking.
• Availability cache — holds recent answers so that reads never reach the database.
• Read replicas — follower copies of the primary, used for availability only. They absorb the cache misses.
• Idempotency store — remembers which customer intents have already been served.
• Saga orchestrator — drives the multi-service steps and keeps a durable step log, so that a crash resumes rather than restarts. It calls the payment service, the loyalty service and the confirmation email in that order.
• Retry queue — where anything that failed and must be attempted again later goes (ch 20).
• Expiry sweeper — a background job that releases holds nobody completed.

The four claims the picture makes

Each has a section behind it:

1. The inventory decrement and the reservation insert are in one transaction on one primary (section 8).
2. The payment call is outside it (section 9).
3. The cache is refreshed by the write itself rather than left to expire on a timer — that is the arrow marked write-through invalidate (section 10).
4. The confirmation email is last, because it is the only step with no way to undo it (section 11).

The arrow that must not exist is the one from the reservation transaction to the payment gateway. Section 8 prices exactly what that arrow costs, and section 9b shows the code that avoids it.

7. Deep dive 1: the double-booking race, traced

Two well-written booking requests can sell the same room, and the trace below shows it happening statement by statement. The real defect it exposes is not the one most candidates name.

Here is the setup. One room-night is left: total_inventory = 11, total_reserved = 10, so remaining = 1. Two requests arrive 4 milliseconds apart, on two different application servers, against one database running at its default isolation level, READ COMMITTED.

An isolation level is the database setting that decides how much two overlapping transactions are allowed to see of each other. READ COMMITTED is the mildest useful one and the default in Postgres, MySQL and SQL Server. It promises only that you never read a change another transaction has not committed yet — and, as the trace shows, that promise is not enough.

The trace below has two columns, T1 on the left and T2 on the right, with vertical position meaning time: a statement further down happens later. Follow it top to bottom and watch the two SELECT results, both of which come back 1, and then the two UPDATE statements, both of which set the same literal value. The last two lines are the damage.

 T1  (READ COMMITTED)                    T2  (READ COMMITTED)
 BEGIN                                   BEGIN
 SELECT total_inventory - total_reserved
   FROM room_inventory
  WHERE hotel_id=812
    AND room_type_id=3
    AND date='2026-11-14';       -> 1
                                         SELECT total_inventory - total_reserved
                                           FROM room_inventory
                                          WHERE hotel_id=812
                                            AND room_type_id=3
                                            AND date='2026-11-14';      -> 1
 -- remaining is 1, allow the booking
                                         -- remaining is 1, allow the booking
 UPDATE room_inventory
    SET total_reserved = 11              -- the value the APP computed
  WHERE hotel_id=812 AND room_type_id=3
    AND date='2026-11-14';
 INSERT INTO reservations ...;
 COMMIT
                                         UPDATE room_inventory
                                            SET total_reserved = 11
                                          WHERE hotel_id=812 AND room_type_id=3
                                            AND date='2026-11-14';
                                         INSERT INTO reservations ...;
                                         COMMIT

 -- total_inventory 11, total_reserved 11, and 12 reservation rows exist.
 -- The counter is wrong AND the room-night is sold twice.

Two things to notice, and the second is the one candidates miss.

Both transactions read remaining = 1 and both wrote 0.

Nothing in READ COMMITTED connects the SELECT to the UPDATE that follows it. The level gives each statement a fresh snapshot — a consistent view of the database as of the moment that statement began. So T2’s SELECT legitimately saw the world before T1 committed, and its UPDATE legitimately overwrote the world after.

This is the textbook lost update: two transactions read a value, each computes a new one from what it read, and the second write silently erases the first. The anomaly matrix in sql 03 lists lost update as permitted at READ COMMITTED. It is not a database bug; it is the published definition of the level.

Now write the UPDATE the other way — SET total_reserved = total_reserved + 1, letting the database read the current value instead of the application.

The lost update disappears, because that statement re-reads the latest committed row while holding a row lock: an exclusive claim on that single row, which blocks any other writer until the transaction ends.

But run the numbers. total_reserved ends at 12 against a total_inventory of 11, and you are still oversold. The difference is that this version leaves evidence — a row that visibly violates its own invariant, which a CHECK constraint would have refused outright.

So the defect is not “we did not lock”. The defect is that the decision and the write were not the same step. Anything that re-unites them fixes it, and the three ways to do that — priced against each other in section 8 — differ only in cost and failure behaviour.

What each isolation level actually does to this trace

Since the defect is a permitted anomaly rather than a mistake, the obvious next move is to raise the isolation level. This table says what each level actually does to the trace above, and the answer is engine-specific in a way that catches people out.

The column to read is the middle one. Two of the five rows say “Overbooks” — and the surprise is that one of those two is REPEATABLE READ, a level most people assume fixes this.

Three terms in that table need unpacking.

• REPEATABLE READ is the level that promises a transaction sees the same data every time it reads, as if it had photographed the database at its start.
• Snapshot isolation is PostgreSQL’s implementation of that promise: every read comes from the photograph, and any write landing on a row the photograph has since gone stale on is refused with error code 40001, a serialization failure.
• InnoDB is MySQL’s storage engine. SERIALIZABLE is the strongest level: the database guarantees the result is the same as if the transactions had run one after another with no overlap at all.

“REPEATABLE READ fixes it” is only true on one of the two most popular engines, and the difference is exactly the one sql 03 calls out. InnoDB serves the transaction’s snapshot to a plain SELECT, but serves the latest committed row to any statement that locks or writes. So the read and the write see different worlds inside one transaction. Say which engine you mean, or the claim cannot be tested.

SERIALIZABLE is correct and is still the wrong default here, for two reasons specific to this problem.

It turns contention into aborted transactions, which means every transaction must be safe to run again from the start. A booking transaction with a payment capture inside it would not be, because the money has already moved (why SERIALIZABLE is not always the answer).

Its abort rate grows faster than linearly as contention rises, so it degrades worst during exactly the flash sale you bought it for.

8. Deep dive 2: three fixes, priced

The race in section 7 has three standard cures — hold a lock, detect a conflict and retry, or fold the check into the write. At this system’s scale all three turn out to be affordable, so the choice is made on failure behaviour instead.

The unit cost everything is measured against

Establish the unit cost first, because every fix below is priced in the same currency: the time one booking transaction spends inside the database. Call that time T.

Why T is the only number that matters. While a transaction holds a row, no other transaction can change that row. So one row can be updated at most once per T — a ceiling of 1/T updates per second. Shrink T and the ceiling rises; put a slow network call inside the transaction and the ceiling collapses.

An fsync is the operating-system call that forces data out of memory onto durable disk. A database commit must do one, and it is the slowest part of an otherwise trivial transaction.

The block below adds up the four things a booking transaction does, in milliseconds, and then converts that total into a per-second ceiling.

in-transaction time, in ms: lock or conditional UPDATE 1 + INSERT 1
                            + commit fsync 1 + two app round trips 2
  1 + 1 + 1 + 2                          =  5
single-row booking ceiling, per second
  1,000 / 5                              =  200

So the ceiling is 200 bookings per second on one row (1,000 ms per second divided by 5 ms per transaction).

Now the demand on the single hottest row, which is the only thing that ceiling has to beat. The worst case is one date at one 200-room property, with the entire day’s inventory sold inside a single flash-sale hour of 3,600 seconds.

a 200-room property can sell at most 200 room-nights for one date;
compress every one of them into a single flash-sale hour:
  200 / 3,600                            =  0.0556
headroom against the 200/s ceiling
  200 / 0.0556                           =  3,597
utilisation of the hottest row in the system
  0.0556 / 200                           =  0.000278

That last line is 0.000278, which is 0.028% — call it 0.03%.

The hottest row in the entire system runs at 0.03% of what one pessimistic lock can sustain. Because every option below is affordable, the choice is made on failure behaviour rather than on throughput.

Fix 1 — pessimistic: SELECT ... FOR UPDATE

Pessimistic concurrency control assumes a conflict will happen and prevents it up front by taking a lock. The SQL for that is SELECT ... FOR UPDATE, which reads rows and locks them against other writers until the transaction ends.

The statement below reads every night of the stay, locks all of them, lets the application decide, then writes. The two clauses to notice are ORDER BY date, which is not cosmetic, and FOR UPDATE, which is what turns a read into a lock.

BEGIN;
SELECT total_inventory, total_reserved
  FROM room_inventory
 WHERE hotel_id = $1 AND room_type_id = $2
   AND date >= $3 AND date < $4                 -- half-open: section 3c
 ORDER BY date                                  -- deterministic lock order
   FOR UPDATE;                                  -- N rows for an N-night stay
-- decide in application code, then
UPDATE room_inventory SET total_reserved = total_reserved + 1
 WHERE hotel_id = $1 AND room_type_id = $2
   AND date >= $3 AND date < $4;
INSERT INTO reservations (...) VALUES (...);
COMMIT;

The price is a row lock held from the SELECT all the way to the COMMIT. So one row sustains 1/T = 200 bookings per second, and bookers who arrive during that window wait in line rather than failing.

ORDER BY date is load-bearing. A statement that locks several rows takes them in whatever order the query planner chose, which is not stable across runs. Two overlapping stays that acquire the same nights in opposite orders is a textbook deadlock — each transaction holds a row the other is waiting for, so neither can proceed (deadlock prevention). Sorting the rows into one agreed order makes that cycle impossible.

The cost of getting it wrong is worse than an error. Postgres does not even look for such a cycle until its deadlock_timeout (one second by default) expires, so the bug costs a full second of latency before it costs you an error message.

Use pessimistic locking when the decision depends on values the write statement cannot refer to — a rate table, a loyalty tier, a policy row in another table, or anything the application has to look at before it can choose. That is the case a conditional UPDATE genuinely cannot express, because the condition attached to an UPDATE can only mention columns of the row being written.

A multi-night stay is not that case, and it is worth being precise about why, because the reflex answer is that N nights need N locks. They do not.

One UPDATE covering the whole date range handles all N nights, and its rowcount is the decision. Rowcount is the number of rows a statement actually changed, which the database returns to the caller. A rowcount equal to the number of nights means every night was available and every night is now taken. Anything less means some night was sold out, at which point rolling the transaction back releases the nights that did succeed.

Section 9b shows that statement in full, and it is the default path in this design. What FOR UPDATE buys is the ability to read the numbers before deciding — to say “only 1 left on the 15th, offer the guest a different room type” instead of “the rowcount was 2, something failed”.

Fix 2 — optimistic: version column plus retry

Optimistic concurrency control assumes conflicts are rare, so it takes no lock. Instead it records which version of the row it read, and refuses the write if that version has moved on. The loser is told nothing happened and tries again.

That is what the version column in section 5’s schema is for. Every write bumps it by one, so a caller that read version 7 and finds the row at version 8 knows somebody else got there first. In the statement below, watch the AND version = $4 line: it is the whole mechanism.

UPDATE room_inventory
   SET total_reserved = total_reserved + 1, version = version + 1
 WHERE hotel_id = $1 AND room_type_id = $2 AND date = $3
   AND version = $4                             -- the version the caller read
   AND total_reserved + 1 <= total_inventory;
-- rowcount 0: either someone else moved first, or it is sold out. Re-read to tell.

The price is that no lock is held between the read and the write, but a conflict wastes the whole attempt.

How often does that happen? Multiply the arrival rate by the width of the window in which a conflict is possible — and that window is the transaction time itself, because a second writer only conflicts if it arrives while the first is still in flight. Writing the arrival rate as lambda, the estimate is lambda x T.

conflict window = the transaction time, 5 ms = 0.005 s
retry probability on the hottest row, first-order lambda x T
  0.0556 x 0.005                         =  0.000278

0.000278 is one retry in about 3,600 bookings (1 / 0.000278 = 3,597). Under normal load, optimistic control is strictly cheaper than pessimistic — no lock is ever held.

Under heavy contention it inverts. When c writers pile onto one row, only one succeeds per round, so c - 1 retry, then c - 2, and so on. The total attempts are c + (c-1) + ... + 1 = c(c+1)/2, which grows with the square of the crowd.

attempts to seat 10 concurrent bookings on one row
  10 x 11 / 2                            =  55
wasted attempts per successful booking
  55 / 10                                =  5.5
attempts to seat 50
  50 x 51 / 2                            =  1,275
wasted per success
  1,275 / 50                             =  25.5

Five times the crowd costs roughly five times as much wasted work per booking — 5.5 wasted attempts each at 10 writers, 25.5 each at 50.

Pessimistic and optimistic share the same ceiling of 1/T. They differ in what happens above it. Pessimistic makes callers queue, so latency rises while throughput holds steady. Optimistic burns wasted work in proportion to the square of the crowd, so throughput falls as load rises — a feedback loop where the failures cause more failures. That is the reason a flash sale is the one place in this design to switch to locking.

Fix 3 — the constraint, plus a conditional update

The third fix removes the read entirely. The availability check becomes part of the UPDATE statement’s WHERE clause, so there is no gap between deciding and writing for anything to slip into.

Two statements follow: the single-night form, then the same idea over a date range. The line to look at in both is AND total_reserved < total_inventory — that is the availability check, living inside the write.

-- schema: CHECK (total_reserved <= total_inventory)
UPDATE room_inventory
   SET total_reserved = total_reserved + 1
 WHERE hotel_id = $1 AND room_type_id = $2 AND date = $3
   AND total_reserved < total_inventory;         -- the check IS the write
-- rowcount 0 means sold out. There is no interleaving that makes this wrong.

-- The multi-night form is the same statement over a range, and the rowcount
-- is still the decision. No lock is held between a read and a write, because
-- there is no read.
UPDATE room_inventory
   SET total_reserved = total_reserved + 1
 WHERE hotel_id = $1 AND room_type_id = $2
   AND date >= $3 AND date < $4                  -- half-open: section 3c
   AND total_reserved < total_inventory;
-- rowcount < nights means SOME night was sold out; ROLLBACK releases the rest.

The price is zero. No extra network round trip, no lock held beyond the one the UPDATE takes anyway, no version column to read first, and no retry loop.

The condition is evaluated by the same statement that performs the write, while that statement holds the row lock. It is the same move as writing count = count + 1 instead of reading the count and assigning it, described in the lost-update section of sql 03.

The CHECK constraint is the backstop to those two. It cannot prevent anything the conditional UPDATE already prevents. What it prevents is the next code path — a bulk importer, an admin tool, a data migration — written by somebody who does not know the rule. It turns a silent overbooking into a loud database error, SQLSTATE 23514 (the standard code for “a check constraint was violated”), which the API turns into a 409 response.

The four guards, side by side

The last column is the one that decides the argument, because only one mechanism has a Yes in it.

Ship all four. The answer to “which one” is that they are not alternatives — three of them enforce the rule and the fourth is the rule written down where the database can see it.

• Default to the conditional UPDATE, including for multi-night stays, where the ranged form plus a rowcount check is the entire mechanism.
• Escalate to FOR UPDATE when the decision has to read tables the UPDATE cannot mention.
• Keep the CHECK forever, because it costs nothing and it is the only one of the four that protects you from code you have not written yet.

9. Deep dive 3: idempotency, and the payment that must not run twice

There is a second way to sell a room twice — not two users racing, but one user’s request arriving twice. Four rules make a retry harmless, and the full booking write further down applies every one of them.

The client sends POST /v1/reservations, the response is lost to a dropped mobile connection, and the client retries.

From the server’s side that retry is indistinguishable from a second booking, and getting it wrong charges a card twice.

You cannot fix this by making delivery reliable. Exactly-once delivery does not exist: no protocol can guarantee a message is delivered once and only once over an unreliable network.

What exists is at-least-once delivery — the sender keeps retrying until it hears back — plus a deduplication key, a string that lets the receiver recognise “I have already done this one”.

Here that key must be chosen by the client, because only the client knows that two requests are one intent rather than a customer genuinely booking two rooms.

9a. The idempotency rules, in one place

These are the four rules this repository uses everywhere a retry must not repeat a side effect. Chapter 27 and chapter 28 cite them rather than inventing their own, because three chapters with three different idempotency designs is how a company ends up with three different double-charge bugs.

R1 is about how the key is built, R2 about how many keys one intent needs, R3 about how the key is claimed, and R4 about where the rules apply — and each rule carries the specific bug it prevents.

Three phrases in that table are doing heavy lifting.

A canonical hash of the request content. Sort the request’s fields into a fixed order, drop anything that differs between attempts, serialize the result the same way every time, and run it through a hash function such as SHA-256 to get a short fixed-length fingerprint. Two attempts at the same intent then produce the same fingerprint, and two genuinely different requests almost certainly do not.

To namespace a key is simply to append a label to it, so that key:auth and key:refund are different keys derived from one client-chosen string.

An atomic claim is the heart of R3: a single database statement that both checks whether the key is already taken and takes it if not, with no gap in between. INSERT ... ON CONFLICT DO NOTHING is PostgreSQL’s version — it inserts the row, or quietly does nothing if a row with that key already exists, and reports which of the two happened through the rowcount.

The alternative, a SELECT to check followed by an INSERT to claim, is exactly the race of section 7 moved one table over, and its window is a whole network round trip wide.

The code below is the demonstration, in four parts:

1. idempotency_key() and op_key() — R1 and R2, with assertions that a retry hashes to the same key and a changed amount does not;
2. Claims — R3’s atomic claim, with dict.setdefault standing in for INSERT ... ON CONFLICT DO NOTHING;
3. eight threads released together against Claims, asserting that exactly one charges the card;
4. RacyClaims — the same thing written as check-then-act, where the assertion is that all eight charge.

Part 4 is the one to read closely. It is the negative control, and it is the more persuasive of the two results.

import hashlib, json, threading, time

VOLATILE = {"attempt", "retry_count", "client_ts", "requested_at", "trace_id"}

def idempotency_key(request: dict) -> str:
    """R1. A canonical hash of WHAT is being asked for. What is excluded is as
    load-bearing as what is included: anything that changes between attempts
    turns a retry into a new intent."""
    canonical = {k: v for k, v in sorted(request.items()) if k not in VOLATILE}
    return hashlib.sha256(
        json.dumps(canonical, sort_keys=True, separators=(",", ":")).encode()
    ).hexdigest()

def op_key(key: str, operation: str) -> str:
    """R2. One row per (intent, operation)."""
    return key + ":" + operation

body = {"hotel_id": 812, "room_type_id": 3, "start_date": "2026-11-14",
        "end_date": "2026-11-17", "guest_id": 99120, "amount_cents": 84000}
retry = dict(body, attempt=2, client_ts="2026-11-01T10:22:09Z")

assert idempotency_key(body) == idempotency_key(retry)      # a retry is one intent
assert idempotency_key(dict(body, amount_cents=99000)) != idempotency_key(body)
k = idempotency_key(body)
assert op_key(k, "auth") != op_key(k, "refund")             # two effects, two rows


class Claims:
    """R3, as the only method on the store: the claim is ONE statement.
    `dict.setdefault` stands in for `INSERT ... ON CONFLICT DO NOTHING` -- it
    returns whatever row is in the table after the call, so the winner is known
    by identity and there is no gap between the check and the act."""

    def __init__(self, latency=0.002):
        self.rows, self.latency = {}, latency

    def claim(self, key, request_hash):
        row = {"hash": request_hash, "state": "in_progress", "response": None}
        time.sleep(self.latency)                     # the statement's round trip
        current = self.rows.setdefault(key, row)     # ON CONFLICT DO NOTHING
        return current is row, current


claims, charges, guard = Claims(), [], threading.Lock()
gate = threading.Barrier(8)

def one_attempt():
    gate.wait()                                      # all 8 retries land together
    won, _ = claims.claim(op_key(k, "auth"), k)
    if won:
        with guard:
            charges.append(1)                        # the card is charged HERE

threads = [threading.Thread(target=one_attempt) for _ in range(8)]
for t in threads:
    t.start()
for t in threads:
    t.join()

assert sum(charges) == 1, f"{sum(charges)} of 8 concurrent retries charged the card"


class RacyClaims(Claims):
    """The negative control, and the more persuasive of the two assertions: a
    `get` to look, then an assignment to claim, with the round trip in the gap.
    That is exactly what `SELECT` followed by `INSERT` is."""

    def claim(self, key, request_hash):
        row = {"hash": request_hash, "state": "in_progress", "response": None}
        time.sleep(self.latency)                     # the SELECT round trip
        current = self.rows.get(key)                 # look ...
        if current is None:
            time.sleep(self.latency)                 # the INSERT round trip
            self.rows[key] = row                     # ... then claim
            return True, row
        return False, current


racy, racy_charges = RacyClaims(), []
racy_gate = threading.Barrier(8)

def one_racy_attempt():
    racy_gate.wait()
    won, _ = racy.claim(op_key(k, "auth"), k)
    if won:
        with guard:
            racy_charges.append(1)

racy_threads = [threading.Thread(target=one_racy_attempt) for _ in range(8)]
for t in racy_threads:
    t.start()
for t in racy_threads:
    t.join()

assert sum(racy_charges) == 8, (
    f"check-then-act charged {sum(racy_charges)} of 8, not all eight")

Those two assertions are the entire section, and the second is the one that convinces. One of eight charging the card shows the design works; eight of eight charging the card shows what the design is for. Written the other way — a get to look, then an assignment to claim, with a network round trip in the gap, which is precisely what a SELECT followed by an INSERT is — every thread finds no row, every thread decides it is first, and every thread charges. The rule is not “look before you write”; it is “let the write be the look”.

9b. The booking write, end to end

Here is the whole booking as one function, so the ordering of the two transactions and the payment call between them is visible in one place.

Read reserve() as three phases:

1. Step 1, one transaction. Claim the idempotency key, take the inventory for every night, insert the reservation as pending, and record that a payment is about to be attempted.
2. Step 2, no transaction at all. Call the payment provider. This is the slow part, and it is deliberately outside the database.
3. Step 3, a second transaction. Record the outcome: confirm the reservation, or release every night.

The slow payment call sits between the two transactions, not inside either one.

flowchart LR
    T1["Transaction 1<br/>claim idempotency key<br/>take inventory (conditional UPDATE)<br/>insert pending reservation<br/>record saga step 2"] --> P["Authorize payment<br/>outside any transaction<br/>slow, ~3 s"]
    P --> T2["Transaction 2<br/>confirm, or release every night<br/>store response body"]

The helper above it, release_nights, is the undo path used when payment is declined.

import hashlib, json


class SoldOut(Exception):
    """Raised inside the transaction, so the rollback is the release."""


def release_nights(db, res_id, body) -> str:
    """C1 of the saga, and the decline path of step 3 below. The orchestrator
    retries it after a timeout with no way to know whether the first attempt
    landed, so it MUST be safe to run twice (R4). The guard is the conditional
    status transition -- the decrement itself is not idempotent and cannot be
    made so, because `total_reserved - 1` has no idea it already ran."""
    claimed = db.execute(
        "UPDATE reservations SET status='cancelled' "
        " WHERE reservation_id=%s AND status='pending'", (res_id,)).rowcount
    if claimed == 0:
        return "already released"            # nothing left to give back
    db.execute("UPDATE room_inventory SET total_reserved = total_reserved - 1 "
               " WHERE hotel_id=%s AND room_type_id=%s "
               "   AND date >= %s AND date < %s AND total_reserved > 0",
               (body["hotel_id"], body["room_type_id"],
                body["start_date"], body["end_date"]))
    return "released"

def reserve(db, gateway, key: str, body: dict):
    """One user intent -> at most one reservation and at most one charge.
    `key` is R1's canonical hash of `body`, sent by the client."""
    h = hashlib.sha256(json.dumps(body, sort_keys=True).encode()).hexdigest()

    with db.transaction():                       # step 1: the ONLY DB transaction
        claimed = db.execute(
            "INSERT INTO idempotency (key, request_hash, state) "
            "VALUES (%s, %s, 'in_progress') ON CONFLICT (key) DO NOTHING",
            (key, h)).rowcount == 1
        if not claimed:
            prior = db.execute(
                "SELECT request_hash, state, response_status, response_body "
                "FROM idempotency WHERE key = %s", (key,)).one()
            if prior.request_hash != h:
                return 422, {"error": "idempotency_key_reused_with_different_body"}
            if prior.state == "in_progress":
                return 409, {"error": "in_flight", "retry_after": 2}
            return prior.response_status, prior.response_body   # byte-identical replay

        # One ranged conditional UPDATE covers every night of the stay, and the
        # rowcount is the decision. This is why a multi-night stay does not
        # need FOR UPDATE -- see section 8, fix 1.
        wanted = len(nights(body["start_date"], body["end_date"]))   # section 3c
        rows = db.execute(
            "UPDATE room_inventory SET total_reserved = total_reserved + 1 "
            " WHERE hotel_id=%s AND room_type_id=%s AND date >= %s AND date < %s "
            "   AND total_reserved < total_inventory",
            (body["hotel_id"], body["room_type_id"],
             body["start_date"], body["end_date"])).rowcount
        if rows != wanted:                       # some night was sold out
            raise SoldOut                        # rollback releases every night
        res_id = db.execute(
            "INSERT INTO reservations (status, idempotency_key, ...) "
            "VALUES ('pending', %s, ...) RETURNING reservation_id", (key,)).one()
        # The saga step is recorded BEFORE the step runs, in the transaction
        # that took the inventory. A crash between step 2 and step 3 is the
        # window where the money has moved and nothing says so; this row is
        # what the orchestrator of section 11 resumes from.
        db.execute(
            "INSERT INTO saga_log (saga_id, reservation_id, step, state, "
            "next_attempt_at) VALUES (%s, %s, 2, 'pending', now())",
            (key, res_id))

    # step 2: OUTSIDE the transaction. The gateway gets its own derived key (R2).
    auth = gateway.authorize(amount=body["amount_cents"],
                             idempotency_key=key + ":auth")

    with db.transaction():                       # step 3: settle the outcome
        db.execute("UPDATE saga_log SET state=%s WHERE saga_id=%s AND step=2",
                   ("done" if auth.approved else "declined", key))
        if auth.approved:
            db.execute("UPDATE reservations SET status='confirmed' "
                       " WHERE reservation_id=%s AND status='pending'", (res_id,))
            out = (201, {"reservation_id": res_id, "status": "confirmed"})
        else:
            release_nights(db, res_id, body)     # idempotent; safe to retry
            out = (402, {"error": "payment_declined"})
        db.execute("UPDATE idempotency SET state='done', response_status=%s, "
                   "response_body=%s WHERE key=%s", (out[0], out[1], key))
    return out

Untested code drifts from its callers. reserve is the centre of this chapter, and because it was never executed, it came to be written against datetime.date while section 4’s API sends ISO strings. The test harness below exercises it.

The listing below is the smallest fake database and gateway that make reserve callable. FakeDB.execute pattern-matches on the first words of each SQL statement and keeps four of section 5’s tables in dictionaries; its transaction() context manager really does roll back, by restoring a snapshot taken on entry.

Skip past the plumbing to the five numbered calls at the bottom. They walk every branch of reserve:

1. the happy path — three nights taken, one charge, one confirmed reservation;
2. the retry — the same key again, no second charge, a byte-identical replay;
3. the decline — payment refused, all three nights given back;
4. the sold-out night — rowcount 2 against a wanted of 3, so the rollback releases the two that succeeded and the card is never touched;
5. the zero-night stay — caught by section 3c’s range guard before it can reach the gateway.

from contextlib import contextmanager
from types import SimpleNamespace


class Res:
    """What a driver hands back: a rowcount, and `.one()` for a returned row."""

    def __init__(self, rowcount=0, row=None):
        self.rowcount, self.row = rowcount, row

    def one(self):
        return self.row


class FakeDB:
    """Four of section 5's tables, in dicts, with a rollback that really rolls
    back. Enough to RUN `reserve` rather than only to read it."""

    def __init__(self, stay, remaining=1):
        self.idem, self.inv = {}, {d: remaining for d in nights(*stay)}
        self.res, self.saga, self.seq = {}, [], 0

    @contextmanager
    def transaction(self):
        snap = (dict(self.idem), dict(self.inv), dict(self.res), list(self.saga))
        try:
            yield self
        except Exception:                            # ROLLBACK: every night back
            self.idem, self.inv, self.res, self.saga = snap
            raise

    def execute(self, sql, params=()):
        s = " ".join(sql.split())
        if s.startswith("INSERT INTO idempotency"):
            if params[0] in self.idem:
                return Res(0)                        # ON CONFLICT DO NOTHING
            self.idem[params[0]] = {"request_hash": params[1],
                                    "state": "in_progress",
                                    "response_status": None, "response_body": None}
            return Res(1)
        if s.startswith("SELECT request_hash"):
            return Res(1, SimpleNamespace(**self.idem[params[0]]))
        if s.startswith("UPDATE room_inventory SET total_reserved = total_reserved + 1"):
            taken = [d for d in nights(params[2], params[3]) if self.inv.get(d, 0) > 0]
            for d in taken:
                self.inv[d] -= 1
            return Res(len(taken))                   # the rowcount IS the decision
        if s.startswith("UPDATE room_inventory SET total_reserved = total_reserved - 1"):
            for d in nights(params[2], params[3]):
                self.inv[d] += 1
            return Res(len(self.inv))
        if s.startswith("INSERT INTO reservations"):
            self.seq += 1
            rid = f"res_{self.seq}"
            self.res[rid] = "pending"
            return Res(1, rid)
        if s.startswith("INSERT INTO saga_log"):
            self.saga.append({"saga_id": params[0], "reservation_id": params[1],
                              "step": 2, "state": "pending"})
            return Res(1)
        if s.startswith("UPDATE saga_log"):
            for row in self.saga:
                row["state"] = params[0]
            return Res(len(self.saga))
        if s.startswith(("UPDATE reservations SET status='confirmed'",
                         "UPDATE reservations SET status='cancelled'")):
            hit = self.res.get(params[0]) == "pending"
            if hit:
                self.res[params[0]] = "confirmed" if "confirmed" in s else "cancelled"
            return Res(1 if hit else 0)
        if s.startswith("UPDATE idempotency SET state='done'"):
            self.idem[params[2]].update(state="done", response_status=params[0],
                                        response_body=params[1])
            return Res(1)
        raise AssertionError(f"unhandled statement: {s[:60]}")


class FakeGateway:
    def __init__(self, approved=True):
        self.approved, self.calls = approved, []

    def authorize(self, amount, idempotency_key):
        self.calls.append(idempotency_key)
        return SimpleNamespace(approved=self.approved)


intent = {"hotel_id": 812, "room_type_id": 3, "start_date": "2026-11-14",
          "end_date": "2026-11-17", "guest_id": 99120, "amount_cents": 84000}
span = (intent["start_date"], intent["end_date"])

# 1. the happy path. Three nights taken, one charge, one confirmed reservation,
#    and a saga_log row that existed before the gateway was ever called.
db, gw = FakeDB(span, remaining=1), FakeGateway(approved=True)
assert reserve(db, gw, "k1", intent) == (
    201, {"reservation_id": "res_1", "status": "confirmed"})
assert list(db.inv.values()) == [0, 0, 0]
assert gw.calls == ["k1:auth"]                  # R2: the derived key, not `key`
assert db.saga[0]["step"] == 2 and db.saga[0]["state"] == "done"

# 2. the retry of that same intent. No second charge; a byte-identical replay.
assert reserve(db, gw, "k1", intent) == (
    201, {"reservation_id": "res_1", "status": "confirmed"})
assert gw.calls == ["k1:auth"]                  # the gateway was not called again

# 3. payment declined. C1 gives every night back.
db2, gw2 = FakeDB(span, remaining=1), FakeGateway(approved=False)
assert reserve(db2, gw2, "k2", intent) == (402, {"error": "payment_declined"})
assert list(db2.inv.values()) == [1, 1, 1]

# 4. one night short. The rowcount is 2 against a `wanted` of 3, so the
#    rollback releases the nights that DID succeed and the card is untouched.
db3, gw3 = FakeDB(span, remaining=1), FakeGateway(approved=True)
db3.inv[date(2026, 11, 15)] = 0
try:
    reserve(db3, gw3, "k3", intent)
    raise AssertionError("a sold-out night must not confirm")
except SoldOut:
    pass
assert list(db3.inv.values()) == [1, 0, 1]
assert gw3.calls == []

# 5. the zero-night stay. `wanted` would be 0 and `0 != 0` is False, so before
#    section 3c's range guard this reached the gateway and charged the card for
#    a stay that took no inventory at all.
db4, gw4 = FakeDB(span, remaining=1), FakeGateway(approved=True)
try:
    reserve(db4, gw4, "k4", dict(intent, end_date=intent["start_date"]))
    raise AssertionError("a zero-night stay must not be bookable")
except ValueError:
    pass
assert gw4.calls == []
assert db4.idem == {}                           # the rollback took the claim too

Seven design points, and each of them is a question an interviewer asks.

The idempotency claim and the inventory decrement are in the same transaction. If they were in two, a crash in between is exactly the window that produces a second reservation for one intent. The claim is an INSERT ... ON CONFLICT DO NOTHING, which is a single atomic test-and-set — a check and a claim fused into one statement — and not a SELECT followed by an INSERT, which is the same race this chapter is about, one table over.

The gateway call is outside every transaction. Here is what a 3-second network call inside the booking transaction would cost, using the same 1/T ceiling as section 8.

The block adds the gateway’s 3,000 ms to the 5 ms transaction, recomputes the ceiling, and then checks that new ceiling against a bigger property’s flash-sale demand. Watch the last two lines: they are the ones that turn “slower” into “broken”.

in-transaction time with a 3 s gateway call, in ms
  5 + 3,000                              =  3,005
single-row ceiling, per second
  1,000 / 3,005                          =  0.333
collapse factor against the 200/s ceiling
  200 / 0.333                            =  601
the flash-sale rate for a 500-room property
  500 / 3,600                            =  0.139
remaining headroom
  0.333 / 0.139                          =  2.40

A 601x collapse, and a 500-room flash sale is then inside 2.4x of the ceiling — one gateway slowdown away from queueing every booking in the hotel behind a single row lock. This is the single most common structural mistake in the problem.

The saga_log row for step 2 is written inside step 1’s transaction, before step 2 runs. That is the one ordering that makes “payment succeeded, the confirm step crashed” recoverable: the row saying a payment is about to be attempted for this reservation is durable before the attempt, so a process that dies between step 2 and step 3 leaves evidence rather than a silent hole. What resumes from that row is the orchestrator of section 11, whose retry loop and backoff are ch 20’s and are not written out here; this function is the single-service half, and the log row is its handshake with the other half.

The gateway gets key + ":auth", not key. Two independent systems deduplicating on the same string is a collision waiting for the day somebody routes a refund through the same key. Derive one key per side effect from the single key the client chose, as rule R2 says.

Authorize, do not capture. These are the two halves of a card payment: an authorization reserves the money on the customer’s card without moving it, and a capture actually takes it. An authorization that turns out to be unwanted is voided and leaves nothing on the guest’s statement; a capture that turns out to be unwanted is a refund, which is visible on the statement, slow to settle, and generates a call to support. So authorize at booking and capture later, at the cancellation deadline or at check-in.

A request that finds state = 'in_progress' gets a 409, not a second attempt. The tempting alternative — wait for the first attempt to finish and return its answer — holds a request open across a slow gateway call, so a client that retries aggressively leaks server threads until the service stops answering anyone.

Something has to move that in_progress row, or the 409 becomes permanent.

Trace the failure. The process dies after step 1 commits. Nothing in the code above ever runs again for that key. The reservation sits pending until the sweeper releases it — but the idempotency row stays in_progress for the whole 24-hour TTL, so every retry the customer makes gets 409 in_flight, retry_after: 2. The customer is refused for a room the sweeper has already put back on sale.

So the sweeper owns both rows, not one. An idempotency row still in_progress when its reservation’s hold expires is moved to state='abandoned' in the same transaction that releases the hold, and abandoned is treated as absent, so the next retry re-runs the intent instead of being turned away.

The window that matters is the pending-hold TTL, not the idempotency TTL, and pairing them in one transaction is what keeps the two from disagreeing.

The release is guarded by a status change, not by the decrement.

Rule R4 says a compensation is a data-changing call like any other and must be safe to run twice. But total_reserved = total_reserved - 1 can never be made safe to run twice on its own — subtraction has no way to know it already happened.

So the status change carries the safety. WHERE status='pending' succeeds with rowcount 1 exactly once, ever, and the decrement is allowed to run only when it does.

Notice what a blind decrement run twice actually does. It does not merely release the room twice; it invents a room-night the hotel does not have. And the CHECK constraint cannot catch that, because total_reserved is moving down, and down is the direction the constraint permits.

The code below is the smallest thing that demonstrates it: two tiny tables, one compensation, run twice serially and then four times at once.

The concurrent run is the one that matters. Written as an if to look and an assignment to claim, claim_release is R3’s race one table over — but with nothing between the two statements, CPython’s global interpreter lock makes them effectively atomic, so the serial test passes and the design is never exercised. The round trip is modelled explicitly here for the same reason it is modelled in the section 9a listing: a claim is a statement sent to a database, and the gap is the whole bug.

import threading, time


class Rows:
    """Just enough of the two tables to run the compensation twice."""

    def __init__(self, stay, reserved):
        self.reserved = {d: reserved for d in stay}
        self.status = {"res_1": "pending"}
        self._lock = threading.Lock()        # stands in for the row lock

    def claim_release(self, res_id):
        """UPDATE reservations SET status='cancelled'
             WHERE reservation_id=%s AND status='pending'
           ONE statement: the test and the set are inside the row lock. Written as
           an if-then-assign with a round trip between them, this is R3's race and
           every concurrent retry decrements."""
        with self._lock:
            time.sleep(0.001)                # the statement's round trip
            if self.status[res_id] != "pending":
                return 0
            self.status[res_id] = "cancelled"
            return 1

    def give_back(self, stay):
        """UPDATE room_inventory SET total_reserved = total_reserved - 1
            WHERE ... AND date >= %s AND date < %s AND total_reserved > 0"""
        for d in stay:
            assert self.reserved[d] > 0
            self.reserved[d] -= 1


def release(db, res_id, stay):
    if db.claim_release(res_id) == 0:
        return "already released"
    db.give_back(stay)
    return "released"


stay = ["2026-11-14", "2026-11-15", "2026-11-16"]      # half-open, section 3c
db = Rows(stay, reserved=5)

assert release(db, "res_1", stay) == "released"
assert db.reserved[stay[0]] == 4

release(db, "res_1", stay)              # the orchestrator retries the compensation
assert db.reserved[stay[0]] == 4        # a blind decrement lands on 3: a room-night
assert sum(db.reserved.values()) == 12  # that never existed is now for sale

# Four retries of ONE compensation, landing together -- which is what a
# durable log with at-least-once delivery produces after a timeout. Exactly
# one may win the claim. Take the lock away and put a round trip between the
# `if` and the assignment, and all four win, all four decrement: 12 room-nights
# come back instead of 3, and the counter lands on 3 of an honest 12.
concurrent = Rows(stay, reserved=5)
gate = threading.Barrier(4)

def retry_the_compensation():
    gate.wait()
    release(concurrent, "res_1", stay)

retries = [threading.Thread(target=retry_the_compensation) for _ in range(4)]
for r in retries:
    r.start()
for r in retries:
    r.join()

assert concurrent.status["res_1"] == "cancelled"
assert sum(concurrent.reserved.values()) == 12, (
    f"{15 - sum(concurrent.reserved.values())} room-nights released, not 3")

TTL, derived

The last question the idempotency store raises is how long to keep its records. TTL stands for time to live: how long a stored record survives before it is deleted automatically.

The instinct is to pick a TTL from storage cost, so start by showing that storage cost is not a real input. The block below counts records per day, builds a per-record byte budget column by column, and multiplies.

assume  3 payment attempts per completed booking (declines, 3-D Secure, refresh)

idempotency records per day
  233,333 x 3                            =  699,999
record bytes: key 16 + request_hash 32 + state 1 + stored response 512
              + created_at 8 + overhead 40
  16 + 32 + 1 + 512 + 8 + 40             =  609
24 hours of records, in bytes
  699,999 x 609                          =  426,299,391
7 days of records, in bytes
  426,299,391 x 7                        =  2,984,095,737

426 MB for a 24-hour window. Storage is not the input to this decision, and saying so is the point — a candidate who proposes a 1-hour TTL “to save space” has optimised 400 MB and reopened the double-charge window.

The TTL is a choice about meaning: it is how long two requests still count as the same intent. Bound it from both sides.

From below, by the longest legitimate retry. A client backoff of 1, 2, 4, 8 seconds totals 15 seconds. A human refreshing the page is minutes. A mobile app resuming after a flight is hours.

From above, by the point where replaying a stored response would be wrong — the user has since cancelled, and a resurrected 201 would confuse them.

24 hours sits comfortably between those, which is why every payment API converges on it.

Keep the response body, not just the key. A retry must get the same reservation id, and a bare “duplicate” tells the client nothing it can show a user.

10. Deep dive 4: cache invalidation, and the direction that matters

A cache can be wrong in two directions. One of them is roughly 3,600 times more expensive than the other — and neither can break the booking invariant.

At a 400:1 ratio of reads to writes, putting a cache in front of availability is obviously right (cache economics). The interesting question is what happens when the cached number is out of date, and the two ways of being out of date are not symmetric.

• Stale-unavailable — the cache still says sold out after a cancellation freed a room. A guest who would have booked does not see the room.
• Stale-available — the cache still shows rooms after the last one sold. A guest is led all the way to the payment page and then refused.

The block below prices both, in the same units, so they can be compared. Each half follows the same three steps: how many times a day this kind of staleness starts, how long each episode lasts, and how much damage accumulates in that window. The final line divides one by the other.

assume  20% of bookings cancel, 5% of bookings take a row's last unit, 60 s TTL

cancellations per day
  233,333 x 0.20                         =  46,667
sell-outs per day
  233,333 x 0.05                         =  11,667
stale-UNAVAILABLE row-seconds per day
  46,667 x 60                            =  2,800,020
the same, as room-days
  2,800,020 / 86,400                     =  32.4
as a fraction of the 700,000 room-nights sold per day
  32.4 / 700,000                         =  0.0000463
stale-AVAILABLE row-seconds per day
  11,667 x 60                            =  700,020
booking attempts landing in them, at the hottest-row rate of 0.0556/s
  700,020 x 0.0556                       =  38,921
as a fraction of daily bookings
  38,921 / 233,333                       =  0.167
harm ratio
  0.167 / 0.0000463                      =  3,607

The stale-available figure is an upper bound — it assumes every row that just sold out is receiving flash-sale traffic — and the point survives being loose by an order of magnitude either way.

A stale “unavailable” hides 0.005% of inventory for a minute.

A stale “available” walks users all the way to the payment page and fails them there, and on the hottest rows that is up to 17% of booking attempts.

The second failure lands late in the funnel — the funnel being the shrinking sequence of search, browse, choose, pay — after the user has typed in card details. That is the most expensive moment in the product to say no.

Note carefully what a stale “available” does not do: it does not overbook. The reservation path re-checks against the database with the conditional UPDATE of section 8, so the cache may be wrong in both directions and the invariant is untouched.

The cache is a hint about conversion, never a participant in correctness. That separation is exactly what lets you cache aggressively without having to argue about consistency between two stores.

Four consequences follow.

• Invalidate on write; do not expire on a timer. Invalidating means deleting the cached entry as part of the write that made it wrong, so the next reader is forced back to the database. At 8.10 writes per second at peak, and one to three cached rows touched per booking, a write-through invalidate costs at most about 24 cache deletions per second — nothing. There is no budget argument for a short expiry here. Keep a TTL of minutes purely as a backstop for the case where an invalidation was lost, because its job is to bound a bug, not to bound staleness.
• Bias the cached value downward. When a row is within one room of sold out, do not cache it at all; serve it from a read replica instead. That converts the expensive direction of staleness into the cheap one for precisely the rows where it matters.
• Cache the availability of a row, not of a whole search result. A cached search result keyed on (city, date range, guests) has enormous cardinality — the number of distinct keys that can exist, here every city times every pair of dates times every party size — and one booking would invalidate thousands of those entries. Keyed on (hotel_id, room_type_id, date), a booking invalidates one to three entries.
• The last remaining room is a hot key, meaning a single cache key receiving far more traffic than any other, and no scheme for spreading keys across servers helps when the traffic concentrates on one (ch 05). Fortunately the write rate on it is 0.0556 per second; only the reads concentrate, and those are served from a replicated cache entry.

The ordering of the two operations follows the same rule as any write that touches two stores (sql 03): commit the database first, then delete the cache entry. Deleting first leaves a window in which another request reads the not-yet-committed database, repopulates the cache with the old value, and leaves it wrong until the next write — which on a quiet date may be days away.

11. Deep dive 5: when the booking spans services

One structural problem remains: a booking has to change four systems that share no database.

Inventory, payment, loyalty and messaging are four services with four separate databases. No single transaction can span them, and the two candidate answers price out very differently.

Why not two-phase commit

Two-phase commit (2PC) is the classic protocol for making several databases commit or abort together. A coordinator asks every participant to PREPARE, meaning “get ready and promise you can commit”. Once all of them have promised, it tells them all to commit.

The promise is the expensive part. A prepared participant is holding its locks and is not allowed to decide anything on its own until the coordinator comes back.

The block below prices 2PC twice: first in steady state, where it adds a few milliseconds, and then during a coordinator crash, where the row is frozen for the whole failover. Compare the two answers — the first is a mild cost and the second is a design-killer.

2PC adds two in-datacenter round trips at 0.5 ms (ch 02) plus a participant
fsync of the prepare record at 1 ms
in-transaction time, in ms
  5 + 0.5 + 0.5 + 1                      =  7
single-row ceiling under 2PC, per second
  1,000 / 7                              =  143
coordinator crash with a 30 s failover: row throughput while blocked
  1 / 30                                 =  0.0333
against the hottest-row demand of 0.0556/s
  0.0556 / 0.0333                        =  1.67

The steady-state cost is mild — 200 bookings per second becomes 143, and nobody notices.

The disqualifying cost is the failure mode. A coordinator that crashes after PREPARE leaves every participant holding locks with no authority to release them. During a 30-second failover the hottest row can serve one booking every 30 seconds, against a demand of one every 18 seconds (1 / 0.0556 = 18). It is oversubscribed by 1.67x, and every booking behind it times out.

Two-phase commit does not degrade gently. It converts a partial failure into an indefinite lock hold.

It also cannot include the payment gateway, which is a company that will never enrol as a participant in your transaction. So even a perfectly working 2PC leaves the hardest step outside it.

The saga, with compensations

The alternative is a saga: run the steps as ordinary local transactions, one service at a time, and pair each forward step with a compensation that undoes it after the fact.

There is no rollback across the whole thing, because some steps have already committed and been observed. There is only a deliberate, recorded undo.

In the diagram below, the solid arrows across the top are the five forward steps in order, and the dashed arrows underneath are the compensations. The thing to notice is step 5: it has no dashed arrow, and it is coloured red for the same reason.

flowchart LR
    S1["1 reserve inventory<br/>local txn"] --> S2["2 authorize payment<br/>gateway, keyed"]
    S2 --> S3["3 confirm reservation<br/>local txn"]
    S3 --> S4["4 award loyalty points"]
    S4 --> S5["5 send confirmation<br/>NO compensation"]

    S1 -.->|"C1 release nights"| X1(["inventory restored"])
    S2 -.->|"C2 void the auth"| X2(["nothing on the statement"])
    S3 -.->|"C3 cancel + notify"| X3(["user-visible"])
    S4 -.->|"C4 revoke points"| X4(["balance restored"])

    style S5 fill:#9d0208,color:#fff
    style S2 fill:#bc6c25,color:#fff
    style S1 fill:#1d3557,color:#fff

The five forward steps:

Three rules turn that picture into a design.

Order the steps so the least reversible one is last. Voiding an authorization leaves no trace anywhere. A refund leaves a line on the guest’s statement. A confirmation email, once sent, cannot be unsent.

Sending the confirmation before the charge has settled means the only compensation available is a second email apologising for the first — and that is not a compensation, it is an incident.

Every compensation is safe to run twice, and safe to run when the forward step never happened at all. release_nights(reservation_id) must do nothing if the reservation is already released, because the orchestrator will retry it after a timeout with no way to know whether the first attempt landed. Section 9b has both the implementation and the test proving a second run moves no inventory. The forward steps carry idempotency keys for the same reason, under the same four rules of section 9a.

The pending reservation is a semantic lock — a lock enforced by the meaning of a column value rather than by the database’s locking machinery. It holds the room-nights without holding a database lock, which is exactly what lets the transaction commit in 5 milliseconds while the gateway takes 3 seconds.

That hold is not free, so price it. The block below converts a hold duration into a count of concurrent holds, then into room-nights, then into a fraction of inventory. It does this twice, at 15 minutes and at 60 minutes, and then against a second denominator so you can see how much the choice of denominator changes the answer.

peak booking rate, 233,333 x 3 over the real 86,400
  233,333 x 3 / 86,400                   =  8.1018
holds in flight at a 15-minute TTL
  15 x 60 x 8.1018                       =  7,292
a hold is a RESERVATION, and the average one holds 3 room-nights
  7,292 x 3                              =  21,876
as a fraction of one night's 1,000,000 rooms
  21,876 / 1,000,000                     =  0.0219
holds in flight at a 60-minute TTL
  60 x 60 x 8.1018                       =  29,167
room-nights held
  29,167 x 3                             =  87,501
as a fraction of one night's rooms
  87,501 / 1,000,000                     =  0.0875
against the whole 500-day forward inventory instead
  21,876 / (1,000,000 x 500)             =  0.0000438

Watch the units, because this is where the number is usually got wrong: a pending hold is a reservation, not a room.

Dividing 7,292 reservations by 1,000,000 rooms compares two different things, and it understates the tax by the average stay length — a factor of 3. Multiply by the 3-night average first.

Then choose a denominator and name it. Against one night’s rooms the hold is a real constraint (2.2%). Against the full 500-day forward inventory it rounds to nothing (0.0044%). The near denominator is the honest one, because a hold and the booking it blocks are competing for the same night.

The pending hold is a tax on inventory: 2.2% of a single night’s rooms at 15 minutes, 8.8% at an hour. The 0.0044% figure is the one to quote only if someone asks whether the chain as a whole notices.

Choose the hold’s length from the longest legitimate payment interaction — a 3-D Secure challenge (section 4) takes minutes and not seconds. Then run a sweeper that releases expired holds, because a hold nothing ever releases is inventory permanently deleted by a crash.

The saga log is a durable work queue

Each step writes (saga_id, step, state, next_attempt_at) before it runs and updates the row after. A crash mid-step is therefore resumed rather than lost — and a step may run more than once, which is why every step must be safe to repeat. The retry timing and the queue mechanics come from ch 20 rather than being re-derived here.

The one thing a saga cannot give you is isolation. Between step 1 and step 3 the reservation is visible to everyone in a half-finished state, so every reader has to understand what pending means. That is exactly why status appears in the API contract in section 4 rather than being hidden as an implementation detail.

12. Deliberate overbooking is a constant, not a bug

Hotels sell more rooms than they have, on purpose, because a predictable fraction of guests never arrive. The allowance can be computed — and, more importantly, expressed so that it changes no code and threatens no invariant. A guest who booked and does not show up is a no-show.

Setting up the model

Sell 200 + a rooms against 200 physical ones, where a is the allowance. You have to walk somebody whenever fewer than a guests no-show — if only 5 people fail to arrive and you sold 7 extra rooms, 2 guests have nowhere to sleep.

The number of no-shows is a binomial count: 200 + a independent guests, each of whom fails to arrive with probability 5%. Written X ~ Binomial(200 + a, 0.05).

The count is 200 + a and not 200, because you sold 200 + a rooms, and every room you sold has a guest in it who may not turn up. Taking n = 200 is the standard slip here, and it overstates the walk probability at every allowance.

So the probability of walking someone is P(X <= a - 1), and the allowance you want is the smallest a whose walk probability the business finds acceptable — here, around 10%.

Note that n moves with a. That is why the exact table below is computed row by row rather than read off one fixed distribution.

Three statistical terms the arithmetic uses

• The standard deviation measures how far the actual count typically strays from its average.
• A quantile of the normal distribution is the multiple of the standard deviation you step away from the mean to cut off a chosen probability. 1.28 cuts off the bottom 10%.
• The continuity correction is the half-unit adjustment you apply when approximating a whole-number count with a smooth curve, because “fewer than 7” and “at most 6” meet at 6.5 rather than at 7.

The allowance, computed two ways

First the quick normal approximation. Mean, then standard deviation, then step 1.28 standard deviations below the mean and add the half-unit correction.

assume  5% no-show on a 200-room property

expected no-shows
  200 x 0.05                             =  10
standard deviation of the no-show count
  (200 x 0.05 x 0.95) ^ 0.5              =  3.08
allowance from the normal quantile, WITH the continuity correction
  10 - 1.28 x 3.08 + 0.5                 =  6.55
round up, because the allowance is an integer
                                         =  7

Now check that against the exact binomial probabilities rather than trusting the smooth approximation, because at these counts the half-unit matters more than the shape of the tail does.

Each row below tries one allowance. Note that n changes with a, since selling more rooms means more guests who could fail to arrive. The number on the right is the probability of having to walk at least one guest.

a = 6:  P(walk) = P(X <= 5), X ~ Binomial(206, 0.05)   =  0.052
a = 7:  P(walk) = P(X <= 6), X ~ Binomial(207, 0.05)   =  0.104
a = 8:  P(walk) = P(X <= 7), X ~ Binomial(208, 0.05)   =  0.179

Seven.

The continuity-corrected normal says 6.55. The exact binomial confirms it: 7 lands at 10.4%, within a rounding of the 10% the business chose. An allowance of 6 lands at 5.2% — a policy half as risky as the one anybody asked for, bought with one saleable room a night at every property in the chain.

The allowance is derived, not guessed. Two things are worth noticing about how it could go wrong.

The wrong n hides the answer. At Binomial(200, 0.05) the same three rows read 6.2%, 12.4% and 21.3%. So 7 overshoots 10%, and “round up, because the allowance is an integer” is quietly doing the work — in the risk-increasing direction.

Skipping the continuity correction is a separate error and produces a different wrong answer. 10 - 1.28 x 3.08 = 6.06 solves for a cut point on a smooth curve and then reads a whole number off it. For a count of guests the cut point sits half a unit lower, at a - 0.5.

The way you express the result is total_inventory = 207 for that date — a change to one number in one row, which leaves the CHECK constraint, the conditional UPDATE and the entire concurrency story untouched.

When the interviewer asks whether overbooking is ever acceptable: yes, as a yield-management decision expressed as a number in a column. It is not a licence to have a data race, because a race gives you an overbook you did not choose, on a date you did not model, in an amount you cannot bound.

Yield management is the practice of adjusting what and how much you sell to maximise revenue against forecast demand. The two-column model of section 5 exists precisely so that this is one honest integer and not a lie about how many rooms the hotel has.

13. Bottlenecks and scaling

Every limit derived so far, in one table, so that “what breaks first, and at what number” is visible at a glance.

Read the middle column first. Nothing in it is close to a hardware limit — which is the point. The two rows that describe real work are “Reservation table”, which grows without bound over years, and “Pending holds”, which grows without bound if the sweeper stops.

Replica lag in that last-but-one row is the delay between the primary committing a change and a read replica reflecting it — usually milliseconds, occasionally seconds. That makes the row worth restating as a rule: the booking transaction must never read a replica. Displaying availability from a replica is fine, but a SELECT ... FOR UPDATE or a conditional UPDATE evaluated against data that is a second out of date is the double-booking race of section 7 with a much wider window. Route by intent — is this read part of a decision to sell? — rather than by whether the statement happens to be a SELECT.

14. Failure modes

Every way the system can fail leaves a concrete trace, has a signal that detects it, and — if the design above did its job — already has a guard in place to stop it.

Every row’s last column points back at a mechanism built earlier in the chapter. If you can name the guard column from memory, you can defend the design.

15. Alternatives rejected

Each entry below names a design an interviewer may propose, states what it is good at, says why this chapter does not use it, and names the situation where it would be the right answer.

Redis DECR as the source of truth for inventory. Redis is an in-memory data store, and DECR atomically subtracts one from a counter. Good: atomic, microseconds fast, no lock contention at any rate this system could reach. Rejected because the decrement and the reservation row cannot commit together — a crash between them either sells a room with no booking or books a room it never claimed — and because Redis persistence acknowledges before the fsync window closes, so the counter can lose writes that a confirmed reservation depends on. Correct as a front gate for pure rate-shedding (reject obviously hopeless requests before they reach the database), which is a different job from being the ledger.

Event sourcing the inventory. Event sourcing stores the sequence of things that happened — booked, cancelled, modified — and derives the current state by replaying them, instead of storing the current state directly. Good: a perfect audit trail, a natural fit for cancellations and modifications, and the reservation history is genuinely part of the product. Rejected because enforcing remaining >= 0 requires knowing remaining at the moment of the write, which means replaying the event stream on every booking — so in practice you keep a running counter alongside it, and to make that counter authoritative you serialize writes against it, which is the design already on this page plus more moving parts. Keep the event log as a derived audit stream, not as the place the rule is enforced.

SERIALIZABLE everywhere. Good: you stop having to reason about which anomalies your level permits, and the write-skew case that snapshot isolation misses — two transactions each reading a set of rows and each writing a different row, together breaking a rule neither broke alone — is genuinely handled. Rejected because it demands transactions that can be safely re-run and a booking’s most important step is a payment; because its abort rate grows superlinearly exactly during the flash sale you bought it for; and because a conditional UPDATE already makes the invariant a write-write conflict, which even snapshot isolation catches. Reach for it when an invariant spans rows the transaction does not write and cannot be expressed as a constraint — which is not this problem, because the constraint is expressible.

One remaining column instead of two. Good: one less field, and the conditional UPDATE reads slightly better. Rejected because a deliberate overbook of six rooms then has to be encoded as a lie about how many rooms exist, an out-of-service room becomes indistinguishable from a sale, and reconciliation against the reservation table loses its second anchor. Two columns cost 2 bytes per row — 25 MB across the whole 12.5 M-row table.

Two-phase commit across the services. Good: real all-or-nothing behaviour across four databases, and the reasoning is simple to explain. Rejected on the failure mode priced in section 11 — a coordinator crash holds every participant’s locks indefinitely and oversubscribes the hottest row by 1.67x — and on the fact that the payment gateway will never enrol as a participant, so the hardest step stays outside the protocol regardless. Correct inside one database across several tables, which is exactly where this design already uses it: the idempotency claim, the inventory decrement and the reservation insert commit together.

Per-physical-room inventory. Good: you always know which room a guest has, and a room out of service is a single row. Rejected on the 36 GB table, on the re-assignment churn every date change causes, and above all because it contradicts how hotels operate — assignment is a check-in decision that trades against upgrades, adjoining rooms and housekeeping routes. Correct for products where the unit really is the unit, such as a specific seat or a specific vacation home.

16. Interviewer pushback

These are the seven questions this design attracts, with the answer written the way it should be spoken. The italic line under each one names what the question is actually testing, which is usually not what it appears to ask.

“Two users click Book at the same time. Walk me through what happens in the database.” Testing: whether you can name the interleaving or only the word “race”. Both transactions run SELECT total_inventory - total_reserved and both get 1, because at READ COMMITTED each statement takes its own snapshot and nothing binds the read to the write that follows. Both then write total_reserved = 11 computed in application code, both insert a reservation, and both commit. The row ends at 11 of 11 with twelve reservations against it — the counter is wrong and the room is sold twice. If instead the update is total_reserved = total_reserved + 1 the lost update disappears, because that statement re-reads under a row lock, and you land on 12 of 11: still oversold, but now it violates a constraint you can declare. The fix in either case is to make the check part of the write: UPDATE ... WHERE total_reserved < total_inventory, and treat rowcount 0 as sold out.

“Doesn’t READ COMMITTED prevent that? Or REPEATABLE READ?” Testing: precision about levels, which is where most answers get vague. READ COMMITTED explicitly permits lost update; it is in the standard’s own anomaly table and it is the default in Postgres, MySQL and SQL Server. REPEATABLE READ depends on the engine, and this is the specific place they diverge. PostgreSQL implements it as snapshot isolation, so the second transaction’s update to a row that changed after its snapshot raises 40001 and aborts — correct, at the price of a mandatory retry loop on every transaction. InnoDB does not abort: the plain SELECT reads a snapshot but the UPDATE reads the latest committed row and blocks on the lock, so the application’s stale 11 is written unchallenged. So on Postgres RR happens to save you and on InnoDB it does not, and an answer that says “use repeatable read” without naming the engine is untestable.

“You said you take a lock. Doesn’t that destroy throughput?” Testing: whether “pessimistic locking doesn’t scale” is a belief or a measurement. Let me price it. The transaction is about 5 ms — a lock, an insert, a commit fsync and two application round trips — so one row sustains 200 bookings a second. The busiest row in the system is one date at one 200-room property, and even if every one of those 200 room-nights sells inside a single flash-sale hour that is 0.056 a second. So the hottest row runs at 0.03% of the ceiling, with 3,597x of headroom. Pessimistic locking is free here. It stops being free the moment the transaction gets longer, which is the actual risk: put a 3-second payment call inside it and the ceiling drops from 200 to 0.33 a second, a 601x collapse, and a 500-room flash sale at 0.14 a second is then within 2.4x of saturation.

“Where does the payment call go, then, and what stops a double charge?” Testing: whether idempotency is a design or a word. Outside every database transaction, between two of them. The first transaction claims a client-supplied idempotency key with INSERT ... ON CONFLICT DO NOTHING, decrements inventory, and writes a pending reservation — all three or none, because a crash between the key claim and the decrement is exactly the double-booking window. Then the gateway is called with a derived key, key + ":auth", so my dedup namespace and theirs cannot collide. Then a second transaction confirms or releases and stores the response body against the key, so a retry replays byte-identical output rather than a bare “duplicate”. I authorize rather than capture, because a void leaves nothing on the guest’s statement and a refund does. Twenty-four hour TTL, which is 426 MB a day at three payment attempts per booking — storage is not what decides the TTL, the meaning of “the same intent” is.

“Your cache says a room is available and it isn’t. How bad is that?” Testing: whether you can tell the two staleness directions apart. It never overbooks, because the reservation path re-checks against the database with the conditional update — the cache is a hint about conversion, not a participant in correctness. What it costs is a failure at the worst point in the funnel, after card entry. At a 60-second TTL, sell-outs are 5% of 233,333 bookings a day, so 700,020 row-seconds of false availability, and on hot rows that is up to 39,000 failed attempts a day, 17% of all bookings. The other direction — a cancelled room staying hidden — costs 46,667 cancellations times 60 seconds, which is 32 room-days, 0.005% of the 700,000 room-nights sold. The two harms differ by about 3,600x. So I invalidate on write rather than expire on a timer — at eight writes a second, each touching up to three nights, that is a couple of dozen cache deletes a second, which costs nothing. I keep a long TTL purely as a backstop against a missed invalidation, and I refuse to cache any row within one unit of sold out.

“Reservation, payment and loyalty are separate services. Two-phase commit?” Testing: whether you know what 2PC actually fails at. No. The steady-state cost is tolerable — two extra in-datacenter round trips and a prepare fsync take the transaction from 5 ms to 7 ms, so 200 a second becomes 143. The problem is the coordinator crash: after PREPARE the participants hold locks and have no authority to release them, so through a 30-second failover the hot row can do one booking every 30 seconds against a demand of one every 18, and everything behind it times out. And the payment gateway will never enrol as a participant anyway, so the hardest step is outside the protocol regardless. I use a saga: reserve, authorize, confirm, award points, send mail — with a compensation for each, ordered so the irreversible step is last, and with the pending reservation acting as a semantic lock that holds inventory without holding a database lock. That hold is an inventory tax I price: fifteen minutes at 8.10 bookings a second is 7,292 concurrent holds, and a hold is a reservation rather than a room — times the 3-night average that is 21,876 room-nights, 2.2% of a single night’s inventory.

“Is overbooking ever acceptable?” Testing: whether you conflate a business policy with a data race. Deliberately, yes — it is how the industry works, because guests do not arrive. At a 5% no-show rate the no-show count is Binomial(200 + a, 0.05) — 200 + a, because that is how many rooms I sold and therefore how many guests can fail to arrive; approximating at n = 200 gives mean 10, standard deviation 3.08. I walk someone whenever fewer than a guests no-show, so the allowance is the smallest a with P(X <= a-1) near 10%. The normal quantile with a continuity correction gives 10 - 1.28 x 3.08 + 0.5 = 6.55, so 7 — and the exact binomial confirms it: an allowance of 7 lands at 10.4%, within a rounding of the 10% the business chose, while 6 lands at 5.2%, half the risk anybody asked for. I express it as total_inventory = 207 for that date and change nothing else: the CHECK still holds, the conditional update still holds, the concurrency story is untouched. That is the whole argument for two columns rather than one. What is never acceptable is an overbook that arrives through a lost update, because then the amount is unbounded, the date is unpredictable, and no yield model knows it happened.

“Do you need to shard any of this?” Testing: whether you will over-engineer when the numbers say not to. Not for throughput. Eight writes a second and 3,241 reads a second is one primary and two replicas, and the entire forward inventory is 900 MB, so it is buffer-pool resident and every availability read is a memory hit. Reservations reach 128 GB over five years, which is a monthly partition and an archive job, not a shard. If I did shard — for blast radius, for a per-tenant isolation requirement, or because the chain acquired another chain — the key is hotel_id, because every booking transaction touches rows for exactly one hotel, so every write stays single-shard and the correctness story never acquires a distributed transaction. Choosing the shard key so the invariant stays local is the key decision.

Cheat sheet

One line per idea, in the order the chapter builds them, for revision the morning of an interview. If a line does not immediately unpack into a paragraph you could say out loud, go back to the section it came from.

Related: sql 03 — Database Internals is the isolation, locking and MVCC machinery this chapter spends; 10 — Notification System is why idempotency keys exist at all; 20 — Distributed Message Queue is the durable retry the saga log rides on; 24 — Distributed Email Service is the same correctness question asked where the storage, not the invariant, is the constraint.