Sequential Convoy

The previous lesson treated order as a preference: a priority queue chose which order to take jobs in, letting the fast one go ahead of the slow one. A job’s wait there was a service-level decision, not a correctness problem. For some jobs, though, order is not something that can be chosen. The same shipment’s state events — accepted, transferred, out for delivery, delivered — overwrite each other; if they are processed in reverse order, the shipment appears back in transfer after it has already been delivered.

Sequential convoy is an arrangement that routes jobs carrying an order constraint into a single lane by key, while preserving concurrency across lanes. Queue mechanics, delivery guarantees, and counting order violations by inverted pairs were established in the Caching, Queues and Asynchronous Processing course; delivery guarantees are not discussed here. This lesson’s question is a capacity question: how much concurrency does preserving order give back, and is there a way to escape this constraint.

The Event That Carries an Order Constraint

Not every event belonging to a shipment demands order. The information “arrived at the zone” is a state transition; a “passed through the scanner” record does not overwrite the state, it is only appended to the history. The criterion for the distinction fits in one sentence: if an event erases a field’s previous value, it carries an order constraint.

The model builds this distinction with a state machine. Four steps are ordered, and each event carries a step number. Three arrangements are run on the same event set: the free arrangement, which distributes events with no constraint; the convoy arrangement, which opens a lane per key; and the version-stamp arrangement, which releases events freely and checks the step number in the handler. A fourth column shifts the convoy’s key from shipment to line.

// convoy/event.mjs — a deterministic set of state events and the in-process model of three
// arrangements. A tick is an abstract step; duration is a model parameter, not a measured
// time.
export const STEP = { accepted: 1, transferred: 2, outForDelivery: 3, delivered: 4 };
export const EVENTS = [           // [tracking no, line, state, duration]
  ["TR-4821", "L1", "accepted", 1], ["TR-9007", "L1", "accepted", 3],
  ["TR-4821", "L1", "transferred", 4], ["TR-5533", "L2", "accepted", 1],
  ["TR-4821", "L1", "outForDelivery", 1], ["TR-9007", "L1", "transferred", 1],
  ["TR-2214", "L2", "accepted", 2], ["TR-4821", "L1", "delivered", 1],
  ["TR-5533", "L2", "transferred", 3], ["TR-9007", "L1", "outForDelivery", 1],
  ["TR-7788", "L3", "accepted", 1], ["TR-5533", "L2", "outForDelivery", 1],
  ["TR-2214", "L2", "transferred", 4], ["TR-9007", "L1", "delivered", 1],
  ["TR-5533", "L2", "delivered", 1], ["TR-7788", "L3", "transferred", 2],
  ["TR-2214", "L2", "outForDelivery", 1], ["TR-7788", "L3", "outForDelivery", 1],
  ["TR-2214", "L2", "delivered", 1], ["TR-7788", "L3", "delivered", 1],
];

// Events are distributed to consumers; when a consumer frees up, it takes the next job.
// laneOf: the lane name by the convoy key, null if there is no order constraint.
function run(events, consumers, laneOf) {
  const free = new Array(consumers).fill(0);   // the tick each consumer will be free at
  const laneFree = new Map();                  // the tick each lane will be free at
  return events.map((e) => {
    const c = free.indexOf(Math.min(...free));
    const lane = laneOf ? laneOf(e) : null;
    const start = Math.max(free[c], lane === null ? 0 : (laneFree.get(lane) ?? 0));
    const finish = start + e.duration;
    free[c] = finish;
    if (lane !== null) laneFree.set(lane, finish);
    return { ...e, consumer: c, finish, lane };
  });
}

// Events applied in finish order: last writer wins, or a version stamp.
function apply(finished, stamped) {
  const state = new Map(), s = { backwardWrite: 0, skipped: 0 };
  for (const e of [...finished].sort((a, b) => a.finish - b.finish || a.order - b.order)) {
    const current = state.get(e.trackingNo) ?? 0;
    if (STEP[e.state] < current) {
      s.backwardWrite += 1;
      if (stamped) { s.skipped += 1; continue; }   // the stamp rejects backward writes
    }
    state.set(e.trackingNo, STEP[e.state]);
  }
  const wrong = [...state.entries()].filter(([, a]) => a !== STEP.delivered).map(([n]) => n);
  return { ...s, wrongFinalState: wrong.length, wrong, tick: Math.max(...finished.map((e) => e.finish)) };
}

export function arrangement(name, consumers) {
  const events = EVENTS.map(([trackingNo, line, state, duration], order) => ({ trackingNo, line, state, duration, order }));
  const LANE = { free: null, convoy: (e) => e.trackingNo, "convoy-line": (e) => e.line,
    "version-stamp": null };
  const finished = run(events, consumers, LANE[name]);
  const r = apply(finished, name === "version-stamp");
  const load = new Map();
  for (const e of finished) if (e.lane !== null) load.set(e.lane, (load.get(e.lane) ?? 0) + e.duration);
  return { ...r, lanes: load.size, busiestLane: load.size ? Math.max(...load.values()) : 0,
    workload: EVENTS.reduce((t, e) => t + e[3], 0) };
}

