Director’s commentary · No Reload

Faster in chunks

The 2005–06 hotel search behind Disk 8: results streamed into the page without a reload, a .NET backend asking the supplier on several threads, and the two puzzles that teach it.

Around 2005 I was the lead developer at a hotel-booking site. There were three of us and no designer, and I was the sysadmin too; I even ran the pay-per-click. Most of the travel web still reloaded the whole page when you pressed Search. Ours didn't. I'd written a JavaScript framework that did much the same job Prototype and jQuery would go on to do (mine never got a name, which the narration makes a joke of), and on top of it our results page asked the server for hotels in the background. The server, a .NET backend, asked the supplier, Hotelbeds, on several threads at once, and the results streamed into the page in chunks as they came back. In my own words, it was something even the big players didn't do. Disk 8 turns the two halves of that into two puzzles.

Ajax before it had the name

The trick itself wasn't new. Internet Explorer had shipped the object that makes background requests back in 1999, and the other browsers had followed with their own. What it didn't have was a name. That arrived in February 2005, when an essay called the technique Ajax, and suddenly everyone was doing the thing a few of us had been quietly getting on with. Prototype appeared that same month, and jQuery was announced in January 2006.

The first puzzle, No Reload, asks you to wire one round trip in the right order, as a ring of pipes: the page, the request, our server, the supplier, the response, and the callback that drops the results into the page. When the order's right, water flows all the way round and the first hotels slide into the page in place. When it's wrong, the water gets as far as the first wrong piece and leaks, and the leak tells you why.

export const CORRECT_ORDER: readonly PieceId[] = ["page", "request", "server", "supplier", "response", "callback"];
// …
/** Why a piece can't sit this early in the loop. Keyed by the piece that arrived too soon. */
export const TOO_EARLY: Record<PieceId, string> = {
  page: "Something's crossed. Follow the water and see where it stops.",
  request: "A request has to come from somewhere. It starts on the page, where the customer presses Search.",
  server: "The server can't answer a question nobody's asked yet.",
  supplier: "The supplier doesn't talk to web pages. Only our server has its number.",
  response: "Nothing can come back before the supplier's had a look.",
  callback: "The callback's got nothing to put on the page until the response turns up.",
};

It's a teaching device more than a brain-teaser. Every wrong answer is a small fact about how the web works: requests start on the page, the supplier never talks to a browser, nothing comes back before somebody has looked.

Why one big request was slow

The second puzzle, Faster in Chunks, is the heart of the chapter, so the model behind it had to be honest. Any round trip to the supplier has a fixed cost (connecting, authenticating and wrapping everything in XML) plus time for each hotel it checks. Ask for everything in one request and the supplier works through every resort one after another and only replies when it has the lot. The first hotel and the last arrive together.

/** Fixed cost of any one round trip to the supplier (connection, auth, XML wrapping). */
export const REQUEST_OVERHEAD_MS = 450;
/** Supplier time per hotel checked. */
export const PER_HOTEL_MS = 110;
/** Received wisdom at the time: about eight seconds and they've gone elsewhere. */
export const PATIENCE_MS = 8000;
// …
export function naiveTiming(chunks: readonly Chunk[]): Timing {
  const total = REQUEST_OVERHEAD_MS + chunks.reduce((s, c) => s + c.workMs, 0);
  return { firstResultMs: total, totalMs: total };
}

With a typical search, that's somewhere between ten and twelve seconds of an hourglass cursor, against a patience meter that empties at eight, which was the received wisdom at the time for how long people would wait for a page. Split the same search into one chunk per resort and send the chunks on parallel threads, and each chunk's hotels land on the page the moment its own response does.

export function simulatePlan(chunks: readonly Chunk[], plan: Plan): RunResult {
  const byId = new Map(chunks.map((c) => [c.id, c]));
  const events: ChunkEvent[] = [];
  const laneTotals = plan.map((queue, lane) => {
    let t = 0;
    for (const id of queue) {
      const c = byId.get(id);
      if (!c) continue;
      events.push({ chunkId: id, lane, startMs: t, endMs: t + c.latencyMs });
      t += c.latencyMs;
    }
    return t;
  });
  events.sort((a, b) => a.endMs - b.endMs || a.lane - b.lane);
  return {
    events,
    laneTotals,
    firstResultMs: events.length ? events[0].endMs : 0,
    totalMs: events.length ? Math.max(...laneTotals) : 0,
  };
}

Scheduling the chunks

In the puzzle you put chunks onto worker lanes yourself, by dragging or by picking a chunk and then a thread, and there are two things to optimise that pull in different directions. One is how long until everything has arrived. The other is how long until anything has, which is what the customer actually feels. The game's own answer, behind the Deal them out button, does both in two passes. First it hands out the biggest chunks first, each to whichever thread will be free soonest, which is the classic way to get a pile of jobs finished early. Then it reorders each thread's queue quickest-first, so every thread puts something on the page as soon as it can.

export function dealOut(chunks: readonly Chunk[], plan: Plan): Plan {
  const byId = new Map(chunks.map((c) => [c.id, c]));
  const next = plan.map((q) => q.slice());
  const load = next.map((q) => q.reduce((s, id) => s + (byId.get(id)?.latencyMs ?? 0), 0));
  const placedBefore = new Set(plan.flat());
  const todo = unassigned(plan, chunks)
    .map((id) => byId.get(id)!)
    .sort((a, b) => b.latencyMs - a.latencyMs || a.id - b.id);
  for (const c of todo) {
    let best = 0;
    for (let i = 1; i < load.length; i++) if (load[i] < load[best]) best = i;
    next[best].push(c.id);
    load[best] += c.latencyMs;
  }
  // Newly dealt chunks go quickest-first, after anything the player already queued.
  return next.map((q) => {
    const kept = q.filter((id) => placedBefore.has(id));
    const dealt = q.filter((id) => !placedBefore.has(id)).sort((a, b) => byId.get(a)!.latencyMs - byId.get(b)!.latencyMs || a - b);
    return [...kept, ...dealt];
  });
}

The numbers make the point on their own. Across a few seeds, the single request takes 10.4 to 11.5 seconds. With three threads dealt out that way, the first hotels appear after about 1.3 seconds and the last after about 5.3. With four, everything is in by under 4 seconds. The before-and-after card at the end of the puzzle shows your own version of those two numbers.

What I'd do differently

The model is kinder than a real supplier. It assumes the supplier doesn't slow down when you hit it with four requests at once, and real ones push back: rate limits, connection pools, the occasional request that just never comes back. An honest fifth lane would make every other lane a little slower, and the puzzle would be about finding the sweet spot rather than simply adding threads.

And the details are placeholders. The eight Mallorcan resorts are stand-ins, and I still need to dig out of my memory how the real backend split its searches, by resort or by batches of hotel codes, and how many threads it ran. The shape of it, chunks on parallel threads streaming into a page that never reloaded, is what I built. The numbers will change when I remember them properly.