---
title: Transactions
source: 'https://academia.sh/en/courses/nosql/transactions'
course: 'Non-Relational Data Models'
language: en
updated: '2026-08-23T07:00:45+00:00'
license: 'CC BY-SA 4.0'
---

# Transactions

Counting where single-document atomicity is enough and where it is not: two concurrent loans for the same copy, run across all twenty step orderings, produce zero violations in the embedded scheme, twelve of the twenty orderings in the referenced scheme produce two open loans, and a multi-document transaction closes those twelve at a cost of eighteen aborts and a 637,044-byte rollback image.

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.

```js
// 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.

```js
// 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.