Transactions and Optimistic Locking

The previous lesson showed that all of a transaction’s keys can be gathered onto the same node, but it did not ask what happens once they are. A loan transaction that checks a branch limit does this: it reads the branch’s concurrent-loan counter, checks whether it is over the limit, and only then increments it. There is a gap between the read and the increment, and in that gap another clerk may have changed the same counter.

The optimistic locking pattern — compare versions, retry on conflict — was built up and measured in the Data Access Layer and Business Logic course; it is not repeated here. This lesson’s subject is how the pattern plays out inside an in-memory store: the store is single-threaded, it processes commands in order, and a transaction block runs without splitting. These two properties determine both how a collision is detected and who pays its cost.

Watch, Think, Send

The client first puts the counter under watch, then reads it. Comparing the value it read against the limit happens on the client’s side, not the store’s; the store serves other clients meanwhile. When the client sends the transaction, the store checks exactly one question: has the watched key changed since the watch was set. If it has, the transaction does not run at all, and the client starts over.

The collision window is exactly this think interval, and its length is in the client’s hands. What the store controls is something else: while a transaction block runs, no other command can interleave. This explains where atomicity comes from, and it also writes down its cost — the longer the block, the longer every client waits.

Mechanism

The mechanism is a model: no real store, network, or client is set up. A tick is an abstract step, and the store processes exactly one command per tick.

CU8 — the think interval is 3 ticks, the transaction block defaults to 4 commands. Rationale: the arithmetic between reading and sending and the block’s length are two independent settings, and each is measured separately. CU9 — 55 percent of jobs are loans (+1), 45 percent are returns (−1), and the job list is generated independent of the scheme. Rationale: the counter should hover near the limit so the check actually binds, and the same job list needs to run under all three schemes. CU10 — a watched key holds 48 bytes of overhead, a counter 64, a lock key 64. Rationale: a watch record holds the key binding and the version; the counter and the lock are each a single entry.

// transaction/model.mjs — the SINGLE-THREADED in-memory store is an IN-PROCESS MODEL. A tick is an
// abstract step: the store processes exactly one command per tick, and a transaction block runs
// without splitting, holding the block for that many ticks. No real store, network, or client is
// set up. Think time is the client's own arithmetic between reading and sending; the store serves
// others meanwhile, and the collision window is exactly that gap.
export const COUNTER_BYTES = 64, WATCH_BYTES = 48, LOCK_BYTES = 64;

export function generator(seed) {  // linear congruential generator; seed is visible
  let s = seed >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; };
}

export function run({ scheme, clients, branches = 6, limit = 20, tasks = 30, think = 3,
                      block = 4, seed = 20260731 }) {
  const rnd = generator(seed);
  // Job list is generated independent of the scheme: each job is either a loan (+1) or a return (-1).
  const jobs = [...Array(clients)].map(() => [...Array(tasks)].map(() => rnd() < 0.55));
  const counter = Array(branches).fill(10), version = Array(branches).fill(0), lock = Array(branches).fill(-1);
  const c = [...Array(clients)].map((_, i) => ({ id: i, br: i % branches, i: 0, phase: 0, wait: 0, seen: 0 }));
  let tick = 0, busy = 0, turn = 0, collisions = 0, overLimit = 0, blocked = 0, blockWait = 0, done = 0;

  const apply = (x) => {                                    // job's effect on the counter; limit IS enforced
    const grow = jobs[x.id][x.i];
    if (grow && counter[x.br] < limit) counter[x.br] += 1;
    else if (!grow && counter[x.br] > 0) counter[x.br] -= 1;
    version[x.br] += 1; x.i += 1; done += 1; x.phase = 0;
  };

  while (done < clients * tasks && tick < 400000) {
    tick += 1;
    for (const x of c) if (x.wait > 0) x.wait -= 1;
    const ready = c.filter((x) => (x.i < tasks || x.phase > 0) && x.wait === 0);
    if (busy > 0) { busy -= 1; blocked += ready.length; blockWait += ready.length; continue; }
    if (ready.length === 0) continue;
    const x = ready[turn % ready.length]; turn += 1;        // the store serves one command
    blocked += ready.length - 1;
    if (scheme === "atomic") {                              // one atomic step, NO condition
      const grow = jobs[x.id][x.i];
      if (grow) { if (counter[x.br] >= limit) overLimit += 1; counter[x.br] += 1; }
      else if (counter[x.br] > 0) counter[x.br] -= 1;
      version[x.br] += 1; x.i += 1; done += 1;
    } else if (scheme === "watch") {
      if (x.phase === 0) { x.seen = version[x.br]; x.phase = 1; }   // watch
      else if (x.phase === 1) { x.wait = think; x.phase = 2; }       // read, then the client computes
      else if (version[x.br] !== x.seen) { collisions += 1; x.phase = 0; }  // watched key changed
      else { busy = block - 1; apply(x); }                    // transaction block runs WITHOUT splitting
    } else {                                                  // coarse lock: held across the think gap
      if (x.phase === 0) { if (lock[x.br] === -1) { lock[x.br] = x.id; x.phase = 1; } }
      else if (x.phase === 1) { x.wait = think; x.phase = 2; }
      else if (x.phase === 2) { apply(x); x.phase = 3; }
      else { lock[x.br] = -1; x.phase = 0; }
    }
  }
  const overhead = scheme === "watch" ? clients * WATCH_BYTES : scheme === "lock" ? branches * LOCK_BYTES : 0;
  return { tick, collisions, overLimit, blocked, blockWait, done, counter,
           retries: collisions / (clients * tasks), memory: branches * COUNTER_BYTES + overhead, overhead };
}

