Ordering and Partitioning

The previous lesson separated the delivery count from the effect count, but neither measurement looked at the delivery’s order at all. There are places in the loan system where order is decisive. If the same book’s “issued” and “returned” events are processed out of order, the branch stock summary shows the book as both on the shelf and with the member; the book’s final state forms according to the processing order, not the events’ real time.

This lesson measures a tension. So far, the way to speed work up was adding consumers; adding consumers breaks order. To see the numerical face of the problem, an order violation first has to be turned into something measurable.

How an Ordering Violation Is Counted

Events are given a number that reflects the order they were produced in. After processing, events are arranged by finish time. If two events land in this arrangement in the reverse of their production order, an inversion occurs — the same count Algorithms uses to measure sorting performance. Two separate counts are kept: the global inversion count over all pairs, and the in-key inversion count only between events of the same book.

The distinction matters, because the loan system does not need global order. Which order two different books’ events finish in changes nothing. What produces a wrong result when broken is the order of the same book’s events.

// partition.mjs — a fixed-seed event sequence, the partitioning run, and the inversion counter
export function generator(seed) {              // fixed-seed linear congruential generator
  let x = seed;
  return () => (x = (x * 1103515245 + 12345) % 2147483648) / 2147483648;
}

export function events(count = 24, seed = 20250720) {
  const rand = generator(seed);
  const TYPES = ["issued", "return_received", "reserved"];
  const list = [];
  for (let order = 0; order < count; order++) {
    const bookId = 1 + Math.floor(rand() * 6);            // book 1..6
    list.push({ order, bookId, type: TYPES[Math.floor(rand() * 3)], duration: 1 + Math.floor(rand() * 3) });
  }
  return list;
}

const sortByFinish = (a) => [...a].sort((x, y) => x.finish - y.finish || x.slot - y.slot);

// Each partition is processed by a single worker, in arrival order.
export function partitioned(list, partitionCount) {
  const finish = new Array(partitionCount).fill(0);
  const result = list.map((e) => {
    const p = e.bookId % partitionCount;                  // partition key: book id
    finish[p] += e.duration;
    return { ...e, slot: p, finish: finish[p] };
  });
  return { result: sortByFinish(result), duration: Math.max(...finish), load: finish };
}

// No partitioning: every message goes to whichever worker is free at that moment.
export function competing(list, workerCount) {
  const available = new Array(workerCount).fill(0);
  const result = list.map((e) => {
    let k = 0;
    for (let i = 1; i < workerCount; i++) if (available[i] < available[k]) k = i;
    available[k] += e.duration;
    return { ...e, slot: k, finish: available[k] };
  });
  return { result: sortByFinish(result), duration: Math.max(...available), load: available };
}

// Number of inversions among events arranged by finish order.
export function violations(byFinish) {
  let global = 0, inKey = 0;
  for (let i = 0; i < byFinish.length; i++)
    for (let j = i + 1; j < byFinish.length; j++)
      if (byFinish[i].order > byFinish[j].order) {
        global += 1;
        if (byFinish[i].bookId === byFinish[j].bookId) inKey += 1;
      }
  return { global, inKey };
}

Adding Consumers Breaks Order

The first measurement runs the competing-consumer arrangement: every message goes to whichever worker is free at that moment, with no partitioning. Twenty-four events are spread across six different books, and their durations are generated from a fixed seed.

// competing-order.mjs — adding workers with no partitioning: duration drops, in-key order breaks
import { events, competing, violations } from "./partition.mjs";
const list = events();

console.log(`events=${list.length}  distinct books=${new Set(list.map((e) => e.bookId)).size}`);
console.log("workers  duration  global inversions  in-key inversions");
for (const n of [1, 2, 3, 4]) {
  const r = competing(list, n);
  const v = violations(r.result);
  console.log(`${String(n).padStart(7)}${String(r.duration).padStart(10)}` +
              `${String(v.global).padStart(19)}${String(v.inKey).padStart(19)}`);
}

node competing-order.mjs

events=24  distinct books=6
workers  duration  global inversions  in-key inversions
      1        44                  0                  0
      2        22                  4                  1
      3        15                  9                  1
      4        12                 17                  3