// convoy/measure.mjs — four arrangements on the same event set: order breakage, ticks, and lane load
import { arrangement, EVENTS } from "./event.mjs";

const CONSUMERS = 4;
const FIELD = [["backwardWrite", "backward write"], ["wrongFinalState", "wrong final state"],
  ["skipped", "skipped event"], ["tick", "tick"], ["lanes", "lane"], ["busiestLane", "busiest lane"]];
const D = ["free", "convoy", "convoy-line", "version-stamp"].map((a) => [a, arrangement(a, CONSUMERS)]);

console.log(`${EVENTS.length} state events, ${new Set(EVENTS.map((e) => e[0])).size} shipments, ` +
  `${CONSUMERS} consumers, total workload ${D[0][1].workload} ticks`);
console.log();
console.log(`${"measure".padEnd(18)}${D.map(([a]) => a.padStart(15)).join("")}`);
for (const [k, label] of FIELD)
  console.log(`${label.padEnd(18)}${D.map(([, r]) => String(r[k]).padStart(15)).join("")}`);

const [free, convoy, line, stamp] = D.map(([, r]) => r);
console.log(`\nshipments with a wrong final state under free = ${free.wrong.join(", ")}`);
console.log(`convoy / free tick ratio = ${(convoy.tick / free.tick).toFixed(3)}, ` +
  `line convoy / free = ${(line.tick / free.tick).toFixed(3)}`);
console.log(`effective concurrency = workload / ticks: free ${(free.workload / free.tick).toFixed(2)}, ` +
  `convoy ${(convoy.workload / convoy.tick).toFixed(2)}, line convoy ${(line.workload / line.tick).toFixed(2)}`);
console.log(`steps missing from state history under the stamp arrangement = ${stamp.skipped}`);

console.log(`\n${"consumers".padEnd(10)}${["free", "convoy", "convoy-line"].map((a) => a.padStart(12)).join("")}`);
for (const c of [1, 2, 4, 8]) {
  const row = ["free", "convoy", "convoy-line"].map((a) => String(arrangement(a, c).tick).padStart(12));
  console.log(`${String(c).padEnd(10)}${row.join("")}`);
}

20 state events, 5 shipments, 4 consumers, total workload 32 ticks

measure                      free         convoy    convoy-line  version-stamp
backward write                  5              0              0              5
wrong final state               1              0              0              0
skipped event                   0              0              0              5
tick                            8             13             19              8
lane                            0              5              3              0
busiest lane                    0              8             14              0

shipments with a wrong final state under free = TR-4821
convoy / free tick ratio = 1.625, line convoy / free = 2.375
effective concurrency = workload / ticks: free 4.00, convoy 2.46, line convoy 1.68
steps missing from state history under the stamp arrangement = 5

consumers         free      convoy convoy-line
1                   32          32          32
2                   16          17          23
4                    8          13          19
8                    5           9          14

Reading the Numbers

The first two rows separate two numbers that should not be confused. Under the free arrangement, 5 of the 20 events overwrote a step ahead of themselves, but only one shipment ended up in a wrong final state. The difference is that most of the backward writes close themselves: a correct event arriving later erases the wrong value. Only the last backward write applied stays broken. The measurement names it directly: the broken shipment is TR-4821. A mechanism that reports order breakage only by violation count shows damage five times larger than reality; a mechanism that checks only the final state misses that the problem happened five times.

The convoy column zeroes both numbers and collects the cost in one place: tick count rises from 8 to 13, effective concurrency falls from 4.00 to 2.46. The ratio is 1.625 — the order constraint takes back roughly two-fifths of the concurrency. This is the pattern’s direct cost, and it is not unavoidable — it depends on the key.

The fourth column shows a way to escape the constraint. The version-stamped handler releases events freely, and tick count stays at 8, concurrency at 4.00; backward writes are still 5, but because the handler rejects them, wrong final state is 0. The cost shows up in a new row: 5 skipped events. These shipments’ state history is missing five steps — the final state is correct, the path is not. The two arrangements buy the same correctness in different currencies: the convoy pays in throughput, the version stamp pays in history.

Lane Granularity Sets the Ceiling

The difference between the third and fourth columns is only the key. When the convoy key is the tracking number, 5 lanes open and the busiest lane carries 8 ticks of work; when the key is the line, lanes drop to 3 and the busiest lane carries 14 ticks. Tick count rises from 13 to 19, concurrency falls from 2.46 to 1.68. A coarse key puts unrelated shipments in the same lane: shipment TR-2214’s out-for-delivery event waits behind shipment TR-5533’s four-tick transfer event. There is no order relationship between them.

The table below shows why this is a capacity question. As consumer count rises from 1 to 8, the free arrangement falls from 32 ticks to 5. The convoy stalls at 9 ticks, the line convoy at 14 — both at the busiest lane’s load. Lane load is the ceiling on throughput, and adding consumers does not raise that ceiling. The real question when designing a sequential convoy is not consumer count, but what the busiest lane carries.

Back to the Estimate