// transaction/measure.mjs — same job: first concurrency, then three schemes, then transaction block length
import { run, COUNTER_BYTES, WATCH_BYTES } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const row = (cells, widths) => cells.map((c, i) => s(c, widths[i])).join(" | ");
const pct = (x, n) => s((x * 100).toFixed(2) + "%", n);

console.log("6 branches, concurrent-loan limit per branch 20. Each client does 30 jobs (55% loan,");
console.log("45% return; seed 20260731). Think 3 ticks, transaction block 4 commands. Watch scheme:\n");
const W1 = [7, 5, 10, 16, 11, 21];
console.log(row(["clients", "jobs", "collisions", "retries per job", "total ticks", "blocked client-ticks"], W1));
console.log(W1.map((w) => "-".repeat(w)).join("-|-"));
for (const n of [2, 4, 8, 16, 32]) {
  const r = run({ scheme: "watch", clients: n });
  console.log(row([n, n * 30, r.collisions, r.retries.toFixed(3), r.tick, r.blocked], W1));
}

console.log("\n16 clients fixed; three schemes:");
const W2 = [7, 11, 10, 10, 8, 14, 10];
console.log(row(["scheme", "total ticks", "collisions", "over limit", "blocked", "overhead bytes", "held bytes"], W2));
console.log(W2.map((w) => "-".repeat(w)).join("-|-"));
for (const scheme of ["atomic", "watch", "lock"]) {
  const r = run({ scheme, clients: 16 });
  console.log(row([scheme, r.tick, r.collisions, r.overLimit, r.blocked, r.overhead, r.memory], W2));
}

console.log("\n16 clients, watch scheme; transaction block length varies:");
const W3 = [5, 11, 10, 21, 10, 12];
console.log(row(["block", "total ticks", "collisions", "waiting due to block", "blocked", "wait share"], W3));
console.log(W3.map((w) => "-".repeat(w)).join("-|-"));
for (const b of [1, 2, 4, 8, 16]) {
  const r = run({ scheme: "watch", clients: 16, block: b });
  console.log(row([b, r.tick, r.collisions, r.blockWait, r.blocked, pct(r.blockWait / r.blocked, 11)], W3));
}

console.log("\nquantities independent of the run:");
console.log("  watch overhead = client count x " + WATCH_BYTES + " bytes (per watched key)");
console.log("  clients : " + [2, 4, 8, 16, 32].map((n) => s(n, 7)).join(""));
console.log("  bytes   : " + [2, 4, 8, 16, 32].map((n) => s(n * WATCH_BYTES, 7)).join(""));
console.log("  counter memory = 6 x " + COUNTER_BYTES + " = " + 6 * COUNTER_BYTES + " bytes (independent of scheme)");
console.log("  job waiting while a transaction block runs <= (block - 1) x ready-client count");
console.log("  block   : " + [1, 2, 4, 8, 16].map((n) => s(n, 7)).join(""));
console.log("  upper bound (15 ready clients): " + [1, 2, 4, 8, 16].map((n) => s((n - 1) * 15, 7)).join(""));

6 branches, concurrent-loan limit per branch 20. Each client does 30 jobs (55% loan,
45% return; seed 20260731). Think 3 ticks, transaction block 4 commands. Watch scheme:

clients |  jobs | collisions |  retries per job | total ticks |  blocked client-ticks
--------|-------|------------|------------------|-------------|----------------------
      2 |    60 |          0 |            0.000 |         387 |                   470
      4 |   120 |          0 |            0.000 |         717 |                  2244
      8 |   240 |         87 |            0.362 |        1704 |                 10070
     16 |   480 |        475 |            0.990 |        4314 |                 54181
     32 |   960 |       2201 |            2.293 |       12372 |                350407

16 clients fixed; three schemes:
 scheme | total ticks | collisions | over limit |  blocked | overhead bytes | held bytes
--------|-------------|------------|------------|----------|----------------|-----------
 atomic |         480 |          0 |         86 |     7080 |              0 |        384
  watch |        4314 |        475 |          0 |    54181 |            768 |       1152
   lock |        4353 |          0 |          0 |    58883 |            384 |        768

16 clients, watch scheme; transaction block length varies:
block | total ticks | collisions |  waiting due to block |    blocked |   wait share
------|-------------|------------|-----------------------|------------|-------------
    1 |        2965 |        506 |                     0 |      37476 |        0.00%
    2 |        3356 |        475 |                  6268 |      41303 |       15.18%
    4 |        4314 |        475 |                 19146 |      54181 |       35.34%
    8 |        6230 |        475 |                 44902 |      79937 |       56.17%
   16 |       10062 |        475 |                 96414 |     131449 |       73.35%

