Transactions

The previous lesson’s backfill touched 3,200 documents one at a time, and it made visible an assumption the topic has not stated until now: every write covered a single document. The document model’s atomicity guarantee sits exactly here. Single-document atomicity is a write to a document happening either completely or not at all — no matter how many fields, nested documents, or array elements the document carries. No such bond exists between two writes to two documents.

This lesson’s question is whether the library’s daily work fits inside that guarantee. Issuing a loan changes a copy’s status and writes a loan record. Between the two changes there is an invariant that must be preserved: a copy cannot be in more than one open loan at the same time. Whether this invariant fits inside a single document depends on the schema’s decision.

The Indivisible Write and the Multi-Document Transaction

The query-side counterpart of single-document atomicity is the conditional write: read, check, and write are one indivisible step. If two tasks attempt a conditional write on the same document at the same time, one wins, and the other sees that the condition no longer holds and writes nothing.

A multi-document transaction spreads the same guarantee across more than one document. Its cost is three items: a rollback image is kept for every document touched, documents stay locked for the duration of the transaction, and a transaction that finds a lock held by someone else aborts and is retried from the start. The theory of transactions, isolation levels, and locking was built in the Data Modeling and Relational Theory and Relational Database Administration courses; what is measured here is scope — how many documents the guarantee wraps, and what that costs.

// transaction.mjs — single-document atomicity and multi-document transactions. A
// single-document write is conditional and indivisible: read, check, and write are one
// step. A multi-document transaction locks every document it touches while reading,
// applies the write immediately but keeps a rollback image; if a lock is held by someone
// else, the transaction aborts and the images are written back.

export function bytes(d) {                          // lesson 01's encoding rule
  if (d === null || d === undefined) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (typeof d === "string") return 4 + Buffer.byteLength(d) + 1;
  const item = Array.isArray(d) ? d.map((v, i) => [String(i), v]) : Object.entries(d);
  return 5 + item.reduce((t, [a, v]) => t + 2 + Buffer.byteLength(a) + bytes(v), 0);
}

export class Store {
  constructor() {
    this.collection = new Map();
    this.lock = new Map();
    this.o = { documentsWritten: 0, bytesWritten: 0, rollbackBytes: 0, aborted: 0 };
  }
  c(name) {
    if (!this.collection.has(name)) this.collection.set(name, new Map());
    return this.collection.get(name);
  }
  find(name, k) {                                    // a read returns a copy of the document
    const b = this.c(name).get(k);
    return b === undefined ? undefined : structuredClone(b);
  }
  write(name, b) {
    this.o.documentsWritten += 1;
    this.o.bytesWritten += bytes(b);
    this.c(name).set(b._k, b);
  }
  // Single-document atomicity: read-check-write is indivisible. Nothing happens if the condition fails.
  conditionalWrite(name, k, condition, apply) {
    const b = this.find(name, k);
    if (b === undefined || !condition(b)) return false;
    this.write(name, apply(b));
    return true;
  }
}

export class Transaction {
  constructor(store) {
    Object.assign(this, { store, locked: [], image: [] });
  }
  lock(name, k) {
    const key = `${name}/${k}`, owner = this.store.lock.get(key);
    if (owner === this) return true;
    if (owner) return false;                          // held by someone else: a conflict
    this.store.lock.set(key, this);
    this.locked.push(key);
    return true;
  }
  read(name, k) {                                     // a locked read
    return this.lock(name, k) ? this.store.find(name, k) : this.rollback();
  }
  write(name, b) {
    if (!this.lock(name, b._k)) return this.rollback();
    const previous = this.store.c(name).get(b._k);
    this.image.push([name, b._k, previous]);
    this.store.o.rollbackBytes += bytes(previous);
    this.store.write(name, b);
    return true;
  }
  commit() {
    this.release();
    return true;
  }
  rollback() {                                        // images are written back in reverse order
    for (const [name, k, previous] of [...this.image].reverse())
      if (previous === undefined) this.store.c(name).delete(k);
      else this.store.c(name).set(k, previous);
    this.store.o.aborted += 1;
    this.release();
    return undefined;
  }
  release() {
    for (const key of this.locked) this.store.lock.delete(key);
    this.locked = [];
  }
}