With a single worker, both numbers are zero: the ordering guarantee is not free, it comes with the condition of a single consumer. When worker count rises to four, total duration drops from 44 to 12, but the in-key inversion count rises to three. Those three pairs are cases where two of the same book’s events finish in reverse order — exactly where the stock summary produces a wrong result.

The result is a trade-off, and neither extreme is acceptable. A single consumer preserves order but throughput drops to a third. Four consumers give throughput but break correctness. What is needed sits somewhere in the middle: preserving order only where it is needed.

Partitioning by Key

Where it is needed is clear: the same book’s events. So let messages be distributed not to workers, but to keys. Let every message fall into a partition derived from a partition key, and let every partition be processed by a single worker, in arrival order.

The rule gives two conditions at once. All of the same key’s events fall into the same partition, so the order between them is preserved. Because different partitions run independently of one another, concurrency equal to the partition count is achieved.

// partitioned-order.mjs — the same workload keeps its in-key order once partitioned by key
import { events, partitioned, violations } from "./partition.mjs";
const list = events();

console.log("partitions  duration  global inversions  in-key inversions  partition loads");
for (const p of [1, 2, 3, 4, 6]) {
  const r = partitioned(list, p);
  const v = violations(r.result);
  console.log(`${String(p).padStart(10)}${String(r.duration).padStart(10)}` +
              `${String(v.global).padStart(19)}${String(v.inKey).padStart(19)}   ${r.load.join(" ")}`);
}

node partitioned-order.mjs

partitions  duration  global inversions  in-key inversions  partition loads
         1        44                  0                  0   44
         2        24                 20                  0   24 20
         3        20                 24                  0   20 13 11
         4        21                 25                  0   3 14 21 6
         6        14                 44                  0   14 10 7 6 3 4

The in-key inversion column is zero regardless of partition count. The global inversion count, though, rises together with partition count, reaching 44 at six partitions. Reading the two columns together is the essence of the lesson: partitioning buys in-key order by giving up global order. What is lost never had value in the first place; what is preserved determines correctness.

The duration column tells a second truth. Duration drops as partition count rises, but not evenly: 21 at four partitions, 20 at three. The partition-loads column shows why — at four partitions the loads are 3, 14, 21, and 6; the other three sit idle until the fullest partition finishes its work. Raising the partition count raises concurrency capacity, not concurrency actually achieved. What determines real concurrency is how evenly the load lands across the partitions.

Choosing the Partition Key

Choosing the key is not a performance tuning setting, it is a correctness decision: the ordering guarantee holds exactly within the set the key defines, and not at all outside it.

If the book’s id is chosen as the key, the same book’s issue and return events stay ordered, but the same member’s events across two different books do not. If the member’s id is chosen, the opposite holds. The question that decides the criterion is: which pair of events, processed out of order, produces a wrong result? For the stock summary the answer is the book, because whether a book is on the shelf depends only on that book’s events. For a counter that tracks a member’s open loan count, the answer is the member.

If both are needed, a single key is not enough. In that case, either a coarser key is chosen — the branch, say — and concurrency drops, or an effect is designed that does not depend on order. The second is usually cheaper: a version number is attached to the event, and the consumer applies only a version greater than the one it has already seen. An effect built this way silently ignores a stale event that arrives late, and needs no ordering guarantee at all.

Hot Key

Partition imbalance is not random; it usually comes from a single key producing far more events than the others. A heavily requested book can generate more than half of all transactions on its own. A key like this is called a hot key.

// hot-key.mjs — one book's load piles into a single partition; adding partitions does not split it
import { generator, partitioned } from "./partition.mjs";

function hotEvents(count = 30, seed = 7) {
  const rand = generator(seed);
  const list = [];
  for (let order = 0; order < count; order++) {
    const bookId = rand() < 0.6 ? 3 : 1 + Math.floor(rand() * 6);   // book 3 is heavily requested
    list.push({ order, bookId, duration: 1 + Math.floor(rand() * 3) });
  }
  return list;
}