quantities independent of the run:
  watch overhead = client count x 48 bytes (per watched key)
  clients :       2      4      8     16     32
  bytes   :      96    192    384    768   1536
  counter memory = 6 x 64 = 384 bytes (independent of scheme)
  job waiting while a transaction block runs <= (block - 1) x ready-client count
  block   :       1      2      4      8     16
  upper bound (15 ready clients):       0     15     45    105    225

Collisions Are Not Linear

The first table doubles concurrency and counts collisions. At two and four clients there is not a single collision: clerks spread across six branches do not touch the same counter at the same time. At eight clients, 87 collisions are measured; at sixteen, 475; at thirty-two, 2,201. While job count doubles, collisions grow four to five times over, because a collision is proportional not to client count but to the number of client pairs touching the same counter in the same window.

The retries-per-job column makes this directly readable: 0.362, then 0.990, then 2.293. At thirty-two clients, a loan transaction is sent about three times on average, and two of those go to waste. Total ticks climb from 1,704 to 12,372 — as the job count quadruples, the ticks spent grow sevenfold.

The blocked-client-ticks column grows from 10,070 to 350,407, thirty-five times over. This number is the sum of ticks spent by clients that are ready but not yet served, and it is the real measure of a single-threaded store: even when no work is happening, someone is waiting.

The Same Job Under Three Schemes

The second table puts three schemes side by side at sixteen clients. The unconditional atomic step is the fastest, and it is wrong. 480 jobs finish in 480 ticks — one tick per command, not a single retry. The over-limit column writes down what that buys: the branch limit was exceeded 86 times. An atomic increment resolves a race condition, but it cannot enforce a check; reading the limit and acting on it takes two steps, and something else gets in between them.

The watch scheme is correct and spends nine times the ticks. 4,314 ticks, 475 collisions, zero over-limit violations. The difference is the price of correctness, and its size is exactly what is measured here.

A coarse lock gives the same correctness and is not cheaper. At 4,353 ticks it sits slightly above the watch scheme, and at 58,883 blocked client-ticks it stays clearly above it. The reason is that the lock is held across the client’s think interval too: no collisions, but plenty of waiting. Optimistic control’s advantage here is that it keeps no one waiting when there is no collision.

The memory columns recall this course’s rule. Watch overhead grows with client count: 768 bytes at sixteen clients, 1,536 at thirty-two. The protected data itself is nothing more than six counters, 384 bytes. Past eight clients, the collision-control ledger outweighs the data it protects. The lock’s overhead, in contrast, is per branch and independent of client count: 384 bytes. The memory difference between the two approaches comes down to what the overhead is bound to.

The Length of the Transaction Block

The third table isolates the cost specific to a single-threaded store. At block length 1, the wait caused by the block is zero. At block length 16, 96,414 client-ticks accumulate purely while the block runs, making up 73.35 percent of total waiting. The collision count is nearly constant across these rows (475) — block length does not change collisions, because the collision window sits in the think interval.

What changes is that no one else can be served while the transaction runs. Total ticks climb from 2,965 to 10,062. The run-independent upper bound is in the last row: at block length 16, with 15 ready clients, that is 225 client-ticks for a single transaction. Adding a command to a transaction block charges that command to every client’s bill.

Summary

• Collisions do not grow linearly with concurrency: there were no collisions at two and four clients; 87, 475, and 2,201 collisions were measured at 8, 16, and 32; retries per job climbed from 0.362 to 2.293.
• The unconditional atomic step finished 480 jobs in 480 ticks with zero collisions, but exceeded the branch limit 86 times: an atomic increment resolves the race, it does not enforce the check.
• The watch scheme spent 4,314 ticks with zero over-limit violations; the price of correctness is that ninefold factor.
• A coarse lock gave the same correctness in 4,353 ticks but blocked 58,883 client-ticks (54,181 for watch), because the lock is held across the client’s think interval too.
• Watch overhead is per client (768 bytes at 16 clients) and exceeds the six counters’ 384 bytes; lock overhead is per branch and does not grow with client count.
• As the transaction block grew from 1 to 16, total ticks climbed from 2,965 to 10,062, block-caused waiting from 0 to 96,414 client-ticks, reaching 73.35 percent of total waiting; the collision count did not change.

Next Step

This lesson measured under what conditions a write gets accepted, but it never asked who finds out that it was accepted. Notifying a waitlisted reader once the loan counter hits its limit, refreshing the shelf display once a book is returned, a branch board showing the latest activity — all of these ask the same question: how does a change reach the parties waiting on it. This work does not require reading a key; the store itself can distribute a message to its subscribers. The next lesson measures what that distribution is, and more importantly what it is not: there is no delivery guarantee, a message to a channel with no subscriber is lost, and a slow subscriber grows a buffer in the store’s memory.