The model’s 20 events are not a volume figure. What is measured is a ratio, applied to K01’s peak write rate: 97.22 state events per second, a computed value from the Back-of-the-Envelope Estimation lesson. This lesson adds one assumption:

KK1 — share of state events carrying an order constraint: 4/7. Its rationale is written in K01’s V4 line: seven events per shipment were justified as “acceptance, transfer, out for delivery, delivery, and intermediate states”; four are named state transitions, three are intermediate records. This number is not added to K01’s assumption table; its sensitivity is calculated below with 5/7.

// convoy/cost.mjs — applies the model's concurrency cost to K01's peak write rate
import { arrangement } from "./event.mjs";

const PEAK_WRITE = 97.22;          // K01 Back-of-the-Envelope Estimation, calculation class
const C = 4;
const concurrency = (a) => arrangement(a, C).workload / arrangement(a, C).tick;
const cost = { convoy: concurrency("free") / concurrency("convoy"),
  "convoy-line": concurrency("free") / concurrency("convoy-line") };

console.log(`${"KK1".padStart(5)}${"constrained ev/s".padStart(18)}${"unconstrained ev/s".padStart(20)}` +
  `${"convoy x".padStart(11)}${"line convoy x".padStart(15)}`);
for (const KK1 of [4 / 7, 5 / 7]) {          // KK1: share of state events carrying an order constraint
  const constrained = PEAK_WRITE * KK1, unconstrained = PEAK_WRITE - constrained;
  const selective = (name) => KK1 * cost[name] + (1 - KK1);
  console.log(`${KK1.toFixed(3).padStart(5)}${constrained.toFixed(2).padStart(18)}` +
    `${unconstrained.toFixed(2).padStart(20)}${selective("convoy").toFixed(3).padStart(11)}` +
    `${selective("convoy-line").toFixed(3).padStart(15)}`);
}
console.log(`\nif the entire stream is routed through the convoy: convoy x${cost.convoy.toFixed(3)}, ` +
  `line convoy x${cost["convoy-line"].toFixed(3)}`);
console.log(`lane load ceiling (8 consumers): convoy ${arrangement("convoy", 8).tick} ticks, ` +
  `line convoy ${arrangement("convoy-line", 8).tick} ticks, free ${arrangement("free", 8).tick} ticks`);

  KK1  constrained ev/s  unconstrained ev/s   convoy x  line convoy x
0.571             55.55               41.67      1.357          1.786
0.714             69.44               27.78      1.446          1.982

if the entire stream is routed through the convoy: convoy x1.625, line convoy x2.375
lane load ceiling (8 consumers): convoy 9 ticks, line convoy 14 ticks, free 5 ticks

55.55 events/s of the peak write rate carries an order constraint, 41.67 events/s does not. If the entire write stream is routed through the convoy, the consumer count required for the same completion rate rises to 1.625 times. Applying the constraint only to the events that carry it — a selective convoy — brings the multiplier down to 1.357; with the line key it is 1.786 instead of 2.375. If KK1 rises to 5/7, the multipliers climb to 1.446 and 1.982: the selective convoy’s gain tracks the share of events without an order constraint, and shrinks as that share shrinks.

The decision is among three options, all measured on the same event set. The version-stamped handler gives up nothing in throughput but leaves a gap in the state history; because the carrier’s history is used in contract disputes, that gap is not free. The shipment-keyed selective convoy keeps the history complete and pays a 1.357 multiplier. The line-keyed convoy adds no extra correctness — it only reduces the lane count — and raises the multiplier to 1.786: a coarse key is a cost with nothing to show for it.

Summary

• Order is a constraint, not a preference: an event that erases a field’s previous value must keep its order; four of the seven events per shipment fall in this class.
• Backward writes and wrong final states are separate numbers: free produced 5 backward writes, but only 1 shipment ended up in a wrong final state, because later correct events closed most of them.
• Sequential convoy zeroes both numbers and takes the cost out of throughput: ticks rise from 8 to 13, effective concurrency falls from 4.00 to 2.46 (a ratio of 1.625).
• The version-stamped handler holds concurrency at 4.00 and zeroes wrong final states, but skips 5 events; the state history is missing five steps.
• Lane load is the ceiling on throughput: with eight consumers, the free arrangement falls to 5 ticks while the convoy stalls at 9 and the line convoy at 14 — both at the busiest lane’s load.
• Back to K01: 55.55 events/s of the peak write rate is constrained; the selective convoy raises the consumer requirement by 1.357 times, by 1.625 if the entire stream is routed through the convoy, and by 1.786 with the coarse key.

Next Step

Every event in this lesson was single-step: a state is written and the job is done. End-of-day billing is not like that. For a seller’s one day, a tariff is calculated, a discount is applied, an invoice line is produced, and a notification is sent; four steps wait on each other, and each step lives in a separate service. A job like this cannot have its order preserved by a key the way it was here, because the problem is not two writes to the same key — it is a single job running in four separate places. The next lesson builds this job in two forms — an arrangement where steps trigger each other with events, and an arrangement where a single orchestrator calls the steps in sequence — and measures both in terms of step count, message count, compensated steps, and unfinished jobs.