const list = hotEvents();
const total = list.reduce((t, e) => t + e.duration, 0);
const hotLoad = list.filter((e) => e.bookId === 3).reduce((t, e) => t + e.duration, 0);
console.log(`events=${list.length}  total duration=${total}  book 3 events=${list.filter((e) => e.bookId === 3).length} load=${hotLoad}`);
console.log("partitions  duration  partition loads");
for (const p of [1, 2, 4, 8]) {
  const r = partitioned(list, p);
  console.log(`${String(p).padStart(10)}${String(r.duration).padStart(10)}   ${r.load.join(" ")}`);
}

const p = 2;
const hotPartition = 3 % p;
const waiting = partitioned(list, p).result.map((e) => ({ ...e, wait: e.finish - e.duration }));
const avg = (d) => d.length === 0 ? "-" : (d.reduce((t, e) => t + e.wait, 0) / d.length).toFixed(1);
const blocked = waiting.filter((e) => e.slot === hotPartition && e.bookId !== 3);
let t = 0;                                  // if the same events sat in a partition with no hot key
const alone = [...blocked].sort((a, b) => a.order - b.order).map((e) => { const b = t; t += e.duration; return b; });
console.log(`partitions=2  average wait of ${blocked.length} non-book-3 events in the hot partition = ${avg(blocked)}`);
console.log(`              same events in a partition with no hot key                               = ` +
            `${(alone.reduce((a, b) => a + b, 0) / alone.length).toFixed(1)}`);

node hot-key.mjs

events=30  total duration=59  book 3 events=18 load=28
partitions  duration  partition loads
         1        59   59
         2        41   18 41
         4        28   9 13 9 28
         8        28   0 10 3 28 9 3 6 0
partitions=2  average wait of 5 non-book-3 events in the hot partition = 11.0
              same events in a partition with no hot key                               = 5.0

Raising partition count from four to eight changed the duration not at all: 28 in both. At eight partitions, two partitions sit completely empty, and one carries a load of 28 units on its own. The number is not a coincidence — it equals book 3’s total load. Because the ordering guarantee makes a key indivisible, the hot key’s load is the system’s lower bound; adding partitions does not lower that bound.

The last two lines show a second cost. Five events that land in the same partition and have nothing to do with the hot key wait an average of 11 units; on their own in a partition, they would wait 5. The hot key’s work delays the unrelated work sitting behind it too. This behavior is called head-of-line blocking — the queueing-layer counterpart of the same phenomenon encountered in network layers.

The fix runs through changing the key. If the ordering guarantee is genuinely needed for the hot key, a single partition is unavoidable, and the only remedy is making that partition’s work cheaper. If it is not needed, the key is refined: a composite key like “book and event type” instead of just the book spreads the hot book’s events across more than one partition — but that means giving up the order between issue and return too. The decision comes back to the same question: which pair’s order determines correctness.

Summary

• An ordering violation is measured as an inversion count; what matters in the loan system is not the global inversion count but the in-key inversion count between the same book’s events.
• Without partitioning, in the competing-consumer arrangement, duration dropped from 44 to 12 as worker count rose to four, but the in-key inversion count rose from zero to three.
• With partitioning by key, the in-key inversion count stayed at zero regardless of partition count; the global inversion count rose to 44 at six partitions. Partitioning buys in-key order by giving up global order.
• Raising partition count raises concurrency capacity, not concurrency itself: at four partitions the loads landed as 3, 14, 21, and 6, so the duration came out worse than at three partitions.
• Because a hot key cannot be split, it sets the system’s lower bound — duration stayed at the same 28 at four and eight partitions — and it raised the average wait of unrelated work in the same partition from 5 units to 11.

Next Step

Every measurement so far quietly carried one assumption: a retried job eventually succeeds. The crash was transient, the second attempt finished the job. In reality, some messages fail on the second attempt too, and the tenth — their body is malformed, the member they reference has been deleted, a business rule will never accept them. In at-least-once mode, a message like this never leaves the queue at all, and in a partitioned arrangement it halts every job behind it. The next lesson builds the structure that removes these messages from the queue and isolates them: an attempt counter, a threshold, and a dead-letter queue.