Same Task, Three Schemes

NS7 (assumption): the catalog is 20,000 book documents, each book has 1–5 copies, and the seed is 424242. NS11 (assumption): the distribution of loan requests across books is Zipf-shaped. NS29 (assumption): the workload is 20,000 loan requests, there are 2,000 members, and the concurrency model processes 8 requests together per round; a second request touching the same document counts as a conflict. Rationale: round width and member count scale the absolute conflict count, they do not change the ratio between schemes.

Returns are not modeled; what is measured is the cost of issuing the loan, and all three schemes answer the same requests in the same order. Concurrency is shown by counting every ordering of two tasks advancing step by step — this is a model, no real thread is set up.

// transaction-measurement.mjs — the same loan-issuing task runs under three schemes:
// single-document conditional write in the embedded schema, two separate single-document
// writes in the referenced schema, and a multi-document transaction in the referenced
// schema. First two concurrent loans are tried across every step ordering, then the write
// volume and conflict count of 20,000 requests are measured. transaction.mjs is in the
// same directory.
import { Store, Transaction } from "./transaction.mjs";

let seed = 424242;                                        // visible seed
const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const N = 20000, MEMBERS = 2000, REQUEST_COUNT = 20000, ROUND = 8;

const RAW = [];
for (let i = 1; i <= N; i += 1) {
  const copy = [];
  for (let j = 0, n = 1 + Math.floor(random() * 5); j < n; j += 1)
    copy.push({ barcode: `B${String(i * 10 + j).padStart(7, "0")}`,
      branch: BRANCH[Math.floor(random() * 6)], status: "shelved" });
  RAW.push({ _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`,
    publication_year: 1950 + (i % 75), copy });
}
const setup = (set = RAW) => {
  const store = new Store();
  for (const b of set) {
    store.c("book").set(b._k, structuredClone(b));
    for (const k of b.copy) store.c("copy").set(k.barcode, { _k: k.barcode, book: b._k, ...k });
  }
  return store;
};

// Three schemes. Each is three steps; the yield between steps is the concurrency point.
function* embedded(store, bookK, barcode, member, n) {
  const book = store.find("book", bookK);
  const k = book.copy.find((x) => x.barcode === barcode);
  yield;
  if (k.status !== "shelved") return false;
  yield;
  return store.conditionalWrite("book", bookK,           // atomic: read-check-write is indivisible
    (b) => b.copy.find((x) => x.barcode === barcode).status === "shelved",
    (b) => {
      Object.assign(b.copy.find((x) => x.barcode === barcode),
        { status: "checked_out", member, loan: n });
      return b;
    });
}
function* referenced(store, bookK, barcode, member, n) {
  const copy = store.find("copy", barcode);
  yield;
  if (copy.status !== "shelved") return false;
  store.write("copy", { ...copy, status: "checked_out" });
  yield;
  store.write("loan", { _k: `O-${n}`, copy: barcode, member, open: true });
  return true;
}
function* transactional(store, bookK, barcode, member, n) {
  const t = new Transaction(store);
  const copy = t.read("copy", barcode);                  // locked read
  yield;
  if (copy === undefined) return false;                  // conflict: transaction aborted
  if (copy.status !== "shelved") { t.commit(); return false; }
  if (!t.write("copy", { ...copy, status: "checked_out" })) return false;
  yield;
  if (!t.write("loan", { _k: `O-${n}`, copy: barcode, member, open: true })) return false;
  t.commit();
  return true;
}
const SCHEMES = [["A embedded single document", embedded], ["B referenced no transaction", referenced],
  ["C referenced transaction", transactional]];

// Measurement 1: two concurrent loans for the same copy, across every step ordering.
const interleavings = (n, m) => n === 0 ? [Array(m).fill(1)] : m === 0 ? [Array(n).fill(0)]
  : [...interleavings(n - 1, m).map((s) => [0, ...s]),
    ...interleavings(n, m - 1).map((s) => [1, ...s])];
const ORDERINGS = interleavings(3, 3);
const openLoans = (store, barcode) =>
  [...store.c("book").values()].filter((b) =>
    b.copy.some((k) => k.barcode === barcode && k.status === "checked_out")).length
  + [...store.c("loan").values()].filter((o) => o.copy === barcode && o.open).length;

console.log(`two concurrent loans for the same copy, ${ORDERINGS.length} step orderings`);
for (const [label, scheme] of SCHEMES) {
  let violation = 0, issued = 0, aborted = 0;
  for (const s of ORDERINGS) {
    const store = setup(RAW.slice(0, 1));                // one book is enough
    const tasks = [scheme(store, "K-00001", "B0000010", "U-0001", 1),
      scheme(store, "K-00001", "B0000010", "U-0002", 2)];
    const outcome = [undefined, undefined];
    const advance = (i) => {
      if (outcome[i] !== undefined) return;
      const r = tasks[i].next();
      if (r.done) outcome[i] = r.value === true;
    };
    for (const choice of s) advance(choice);
    for (const i of [0, 1]) while (outcome[i] === undefined) advance(i);
    const accepted = outcome.filter(Boolean).length, open = openLoans(store, "B0000010");
    issued += accepted;
    aborted += store.o.aborted;
    if (accepted !== open || open > 1) violation += 1;
  }
  console.log(`  ${label.padEnd(28)} violating orderings ${String(violation).padStart(2)}/${ORDERINGS.length}` +
    `  loans issued ${issued}  aborted ${aborted}`);
}

// Measurement 2: 20,000 loan requests. Book choice is Zipf, 2,000 members, 8 requests per round.
const harmonic = Array.from({ length: N }, (_, i) => 1 / (i + 1)).reduce((a, b) => a + b);
const cumulative = [];
for (let i = 0, s = 0; i < N; i += 1) cumulative.push((s += 1 / ((i + 1) * harmonic)));
const pick = (u) => {
  let lo = 0, hi = N - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (cumulative[mid] < u) lo = mid + 1; else hi = mid;
  }
  return lo;
};
const REQUESTS = [];
for (let n = 0; n < REQUEST_COUNT; n += 1) {
  const book = RAW[pick(random())];
  REQUESTS.push({ bookK: book._k, barcode: book.copy[n % book.copy.length].barcode,
    member: `U-${String(n % MEMBERS).padStart(4, "0")}`, n });
}
console.log(`${REQUEST_COUNT} loan requests, the most-requested book is requested ` +
  `${REQUESTS.filter((s) => s.bookK === "K-00001").length} times`);
for (const [label, scheme] of SCHEMES) {
  const store = setup();
  let issued = 0;
  for (const s of REQUESTS) {
    const g = scheme(store, s.bookK, s.barcode, s.member, s.n);
    let r = g.next();
    while (!r.done) r = g.next();
    if (r.value === true) issued += 1;
  }
  const o = store.o;
  console.log(`  ${label.padEnd(28)} issued ${issued}  documents written ${String(o.documentsWritten).padStart(5)}` +
    `  bytes written ${String(o.bytesWritten).padStart(7)}  rollback ${String(o.rollbackBytes).padStart(6)} bytes`);
}
// The lock target depends on the scheme: the book document in the embedded schema, the copy in the referenced schema.
const conflict = (target) => {
  let n = 0;
  for (let i = 0; i < REQUEST_COUNT; i += ROUND) {
    const seen = new Set();
    for (const s of REQUESTS.slice(i, i + ROUND))
      if (seen.has(target(s))) n += 1; else seen.add(target(s));
  }
  return n;
};
console.log(`  requests conflicting in a round of ${ROUND}: book-document target ${conflict((s) => s.bookK)}` +
  `, copy-document target ${conflict((s) => s.barcode)}`);

two concurrent loans for the same copy, 20 step orderings
  A embedded single document   violating orderings  0/20  loans issued 20  aborted 0
  B referenced no transaction  violating orderings 12/20  loans issued 32  aborted 0
  C referenced transaction     violating orderings  0/20  loans issued 20  aborted 18
20000 loan requests, the most-requested book is requested 1980 times
  A embedded single document   issued 6212  documents written  6212  bytes written 2318144  rollback      0 bytes
  B referenced no transaction  issued 6212  documents written 12424  bytes written 1066949  rollback      0 bytes
  C referenced transaction     issued 6212  documents written 12424  bytes written 1066949  rollback 637044 bytes
  requests conflicting in a round of 8: book-document target 1021, copy-document target 296

Where the Invariant Fits

The first three lines are the lesson’s core finding. In the embedded scheme, the loan information is inside the copy, and the copy is inside the book document; the invariant fits inside the boundary of a single document, and the conditional write preserves it in all twenty of the twenty orderings. Across the twenty orderings, 20 loans total are issued — exactly one per ordering. The losing task does not get an error, it just sees that the condition no longer holds.

In the referenced scheme, the same invariant is spread across two documents and breaks in twelve of the twenty orderings: both members read the copy as shelved, both write, and the result is two open loan records for the same copy. 32 loans total are issued, though the correct number is 20. None of these 12 orderings show an error — both tasks return successfully, and the data silently becomes inconsistent.

The multi-document transaction closes those twelve: violations drop to 0, loans issued drop to 20. Its cost is in the last column. Eighteen of the twenty orderings incur an abort; only in two orderings — where the two tasks run entirely separately, start to finish — is no abort needed. The transaction turns twelve silent inconsistencies into eighteen visible aborts. An aborted task does not disappear, it is retried; but every retry means one round’s delay and one wasted write.

The Cost of Scope

The second measurement gives the cost at workload scale. All three schemes issue the same 6,212 loans; the rest of the 20,000 requests are rejected because the requested copy is already checked out — the Zipf distribution piles most requests onto the same handful of books, and the most-requested book alone takes 1,980 requests.

Write volume reproduces the second lesson’s finding. The embedded scheme writes one document per loan, but that document is the entire book: 6,212 writes, 2,318,144 bytes. The referenced scheme writes two documents, both small: 12,424 writes, 1,066,949 bytes. The document count doubles while the bytes roughly halve.

The multi-document transaction’s own line item is the rollback image: 637,044 bytes, 59.7% of the bytes written. This byte answers no query; it is kept only for the possibility of an abort, and discarded once the transaction ends. The transaction’s second line item is conflict, and it depends on the schema. The lock target is the book document in the embedded scheme, the copy document in the referenced scheme. In rounds of eight, book-document-targeted conflict is 1,021, copy-document-targeted conflict is 296 — a 3.4-fold difference. Embedding shortens the read path while also enlarging the lock’s grain: two loans on different copies of the same book do not conflict in separate documents, but do conflict in a single one.

The rule for the decision follows from this: whatever documents the invariant spreads across, that is the scope, and the schema determines that spread. Building a multi-document transaction for an invariant that fits in a single document pays for the rollback image and the aborts for nothing; leaving an invariant that does not fit without a transaction is an inconsistency that looks error-free.

Summary

• Single-document atomicity is a write to a document happening completely or not at all; how many fields or array elements change does not affect this.
• When the invariant fits in a single document, a conditional write is enough: a full loan is issued in all twenty of the twenty step orderings, with no aborts.
• When the invariant spreads across two documents, twelve of the twenty orderings break and 32 loans are issued instead of 20; both tasks return without error, and the inconsistency is silent.
• A multi-document transaction brings the violation count to zero and, in exchange, charges eighteen aborts plus a rollback image of 59.7% of the bytes written (637,044 bytes).
• The lock’s grain comes from the schema: on the same workload, book-document-targeted conflict is 1,021, copy-document-targeted conflict is 296.

Next Step

This topic carried the document model from its type system to multi-document transactions, and at every step tied a decision to a number: how many requests the embedding decision reduces the read path to, how many documents an operator’s semantics returns, how many records a pipeline’s order processes, where an index pulls the scanned-entry count, how many violations a validation rule produces, and what a multi-document transaction costs. All of these measurements share one limit: every one of them was done on a single node. Most of the document model’s promises cannot be tested on a single node — horizontal scaling, and a service surviving the loss of one machine, both need more than one node, and the concepts of locking, aborting, and atomicity measured in this lesson all get redefined there. The next topic moves the store to a distributed setup and asks the first question: if the same data sits on more than one member, who decides which of them accepts a write.