--- title: 'Non-Relational Data Models' source: 'https://academia.sh/en/courses/nosql' language: en updated: '2026-08-23T07:00:44+00:00' license: 'CC BY-SA 4.0' lessons: 19 outcomes: - 'Maps the document, key-value, wide-column, and graph models onto their use cases' - 'Justifies the embed-or-reference decision in a document database' - 'Explains the effect of a consistency model choice on the application' --- # Non-Relational Data Models The families built for requirements the relational model cannot meet: mapping key-value, document, wide-column, graph, and time series stores onto access patterns, counting the consequences of the embed-or-reference decision in the document model, query operators, the aggregation pipeline, indexing and schema validation, the scope of multi-document transactions, and the unavoidable questions of distributed behavior — replica sets, the shard key, read and write concerns, consistency models, and security configuration. ## Model Families The five store families mapped to access pattern: key-value stores reached by a single key, document databases delivering a nested structure in a single read, wide-column stores offering write performance through the column-family model, graph databases making the relationship itself the subject of the query, time series stores whose layout follows timestamped measurement data, and the selection criteria on the path from access pattern to model. ### Key-Value Stores Source: https://academia.sh/en/courses/nosql/key-value-stores The contract and cost of the simplest access model: the value's opacity to the store, measuring the same member page in the relational schema and the key-value model by round trips and records touched, the loss of the ability to query on a field and the application-maintained secondary index being read as a whole, and the trade-off key design sets up between write amplification and the number of read round trips. The Relational Database Administration course closed without asking a single question about the model itself: tables, rows, schema, and transactions were taken as given, and everything measured was measured inside that model. This course makes the given itself the subject, starting with the simplest case. A key-value store defines a single contract: you give a key, you get a value. The store knows nothing about the value. The naming of the families and their comparison by access pattern across four types was established in the Scaling the Data Layer course: there, a semester scan took 3,001 requests in a key-value store while finishing in a single request in a document or wide-column store, and a three-step traversal stayed at a single request in a graph store regardless of depth. That measurement is not repeated here — it is taken as input. This lesson's question is narrower and looks at **the data model itself**: how a store that cannot see inside the value carries library catalog and loan data, which work it makes cheaper, and which capability it loses. #### The Model's Contract In the key-value model, a record has two parts: a unique key and a byte sequence that carries no meaning for the store. The store knows the key, not the value. Three consequences follow from this single sentence. No condition can be written against the value and no part of the value can be updated, because the store recognizes no concept of a field. There is no operation for joining two records either, because a join is defined by matching fields. What is gained in return is a constant step: once the key is known, the record arrives in a single round trip, regardless of the number of records. For the measurement, the library data is built in both models at once; the relational side is genuinely built with `node:sqlite`. **NS1:** the catalog carries 20,000 members and each member has between 1 and 11 loans; the total is 119,993 loans. **NS2:** values are serialized with JSON; bytes read and written are counted from this representation, and on the relational side the result set is converted to the same representation. ```js // kv/model.mjs — the same member page measured in the relational schema and the // key-value model. The relational side is built with node:sqlite; the numbers are // independent of the run. import { DatabaseSync } from "node:sqlite"; const MEMBERS = 20_000, CITIES = ["Ankara", "Istanbul", "Izmir", "Bursa", "Konya"]; function* members() { // member i has 1 + (i % 11) loans for (let i = 1; i <= MEMBERS; i += 1) { const loans = Array.from({ length: 1 + (i % 11) }, (_, j) => ({ loan_id: i * 100 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900, })); yield { member_id: i, name: `Member ${i}`, city: CITIES[i % 5], loans, penalty_cents: loans.reduce((t, o) => t + o.penalty_cents, 0) }; } } class KeyValueStore { // the value is a byte sequence to the store #table = new Map(); roundTrips = 0; records = 0; bytes = 0; write(key, value) { this.roundTrips += 1; this.records += 1; const s = JSON.stringify(value); this.bytes += Buffer.byteLength(s); this.#table.set(key, s); } read(key) { this.roundTrips += 1; const s = this.#table.get(key); if (s === undefined) return undefined; this.records += 1; this.bytes += Buffer.byteLength(s); return JSON.parse(s); } resetCounters() { this.roundTrips = 0; this.records = 0; this.bytes = 0; } } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE member (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, penalty_cents INTEGER NOT NULL); CREATE TABLE loan (loan_id INTEGER PRIMARY KEY, member_id INTEGER NOT NULL, book_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, penalty_cents INTEGER NOT NULL);`); const insertM = db.prepare("INSERT INTO member VALUES (?,?,?,?)"); const insertL = db.prepare("INSERT INTO loan VALUES (?,?,?,?,?)"); const store = new KeyValueStore(); db.exec("BEGIN"); for (const m of members()) { insertM.run(m.member_id, m.name, m.city, m.penalty_cents); for (const o of m.loans) insertL.run(o.loan_id, m.member_id, o.book_id, o.pickup_date, o.penalty_cents); store.write(`member:${m.member_id}`, m); // the same information as a single value } db.exec("COMMIT"); db.exec("CREATE INDEX loan_member ON loan(member_id); CREATE INDEX member_penalty ON member(penalty_cents);"); const bytes = (x) => Buffer.byteLength(JSON.stringify(x)); const TARGET = 4242; console.log(`model: ${MEMBERS} members, ${db.prepare("SELECT count(*) n FROM loan").get().n} loans; ` + `target member ${TARGET}, loan count ${1 + (TARGET % 11)}`); console.log(db.prepare("EXPLAIN QUERY PLAN SELECT * FROM loan WHERE member_id = ?").all()[0].detail); const row = []; { const m = db.prepare("SELECT member_id, name, city, penalty_cents FROM member WHERE member_id = ?").get(TARGET); const o = db.prepare("SELECT loan_id, book_id, pickup_date, penalty_cents FROM loan WHERE member_id = ?").all(TARGET); row.push(["relational, two queries", 2, 1 + o.length, bytes(m) + bytes(o)]); } { const r = db.prepare(`SELECT m.name, m.city, m.penalty_cents, o.loan_id, o.book_id, o.pickup_date FROM member m JOIN loan o ON o.member_id = m.member_id WHERE m.member_id = ?`).all(TARGET); row.push(["relational, single join", 1, r.length, bytes(r)]); } { store.resetCounters(); const v = store.read(`member:${TARGET}`); row.push([`key-value, single key (${v.loans.length} loans)`, store.roundTrips, store.records, store.bytes]); } console.log(`\n${"path".padEnd(40)}${"round trip".padStart(11)}${"record".padStart(7)}${"byte".padStart(7)}`); for (const [a, g, k, b] of row) console.log(a.padEnd(40) + String(g).padStart(11) + String(k).padStart(7) + String(b).padStart(7)); ``` ``` model: 20000 members, 119993 loans; target member 4242, loan count 8 SEARCH loan USING INDEX loan_member (member_id=?) path round trip record byte relational, two queries 2 9 732 relational, single join 1 8 953 key-value, single key (8 loans) 1 1 741 ``` The numbers are of the **measurement** class. The member page is a single round trip, a single record in the key-value model. In the relational schema, the same page either asks for two queries and nine records, or is reduced to a single join; the join brings the round trip down to one but, because it repeats the member's fields on every loan row, it raises the bytes carried from 732 to 953. The key-value value is 741 bytes: the same information, without repetition, in one piece. The gain here comes not from the join's absence but from modeling around the unit of reading: the value is the whole of what the application wants in one pass. The same thing can be done in a relational schema too — that is the denormalization measured in the Data Modeling and Relational Theory course — but there it is a choice; here it is the model's only shape. #### The Loss of Queryability The library's second question is: who are the members whose penalty exceeds a threshold. In the relational schema this calls for an index on a field of the member table; the key-value store has no such concept of a field. ```js // kv/query.mjs — three paths for the "members whose penalty exceeds a threshold" // question on the same data. The generator is identical to kv/model.mjs; the block // runs on its own. import { DatabaseSync } from "node:sqlite"; const MEMBERS = 20_000, CITIES = ["Ankara", "Istanbul", "Izmir", "Bursa", "Konya"], THRESHOLD = 8000; function* members() { for (let i = 1; i <= MEMBERS; i += 1) { const loans = Array.from({ length: 1 + (i % 11) }, (_, j) => ({ loan_id: i * 100 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900, })); yield { member_id: i, name: `Member ${i}`, city: CITIES[i % 5], loans, penalty_cents: loans.reduce((t, o) => t + o.penalty_cents, 0) }; } } class KeyValueStore { #table = new Map(); roundTrips = 0; records = 0; bytes = 0; write(a, d) { const s = JSON.stringify(d); this.#table.set(a, s); } read(a) { this.roundTrips += 1; const s = this.#table.get(a); if (s === undefined) return undefined; this.records += 1; this.bytes += Buffer.byteLength(s); return JSON.parse(s); } keys() { return [...this.#table.keys()].filter((a) => a.startsWith("member:")); } reset() { this.roundTrips = 0; this.records = 0; this.bytes = 0; } } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE member (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL, penalty_cents INTEGER NOT NULL);`); const insert = db.prepare("INSERT INTO member VALUES (?,?,?,?)"); const store = new KeyValueStore(); const index = []; // the secondary index the application maintains by hand db.exec("BEGIN"); for (const m of members()) { insert.run(m.member_id, m.name, m.city, m.penalty_cents); store.write(`member:${m.member_id}`, m); index.push([m.penalty_cents, m.member_id]); } db.exec("COMMIT"); db.exec("CREATE INDEX member_penalty ON member(penalty_cents);"); index.sort((x, y) => x[0] - y[0]); store.write("index:penalty", index); // the index is also a value: read as a whole const bytes = (x) => Buffer.byteLength(JSON.stringify(x)); const row = []; { const r = db.prepare("SELECT member_id FROM member WHERE penalty_cents > ?").all(THRESHOLD); row.push(["relational, penalty index", 1, r.length, bytes(r), r.length]); } { store.reset(); const found = []; for (const a of store.keys()) { const m = store.read(a); if (m.penalty_cents > THRESHOLD) found.push(m.member_id); } row.push(["key-value, key scan", store.roundTrips, store.records, store.bytes, found.length]); } { store.reset(); const d = store.read("index:penalty"); const found = d.filter(([c]) => c > THRESHOLD).map(([, id]) => store.read(`member:${id}`).member_id); row.push(["key-value, application index", store.roundTrips, store.records, store.bytes, found.length]); } console.log(`model: ${MEMBERS} members, threshold ${THRESHOLD} cents; ` + `relational plan: ${db.prepare("EXPLAIN QUERY PLAN SELECT member_id FROM member WHERE penalty_cents > ?").all()[0].detail}`); console.log(`size of the index:penalty value ${bytes(index)} bytes, entry count ${index.length}`); console.log(`\n${"path".padEnd(32)}${"round trip".padStart(11)}${"record".padStart(7)}${"bytes read".padStart(13)}${"result".padStart(8)}`); for (const [a, g, k, b, n] of row) console.log(a.padEnd(32) + String(g).padStart(11) + String(k).padStart(7) + String(b).padStart(13) + String(n).padStart(8)); ``` ``` model: 20000 members, threshold 8000 cents; relational plan: SEARCH member USING COVERING INDEX member_penalty (penalty_cents>?) size of the index:penalty value 243132 bytes, entry count 20000 path round trip record bytes read result relational, penalty index 1 359 6980 359 key-value, key scan 20000 20000 11631090 359 key-value, application index 360 360 592319 359 ``` The numbers are of the **measurement** class. All three paths find the same 359 members; the difference is where the work happens. A covering index lets the relational engine touch only the 359 matching records in a single round trip, carrying 6,980 bytes. In the key-value store the filtering happens in the application, so the whole key space is walked: 20,000 round trips and 11.6 MB — roughly seventeen hundred times as much data as the result, read just to find the result. The third row carries the real lesson. When the application keeps a list sorted by penalty value and writes it to a single key, the round trips drop from 20,000 to 360. But this list is not an index, it is a value: all 243,132 bytes of it are read whole on every query. A relational index is a tree the engine can descend into; an application index can only be read and parsed whole. The bytes read therefore stay at 592,319 — roughly 85 times the relational path. #### Key Design Is the Only Setting In a relational schema, the designer has tables, columns, constraints, and indexes at hand. In the key-value model there is a single setting: what the key is, and where the value's boundary runs. Adding one loan means read-modify-write in the whole-value design: the whole value is read, a record is appended to the array, the whole value is written back. In the separate-key design, only the new record is written. ```js // kv/key-design.mjs — adding a single loan under two key designs, and the cost the // same designs impose on reading a member page. All byte counts come from real // serialization. class KeyValueStore { #table = new Map(); #ordered = false; roundTrips = 0; records = 0; bytesRead = 0; bytesWritten = 0; constructor(ordered) { this.#ordered = ordered; } write(a, d) { const s = JSON.stringify(d); this.roundTrips += 1; this.records += 1; this.bytesWritten += Buffer.byteLength(a) + Buffer.byteLength(s); this.#table.set(a, s); } read(a) { this.roundTrips += 1; const s = this.#table.get(a); if (s === undefined) return undefined; this.records += 1; this.bytesRead += Buffer.byteLength(s); return JSON.parse(s); } prefix(p) { // only exists in an ordered key space if (!this.#ordered) throw new Error("no prefix scan in a hashed key space"); this.roundTrips += 1; const c = []; for (const [a, s] of [...this.#table].sort(([x], [y]) => (x < y ? -1 : x > y ? 1 : 0))) if (a.startsWith(p)) { this.records += 1; this.bytesRead += Buffer.byteLength(s); c.push(JSON.parse(s)); } return c; } reset() { this.roundTrips = 0; this.records = 0; this.bytesRead = 0; this.bytesWritten = 0; } } const loan = (i, j) => ({ loan_id: i * 1000 + j, book_id: 1 + ((i * 7 + j * 13) % 200_000), pickup_date: `2024-${String(1 + ((i + j) % 12)).padStart(2, "0")}-15`, penalty_cents: (i * 37 + j * 11) % 900 }); console.log(`adding a single loan (the new record itself is ${Buffer.byteLength(JSON.stringify(loan(1, 0)))} bytes)`); console.log(`${"loan count k".padStart(14)}${"whole value: written".padStart(25)}` + `${"factor".padStart(8)}${"separate key: written".padStart(23)}${"factor".padStart(8)}`); for (const k of [1, 8, 64, 512]) { const whole = new KeyValueStore(true), separate = new KeyValueStore(true); const m = { member_id: 7, name: "Member 7", city: "Izmir", loans: Array.from({ length: k }, (_, j) => loan(7, j)) }; whole.write("member:0007", m); for (let j = 0; j < k; j += 1) separate.write(`member:0007:loan:${String(j).padStart(6, "0")}`, loan(7, j)); const next = loan(7, k); whole.reset(); separate.reset(); const v = whole.read("member:0007"); v.loans.push(next); whole.write("member:0007", v); // read-modify-write separate.write(`member:0007:loan:${String(k).padStart(6, "0")}`, next); // only the new record console.log(String(k).padStart(14) + String(whole.bytesWritten).padStart(25) + (whole.bytesWritten / separate.bytesWritten).toFixed(1).padStart(8) + String(separate.bytesWritten).padStart(23) + "1.0".padStart(8)); } const K = 64; const setup = (ordered) => { const d = new KeyValueStore(ordered); for (let j = 0; j < K; j += 1) d.write(`member:0007:loan:${String(j).padStart(6, "0")}`, loan(7, j)); d.write("member:0007", { member_id: 7, name: "Member 7", city: "Izmir" }); d.write("member:0007:loan-list", Array.from({ length: K }, (_, j) => j)); d.reset(); return d; }; console.log(`\nreading the same member's ${K}-loan page`); console.log(`${"key space".padEnd(34)}${"round trip".padStart(11)}${"record".padStart(7)}${"bytes read".padStart(13)}`); const s = setup(true); s.read("member:0007"); s.prefix("member:0007:loan:"); console.log("ordered, prefix scan".padEnd(34) + String(s.roundTrips).padStart(11) + String(s.records).padStart(7) + String(s.bytesRead).padStart(13)); const h = setup(false); h.read("member:0007"); for (const j of h.read("member:0007:loan-list")) h.read(`member:0007:loan:${String(j).padStart(6, "0")}`); console.log("hashed, application key list".padEnd(34) + String(h.roundTrips).padStart(11) + String(h.records).padStart(7) + String(h.bytesRead).padStart(13)); ``` ``` adding a single loan (the new record itself is 74 bytes) loan count k whole value: written factor separate key: written factor 1 223 2.3 99 1.0 8 767 7.7 100 1.0 64 5128 51.8 99 1.0 512 40459 400.6 101 1.0 reading the same member's 64-loan page key space round trip record bytes read ordered, prefix scan 2 65 4966 hashed, application key list 66 66 5149 ``` The top table shows write amplification: the information added is 74 bytes on every row, but the bytes written in the whole-value design climb from 223 to 40,459. The factor grows in direct proportion to the member's loan count and reaches 400.6 at 512 loans. In the separate-key design, the bytes written do not change as the member grows: between 99 and 101 bytes, a factor of 1. The bottom table shows the cost. Once loans are spread across separate keys, the member page no longer arrives in a single round trip. In an ordered key space — stores that keep keys in lexicographic order — a prefix scan counts as a single request and finishes in 2 round trips. In a hashed key space there is no concept of a prefix, because consecutive keys do not land in consecutive places; the application must also keep a list of keys and fetch every loan one at a time: 66 round trips. The same 65 records, the same order of magnitude in bytes, thirty-three times the round trips. Read together, the two tables yield the model's single rule: in a key-value store, the boundary of the value is the boundary of the application's unit of access. Keep the boundary wide and reading drops to a single round trip while write amplification grows; keep it narrow and writing gets cheap while reading becomes dependent on whether the key space is ordered. The decision is made through key naming, not schema; changing it later means rewriting all the data. #### Summary - The key-value model defines a single contract: give a key, get a value. The store cannot see inside the value; there is therefore no condition on a field, no partial update, and no join. - The member page is 1 round trip and 1 record in the key-value model; in the relational schema it is 2 round trips and 9 records, or 1 round trip and 8 records with a single join, at 953 bytes instead of 732. - Querying on a field disappears: the 359 members whose penalty exceeds the threshold are found in 1 round trip and 6,980 bytes with a relational index, while a key scan costs 20,000 round trips and 11.6 MB. - The secondary index the application keeps is not a tree but a value: it brings the round trips down to 360, but reads the 243,132-byte list whole on every query and leaves a window of inconsistency with the record. - Key design is the only setting: a 74-byte addition in the whole-value design writes 40,459 bytes for a member with 512 loans (a factor of 400.6), while the separate-key design keeps the factor at 1 — but then the member page costs 2 round trips in an ordered key space and 66 in a hashed one. #### Next Step Every gain in this lesson rested on one assumption: what the application wants is always a single whole with a known key. The moment the assumption fails, the model collapses — filtering on a field inside the value means 20,000 round trips. The question left standing is what would change if the store could see inside the value. The next lesson takes up that family and measures two things: the difference between a nested structure arriving in a single read and the same data assembled through a relational join, and the load that schema flexibility shifts onto the read side — the cost of checking, on every read, whether a field exists at all. ### Document Databases Source: https://academia.sh/en/courses/nosql/document-databases What a store that can see inside the value gains and what it costs: the combinatorial explosion of assembling a nested book record from four relational tables against reading it as a single document, the effect of an in-place field update on write amplification, and the load schema flexibility shifts onto the read side — the record count an indexed query silently misses and the document count a defensive read scans when three schema versions coexist in the same collection. The previous lesson closed with a single question: what would change if the store could see inside the value. The document database is exactly that change. A record is still named by a single key, but the store now recognizes the value's fields: a condition can be written against a field, an index can be built on a field, and the field itself can be updated in place. This lesson measures two things. The first is the gain: the difference between a nested book record arriving in a single read and the same record assembled by joining four relational tables. The second is the cost: fields not being enforced by a schema moves the check from write time to read time, and this move has a number attached to it. #### The Document and the Collection In the document model, a record is a **document**: a tree of named fields whose values may themselves be a document or an array. Documents are gathered into a **collection**. A collection is not a table, because the documents inside it are not required to carry the same fields; a document is not a row either, because a field is not required to be scalar. These two relaxations have a direct consequence: multi-valued attributes that the relational model must spread across separate tables — a book's authors, subjects, copies — stay inside the document. What first normal form forbids is the document model's definition. **NS1:** the catalog carries 50,000 books; book `i` has between 1 and 3 authors, between 2 and 4 subjects, and between 1 and 5 copies. **NS2:** the relational side is built with `node:sqlite` and every join column carries an index; bytes are counted from the same JSON representation on both sides. ```js // document/nesting.mjs — the same book record read from four relational tables and // from a single document. The relational side is built with node:sqlite; the numbers // are independent of the run. import { DatabaseSync } from "node:sqlite"; const BOOKS = 50_000, AUTHORS = ["Atay", "Saramago", "Tanpinar", "Woolf", "Borges"]; const SUBJECTS = ["novel", "essay", "poetry", "history", "philosophy", "atlas"]; function* books() { // book i: 1+(i%3) authors, 2+(i%3) subjects, 1+(i%5) copies for (let i = 1; i <= BOOKS; i += 1) yield { book_id: i, title: `Book ${i}`, publication: { year: 1960 + (i % 65), language: i % 4 === 0 ? "en" : "tr" }, authors: Array.from({ length: 1 + (i % 3) }, (_, j) => AUTHORS[(i + j) % 5]), subjects: Array.from({ length: 2 + (i % 3) }, (_, j) => SUBJECTS[(i * 2 + j) % 6]), copies: Array.from({ length: 1 + (i % 5) }, (_, j) => ({ copy_id: i * 10 + j, branch_id: 1 + ((i + j) % 9), status: j % 3 === 0 ? "on_shelf" : "on_loan" })), }; } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, publication_year INTEGER NOT NULL, language TEXT NOT NULL); CREATE TABLE book_author (book_id INTEGER NOT NULL, position INTEGER NOT NULL, name TEXT NOT NULL); CREATE TABLE book_subject (book_id INTEGER NOT NULL, subject TEXT NOT NULL); CREATE TABLE copy (copy_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL, branch_id INTEGER NOT NULL, status TEXT NOT NULL);`); const insertBook = db.prepare("INSERT INTO book VALUES (?,?,?,?)"); const insertAuthor = db.prepare("INSERT INTO book_author VALUES (?,?,?)"); const insertSubject = db.prepare("INSERT INTO book_subject VALUES (?,?)"); const insertCopy = db.prepare("INSERT INTO copy VALUES (?,?,?,?)"); const collection = new Map(); // document collection: book_id -> document db.exec("BEGIN"); for (const b of books()) { insertBook.run(b.book_id, b.title, b.publication.year, b.publication.language); b.authors.forEach((a, j) => insertAuthor.run(b.book_id, j, a)); for (const t of b.subjects) insertSubject.run(b.book_id, t); for (const c of b.copies) insertCopy.run(c.copy_id, b.book_id, c.branch_id, c.status); collection.set(b.book_id, JSON.stringify(b)); } db.exec("COMMIT"); db.exec(`CREATE INDEX author_idx ON book_author(book_id); CREATE INDEX subject_idx ON book_subject(book_id); CREATE INDEX copy_idx ON copy(book_id);`); const bytes = (x) => Buffer.byteLength(JSON.stringify(x)); const TARGET = 4244; const target = JSON.parse(collection.get(TARGET)); console.log(`target book ${TARGET}: ${target.authors.length} authors, ${target.subjects.length} subjects, ` + `${target.copies.length} copies; product ${target.authors.length * target.subjects.length * target.copies.length}`); const rows = []; { let n = 0, by = 0; for (const s of ["SELECT * FROM book WHERE book_id = ?", "SELECT name FROM book_author WHERE book_id = ?", "SELECT subject FROM book_subject WHERE book_id = ?", "SELECT * FROM copy WHERE book_id = ?"]) { const r = db.prepare(s).all(TARGET); n += r.length; by += bytes(r); } rows.push(["relational, four queries", 4, n, by]); } { const r = db.prepare(`SELECT k.title, k.publication_year, k.language, y.name, t.subject, n.branch_id, n.status FROM book k JOIN book_author y ON y.book_id = k.book_id JOIN book_subject t ON t.book_id = k.book_id JOIN copy n ON n.book_id = k.book_id WHERE k.book_id = ?`).all(TARGET); rows.push(["relational, single join", 1, r.length, bytes(r)]); } { rows.push(["document, single read", 1, 1, Buffer.byteLength(collection.get(TARGET))]); } console.log(`\n${"path".padEnd(28)}${"round trip".padStart(11)}${"row/document".padStart(14)}${"byte".padStart(7)}`); for (const [a, g, k, y] of rows) console.log(a.padEnd(28) + String(g).padStart(11) + String(k).padStart(14) + String(y).padStart(7)); // Changing a single field on the same record: copy status "on_shelf" -> "on_loan" const before = Buffer.byteLength(collection.get(TARGET)); const field = Buffer.byteLength(JSON.stringify({ status: "on_loan" })); console.log(`\nsingle-field update (copy status)`); console.log(`${"model".padEnd(28)}${"bytes written".padStart(14)}${"factor".padStart(8)}`); console.log("relational, single row".padEnd(28) + String(field).padStart(14) + "1.0".padStart(8)); console.log("document, field in place".padEnd(28) + String(field).padStart(14) + "1.0".padStart(8)); console.log("key-value, whole value".padEnd(28) + String(before).padStart(14) + (before / field).toFixed(1).padStart(8)); ``` ``` target book 4244: 3 authors, 4 subjects, 5 copies; product 60 path round trip row/document byte relational, four queries 4 13 552 relational, single join 1 60 7840 document, single read 1 1 437 single-field update (copy status) model bytes written factor relational, single row 20 1.0 document, field in place 20 1.0 key-value, whole value 437 21.9 ``` The numbers are of the **measurement** class and are deterministic. The top table shows the relational side's real dilemma. Four separate queries bring back 13 rows and 552 bytes, but cost four round trips. Writing three joins to bring the round trips down to one produces a result of 60 rows: the product of three authors, four subjects, and five copies. The book's title, publication year, and language repeat sixty times, and the bytes carried climb from 552 to 7,840 — fourteen times as much. This is not a flaw in the join but its definition — a relational result set is a flat table, and when three independent multi-valued attributes are brought side by side on the same plane, the product is unavoidable. On the document side, the same record is a single round trip, a single document, 437 bytes. There is no repetition, because the result is not flattened: authors stay an array, subjects stay an array, copies stay an array of documents. The tree the application wants is the tree that sits on disk. The bottom table is the document side's counterpart to the previous lesson's write amplification measurement. Changing a copy's status is 20 bytes of information. The relational engine updates a single row. The document database updates the field in place inside the document — because the store recognizes the field, it does not have to write the whole document back. In the key-value store, the same change means rewriting all 437 bytes of the value: a factor of 21.9. The document model keeps one end of the previous lesson's trade-off — a wide value, a single read — and gets the other end, no write amplification paid, for free. #### Schema Moves to the Read Side This gain has a cost, and the cost is the schema itself. In a relational schema, `NOT NULL` is a write-time rule: a record without the field is rejected, and the reader never has to check whether the field exists. In a document collection there is no such rule; whether the field exists is asked on every read. This is not a design flaw but the natural consequence of an application changing over time. Three schema versions written at different times sit side by side in the same collection: in the first version, the publication year is a top-level `year` field; in the second, it has moved into a `publication` subdocument; in the third, a `digital` field has been added as well. The question does not change — which books were published after 2000. ```js // document/schema.mjs — the load schema flexibility shifts onto the read side. Three // schema versions coexist in the same collection; the same question is asked four // ways. The relational side is built with node:sqlite. import { DatabaseSync } from "node:sqlite"; const BOOKS = 50_000, THRESHOLD = 2000; function version(i) { return i <= 20_000 ? 1 : i <= 40_000 ? 2 : 3; } function document(i) { // v1: year at top level; v2: publication.year; v3: + digital const year = 1960 + (i % 65), common = { book_id: i, title: `Book ${i}` }; if (version(i) === 1) return { ...common, year, language: i % 4 === 0 ? "en" : "tr" }; const b = { ...common, publication: { year, language: i % 4 === 0 ? "en" : "tr" } }; return version(i) === 3 ? { ...b, digital: i % 2 === 0 } : b; } class DocumentStore { #documents = []; #index = new Map(); roundTrips = 0; scanned = 0; add(b) { this.#documents.push(b); } get(b, path) { return path.split(".").reduce((o, k) => (o == null ? undefined : o[k]), b); } buildIndex(path) { const entries = []; for (const b of this.#documents) { const v = this.get(b, path); if (v === undefined) continue; // a document without the field never enters the index for (const x of Array.isArray(v) ? v : [v]) entries.push([x, b.book_id]); } this.#index.set(path, entries.sort((p, q) => p[0] - q[0])); return entries.length; } indexedGreaterThan(path, threshold) { // in a sorted index, the suffix above the threshold is read this.roundTrips += 1; const entries = this.#index.get(path); let a = 0, u = entries.length; while (a < u) { const o = (a + u) >> 1; if (entries[o][0] <= threshold) a = o + 1; else u = o; } this.scanned += entries.length - a; return entries.slice(a).map(([, id]) => id); } scanGreaterThan(predicate) { // no index: every document is checked one by one this.roundTrips += 1; const c = []; for (const b of this.#documents) { this.scanned += 1; if (predicate(b)) c.push(b.book_id); } return c; } reset() { this.roundTrips = 0; this.scanned = 0; } } const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, publication_year INTEGER NOT NULL, language TEXT NOT NULL);`); const insert = db.prepare("INSERT INTO book VALUES (?,?,?,?)"); const store = new DocumentStore(); db.exec("BEGIN"); for (let i = 1; i <= BOOKS; i += 1) { const b = document(i); insert.run(i, b.title, b.year ?? b.publication.year, b.language ?? b.publication.language); store.add(b); } db.exec("COMMIT"); db.exec("CREATE INDEX book_year ON book(publication_year);"); const idxPubYear = store.buildIndex("publication.year"), idxYear = store.buildIndex("year"); console.log(`${BOOKS} books, threshold ${THRESHOLD}; version distribution 1:20000 2:20000 3:10000`); console.log(`index entry count — publication.year: ${idxPubYear}, year: ${idxYear}`); const correct = db.prepare("SELECT book_id FROM book WHERE publication_year > ?").all(THRESHOLD).map((r) => r.book_id); const rows = []; rows.push(["relational, publication_year index", 1, correct.length, correct.length]); store.reset(); let r = store.indexedGreaterThan("publication.year", THRESHOLD); rows.push(["document, publication.year index", store.roundTrips, store.scanned, r.length]); store.reset(); r = [...store.indexedGreaterThan("publication.year", THRESHOLD), ...store.indexedGreaterThan("year", THRESHOLD)]; rows.push(["document, union of two indexes", store.roundTrips, store.scanned, r.length]); store.reset(); r = store.scanGreaterThan((b) => (b.publication?.year ?? b.year) > THRESHOLD); rows.push(["document, defensive scan", store.roundTrips, store.scanned, r.length]); console.log(`\n${"path".padEnd(37)}${"round trip".padStart(11)}${"entries scanned".padStart(16)}` + `${"result".padStart(8)}${"missing".padStart(9)}`); for (const [a, g, t, n] of rows) console.log(a.padEnd(37) + String(g).padStart(11) + String(t).padStart(16) + String(n).padStart(8) + String(correct.length - n).padStart(9)); let rejected = 0, accepted = 0; // 500 records without a year field for (let i = BOOKS + 1; i <= BOOKS + 500; i += 1) { try { insert.run(i, `Book ${i}`, null, "tr"); } catch { rejected += 1; } store.add({ book_id: i, title: `Book ${i}` }); accepted += 1; } console.log(`\n500 records without a year field — relational rejected: ${rejected}, document collection accepted: ${accepted}`); store.reset(); const after = store.scanGreaterThan((b) => (b.publication?.year ?? b.year) > THRESHOLD); console.log(`defensive scan now visits ${store.scanned} documents, result ${after.length}`); ``` ``` 50000 books, threshold 2000; version distribution 1:20000 2:20000 3:10000 index entry count — publication.year: 30000, year: 20000 path round trip entries scanned result missing relational, publication_year index 1 18456 18456 0 document, publication.year index 1 11083 11083 7373 document, union of two indexes 2 18456 18456 0 document, defensive scan 1 50000 18456 0 500 records without a year field — relational rejected: 500, document collection accepted: 500 defensive scan now visits 50500 documents, result 18456 ``` The second row is this lesson's most expensive number. The query does not error, does not return empty, does not run slowly: it returns 11,083 results in a single round trip, and 7,373 books silently disappear. The reason lies in the definition of the index itself — a document without the `publication.year` field never enters the index, so for a query answered from the index, those documents do not exist. This cannot happen in a relational schema, because the absence of the field is rejected at write time; the last row confirms it: the same 500 incomplete records were rejected on the relational side and accepted into the document collection. There are two paths to the correct result, and each has a cost. The union of two indexes gives the correct 18,456 records, but the round trips double, and it requires keeping a separate index for every schema version and the query author knowing every version. A defensive scan gives the correct answer in a single round trip, but it cannot use any index: because the condition chooses between two separate paths, it is not an indexable expression. Entries scanned climb from 18,456 to 50,000 — 2.7 times the result. After the 500 records with a missing field are added, the scan stretches to 50,500 documents; the result does not change. The trade-off fits in one sentence: the document model does not remove schema checking, it moves it from write time to read time. The flexibility gained on the write side comes back on the read side as either a correctness gap, an index multiplication, or a scan. For this load to disappear entirely, the schema has to be put back into the collection; how that is done and what it costs is a later topic in this course. #### Summary - In the document model, a record is a tree whose fields may themselves be documents or arrays; a collection does not require documents to carry the same fields. - The nested book record is 1 round trip and 437 bytes on the document side; on the relational side it is either 4 round trips and 552 bytes, or, with a single join, 60 rows and 7,840 bytes — the product of three multi-valued attributes. - Updating the field in place writes 20 bytes; the same change in the key-value model means rewriting the whole value, a factor of 21.9. - Schema flexibility moves the check to read time: in a three-version collection, a query answered from the `publication.year` index silently misses 7,373 records, while the relational schema rejects the same 500 incomplete records at write time. - Both paths to the correct answer exact a cost: the union of two indexes raises the round trips to 2, and a defensive scan, unable to use an index, raises entries scanned from 18,456 to 50,000. #### Next Step So far, both families have treated the record as a single whole: the key-value store treated the value as an opaque whole, and the document database recognized the tree but still kept the whole document in one place. In both, all of a record's fields sit side by side on disk, so a read for a single field also reads the location where the whole record lives. If a catalog record has forty fields and a query wants only two, the remaining thirty-eight pass through disk as well. The next lesson takes up the family that splits layout by field, and measures three things: the bytes the same query reads under column-family layout, what it means for thousands of columns to gather under a single key, and the cost an append-only write path — in place of in-place modification — exacts on deletion. ### Wide-Column Stores Source: https://academia.sh/en/courses/nosql/wide-column-stores The two-way cost of splitting layout by field: the page count the same data reads under row layout versus column-family layout, the range slice of a wide row that gathers thousands of columns under a single key, the partition key determining the access pattern and the write amplification of serving two patterns at once, and the effect of the append-only write path and the tombstone on space amplification and entries read. In the previous two families, all of a record's fields sat side by side on disk. In the key-value store the value was a single byte sequence; the document database recognized the tree but still kept the document in one place. This had one consequence: a query that wants only two fields reads the location where the whole of that record lives. The wide-column store splits layout at exactly this point. The model is this: a row is named by a key, the row's columns are split into pre-declared **column families**, and the columns of the same family sit together on disk. This lesson measures three things: the effect of layout on bytes read, thousands of columns gathering under a single key, and the write path being append-only in place of in-place modification. #### What Layout Changes The unit of reading is not the byte itself; the store reads the disk page by page. So the answer to the layout question is not "how many fields were read" but **how many pages were touched**. **NS1:** the catalog carries 20,000 records split into four families — identity, publication, circulation, text; the summary field is the largest part of a record. **NS2:** a page is 4,096 bytes, and reading touches the whole page whenever it touches any byte of that page. ```js // column/layout.mjs — the same records serialized to disk in row layout and in // column-family layout, then the 4096-byte pages two queries touch are counted. // The unit of reading is the page; in column-family layout the unit of access is // the family, not the column. const RECORDS = 20_000, PAGE = 4096; const FAMILY = { identity: ["book_id", "title", "author"], publication: ["year", "language", "isbn"], circulation: ["loan_count", "branch_id", "status"], text: ["summary"] }; const book = (i) => ({ book_id: i, title: `Book ${i} ${"a".repeat(30)}`, author: `Author ${i % 500} ${"b".repeat(12)}`, year: 1960 + (i % 65), language: i % 4 === 0 ? "en" : "tr", isbn: `978-${String(1000000000 + i)}`, loan_count: i % 97, branch_id: 1 + (i % 9), status: i % 3 === 0 ? "on_shelf" : "on_loan", summary: `${"c".repeat(280)} ${i}` }); function serialize(rowLayout) { // [start, end] byte range for each field const locations = new Map(); let offset = 0; const place = (i, field) => { const n = Buffer.byteLength(String(book(i)[field])); locations.set(`${i}|${field}`, [offset, offset + n]); offset += n; }; if (rowLayout) { for (let i = 1; i <= RECORDS; i += 1) for (const a of Object.values(FAMILY)) for (const field of a) place(i, field); } else { for (const a of Object.values(FAMILY)) for (let i = 1; i <= RECORDS; i += 1) for (const field of a) place(i, field); } return { locations, size: offset }; } const pageCount = (ranges) => { const s = new Set(); for (const [b, u] of ranges) for (let p = b / PAGE | 0; p <= (u - 1) / PAGE | 0; p += 1) s.add(p); return s.size; }; const rowLayout = serialize(true), familyLayout = serialize(false); console.log(`${RECORDS} records, ${rowLayout.size} bytes total, ${Math.ceil(rowLayout.size / PAGE)} pages`); for (const [name, fields] of Object.entries(FAMILY)) { let n = 0; for (let i = 1; i <= RECORDS; i += 1) for (const field of fields) n += familyLayout.locations.get(`${i}|${field}`)[1] - familyLayout.locations.get(`${i}|${field}`)[0]; console.log(` family ${name.padEnd(11)} ${String(n).padStart(9)} bytes`); } const TARGET = 4244; const S1 = [], A1 = []; // S1: circulation family across all records for (let i = 1; i <= RECORDS; i += 1) for (const field of FAMILY.circulation) { S1.push(rowLayout.locations.get(`${i}|${field}`)); A1.push(familyLayout.locations.get(`${i}|${field}`)); } const S2 = [], A2 = []; // S2: all fields of a single record for (const a of Object.values(FAMILY)) for (const field of a) { S2.push(rowLayout.locations.get(`${TARGET}|${field}`)); A2.push(familyLayout.locations.get(`${TARGET}|${field}`)); } console.log(`\n${"query".padEnd(38)}${"row layout".padStart(17)}${"family layout".padStart(16)}${"ratio".padStart(7)}`); for (const [name, s, a] of [["circulation summary across all books", S1, A1], [`all fields of a single book (${TARGET})`, S2, A2]]) { const ps = pageCount(s), pa = pageCount(a); console.log(name.padEnd(38) + `${ps} pages`.padStart(17) + `${pa} pages`.padStart(16) + (ps / pa).toFixed(2).padStart(7)); } ``` ``` 20000 records, 7666879 bytes total, 1872 pages family identity 1353388 bytes family publication 400000 bytes family circulation 204597 bytes family text 5708894 bytes query row layout family layout ratio circulation summary across all books 1872 pages 51 pages 36.71 all fields of a single book (4244) 1 pages 5 pages 0.20 ``` The numbers are of the **measurement** class: both layouts were genuinely serialized, the pages were genuinely counted. The two rows say the opposite of each other, and the whole model is in these two rows. Getting the circulation summary for all records reads 1,872 pages under row layout, 51 pages under family layout — a difference of roughly thirty-seven times. The reason is a simple ratio: the circulation family is 204,597 bytes of the data, most of the remaining 7.5 MB is summary text, and under row layout every circulation field sits next to a summary text, so that text gets read along with the page. The second row shows the cost. Reading all of a single book's fields is one page under row layout, five pages under family layout — each family lives in a separate place, so assembling the record means going to five separate places. The ratio is 0.20: family layout is five times worse for this query. A layout decision cheapens one class of query while making another more expensive; the boundary of a family has to be the boundary of the fields that are read together. #### The Wide Row The model's second distinguishing trait is that a row's width is unbounded. Thousands, tens of thousands of columns can gather under a single row key, and the column name is not a schema field but **data**: in the library example, every loan is a column under the book row, and the column name is the loan's timestamp. Because columns stay sorted by name inside the row, a time range is sliced in a single request. This is called a **wide row**. ```js // column/wide-row.mjs — loan history kept as a wide row. Columns stay sorted inside // the row, so a range slice is a single request; the same question asked with a // different partition key falls back to a scan. The numbers are independent of the run. const BOOKS = 5_000, POPULAR = 4_000; // the first five books are loaned POPULAR times class WideColumnStore { #rows = new Map(); roundTrips = 0; columns = 0; entries = 0; write(key, column, value) { if (!this.#rows.has(key)) this.#rows.set(key, new Map()); this.#rows.get(key).set(column, value); this.entries += 1; } slice(key, low, high) { // sorted range inside the row: a single request this.roundTrips += 1; const s = this.#rows.get(key) ?? new Map(); const c = []; for (const [column, d] of [...s].sort(([x], [y]) => (x < y ? -1 : 1))) if (column >= low && column < high) { this.columns += 1; c.push(d); } return c; } scan(predicate) { this.roundTrips += 1; const c = []; for (const [a, s] of this.#rows) for (const [column, d] of s) { this.columns += 1; if (predicate(a, column, d)) c.push(d); } return c; } widest() { let e = 0, k = null; for (const [a, s] of this.#rows) if (s.size > e) { e = s.size; k = a; } return [k, e]; } reset() { this.roundTrips = 0; this.columns = 0; } } const bookStore = new WideColumnStore(), memberStore = new WideColumnStore(); for (let i = 1; i <= BOOKS; i += 1) for (let j = 0, n = i <= 5 ? POPULAR : 1 + (i % 97); j < n; j += 1) { const month = 1 + ((i + j) % 12), day = 1 + ((i * 3 + j * 7) % 28), member = 1 + ((i * 13 + j) % 20_000); const date = `2024-${String(month).padStart(2, "0")}-${String(day).padStart(2, "0")}`; bookStore.write(`book:${i}`, `loan|${date}|${j}`, member); // partition key is the book memberStore.write(`member:${member}`, `loan|${date}|${i}|${j}`, i); // partition key is the member } const [widestKey, widestSize] = bookStore.widest(); console.log(`${BOOKS} books, ${bookStore.entries} loan entries; average row ` + `${(bookStore.entries / BOOKS).toFixed(1)} columns, widest row ${widestKey} ${widestSize} columns`); const TARGET = 3, LOW = "loan|2024-03", HIGH = "loan|2024-04"; const report = (name, store, result) => console.log(name.padEnd(36) + String(store.roundTrips).padStart(11) + String(store.columns).padStart(14) + String(result).padStart(7)); console.log(`\n${"path".padEnd(36)}${"round trip".padStart(11)}${"columns read".padStart(14)}${"result".padStart(7)}`); bookStore.reset(); let r = bookStore.slice(`book:${TARGET}`, LOW, HIGH); report("book partition, range slice", bookStore, r.length); bookStore.reset(); r = bookStore.slice(`book:${TARGET}`, "loan|", "loan}"); report("book partition, whole row", bookStore, r.length); memberStore.reset(); r = memberStore.scan((a, column, d) => column.startsWith(LOW) && d === TARGET); report("member partition, same question", memberStore, r.length); console.log(`\nboth access patterns at once: ${bookStore.entries} + ${memberStore.entries} = ` + `${bookStore.entries + memberStore.entries} entries written, write amplification ` + `${((bookStore.entries + memberStore.entries) / bookStore.entries).toFixed(1)}`); ``` ``` 5000 books, 263867 loan entries; average row 52.8 columns, widest row book:1 4000 columns path round trip columns read result book partition, range slice 1 333 333 book partition, whole row 1 4000 4000 member partition, same question 1 263867 333 both access patterns at once: 263867 + 263867 = 527734 entries written, write amplification 2.0 ``` A month's loans are retrieved by reading 333 columns out of a four-thousand-column row: because the columns are sorted, the store descends to the start of the range and walks to the end, never touching the rest of the row. When the whole row is requested, columns read climb to 4,000 — a wide row is not an advantage by itself, it is an advantage when sliced correctly. The third row shows how decisive the partition key is. When the same data is partitioned by member key, a book's loans are not gathered inside any single row, and the question falls to a scan of 263,867 columns. The known remedy is a familiar decision: the same data is written a second time under a second partition key — the Scaling the Data Layer course measured this decision by request count; its counterpart here is on the write side, and it is exactly double. The wide row's own limit sits in this table too. Because the row is the unit of partitioning, a single row cannot grow without bound: the widest row carries 4,000 columns while the average row carries 52.8. A row that grows without bound is exactly the hot spot named in the Scaling the Data Layer course; the fix is adding a time bucket to the row key. #### The Append-Only Write Path This family's write performance comes not from layout but from the write path. A write never modifies in place: every write is a fresh entry, appended to the sequence. When the in-memory table fills up, it is flushed into an immutable file and never touched again. A delete is a write too — a **tombstone** is placed over the record. A read scans the files newest to oldest and returns the first version it finds. Dropping obsolete versions and tombstones is the job of a separate operation — **compaction**. ```js // column/append-only.mjs — the append-only write path: every write is a fresh entry, // a delete is a tombstone. When the memory table fills up it is flushed to an // immutable file. Reads scan files newest to oldest. Compaction drops obsolete // versions and tombstones. const FILE_SIZE = 25_000, TOMBSTONE = Symbol("tombstone"); class AppendOnlyStore { #memory = new Map(); #files = []; entriesWritten = 0; filesVisited = 0; entriesRead = 0; #flush() { if (this.#memory.size >= FILE_SIZE) { this.#files.push(this.#memory); this.#memory = new Map(); } } write(k, d) { this.#memory.set(k, d); this.entriesWritten += 1; this.#flush(); } delete(k) { this.write(k, TOMBSTONE); } #newestFirst() { return [this.#memory, ...this.#files.slice().reverse()]; } // newest to oldest read(k) { const sources = this.#newestFirst(); for (const s of sources) { this.filesVisited += 1; if (s.has(k)) { this.entriesRead += 1; const d = s.get(k); return d === TOMBSTONE ? undefined : d; } } return undefined; } scan() { const seen = new Set(), c = []; for (const s of this.#newestFirst()) { this.filesVisited += 1; for (const [k, d] of s) { this.entriesRead += 1; if (seen.has(k)) continue; seen.add(k); if (d !== TOMBSTONE) c.push(k); } } return c; } compact() { const merged = new Map(); for (const s of [...this.#files, this.#memory]) for (const [k, d] of s) merged.set(k, d); for (const [k, d] of merged) if (d === TOMBSTONE) merged.delete(k); this.#files = []; this.#memory = new Map(); for (const [k, d] of merged) this.write(k, d); this.entriesWritten = merged.size; return merged.size; } status() { return [this.#files.length + 1, this.entriesWritten]; } reset() { this.filesVisited = 0; this.entriesRead = 0; } } const store = new AppendOnlyStore(), N = 100_000; for (let i = 1; i <= N; i += 1) store.write(`loan:${i}`, { book: i % 5000, return: null }); for (let i = 1; i <= N; i += 1) if (i % 5 < 2) store.write(`loan:${i}`, { book: i % 5000, return: "2024-06-01" }); for (let i = 1; i <= N; i += 1) if (i % 5 === 4) store.delete(`loan:${i}`); const [files, entries] = store.status(); const live = N - Math.floor(N / 5); console.log(`${N} records, ${entries} entries written, ${live} live records; ` + `${files} files, space amplification ${(entries / live).toFixed(2)}`); const measure = (name, task) => { store.reset(); const r = task(); console.log(name.padEnd(30) + String(store.filesVisited).padStart(15) + String(store.entriesRead).padStart(15) + String(r).padStart(9)); }; console.log(`\n${"read".padEnd(30)}${"files visited".padStart(15)}${"entries read".padStart(15)}${"result".padStart(9)}`); measure("recently updated key", () => (store.read("loan:99996") ? "found" : "missing")); measure("key never touched", () => (store.read("loan:2") ? "found" : "missing")); measure("deleted key", () => (store.read("loan:99994") ? "found" : "missing")); measure("key never written", () => (store.read("loan:999999") ? "found" : "missing")); measure("scanning all records", () => store.scan().length); const after = store.compact(); console.log(`\nafter compaction: ${after} entries, ${store.status()[0]} files, ` + `space amplification ${(after / live).toFixed(2)}`); store.reset(); const t = store.scan(); console.log(`the same scan now reads ${store.entriesRead} entries, result ${t.length}`); ``` ``` 100000 records, 160000 entries written, 80000 live records; 7 files, space amplification 2.00 read files visited entries read result recently updated key 2 1 found key never touched 7 1 found deleted key 1 1 missing key never written 7 0 missing scanning all records 7 160000 80000 after compaction: 80000 entries, 4 files, space amplification 1.00 the same scan now reads 80000 entries, result 80000 ``` The write side is cheap, and this table shows why: no write required a read, no file was modified. The cost is on the read side, and in space. For 80,000 live records, 160,000 entries sit on disk; space amplification is 2.00. The 20,000 deleted records are still there — a tombstone does not free space, it fills it. The read rows show where the cost is distributed. A recently updated key is found in 2 files. A key untouched for a long time visits 7 files, because it lives in the oldest one, and the only way to know it is absent from the newer ones is to check all of them. The most expensive is a key that was never written: all 7 files are scanned and the result is absent. A deleted key, on the other hand, finishes in a single file — the tombstone is the newest entry, and the read stops there. The scan row carries the tombstone's real cost: 160,000 entries are read for 80,000 live records. Compaction equalizes these two numbers — entries drop to 80,000, space amplification to 1.00, file count from 7 to 4, and the same scan now reads 80,000 entries. Compaction itself writes all the data once more; so the append-only write path does not cheapen the writing, it **defers** it to the background. #### Summary - In the wide-column model, a row is named by a key, columns are split into column families, and the columns of the same family sit together on disk. - Layout cuts two ways: the circulation summary reads 1,872 pages under row layout, 51 under family layout (36.7 times); all of a single record's fields is 1 page against 5. - In a wide row, the column name is data and the columns are sorted: a month's 333 loans are sliced from a 4,000-column row in a single request, and the same question falls to a 263,867-column scan under a different partition key. - Serving two access patterns at once means writing the same data twice: 263,867 entries climb to 527,734, a write amplification of 2.0. - In the append-only write path, no write requires a read; its cost is a space amplification of 2.00 and a key that was never written visiting 7 files. A tombstone does not free space. - Compaction brings entries from 160,000 down to 80,000 and space amplification to 1.00; in exchange it writes all the data once more. #### Next Step All three families so far shared the same assumption: the subject of the query is the record itself. If the key is known, the record arrives; if there is a condition on a field, an index is built; if a range is wanted, the layout is chosen accordingly. In the library data, though, some questions concern not the records but **the links between records**: the distance between two members through the books they have both borrowed, the authors reachable by walking from an author's collaborators. In the relational model this link is a join table, and every step means another join. The next lesson takes up the family that makes the link itself a first-class object, and measures this: the record count the adjacency list and the join table each touch for the same question, and how that count grows as depth increases. ### Graph Databases Source: https://academia.sh/en/courses/nosql/graph-databases The measured cost of making the link itself a record: the record count the same relationship query touches in the join table versus the adjacency list, whether that count grows with depth like a path count or like a node count, what step-by-step deduplication costs on the relational side, and the gain of two-ended traversal on the shortest-chain question when depth is not known in advance. In the previous three families, the subject of the query was the record itself: if the key is known, the value arrives; if a field carries a condition, an index is built; if a range is wanted, the layout follows it. In the library data, though, some questions concern not the records but the links between them: the books also borrowed by people who borrowed this book, the shortest shared reading chain between two members. In the relational model this link is a join table, and every step is another join; the graph database makes the link a first-class object instead. This lesson builds the model with `node`, measures by depth the record count both models touch for the same question, and counts traversal's cost when depth is not known in advance. #### The Link Itself Is a Record The model is a **property graph**: data consists of nodes and edges, and every node — and **every edge** — carries its own properties. In the library, the nodes are books and members; a loan is not a row but an edge, and the loan's date and duration sit on that edge. Access is different too: a node's neighbors are a list kept beside the node itself — the **adjacency list**. Walking from a node to its neighbors is **traversal**, the concept the Data Structures course covers for trees and graphs, applied here to nodes and edges. **NS3:** the data is generated from 20,000 members, 5,000 books, and 2–12 loans per member; book selection follows a skewed distribution — a few books borrowed heavily, most very little. The generator is self-written, its seed visible in the code. **NS4:** the loan edge is undirected, walked the same way from either side. ```js // graph/model.mjs — property graph: nodes and edges, both carrying properties. The // adjacency list is a real data structure; an edge property sits on the edge itself, // not in a separate table. The generator is exported: the next blocks build the // same set. const SEED = 20240517, MEMBERS = 20_000, BOOKS = 5_000; function* stream(t) { let x = t >>> 0; for (;;) { x = (Math.imul(x, 1103515245) + 12345) >>> 0; yield x / 4294967296; } } export function loans() { // deterministic loan list, seed above const r = stream(SEED), list = []; for (let u = 1; u <= MEMBERS; u += 1) { const n = 2 + Math.floor(r.next().value * 11), seen = new Set(); for (let j = 0; j < n; j += 1) { const p = r.next().value, book = 1 + Math.floor(BOOKS * p * p); // skewed popularity if (seen.has(book)) continue; seen.add(book); list.push({ member: u, book, day: 1 + Math.floor(r.next().value * 364), duration: 3 + Math.floor(r.next().value * 40) }); } } return list; } class PropertyGraph { #nodes = new Map(); #adjacency = new Map(); node(id, properties) { this.#nodes.set(id, properties); this.#adjacency.set(id, []); } edge(a, b, properties) { // undirected: written to both adjacency lists this.#adjacency.get(a).push({ target: b, ...properties }); this.#adjacency.get(b).push({ target: a, ...properties }); } properties(id) { return this.#nodes.get(id); } neighbors(id, predicate) { const l = this.#adjacency.get(id) ?? []; return predicate ? l.filter(predicate) : l; } degree(id) { return (this.#adjacency.get(id) ?? []).length; } } if (import.meta.main) { // measurements print when run directly const g = new PropertyGraph(), TARGET = "book:2500", data = loans(); for (let k = 1; k <= BOOKS; k += 1) g.node(`book:${k}`, { type: "book", title: `Book ${k}`, year: 1960 + (k % 65) }); for (let u = 1; u <= MEMBERS; u += 1) g.node(`member:${u}`, { type: "member", name: `Member ${u}`, branch: 1 + (u % 9) }); for (const o of data) g.edge(`member:${o.member}`, `book:${o.book}`, { type: "loan", day: o.day, duration: o.duration }); let highest = null, e = 0, total = 0; for (let k = 1; k <= BOOKS; k += 1) { const d = g.degree(`book:${k}`); total += d; if (d > e) { e = d; highest = `book:${k}`; } } console.log(`${BOOKS + MEMBERS} nodes (${BOOKS} books + ${MEMBERS} members), ${data.length} edges (loans)`); console.log(`average degree: book ${(total / BOOKS).toFixed(1)}, member ${(data.length / MEMBERS).toFixed(1)}; ` + `highest ${highest} ${e}`); const all = g.neighbors(TARGET), long = g.neighbors(TARGET, (k) => k.duration > 21); console.log(`\n${TARGET} (${g.properties(TARGET).title}, ${g.properties(TARGET).year}): adjacency list ${all.length} edges, ` + `edges with duration>21 via the edge property ${long.length}`); console.log(` first three edges: ${all.slice(0, 3).map((edge) => `${edge.target}(day ${edge.day}, duration ${edge.duration})`).join(", ")}`); } ``` ``` 25000 nodes (5000 books + 20000 members), 139504 edges (loans) average degree: book 27.9, member 7.0; highest book:1 1825 book:2500 (Book 2500, 1990): adjacency list 22 edges, edges with duration>21 via the edge property 11 first three edges: member:202(day 157, duration 19), member:3845(day 73, duration 25), member:4394(day 21, duration 11) ``` The numbers are of the **measurement** class. The edge property lives on the edge itself, not in a side table: loans over 21 days drop from 22 edges to 11 with a single filter over the adjacency list — an edge, too, can carry a condition during traversal. The degree distribution is skewed: average degree on a book node is 27.9, while the highest is 1,825 — a number that returns at the end of the lesson. There is no advantage here yet. Finding the borrowers of a book means reading 22 edges in the graph; in the relational model, the same job is an indexed search on `book_id` reading 22 rows. **At the first degree, the two models do the same work.** The difference begins at the second step. #### The Same Question, Two Models The question is this: the books also borrowed by the members who borrowed a given book — and deeper degrees of the same question. In the relational model this is the loan table joined against itself repeatedly, and every degree adds another join; in the graph, the same question is one more step through the adjacency list. The measure on both sides is the interim record touched, and it is cumulative: the rows each layer produces in the join, the edges crossed in the traversal. **NS5:** the relational side is indexed on `book_id` and `member_id`; the join does not perform a full scan, so the measured difference does not come from a missing index. ```js // graph/two-models.mjs — the same question in two models: a join table on the // relational side (node:sqlite, two indexes), traversal over the adjacency list on // the graph side. Intermediate records touched are counted cumulatively on both // sides. All numbers are independent of the run. import { DatabaseSync } from "node:sqlite"; import { loans } from "./model.mjs"; // same data set, same seed const TARGET = 2500, data = loans(); const db = new DatabaseSync(":memory:"); db.exec("CREATE TABLE loan(member_id INT, book_id INT, day INT, duration INT)"); const insert = db.prepare("INSERT INTO loan VALUES(?,?,?,?)"); db.exec("BEGIN"); for (const o of data) insert.run(o.member, o.book, o.day, o.duration); db.exec("COMMIT"); db.exec("CREATE INDEX i_book ON loan(book_id)"); db.exec("CREATE INDEX i_member ON loan(member_id)"); function join(d) { // d-layer join; COUNT(*) = number of d-step paths let sql = `SELECT COUNT(*) interim, COUNT(DISTINCT o${d}.${d % 2 ? "member_id" : "book_id"}) uniq FROM loan o1`; for (let i = 2; i <= d; i += 1) sql += i % 2 === 0 ? ` JOIN loan o${i} ON o${i}.member_id = o${i - 1}.member_id` : ` JOIN loan o${i} ON o${i}.book_id = o${i - 1}.book_id`; return db.prepare(`${sql} WHERE o1.book_id = ?`).get(TARGET); } const adjacency = new Map(); // adjacency list: node -> neighbor array const link = (a, b) => { if (!adjacency.has(a)) adjacency.set(a, []); adjacency.get(a).push(b); }; for (const o of data) { link(`k:${o.book}`, `u:${o.member}`); link(`u:${o.member}`, `k:${o.book}`); } function traverse(d) { // layer by layer; each layer is a set of unique nodes let layer = new Set([`k:${TARGET}`]), nodes = 0, edges = 0; for (let i = 1; i <= d; i += 1) { const next = new Set(); for (const v of layer) { nodes += 1; for (const w of adjacency.get(v)) { edges += 1; next.add(w); } } layer = next; } return { nodes, edges, unique: layer.size }; } console.log(`${data.length} loan records; start book:${TARGET}, degree ${adjacency.get(`k:${TARGET}`).length}\n`); console.log("depth join rows nodes visited edges traversed unique result"); let cumulative = 0; for (const d of [1, 2, 3, 4, 5]) { const b = join(d), c = traverse(d); cumulative += b.interim; if (b.uniq !== c.unique) throw new Error(`results diverged: ${b.uniq} != ${c.unique}`); console.log(String(d).padStart(5) + String(cumulative).padStart(19) + String(c.nodes).padStart(23) + String(c.edges).padStart(16) + String(c.unique).padStart(14)); } let frontier = new Set([TARGET]), interimRows = 0; // step-by-step deduplication on the relational side for (let i = 1; i <= 5; i += 1) { const outField = i % 2 ? "member_id" : "book_id", inField = i % 2 ? "book_id" : "member_id"; const r = db.prepare(`SELECT ${outField} a FROM loan WHERE ${inField} IN (${[...frontier].map(() => "?").join(",")})`).all(...frontier); interimRows += r.length; frontier = new Set(r.map((x) => x.a)); } console.log(`\nstep-by-step deduplicated join: ${interimRows} rows, ${frontier.size} unique result, five separate statements`); ``` ``` 139504 loan records; start book:2500, degree 22 depth join rows nodes visited edges traversed unique result 1 22 1 22 22 2 218 23 218 166 3 13200 189 11219 8295 4 122105 8484 78082 4996 5 14190839 13480 217544 20000 step-by-step deduplicated join: 217544 rows, 20000 unique result, five separate statements ``` The two models' results are identical at every depth; the code checks this on every row and would throw if they diverged. What is not the same is the cost. At the first and second degree, both sides touch the same number: 22 and 218. The divergence begins at the third degree (13,200 against 11,219), widens at the fourth (122,105 against 78,082), and jumps to a different scale at the fifth: **14,190,839 rows against 217,544 edges**, sixty-five times. The reason fits in one sentence: **a join layer counts paths, a traversal layer counts nodes.** If a book is reached by a hundred different paths, the join produces its neighbors a hundred times; a traversal puts that book into the layer's set once and looks at its neighbors once. The `DISTINCT` at the end cleans up only the last step; it does not spare the interim rows. The last row shows where the boundary lies. The relational engine can imitate a traversal: deduplicating the interim result at every step and passing only the unique set forward reads 217,544 rows — exactly the edge count the traversal crosses. What is missing is not a way of storing data but a shape of query: the query stops being a single statement and splits into five, one more for every added degree. This is exactly what the graph store does; only the query author is spared the work. The Scaling the Data Layer course measured the same contrast by request count; the measure here is records touched. The table's last column is traversal's own limit: at the fourth degree the result is 4,996 books, at the fifth it is 20,000 members — nearly the whole catalog and the whole member roll. The question loses its meaning before it gets expensive. #### The Shortest Chain In some questions, depth is not known in advance: how many steps is the shortest shared reading chain between two members? This question cannot be written with a fixed number of joins, because how many joins to write is the answer itself. Traversal has two forms: walking from one end, or walking from both ends and meeting in the middle. ```js // graph/shortest-chain.mjs — the shortest shared reading chain between two members: // depth is not known in advance. Traversal runs one-ended and two-ended; nodes // visited are counted. import { loans } from "./model.mjs"; // same data set, same seed const adjacency = new Map(); const link = (a, b) => { if (!adjacency.has(a)) adjacency.set(a, []); adjacency.get(a).push(b); }; for (const o of loans()) { link(`k:${o.book}`, `u:${o.member}`); link(`u:${o.member}`, `k:${o.book}`); } function oneEnded(a, b) { // on a shortest path a node is never visited twice const distance = new Map([[a, 0]]); let layer = [a], nodes = 0, edges = 0, mostEdges = [null, 0]; const stop = () => ({ length: distance.get(b), nodes, edges, mostEdges }); while (layer.length) { const next = []; for (const v of layer) { nodes += 1; const d = adjacency.get(v).length; if (d > mostEdges[1]) mostEdges = [v, d]; for (const w of adjacency.get(v)) { edges += 1; if (distance.has(w)) continue; distance.set(w, distance.get(v) + 1); if (w === b) return stop(); next.push(w); } } layer = next; } return null; } function twoEnded(a, b) { // each round the smaller frontier is expanded const distA = new Map([[a, 0]]), distB = new Map([[b, 0]]); let frontA = [a], frontB = [b], nodes = 0, edges = 0; while (frontA.length && frontB.length) { const forward = frontA.length <= frontB.length; const layer = forward ? frontA : frontB, mine = forward ? distA : distB, other = forward ? distB : distA, next = []; for (const v of layer) { nodes += 1; for (const w of adjacency.get(v)) { edges += 1; if (mine.has(w)) continue; mine.set(w, mine.get(v) + 1); if (other.has(w)) return { length: mine.get(w) + other.get(w), nodes, edges }; next.push(w); } } if (forward) frontA = next; else frontB = next; } return null; } console.log(`${"member pair".padEnd(29)}${"chain".padStart(7)}${"one-ended nodes".padStart(17)}${"two-ended nodes".padStart(17)}${"gain".padStart(8)}`); for (const [a, b] of [[7, 19_842], [1_337, 15_004], [42, 9_999]]) { const t = oneEnded(`u:${a}`, `u:${b}`), i = twoEnded(`u:${a}`, `u:${b}`); if (t.length !== i.length) throw new Error(`lengths diverged: ${t.length} != ${i.length}`); console.log(`member:${a} — member:${b}`.padEnd(29) + String(t.length).padStart(7) + String(t.nodes).padStart(17) + String(i.nodes).padStart(17) + `${(t.nodes / i.nodes).toFixed(1)}x`.padStart(8)); } const t7 = oneEnded("u:7", "u:19842"); // the node contributing the most edges to the search const [node, degree] = t7.mostEdges; console.log(`\nthe node contributing the most edges in the first search is ${node}, degree ${degree}: of the ` + `${t7.edges} edges traversed, ${(100 * degree / t7.edges).toFixed(1)}% passed through this node alone`); ``` ``` member pair chain one-ended nodes two-ended nodes gain member:7 — member:19842 4 426 11 38.7x member:1337 — member:15004 2 8 2 4.0x member:42 — member:9999 4 227 7 32.4x the node contributing the most edges in the first search is k:3, degree 611: of the 9477 edges traversed, 6.4% passed through this node alone ``` Both walks find the same length, and the code checks this on every pair. Nodes visited, though, are 426 against 11 and 227 against 7 for four-step chains — thirty to forty times. The reason is structural: each layer grows by roughly the average degree over the last one, so cost concentrates in the final layer. Walking from both ends turns four steps into two plus two, and two small layers sum to less than one large layer. When the chain is two steps, the gain drops to 4.0 times: there is no depth left to split. The last row shows traversal's own cost. The node contributing the most edges to the search is a book with degree 611, alone producing 6.4% of the 9,477 edges crossed. The skew of the degree distribution turns into cost here: access is cheap in this family, but **every traversal through a high-degree node does work equal to that node's degree** — the catalog's highest degree is 1,825, paid in a single step the moment that node is visited. The fix lies outside the model: filter on the edge's type or property, or exclude that node from the traversal. #### Summary - In a property graph, data is nodes and edges, properties sit on both, and the adjacency list is a real data structure kept beside the node: a loan's duration is an edge property, and 11 of 22 edges that exceed 21 days are separated with a single filter. - At the first and second degree, both models touch the same number (22 and 218); the divergence begins at the third degree (13,200 against 11,219), becomes 122,105 against 78,082 at the fourth, and reaches 14,190,839 rows against 217,544 edges at the fifth — sixty-five times. - The difference comes not from how the data is stored but from the shape of the query: a join layer counts paths, a traversal layer counts nodes. The same job drops to 217,544 rows on the relational side if deduplicated step by step, but the query stops being a single statement and becomes five separate ones. - Questions whose depth is not known in advance cannot be written with a fixed number of joins. In the shortest chain, two-ended traversal visits 38.7 and 32.4 times fewer nodes than one-ended; when the chain is short, the gain drops to 4.0 times. - The cost of traversal depends on the degree distribution: 6.4% of the 9,477 edges crossed pass through a single node of degree 611, while the highest degree in the catalog is 1,825. #### Next Step All four families so far share one thing: the data has an identity — a key, a document id, a row key, a node id — and every query starts from an identity or arrives at one. In the library's operational data, though, there is a stream with no identity: shelf temperature measured every minute, an hourly door-crossing counter, a per-minute count of loan transactions. A single measurement is never asked for alone; questions run over ranges, data is only appended and never updated, and aging data is not kept at full resolution forever. The next lesson measures what this access pattern does to a store: the block a time-ordered layout reads for a range query, the space sorted measurements gain in compression, and which question a retention policy makes impossible to answer. ### Time Series Stores Source: https://academia.sh/en/courses/nosql/time-series-stores The cost of storing timestamped measurement data under two layouts: the stored-byte difference between a full timestamp per row and a base timestamp per segment with delta coding and block compression, the segment and entry count a range query scans reversing as the range narrows, and a retention policy aligned to the segment boundary bringing entries touched down to zero. In the four families so far, the record itself was an entity — a book, a member, a loan — and the last model made the link itself a first-class object. A part of the library's data, though, is neither entity nor link: the temperature of shelf zones, the count a turnstile records, the value of a loan counter. These are **time series** — timestamped measurements belonging to a source, arriving in sequence. This data's load profile is unlike the other families'. Writing is append-only; a past measurement is almost never updated. Reading targets not a single record but a range. And the data has an expiration date: a minute-level measurement from three months ago enters no question at all. The lesson measures the store-side counterpart of these three properties: the effect of layout on bytes stored, the unit a range query scans, and the cost of a retention policy. #### Two Layouts, the Same Measurements A measurement row is small: a source id, a timestamp, and a single number — the timestamp can be larger than the value it carries. The time series store's first decision follows from this: measurements are stored not one by one but in **segments**; each segment is one time bucket for one source, writing its base timestamp once and keeping the rest as deltas. **NS25:** twelve shelf zones each carry a temperature sensor, each writing a measurement every 60 seconds, and thirty days of data are examined. **NS26:** in row layout, a measurement carries a 2-byte source id, an 8-byte timestamp, and an 8-byte value. **NS6:** the segment unit is a source–day pair. ```js // time/layout.mjs — the same measurement series serialized in two layouts: (a) a full // timestamp + value per row, (b) a base timestamp per segment + delta coding + block // compression. What is counted is bytes stored; the compression is genuinely run, the // seed is visible. import { deflateSync } from "node:zlib"; const SERIES = 12, DAYS = 30, INTERVAL = 60_000, T0 = Date.UTC(2024, 5, 1); const POINTS = 86_400_000 / INTERVAL; // entries per segment: daily measurement count let seed = 20240601; // visible seed; the generator is self-written const noise = () => ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648 - 0.5); const measurement = (s, i) => // integer in tenths of a degree: 18.4 -> 184 Math.round((18 + s * 0.25 + 3 * Math.sin((i / POINTS) * 2 * Math.PI) + noise() * 0.6) * 10); const varint = (n) => { const bytes = []; let x = ((n << 1) ^ (n >> 31)) >>> 0; // zigzag + varint do { let y = x & 0x7f; x >>>= 7; if (x) y |= 0x80; bytes.push(y); } while (x); return bytes; }; const rowLayout = Buffer.alloc(SERIES * DAYS * POINTS * 18); // 2 bytes series + 8 timestamp + 8 value let offset = 0, rawBytes = 0, segmentBytes = 0, segmentCount = 0; for (let s = 0; s < SERIES; s += 1) for (let g = 0; g < DAYS; g += 1) { const body = []; // segment body: varint of the diffs let previousDelta = 0, previousValue = null; for (let i = 0; i < POINTS; i += 1) { const t = T0 + g * 86_400_000 + i * INTERVAL, d = measurement(s, g * POINTS + i); rowLayout.writeUInt16LE(s, offset); rowLayout.writeDoubleLE(t, offset + 2); rowLayout.writeDoubleLE(d / 10, offset + 10); offset += 18; if (previousValue === null) { body.push(...varint(d)); previousValue = d; continue; } body.push(...varint(INTERVAL - previousDelta)); previousDelta = INTERVAL; // delta of the timestamp delta body.push(...varint(d - previousValue)); previousValue = d; // value delta } const header = Buffer.alloc(14); // base timestamp + series + entry count header.writeDoubleLE(T0 + g * 86_400_000, 0); header.writeUInt16LE(s, 8); header.writeUInt32LE(POINTS, 10); rawBytes += header.length + body.length; segmentBytes += header.length + deflateSync(Buffer.from(body)).length; segmentCount += 1; } const N = SERIES * DAYS * POINTS; console.log(`${SERIES} series x ${DAYS} days x ${POINTS} measurements = ${N} measurements; ` + `${segmentCount} segments, ${POINTS} entries per segment`); console.log(`\n${"layout".padEnd(38)}${"bytes".padStart(11)}${"per measurement".padStart(17)}${"factor".padStart(7)}`); for (const [name, b] of [["full timestamp + value per row", rowLayout.length], ["segment, delta coding only", rawBytes], ["segment, delta + block compression", segmentBytes]]) console.log(name.padEnd(38) + String(b).padStart(11) + (b / N).toFixed(2).padStart(17) + (rowLayout.length / b).toFixed(2).padStart(7)); ``` ``` 12 series x 30 days x 1440 measurements = 518400 measurements; 360 segments, 1440 entries per segment layout bytes per measurement factor full timestamp + value per row 9331200 18.00 1.00 segment, delta coding only 1042560 2.01 8.95 segment, delta + block compression 329013 0.63 28.36 ``` The numbers are of the **measurement** class: both layouts were genuinely serialized, the compression genuinely run. The same 518,400 measurements are 9,331,200 bytes under row layout, 329,013 bytes under the segmented layout: 18 bytes per measurement against 0.63 bytes, twenty-eight times. The middle row separates out where the gain comes from. Delta coding alone, without block compression, brings this down to 2.01 bytes per measurement — nine times. The reason is the shape of the data: because the measurement interval is fixed, consecutive timestamps carry the same delta every time, so the delta of the delta is zero and fits in a single byte, and the value delta is a small integer too — an eight-byte timestamp and an eight-byte value collapse to two. Block compression adds another factor of three on top: a repeating sequence of zeros and small deltas is exactly what a compressor works most efficiently on. The cost sits inside that same decision. A segment is a compressed block; no single measurement inside it can be reached without decompressing the whole segment — the **unit of access is not the measurement, it is the segment**. And the gain depends on the data being ordered and regularly spaced: if measurements arrive late and out of order, the delta of the delta stops being zero and the segment bloats. #### The Time Range Query This family's queries almost always carry a time range. Row layout is a single array sorted by time: the start of the range is found by binary search, but the measurements of **every source** inside the window are read. In segment layout, the metadata — source id and base timestamp — eliminates segments that do not intersect the query without ever opening them. ```js // time/range.mjs — the same measurement set is queried in two layouts. Row layout is // a single array sorted by time: the range is found by binary search, and every // series inside the window is scanned. Segment layout eliminates via metadata // (series, base timestamp), but an opened segment is resolved whole. The numbers // are independent of the run. const SERIES = 12, DAYS = 30, INTERVAL = 60_000, T0 = Date.UTC(2024, 5, 1), POINTS = 1440; const series = [], timestamps = []; // row layout: sorted by time for (let g = 0; g < DAYS; g += 1) for (let i = 0; i < POINTS; i += 1) for (let s = 0; s < SERIES; s += 1) { series.push(s); timestamps.push(T0 + g * 86_400_000 + i * INTERVAL); } const segments = []; // segment layout: segment = (series, day) for (let s = 0; s < SERIES; s += 1) for (let g = 0; g < DAYS; g += 1) segments.push({ series: s, base: T0 + g * 86_400_000, end: T0 + (g + 1) * 86_400_000, entries: POINTS }); function rowQuery(s, low, high) { // binary search + window scan let a = 0, b = timestamps.length; while (a < b) { const o = (a + b) >> 1; if (timestamps[o] < low) a = o + 1; else b = o; } let scanned = 0, result = 0; for (let i = a; i < timestamps.length && timestamps[i] < high; i += 1) { scanned += 1; if (s === null || series[i] === s) result += 1; } return { opened: 0, scanned, result }; } function segmentQuery(s, low, high) { // eliminate via metadata, then open the segment let opened = 0, scanned = 0, result = 0; for (const b of segments) { if (s !== null && b.series !== s) continue; if (b.end <= low || b.base >= high) continue; opened += 1; scanned += b.entries; // an opened segment is resolved whole for (let i = 0; i < b.entries; i += 1) { const t = b.base + i * INTERVAL; if (t >= low && t < high) result += 1; } } return { opened, scanned, result }; } const JUNE_12 = T0 + 11 * 86_400_000; const queries = [["shelf 3, June 12 (full day)", 3, JUNE_12, JUNE_12 + 86_400_000], ["all shelves, June 12-14", null, JUNE_12, JUNE_12 + 3 * 86_400_000], ["shelf 3, June 12 09:00-10:00", 3, JUNE_12 + 9 * 3_600_000, JUNE_12 + 10 * 3_600_000], ["shelf 3, the whole month", 3, T0, T0 + DAYS * 86_400_000]]; console.log(`row layout ${timestamps.length} entries; segment layout ${segments.length} segments`); console.log(`\n${"query".padEnd(35)}${"row: scanned".padStart(15)}${"segments".padStart(9)}` + `${"segment: scanned".padStart(17)}${"result".padStart(8)}`); for (const [name, s, low, high] of queries) { const x = rowQuery(s, low, high), y = segmentQuery(s, low, high); if (x.result !== y.result) throw new Error("the two paths did not give the same result"); console.log(name.padEnd(35) + String(x.scanned).padStart(15) + String(y.opened).padStart(9) + String(y.scanned).padStart(17) + String(x.result).padStart(8)); } ``` ``` row layout 518400 entries; segment layout 360 segments query row: scanned segments segment: scanned result shelf 3, June 12 (full day) 17280 1 1440 1440 all shelves, June 12-14 51840 36 51840 51840 shelf 3, June 12 09:00-10:00 720 1 1440 60 shelf 3, the whole month 518400 30 43200 43200 ``` Three of the four rows favor segment layout; the model's limit is in the fourth. A single day for a single shelf scans 17,280 entries under row layout; under segment layout a single segment is opened and 1,440 entries are read. The ratio is exactly the source count: in the sorted array, one shelf's measurements interleave with the other eleven's, and that interleaving remains no matter how narrow the range. The same coefficient holds across the whole month for the same shelf: 518,400 entries scanned against 30 segments and 43,200 entries. The second row shows the case where segmenting gains nothing: when the query wants every shelf, there is no metadata left to eliminate on, both paths read 51,840 entries, and the segment path only adds the work of opening 36 segments. The third row carries the cost. A one-hour window scans 720 entries under row layout; under segment layout the same question resolves 1,440 entries, because the segment opened is a full day and a compressed block cannot be partially decompressed. The result is 60 measurements either way. **A segment's duration is the range query's smallest unit of reading**: the larger the segment, the greater the compression gain, and the greater the waste for a narrow-range query too. If narrow ranges are asked often, the remedy is storing the measurement a second time at a coarser resolution — this decision is called **downsampling**, and it is measured in the Case Studies course. #### Retention Policy The last point where time series data departs from the others is deletion. A book record is never deleted; a minute-level measurement stops entering any question past a certain age, and a **retention** policy drops it. The question is what this dropping costs. **NS27:** the retention period is seven days. ```js // time/retention.mjs — the retention policy applied in two layouts. In row layout, // every expired record is dropped one by one. In segment layout, a segment that has // fully expired is dropped as a unit; only a segment straddling the boundary is // rewritten. The numbers are independent of the run. const SERIES = 12, DAYS = 30, INTERVAL = 60_000, T0 = Date.UTC(2024, 5, 1), POINTS = 1440; const NOW = T0 + DAYS * 86_400_000; const timestamps = []; // row layout: sorted by time for (let g = 0; g < DAYS; g += 1) for (let i = 0; i < POINTS; i += 1) for (let s = 0; s < SERIES; s += 1) timestamps.push(T0 + g * 86_400_000 + i * INTERVAL); const segments = []; for (let s = 0; s < SERIES; s += 1) for (let g = 0; g < DAYS; g += 1) segments.push({ base: T0 + g * 86_400_000, end: T0 + (g + 1) * 86_400_000, entries: POINTS }); function rowRetention(limit) { // every record is dropped one by one let touched = 0, dropped = 0; for (const t of timestamps) { touched += 1; if (t < limit) dropped += 1; else break; } return { unit: "record", touched, dropped, remaining: timestamps.length - dropped }; } function segmentRetention(limit) { // metadata is read, a segment drops as a unit let touched = 0, dropped = 0, rewritten = 0; for (const b of segments) { if (b.end <= limit) { dropped += b.entries; continue; } // no entry is opened if (b.base >= limit) continue; touched += b.entries; // segment straddling the boundary for (let i = 0; i < b.entries; i += 1) if (b.base + i * INTERVAL < limit) dropped += 1; else rewritten += 1; } return { unit: "segment", touched, dropped, remaining: SERIES * DAYS * POINTS - dropped, rewritten }; } console.log(`${timestamps.length} measurements, ${segments.length} segments, ${POINTS} entries per segment`); console.log(`\n${"retention".padEnd(27)}${"layout".padEnd(9)}${"entries touched".padStart(16)}` + `${"records dropped".padStart(17)}${"remaining".padStart(10)}`); for (const [name, duration] of [["7 days (segment boundary)", 7 * 86_400_000], ["7 days 12 hours", 7.5 * 86_400_000]]) { const limit = NOW - duration; for (const r of [rowRetention(limit), segmentRetention(limit)]) console.log(name.padEnd(27) + r.unit.padEnd(9) + String(r.touched).padStart(16) + String(r.dropped).padStart(17) + String(r.remaining).padStart(10)); } const y = segmentRetention(NOW - 7.5 * 86_400_000); console.log(`\nsegments straddling the boundary: ${y.touched / POINTS} segments opened, ` + `${y.rewritten} entries rewritten`); ``` ``` 518400 measurements, 360 segments, 1440 entries per segment retention layout entries touched records dropped remaining 7 days (segment boundary) record 397441 397440 120960 7 days (segment boundary) segment 0 397440 120960 7 days 12 hours record 388801 388800 129600 7 days 12 hours segment 17280 388800 129600 segments straddling the boundary: 12 segments opened, 8640 entries rewritten ``` The first pair is segmenting's sharpest gain. Both layouts drop the same 397,440 records and leave behind the same 120,960, but row layout touches 397,441 entries to do it: once for every dropped record, plus one more for the record that marks the boundary. In segment layout, entries touched is **zero** — only 360 segments' metadata is read, and the 276 expired segments (397,440 ÷ 1,440, a **calculation**) are dropped as files. Deletion here is not a data operation, it is a file operation. The zero depends on the retention boundary landing exactly on a segment boundary. The second pair breaks this: at seven and a half days, the boundary cuts through the middle of segments, twelve are opened, 17,280 entries are touched, and 8,640 of them are stored a second time because the segments are rewritten. The dropped record count is again the same on both paths; only the amount of work changes. The rule: **when retention is a multiple of segment duration, deletion costs zero**; otherwise the cost is the number of segments straddling the boundary times the segment size. This is the third face of the segment duration decision: the larger the segment, the fewer bytes stored, but the greater the waste for a narrow-range query and the rewriting at the retention boundary. No single value optimizes all three at once. #### Summary - Time series data is written append-only, read by range, and dropped as it ages; the store folds these three properties into the data model itself. - A full timestamp and value cost 18 bytes per row, while a base timestamp plus delta coding brings this to 2.01 bytes, and adding block compression to 0.63 bytes — 9,331,200 bytes against 329,013, a factor of 28.4. The gain depends on the data being ordered and evenly spaced; its cost is that the unit of access is the segment, not the measurement. - Segment metadata eliminates in range queries: one shelf's one day is a single segment and 1,440 entries instead of scanning 17,280. When the query wants every source, there is no elimination, and both paths read 51,840 entries. - Segment duration is the smallest unit of reading: a one-hour window resolves 720 entries under row layout, 1,440 under segment layout, and the result is 60 measurements either way. - When the retention boundary lands exactly on a segment boundary, 397,440 records are deleted with zero entries touched, 276 segments dropped as files; when it does not, 12 segments are opened, 17,280 entries are touched, and 8,640 entries are rewritten. #### Next Step All five families have now been told in the same order: the model's distinguishing mechanics, the query classes it cheapens and the ones it makes more expensive. What emerges is not a ranking — every family cheapened one access pattern by making another more expensive, and every measurement showed a row running the other way too. What remains is a decision: which family for the work at hand. The next lesson answers this question not with preference but with **criteria** — which property of an access pattern points to which family, at what threshold the difference between two families running the same workload starts to matter, and where the cost shows up when the wrong family is chosen. ### Model Selection Criteria Source: https://academia.sh/en/courses/nosql/model-selection-criteria The criteria on the path from access pattern to family, and the number each criterion ties to: which family cheapens each of seven patterns and what guarantee is given up in return, scoring the same five workloads across five families, and the threshold at which the winner changes hands as the mix ratio shifts — one in three hundred fifty thousand for traversal, one in five for a time range. All five families were measured in the same order, and what emerged was not a ranking but a distribution. One question remains: which family for the work at hand. This lesson answers that question not with preference but with criteria. A criterion's job is to translate the information at hand — which queries an application asks and how often — into a family name. This has two conditions. First, every criterion must tie to a number: "it depends" carries no decision, but "below the third degree, the two models touch the same number" does. Second, the criteria must run together over a mix: the cheapest family for a single query and the cheapest family for the whole workload need not be the same. The lesson first ties the criteria to numbers, then scores five workloads across five families and computes the threshold at which the winner changes hands as the mix shifts. #### Five Criteria and the Numbers They Tie To **Access pattern** is the strongest criterion, but its strength depends on the pattern. In the graph lesson, the two models touched the same number at the first and second degree (22 and 218); the divergence was 1.18 times at the third degree, 1.56 at the fourth, 65.2 at the fifth. The criterion follows from this: relationship traversal only starts pointing to a family name past the third degree — before that it carries no decision. **Query surface width** is how many separate fields carry a filter. If there is one field — and it is the key — the key contract is enough. The moment a second field arrives, the difference the key-value lesson measured opens up: the 359 members over the penalty threshold cost 1 round trip and 6,980 bytes with the relational index, 20,000 round trips and 11.6 MB with a key scan. **Write/read ratio** divides what is gained on the read side by what is paid on the write side. The key-value lesson measured a 74-byte addition raising write amplification to a factor of 400.6 in the whole-value design, against a factor of 1 for separate keys; on the read side, the whole value costs 1 round trip, the separate key costs 2 in an ordered key space and 66 in a hashed one. The break-even point falls out of division (a **calculation**): the whole value stays ahead up to one write per 399.6 reads in an ordered key space, one write per 6.1 reads in a hashed one. **The consistency requirement** determines where the index gets kept. The secondary index the application keeps itself brings the round trips down from 20,000 to 360, but reads the 243,132-byte list whole on every query — 34.8 times the 6,980 bytes the relational index reads — and leaves a window of inconsistency with the record. **Schema change frequency** asks whether the check happens at write time or read time. The document lesson measured a query answered from the index silently missing 7,373 records where three schema versions sit side by side; a defensive read gives the correct answer but raises entries scanned from 18,456 to 50,000, a factor of 2.71 — a cost paid continuously if the schema changes often. #### From Access Pattern to Family Every row of the table is an access pattern; the numbers were read from the five lessons' runs. | Access pattern | Family that cheapens it | Measured difference | Guarantee given up | |---|---|---|---| | Point read by a single key | key-value | 1 round trip, 1 record; relational side 2 round trips and 9 records, or with a single join 953 bytes instead of 732 | Condition on a field, partial update, and join drop out of the contract | | Reading a nested structure whole | document | 1 round trip, 437 bytes; relational side 4 round trips and 552 bytes, or with a single join 60 rows and 7,840 bytes | Write-time schema checking: 7,373 records silently missed in a three-version collection | | Range slice from a wide row | wide-column | a month's 333 loans in a single request from a 4,000-column row; 263,867 columns scanned with a partition key that does not match the pattern | The partition key serves one pattern; serving a second raises entries to 527,734, write amplification 2.0 | | Relationship traversal (depth ≥ 3) | graph | 217,544 edges at the fifth degree; the join produces 14,190,839 interim rows — 65.2 times | A single declarative statement: the same job splits into five separate statements on the relational side | | Time range scan | time series | one shelf's one day is a single segment and 1,440 entries; 17,280 entries under row layout | The unit of access is the segment, not the measurement: a one-hour window resolves 1,440 entries for 60 measurements | | Full scan over a field subset | wide-column | the circulation summary reads 51 pages under family layout, 1,872 under row layout — 36.7 times | All fields of a single record is 5 pages instead of 1; layout cuts both ways | | Filtering by a secondary field | document (an index kept by the engine) | In the key-value lesson the relational index finds the 359 members over the threshold in 1 round trip and 6,980 bytes; a key scan costs 20,000 round trips and 11.6 MB | An index assumes a schema; under version drift, a union of two indexes costs 2 round trips, a defensive scan 50,000 entries | The table reads in one direction only: left to right. It does not start as if a family name is already in hand and search for the pattern that fits it; what is in hand is an access pattern, and the table converts it into a family. The fourth column is part of the result too — the cost of what is gained on each row is written on the same row. #### The Same Workload Set, Five Families The table decides for individual patterns one at a time. A real application, though, runs not a single pattern but a mix. The setup below scores the library domain's five workloads across five families. **NS30:** the catalog carries 50,000 books and 20,000 members, a member's loan history is 4,000 columns in a wide row and a month's slice is 333 loans, twelve shelf sensors write once every 60 seconds. **NS31:** the scoring unit is a "unit touched," and a page, a record, a column, an edge, and a segment entry are counted equally; if a family does not carry a pattern's mechanics, that workload is a scan of the underlying collection in that family. **NS32:** mix shares sum to 1, and the cost is a weighted average per request. Eighteen of the twenty-five cells were read from the five lessons' runs (**measurement**), seven were filled by the NS31 rule (**assumption**): document and graph for point read; key-value, graph, and time series for nested read; document and graph for range slice. The weighted totals and thresholds are of the **calculation** class. ```js // selection/scoring.mjs — five library-domain workloads scored across five model // families. Cells were read from the five lessons' runs; unmeasured cells were // filled by the NS31 rule. The unit is "unit touched" (record, page, column, edge, // segment entry). The total is a weighted average, the threshold is solved by // binary search; the input is fixed, the output is independent of the run. const FAMILY = ["key-value", "document", "wide-column", "graph", "time-series"]; const WORKLOADS = [ // [name, cost across the five families] ["point read", [1, 1, 4, 1, 1440]], // 1 round trip / 4 pages / unit of access is the segment ["nested read", [1, 1, 4, 22, 1440]], // document 1 round trip; graph at the first degree ["range slice", [263867, 4000, 333, 4000, 263867]], // partition key matches: 333 ["traversal (degree 5)", [14190839, 14190839, 14190839, 217544, 14190839]], ["time range", [17280, 17280, 17280, 17280, 1440]], // segment elimination ]; const MIX = [ // shares sum to 1 within a mix ["catalog-weighted", [0.70, 0.29, 0.01, 0, 0]], ["history-weighted", [0.30, 0.10, 0.58, 0, 0.02]], ["monitoring-weighted", [0.15, 0.05, 0, 0, 0.80]], ]; const total = (k) => FAMILY.map((_, a) => WORKLOADS.reduce((s, [, n], i) => s + k[i] * n[a], 0)); const cheapest = (t) => FAMILY.filter((_, a) => t[a] === Math.min(...t)).join("/"); function threshold(base, target) { // target workload's share is p; the rest keeps the base's proportion const weights = (p) => { const mix = base.map((w) => w * (1 - p)); mix[target] += p; return mix; }; const initial = cheapest(total(weights(0))); let a = 0, b = 1; for (let i = 0; i < 200; i += 1) { const p = (a + b) / 2; if (cheapest(total(weights(p))) === initial) a = p; else b = p; } return { share: (a + b) / 2, before: initial, after: cheapest(total(weights(Math.min(1, b * 1.01)))) }; } const row = (name, h, extra) => name.padEnd(22) + h.map((v) => v.padStart(13)).join("") + " " + extra; console.log("matrix — unit touched per workload" + `\n${"workload".padEnd(22)}${FAMILY.map((a) => a.padStart(13)).join("")} ${"spread".padEnd(12)}cheapest`); for (const [name, n] of WORKLOADS) console.log(row(name, n.map(String), `${(Math.max(...n) / Math.min(...n)).toFixed(1) + "x"}`.padEnd(12) + cheapest(n))); console.log(`\nmix — weighted total per request` + `\n${"mix".padEnd(22)}${FAMILY.map((a) => a.padStart(13)).join("")} winner`); for (const [name, k] of MIX) { const t = total(k); console.log(row(name, t.map((v) => v.toFixed(2)), cheapest(t))); } console.log("\nthreshold — when the winner changes as a single workload is added to the catalog mix"); for (const [name, i] of [["traversal (degree 5)", 3], ["time range", 4]]) { const e = threshold(MIX[0][1], i); console.log(name.padEnd(22) + `share ${(e.share * 100).toFixed(6).padStart(9)} %` + ` (one in every ${String(Math.round(1 / e.share)).padStart(6)} requests)` + ` ${e.before} -> ${e.after}`); } ``` ``` matrix — unit touched per workload workload key-value document wide-column graph time-series spread cheapest point read 1 1 4 1 1440 1440.0x key-value/document/graph nested read 1 1 4 22 1440 1440.0x key-value/document range slice 263867 4000 333 4000 263867 792.4x wide-column traversal (degree 5) 14190839 14190839 14190839 217544 14190839 65.2x graph time range 17280 17280 17280 17280 1440 12.0x time-series mix — weighted total per request mix key-value document wide-column graph time-series winner catalog-weighted 2639.66 40.99 7.29 47.08 4064.27 wide-column history-weighted 153388.86 2666.00 540.34 2668.10 153647.66 wide-column monitoring-weighted 13824.20 13824.20 13824.80 13825.25 1440.00 time-series threshold — when the winner changes as a single workload is added to the catalog mix traversal (degree 5) share 0.000285 % (one in every 351177 requests) wide-column -> graph time range share 20.389929 % (one in every 5 requests) wide-column -> time-series ``` The first reading of the matrix rows gives the strength of the criterion. Key-value and document are tied on point read and nested read: both touch 1 unit. These two workloads carry no information for choosing between them — the decision is made on the write side, not the read side, with the 399.6 and 6.1 numbers above. Graph is also at 1 unit in the same row; the family's distinguishing power is not in point read but in the fourth row. #### The Mix That Changes the Winner The mix table shows how the single-pattern decision breaks down. In the catalog-weighted mix, the winner is wide-column (7.29 units); document follows at 40.99. In the history-weighted mix, wide-column wins again but widens the gap to 540.34 against 2,666.00. In the monitoring-weighted mix, the ranking reverses: time series, at 1,440.00 units, stays nine times below wide-column's 13,824.80. Three mixes, two winners. The threshold rows carry the real decision. Adding a fifth-degree chain question to the catalog-weighted mix flips the winner from wide-column to graph once that question's share exceeds 0.000285% — one in every 351,177 requests. Adding a time-range query to the same mix puts the threshold at 20.4%, one in five requests. Five orders of magnitude separate the two thresholds. The reason is visible in the matrix: the traversal row's most expensive cell is 14,190,839, the time-range row's is 17,280. However small a workload's share of the mix, if it costs millions of units in the wrong family it can determine the total alone. The criterion takes this shape: not an access pattern's share, but the **product of its share and its cost in the wrong family**. A rare but very expensive query is more decisive than a frequent, cheap one. #### What the Model Does Not Count The scoring model cannot be used without its limits being written down. Three matter. First, the unit: NS31 counts a page, a record, and a segment entry equally, though these are different orders of magnitude. The model therefore carries an order-of-magnitude difference, not the ranking itself — the 7.29-against-40.99 gap in the catalog mix falls inside the model's margin of error, the 1,440-against-13,824 gap in the monitoring mix does not. Second, writing: the model counts only reading. Wide-column wins two mixes because its partition key happens to be chosen exactly for that mix's access pattern. The wide-column lesson measured that serving a second pattern means writing the same data twice, entries rising from 263,867 to 527,734, write amplification 2.0 — a cost the model does not count; the gain is repaid there. Third, the matrix's seven assumption cells are derived from a rule, not measured. The cells that change the result are of the measurement class (the whole traversal row, the whole time-range row, wide-column's 333 in the range slice); the next step is always the same: once the decision narrows to one family, the measurement is repeated in that family's own setup. #### Summary - A criterion carries no decision until it is tied to a number: traversal only points to a family name past the third degree (1.18 → 1.56 → 65.2 times), the whole value stays ahead in an ordered key space up to a ratio of one write per 399.6 reads, and schema versions sitting side by side make the correct answer 2.71 times more expensive. - Every one of the seven access patterns points to a family, and the cost of what is gained is written on the same row: point read to key-value (no condition on a field), nested read to document (no write-time checking), range slice and full scan to wide-column (a single partition key, a single pattern), traversal to graph (no single-statement query), time range to time series (the unit of access is the segment). - Scoring the five workloads leaves key-value and document tied on point read and nested read (both 1 unit); these two carry no information for choosing between them, and the decision is made on the write side. - The cheapest family for a single pattern and for the whole mix are not the same: wide-column wins the catalog- and history-weighted mixes (7.29 and 540.34), time series wins the monitoring-weighted mix (1,440.00). - The winner is decided not by share alone but by share times cost in the wrong family: the winner changes when traversal is asked once in every 351,177 requests, but a time-range query needs only one in five — five orders of magnitude apart. - The scoring model counts units equally and measures only reading, so it carries an order-of-magnitude difference, not the ranking itself; wide-column's gain is repaid by the 2.0 write amplification it does not count. #### Next Step The criteria point to a family. When the decision arrives here — say, keeping the catalog and loan data in the document model — it might seem like the question is settled. It is only starting. Choosing a family is not choosing a schema. The same library domain can be built in the document model in ways that differ enormously: loan records can be embedded inside the member document or kept by reference in a separate collection, a book's copies can be an array or their own documents, a date can be text or a time type. This lesson's scoring matrix wrote the "document" column as a single number; in reality, that column is a range that shifts by multiples depending on the schema chosen, and its width has not been measured yet. The next topic goes inside the document model and starts from the bottom: which types a document's fields carry, how those types are represented on disk, and what the choice of type does to the bytes stored. ## Working with the Document Model The document model's everyday decisions: the consequences of the binary representation and its type system, the effect of the embed-or-reference decision on read and write paths, comparison, logical, and array operators, the aggregation pipeline that transforms and groups in stages, the choice among single-field, compound, and specialized indexes, the cost of adding a rule to a flexible schema, and the scope of multi-document transactions. ### Document Data Types Source: https://academia.sh/en/courses/nosql/document-data-types The byte cost of a document carrying its own field names and type tags: the space the same 20,000 book records take across open-named, short-named, and fixed-schema representations, the share that self-description accounts for, and the difference that writing the same field in two types produces in a range query. The previous topic closed with selection criteria and left an unfinished decision behind it: the work does not end once an access pattern points to a family. Choosing a family is not choosing a schema. The document model allows very different schemas to be built for the same domain, and that permission is not free. This topic counts that cost, and the first question starts at the bottom. In a relational table, a field's name and type are written once in the table definition, and the row holds only the value. The document model has no such definition: every record carries its own field names and types. This lesson's two measures are exactly that — the space that carrying takes in bytes, and the difference that writing the same field in two different types produces in a range query. #### Self-Describing Record A **document** is an ordered list of named fields; a field's value can be a number or text, but it can also be a nested document or an array. Documents sit inside a **collection**. The store saves this structure as a **binary document representation**: every field starts with a **type tag**, writes its name up to a terminating byte, then places the value in the form the type requires. This representation is called **self-describing**; decoding a record needs no external schema. The representation follows three rules. Fixed-length types (integer, decimal, boolean, date) carry no length; their size is known from the tag. Variable-length types (text, nested document, array) write their own length with a four-byte prefix, so a reader can skip a field it does not care about without decoding it. An array is an inner document whose field names run `"0"`, `"1"`, and so on — the array's element count is carried through those names as well. ```js // binary-document.mjs — self-describing binary document representation. // Encoding: [4-byte length] (type tag + field name + NUL + value)* [0x00] export const TAG = { null: 0x0a, int32: 0x10, decimal: 0x01, text: 0x02, document: 0x03, array: 0x04, boolean: 0x08, date: 0x09 }; const ORDER = ["null", "int32", "decimal", "text", "document", "array", "boolean", "date"]; export function typeName(d) { if (d === null) return "null"; if (Array.isArray(d)) return "array"; if (d instanceof Date) return "date"; if (typeof d === "boolean") return "boolean"; if (typeof d === "number") return Number.isInteger(d) ? "int32" : "decimal"; return typeof d === "string" ? "text" : "document"; } export function encode(doc, s = { name: 0, tag: 0, length: 0, value: 0 }) { const parts = []; for (const [name, d] of Object.entries(doc)) { parts.push(Buffer.from([TAG[typeName(d)]]), Buffer.from(name + "\0", "utf8"), value(d, s)); s.tag += 1; s.name += Buffer.byteLength(name) + 1; } const body = Buffer.concat([...parts, Buffer.from([0])]); const header = Buffer.alloc(4); header.writeInt32LE(body.length + 4); s.length += 4; s.value += 1; // closing NUL return Buffer.concat([header, body]); } function value(d, s) { const t = typeName(d), n = { null: 0, boolean: 1, int32: 4, decimal: 8, date: 8 }[t]; if (n !== undefined) { s.value += n; const b = Buffer.alloc(n); if (t === "boolean") b[0] = d ? 1 : 0; if (t === "int32") b.writeInt32LE(d); if (t === "decimal") b.writeDoubleLE(d); if (t === "date") b.writeBigInt64LE(BigInt(d.getTime())); return b; } if (t === "text") { const m = Buffer.from(d + "\0", "utf8"), b = Buffer.alloc(4); b.writeInt32LE(m.length); s.length += 4; s.value += m.length; return Buffer.concat([b, m]); } return encode(t === "array" ? { ...d } : d, s); // array: field names "0","1",... } export function decode(t, offset = 0) { const end = offset + t.readInt32LE(offset), result = {}; let i = offset + 4; while (i < end - 1) { const tag = t[i], stop = t.indexOf(0, i + 1), name = t.toString("utf8", i + 1, stop); i = stop + 1; if (tag === TAG.null) result[name] = null; else if (tag === TAG.boolean) result[name] = t[i++] === 1; else if (tag === TAG.int32) { result[name] = t.readInt32LE(i); i += 4; } else if (tag === TAG.decimal) { result[name] = t.readDoubleLE(i); i += 8; } else if (tag === TAG.date) { result[name] = new Date(Number(t.readBigInt64LE(i))); i += 8; } else if (tag === TAG.text) { const n = t.readInt32LE(i); result[name] = t.toString("utf8", i + 4, i + 3 + n); i += 4 + n; } else { const inner = decode(t, i); result[name] = tag === TAG.array ? Object.values(inner) : inner; i += t.readInt32LE(i); } } return result; } // Ordering looks at type first, then value: type order. export function compare(a, b) { const f = ORDER.indexOf(typeName(a)) - ORDER.indexOf(typeName(b)); if (f !== 0) return f; if (a === null) return 0; if (a instanceof Date) return a.getTime() - b.getTime(); return a < b ? -1 : a > b ? 1 : 0; } ``` #### The Byte Cost of a Name The measurement builds the previous courses' library catalog in document form. **NS7 (assumption):** the catalog holds 20,000 book documents; each book has 1–5 copies and 2–4 tags, and the generation seed is 424242. The same data is encoded under three decisions: field names are written out in full, field names are shortened, or the names and types are stripped from the record and moved to a fixed schema. The third is what a relational row does, and it stands here as the comparison baseline. ```js // field-cost.mjs — the same 20,000 book documents are encoded in two schemas: open field // names and short field names. The same data is also encoded, as a third decision, in a // fixed-schema row. // binary-document.mjs is in the same directory. import { encode, decode } from "./binary-document.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"]; function books(n) { const result = []; for (let i = 1; i <= n; i += 1) { const copyCount = 1 + Math.floor(random() * 5); const copy = []; for (let j = 0; j < copyCount; j += 1) copy.push({ barcode: `B${String(i * 10 + j).padStart(7, "0")}`, branch: BRANCH[Math.floor(random() * BRANCH.length)], status: STATUS[Math.floor(random() * STATUS.length)] }); const tagCount = 2 + Math.floor(random() * 3); const tag = []; for (let j = 0; j < tagCount; j += 1) tag.push(TAGS[Math.floor(random() * 6)]); result.push({ key: `K-${String(i).padStart(5, "0")}`, title: `Studies on Book ${i}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), tag, copy }); } return result; } const SHORT = { key: "_k", title: "t", author: "a", publication_year: "py", tag: "tg", copy: "c", barcode: "bc", branch: "br", status: "st" }; const shorten = (b) => Object.fromEntries(Object.entries(b).map(([a, d]) => [SHORT[a] ?? a, Array.isArray(d) ? d.map((x) => (typeof x === "object" ? shorten(x) : x)) : d])); const RECORDS = books(20000); const measure = (set) => { const s = { tag: 0, name: 0, length: 0, value: 0 }; let bytes = 0; for (const b of set) bytes += encode(b, s).length; return { bytes, ...s }; }; const open = measure(RECORDS), short = measure(RECORDS.map(shorten)); // Fixed-schema row: type and field name sit once in the schema, the record carries only the value. function fixedSchema(set) { let bytes = 0; for (const b of set) { bytes += 4; // publication_year: int32 for (const field of ["key", "title", "author"]) bytes += 2 + Buffer.byteLength(b[field]); bytes += 2 + b.tag.reduce((t, e) => t + 1 + Buffer.byteLength(e), 0); bytes += 2; for (const c of b.copy) bytes += 2 + Buffer.byteLength(c.barcode) + 1 + Buffer.byteLength(c.branch) + 1 + Buffer.byteLength(c.status); } return bytes; } const fixed = fixedSchema(RECORDS); const fields = RECORDS.reduce((t, b) => t + 6 + b.tag.length + b.copy.length * 4, 0); console.log(`document count ${RECORDS.length}`); console.log(`total fields (nested included) ${fields}`); console.log(`open field names ${open.bytes} bytes per document ${(open.bytes / 20000).toFixed(1)}`); console.log(`short field names ${short.bytes} bytes per document ${(short.bytes / 20000).toFixed(1)}`); console.log(`fixed-schema row ${fixed} bytes per document ${(fixed / 20000).toFixed(1)}`); console.log(`open-schema byte breakdown: name ${open.name} type tag ${open.tag} ` + `length field ${open.length} value ${open.value}`); console.log(`self-description share open %${(100 * (open.bytes - fixed) / open.bytes).toFixed(1)}` + ` short %${(100 * (short.bytes - fixed) / short.bytes).toFixed(1)}`); const first = encode(RECORDS[0]); console.log(`first document ${first.length} bytes, decoded first copy: ` + JSON.stringify(decode(first).copy[0])); ``` ``` document count 20000 total fields (nested included) 417706 open field names 7652469 bytes per document 382.6 short field names 6319047 bytes per document 316.0 fixed-schema row 3236623 bytes per document 161.8 open-schema byte breakdown: name 2407316 type tag 417706 length field 1670824 value 3156623 self-description share open %57.7 short %48.8 first document 518 bytes, decoded first copy: {"barcode":"B0000010","branch":"Beyoglu","status":"shelved"} ``` The measurement runs over 417,706 fields — a book document carries 20.9 fields on average, because every copy and every tag is its own field. The open-named representation takes 7,652,469 bytes, the fixed-schema row 3,236,623 bytes. The difference is 4,415,846 bytes, and it is not the data itself but the data describing itself: 2,407,316 bytes go to field names, 417,706 bytes to type tags, 1,670,824 bytes to length prefixes. The arithmetic: of every three bytes stored in the open representation, close to two (57.7%) are not data but definition. Shortening brings that share down to 48.8%. The 1,333,422-byte difference comes purely from shortening the field names — 66.7 bytes per document, which scales out to around 1.3 MB across 20,000 documents. The flip side of the decision can also be counted: a short-named document, read on its own, does not say that the `bc` field is the barcode — that information now lives in the application, not the store. Self-description is exactly that information staying in the record, and its cost has now been measured. #### The Same Field in Two Types The counterpart of carrying type in the record is that the same field can be a different type in two documents. A relational schema blocks this at definition time; the document model has no such block, and the absence of one shows up on the query side. **NS8 (assumption):** in one out of every eight records taken from an external source, the publication year is written as text — `"2010"` instead of `2010`. What a range query does with these documents depends on the operator's semantics, and there are two options. **Type ordering** compares values of different types as well: types are ordered first, and values are ordered only when the type is equal. **Type bracketing** applies the comparison only to values of the same type as the operator's right-hand side; every other value fails to match. ```js // type-mixing.mjs — the same field in two types: publication_year is an integer for part // of the records, text for another part. The same range is counted under two operator // semantics. // binary-document.mjs is in the same directory. import { compare, typeName, encode } from "./binary-document.mjs"; const N = 20000; const items = []; for (let i = 1; i <= N; i += 1) { const year = 1950 + (i % 75); items.push({ key: `K-${String(i).padStart(5, "0")}`, publication_year: i % 8 === 0 ? String(year) : year }); // every eighth document writes text } const asText = items.filter((b) => typeName(b.publication_year) === "text").length; // Decision A: comparison uses type ordering (the total order in sorting). const A = (b, d, dir) => (dir === "ge" ? compare(b.publication_year, d) >= 0 : compare(b.publication_year, d) < 0); // Decision B: comparison applies type bracketing, a value of a different type never matches. const B = (b, d, dir) => typeName(b.publication_year) === typeName(d) && A(b, d, dir); const count = (f, d, dir) => items.filter((b) => f(b, d, dir)).length; console.log(`documents ${N}, publication_year as text ${asText} (%${(100 * asText / N).toFixed(1)})`); console.log(`A type ordering >= 2010 -> ${count(A, 2010, "ge")} < 2010 -> ${count(A, 2010, "lt")}` + ` total ${count(A, 2010, "ge") + count(A, 2010, "lt")}`); console.log(`B type bracketing >= 2010 -> ${count(B, 2010, "ge")} < 2010 -> ${count(B, 2010, "lt")}` + ` total ${count(B, 2010, "ge") + count(B, 2010, "lt")}`); console.log(`single-typed schema >= 2010 -> ` + `${items.filter((b) => Number(b.publication_year) >= 2010).length}`); console.log(`documents B places in neither side ${N - count(B, 2010, "ge") - count(B, 2010, "lt")}`); console.log(`B, when the operand is text: >= "2010" -> ${count(B, "2010", "ge")}`); // Sorting always uses the total order: the result clumps by type. const sorted = [...items].sort((a, b) => compare(a.publication_year, b.publication_year)); const boundary = sorted.findIndex((b) => typeName(b.publication_year) === "text"); console.log(`first text value at position ${boundary}: ${JSON.stringify(sorted[boundary].publication_year)}` + `, previous ${JSON.stringify(sorted[boundary - 1].publication_year)}`); const bytes = (d) => encode({ publication_year: d }).length; console.log(`single-field document: integer ${bytes(2010)} bytes, text ${bytes("2010")} bytes`); ``` ``` documents 20000, publication_year as text 2500 (%12.5) A type ordering >= 2010 -> 5991 < 2010 -> 14009 total 20000 B type bracketing >= 2010 -> 3491 < 2010 -> 14009 total 17500 single-typed schema >= 2010 -> 3990 documents B places in neither side 2500 B, when the operand is text: >= "2010" -> 499 first text value at position 17500: "1950", previous 2024 single-field document: integer 27 bytes, text 32 bytes ``` The correct answer is 3,990: if the entire field were an integer, this many documents would come back for 2010 and later. Neither semantics gives this number, but they miss it in different ways. Type ordering returns 5,991; the excess of 2,001 documents are records written entirely as text, including some from 1950 — because the text type sits after the integer type in the order, every text value is treated as greater than every integer. Type bracketing returns 3,491; the missing 499 documents are records whose year is written as text and whose real value is 2010 or later. Type bracketing's more insidious result shows up in the last line. `>= 2010` and `< 2010` are the two halves of one range, and their total should be 20,000; the measurement gives 17,500. 2,500 documents fall into neither query. These documents look missing in one report and missing in the reverse query too; because no answer ever shows them, the error goes unnoticed. Sorting, on the other hand, always uses the total order: integers run up through position 17,500, then text values follow, so the value `"1950"` lands after the value `2024`. The byte side points the same way: a single-field document takes 27 bytes when the year is an integer, 32 when it is text. Across 2,500 documents the difference is 12,500 bytes — a small number, but carrying the type in the document separates not just space but meaning. The lesson's rule is this: the document model does not bind a field's type at write time, so the job of binding it falls either to the writing application or to a rule placed afterward. How that rule gets placed, and what it catches and what it misses, is the question of this topic's sixth lesson. #### Summary - The binary document representation stores every field with a type tag, a field name, and a length prefix where needed; the record is self-describing and decoding it needs no external schema. - The same 20,000 book documents take 7,652,469 bytes with open names, 6,319,047 with short names, and 3,236,623 bytes in a fixed-schema row; in the open representation, 57.7% of the bytes are not data but definition. - Shortening field names saves 1,333,422 bytes (66.7 bytes per document) and moves the knowledge of what a field is from the store to the application. - Writing the same field in two types breaks a range query: type ordering returns 5,991 documents instead of 3,990, type bracketing returns 3,491. - Under type bracketing, `>= 2010` and `< 2010` total 17,500, not 20,000; 2,500 documents show up in neither answer. #### Next Step This lesson looked inside a single document and counted the cost of a field's name and type. The catalog, however, is not just one document: book, copy, member, and loan records are linked to each other, and the document model allows that link to be built in two different ways — embedding the related data inside the document, or keeping it in a separate collection and pointing to it by key. Both store the same catalog, but they answer the same read with a different number of round trips, rewrite a different number of documents on the same update, and approach the document size limit at a different rate. The next lesson runs both decisions on the same work and counts the difference. ### Embedding and Referencing Source: https://academia.sh/en/courses/nosql/embedding-and-referencing The same catalog's copies built in two schemas, embedded and referenced, and three tasks counted: the book page's round-trip count, the bytes the branch query reads, the bytes five thousand status changes write, and how many books hit the document size limit once loan history is embedded. The previous lesson looked inside a single document: the byte cost of a field name and a type tag was counted, and writing the same field in two types was shown to return 3,491 or 5,991 documents instead of 3,990 in a range query. The catalog, however, is not just one document. Book, copy, member, and loan records are linked to each other, and the document model allows that link to be built in two ways. **Embedding** puts the related data inside the document, as a nested document or an array. **Referencing** keeps the data in a separate collection and carries only its key in the document. Both store the same catalog; where they part ways is how many round trips a read path takes, how many bytes are read, how many documents a single update rewrites, and how large the document grows. This lesson produces those four numbers. The arithmetic of normalization and denormalization was measured in the Data Modeling and Relational Theory and Scaling the Data Layer courses; it is not repeated here — what is measured here is the side that is specific to the document model. #### A Store That Counts A small document store is written for the measurement. The store holds collections, separates key access from full scans, and counts a **round trip**, the number of documents read, and the bytes read on every access. There is also a document size limit: a write that exceeds it is rejected. The equality map exists only to keep the comparison fair; the index's own arithmetic is this topic's fifth lesson's subject. ```js // document-store.mjs — a small document store: collections, key access, scans, equality // mapping, and a document size limit. Every access is counted as a round trip, documents // read, and bytes read. // The byte rule from lesson 01's encoding: fixed-length types take their size from the // tag, variable-length types carry a 4-byte length prefix, every field is 1 byte tag + name + NUL. export function bytes(d) { if (d === null) return 0; if (typeof d === "boolean") return 1; if (typeof d === "number") return Number.isInteger(d) ? 4 : 8; if (d instanceof Date) return 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(limit = 16384) { this.collection = new Map(); this.index = new Map(); this.limit = limit; this.reset(); } reset() { this.o = { roundTrips: 0, documentsRead: 0, bytesRead: 0, documentsWritten: 0, bytesWritten: 0 }; } c(name) { if (!this.collection.has(name)) this.collection.set(name, new Map()); return this.collection.get(name); } write(name, doc) { const n = bytes(doc); if (n > this.limit) throw new Error(`document size limit exceeded: ${n} > ${this.limit}`); this.c(name).set(doc._k, doc); this.o.documentsWritten += 1; this.o.bytesWritten += n; return n; } read(b) { this.o.documentsRead += 1; this.o.bytesRead += bytes(b); return b; } find(name, k) { // key access: one round trip, one document this.o.roundTrips += 1; const b = this.c(name).get(k); return b ? this.read(b) : undefined; } scan(name, condition) { // full scan: the whole collection is read this.o.roundTrips += 1; return [...this.c(name).values()].filter((b) => condition(this.read(b))); } equalityMap(name, field) { // index arithmetic is lesson 05's topic const m = new Map(); for (const b of this.c(name).values()) { const v = b[field]; if (!m.has(v)) m.set(v, []); m.get(v).push(b._k); } this.index.set(`${name}.${field}`, m); } lookup(name, field, value) { this.o.roundTrips += 1; const keys = this.index.get(`${name}.${field}`).get(value) ?? []; return keys.map((k) => this.read(this.c(name).get(k))); } } ``` #### Three Tasks, Two Schemas **NS7 (assumption):** the catalog holds 20,000 books, each book has 1–5 copies, and the seed is 424242. **NS9 (assumption):** the library has three tasks — opening a book page (one book and all of its copies), listing the copies under repair at one branch, and changing one copy's status. All three run in both schemas. ```js // embed-reference.mjs — the same catalog is built in two schemas: copies embedded in the // book, or referenced in a separate collection. Three tasks run in both schemas and the // difference is counted. // document-store.mjs is in the same directory. import { Store, bytes } from "./document-store.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const N = 20000; 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: STATUS[Math.floor(random() * 3)] }); raw.push({ _k: `K-${String(i).padStart(5, "0")}`, title: `Studies on Book ${i}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), copy }); } const COPY_COUNT = raw.reduce((t, b) => t + b.copy.length, 0); const embedded = new Store(); for (const b of raw) embedded.write("book", b); const referenced = new Store(); for (const b of raw) { referenced.write("book", { _k: b._k, title: b.title, author: b.author, publication_year: b.publication_year }); for (const k of b.copy) referenced.write("copy", { _k: k.barcode, book: b._k, branch: k.branch, status: k.status }); } referenced.equalityMap("copy", "book"); referenced.equalityMap("copy", "branch"); const report = (label, o) => console.log(`${label.padEnd(26)} round trips ${String(o.roundTrips).padStart(2)}` + ` documents read ${String(o.documentsRead).padStart(6)} bytes read ${String(o.bytesRead).padStart(8)}`); console.log(`books ${N}, copies ${COPY_COUNT} (per book ${(COPY_COUNT / N).toFixed(2)})`); console.log(`collection size: embedded book ${[...embedded.c("book").values()].reduce((t, b) => t + bytes(b), 0)}` + ` referenced book+copy ${[...referenced.c("book").values()].reduce((t, b) => t + bytes(b), 0) + [...referenced.c("copy").values()].reduce((t, b) => t + bytes(b), 0)}`); // TASK 1 — book page: one book and all of its copies. embedded.reset(); referenced.reset(); embedded.find("book", "K-04242"); report("task1 embedded", embedded.o); referenced.find("book", "K-04242"); referenced.lookup("copy", "book", "K-04242"); report("task1 referenced", referenced.o); // TASK 2 — copies under repair at one branch. embedded.reset(); referenced.reset(); const t2e = embedded.scan("book", (b) => b.copy.some((k) => k.branch === "Kadikoy" && k.status === "in_repair")); report("task2 embedded", embedded.o); const t2r = referenced.lookup("copy", "branch", "Kadikoy").filter((k) => k.status === "in_repair"); report("task2 referenced", referenced.o); console.log(`task2 result: embedded ${t2e.length} book documents, referenced ${t2r.length} copy documents`); // TASK 3 — 5,000 copies change status. embedded.reset(); referenced.reset(); for (let i = 0; i < 5000; i += 1) { const book = raw[(i * 7) % N]; const target = book.copy[i % book.copy.length]; const e = embedded.find("book", book._k); e.copy.find((k) => k.barcode === target.barcode).status = "shelved"; embedded.write("book", e); const r = referenced.find("copy", target.barcode); referenced.write("copy", { ...r, status: "shelved" }); } console.log(`task3 embedded documents written ${embedded.o.documentsWritten} bytes written ${embedded.o.bytesWritten}`); console.log(`task3 referenced documents written ${referenced.o.documentsWritten} bytes written ${referenced.o.bytesWritten}`); ``` ``` books 20000, copies 58595 (per book 2.93) collection size: embedded book 6450690 referenced book+copy 6816640 task1 embedded round trips 1 documents read 1 bytes read 478 task1 referenced round trips 2 documents read 6 bytes read 517 task2 embedded round trips 1 documents read 20000 bytes read 6450690 task2 referenced round trips 1 documents read 10066 bytes read 825072 task2 result: embedded 2934 book documents, referenced 3092 copy documents task3 embedded documents written 5000 bytes written 1616741 task3 referenced documents written 5000 bytes written 402224 ``` The three tasks point in three different directions. Embedding wins on the book page: a single round trip reads 478 bytes, while the referenced schema gathers the same information across two round trips and six documents, reading 517 bytes. The difference is small on the byte side (8.2%) and doubled on the round-trip side — and a round trip, for an application connecting to the store remotely, is a more expensive unit than a byte. The branch query flips the direction. In the embedded schema, the copy is inside the book; finding one branch's copies reads all 20,000 book documents, 6,450,690 bytes. In the referenced schema, the copy has its own collection and can be mapped by branch: 10,066 documents, 825,072 bytes. The bytes read for the same question fall by a factor of 7.8. The two results carrying different counts is also instructive: the embedded scan returns 2,934 **books**, the referenced query returns 3,092 **copies** — the same book can have two copies under repair at the same branch, and in the embedded schema that distinction stays inside the document. The write path gives the third direction. When a copy's status changes, the embedded schema rewrites the entire book: 5,000 changes write 1,616,741 bytes, 323 bytes per change. The referenced schema rewrites only the copy document: 402,224 bytes, 80 bytes per change. The ratio is 4.02, and it grows as the book's field count grows, because every field next to the one that changed gets rewritten too. On the stored-space side the decision runs the other way: the referenced schema takes 6,816,640 bytes, the embedded schema 6,450,690 — the difference is that every copy document carries its own key and the book's key over again. #### An Array That Grows Without Bound The most expensive form of embedding is embedding an array with no end. Loan history is exactly that: the book stays fixed, the history keeps growing. **NS10 (assumption):** the store's document size limit is 16,384 bytes. **NS11 (assumption):** 1,406,280 loans are issued over three years, and the distribution is Zipf-shaped — the share of the book at rank r is proportional to `1/r`. ```js // growth.mjs — embedding loan history in the book document makes it grow. The decision to // embed without limit is compared with the decision to embed only the last 20 records and // leave the rest in a separate collection. // document-store.mjs is in the same directory. import { Store, bytes } from "./document-store.mjs"; const LIMIT = 16384, N = 20000, LOANS = 1406280, TAIL = 20; const base = (i) => ({ _k: `K-${String(i).padStart(5, "0")}`, title: `Studies on Book ${i}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), loan: [] }); const record = (n) => ({ member: `U-${String(n % 90000).padStart(5, "0")}`, checkedOut: new Date(2023, 0, 1 + (n % 1095)), due: new Date(2023, 0, 15 + (n % 1095)) }); // Zipf distribution: the share of the book at rank r is proportional to 1/r. No randomness. const H = Array.from({ length: N }, (_, i) => 1 / (i + 1)).reduce((a, b) => a + b); const share = Array.from({ length: N }, (_, i) => Math.round(LOANS / ((i + 1) * H))); const emptyDoc = bytes(base(1)); const perRecord = bytes({ ...base(1), loan: [record(1)] }) - emptyDoc; const collectionBytes = (d) => [...d.values()].reduce((t, b) => t + bytes(b), 0); console.log(`empty book document ${emptyDoc} bytes, one loan record ${perRecord} bytes`); console.log(`limit ${LIMIT} bytes, rough estimate: ${Math.floor((LIMIT - emptyDoc) / perRecord)} records`); // Decision A: the entire history is embedded. Size is tracked incrementally; the nth // element adds 2 + the length of the index name + the record's bytes to the array. const storeA = new Store(LIMIT); let capped = 0, first = null, dropped = 0; for (let i = 1; i <= N; i += 1) { const b = base(i); let size = emptyDoc, fit = 0; for (let n = 0; n < share[i - 1]; n += 1) { const add = String(n).length + perRecord - 1; if (size + add > LIMIT) break; size += add; b.loan.push(record(n)); fit += 1; } if (fit < share[i - 1]) { capped += 1; dropped += share[i - 1] - fit; first ??= { rank: i, records: fit, size: bytes(b), wanted: share[i - 1] }; } storeA.write("book", b); } console.log(`A unlimited embedding: books hitting the cap ${capped}, loan records that do not fit ${dropped}`); console.log(` first capped book, rank ${first.rank}: ${first.records} records ${first.size} bytes, wanted ${first.wanted}`); console.log(` book collection ${collectionBytes(storeA.c("book"))} bytes`); // Decision B: the last 20 records are embedded, the rest stay in the loan collection. const storeB = new Store(LIMIT); for (let i = 1; i <= N; i += 1) { const b = base(i); for (let n = Math.max(0, share[i - 1] - TAIL); n < share[i - 1]; n += 1) b.loan.push(record(n)); storeB.write("book", b); } const largest = Math.max(...[...storeB.c("book").values()].map(bytes)); console.log(`B last ${TAIL} records embedded: largest document ${largest} bytes, distance to limit ${LIMIT - largest}`); console.log(` book collection ${collectionBytes(storeB.c("book"))} bytes, records remaining in the separate collection ` + `${share.reduce((t, p) => t + Math.max(0, p - TAIL), 0)}`); ``` ``` empty book document 104 bytes, one loan record 61 bytes limit 16384 bytes, rough estimate: 266 records A unlimited embedding: books hitting the cap 515, loan records that do not fit 781509 first capped book, rank 1: 260 records 16374 bytes, wanted 134178 book collection 40880034 bytes B last 20 records embedded: largest document 1340 bytes, distance to limit 15044 book collection 19422356 bytes, records remaining in the separate collection 1125534 ``` The rough estimate says 266 records, but only 260 actually fit. The gap of 6 records comes from the array's own field names: the index name grows to two digits past the tenth element and to three past the hundredth, and each digit adds a byte to the element. This is a consequence of the previous lesson's finding — even inside an array, the field name is stored. The real number is in the second line. 515 of the 20,000 books hit the limit within three years, and 781,509 loan records cannot be written into the document. The most-borrowed book wants 134,178 records and can hold only 260 of them. The limit is not a performance problem, it is a data-loss problem: the embedding decision quietly runs into an irreversible limit here. The second decision removes the limit — the last 20 records are embedded, and the rest stay in a separate collection. The largest book document drops to 1,340 bytes, leaving 15,044 bytes of distance to the limit, and 1,125,534 records move to the separate collection. The book page still shows the last 20 loans in a single round trip; a screen that wants the full history pays for a second round trip. The rule for the decision follows from these three measurements: data that is read together and changed together is embedded; data that is queried separately or grows without bound is kept by reference. Sentences like "more flexible" or "more natural" do not carry this decision; what carries it is the round-trip count, the bytes read, the bytes rewritten, and the distance to the limit. #### Summary - Embedding puts the related data inside the document, referencing keeps it in a separate collection and carries its key; both store the same catalog at a different access cost. - The book page takes 1 round trip and 478 bytes in the embedded schema, 2 round trips and 517 bytes in the referenced schema; the gain is in round trips, not bytes. - The branch query reads 20,000 documents and 6,450,690 bytes in the embedded schema, 10,066 documents and 825,072 bytes in the referenced schema; the ratio is 7.8×. - A copy's status change rewrites the entire book in the embedded schema: 5,000 changes write 1,616,741 bytes, versus 402,224 bytes in the referenced schema (a ratio of 4.02). - An array that grows without bound runs into the document size limit: 515 of 20,000 books exceed it and 781,509 loan records cannot be written; embedding only the last 20 records brings the largest document down to 1,340 bytes. #### Next Step The two decisions that build the schema have been counted; next comes asking questions of that schema. In this lesson, the branch query ran through a hand-written condition function, but a store evaluates the condition itself, using a set of operators: comparison, logical connectives, and array operators. Array operators carry an ambiguity that surfaced in this lesson — when an embedded copy array is asked two conditions at once, whether the conditions must be satisfied by the **same** element or by any two elements of the document is two different answers to the same query. The next lesson builds the operators in their own evaluator and counts that difference. ### Query Operators Source: https://academia.sh/en/courses/nosql/query-operators The semantics of comparison, logical, and array operators are built in their own evaluator: a field path descending into an array, whether conditions are satisfied at the document level or the element level, what negation does on an array and on a missing field — each measured by the number of documents returned. The previous lesson built the schema and counted the cost of the embedding decision; the branch query ran through a hand-written condition function. A store does this work itself, with a set of operators: comparison operators, logical connectives, and operators specific to arrays. This lesson does not drill the syntax of that set — syntax already varies from store to store. What does not vary is the semantics, built and measured here in its own evaluator. The actual question to measure surfaced at the end of the previous lesson. When an embedded copy array is asked two conditions at once, it is ambiguous whether the conditions must be satisfied by the same copy or by any two copies of the document. Both readings are consistent, both are genuinely used, and each returns a different number of documents. #### The Path Descending Into the Array A relational condition looks at a single cell. In the document model, a field path can reach more than one value: the path `copy.branch` produces three values on a book with three copies. The evaluator behaves **existentially** in this case — the condition is true when **any one** of the reached values satisfies it. This single rule is the source of every measurement in the lesson. The evaluator carries three operator classes. Comparison operators (`=`, `<>`, `>`, `>=`, `<`, `<=`, `in`) compare a value against a constant. Logical connectives (`and`, `or`, `not`) combine conditions. Array operators (`any`, `all`, `none`) stand apart from the rest: they look not at values but at **elements**, and apply the sub-condition to each element separately. ```js // operators.mjs — condition evaluator. A path descends into arrays: a field path can // reach more than one value, and the condition is true if any one of those values // satisfies it. const COMPARE = { "=": (a, b) => a === b, "<>": (a, b) => a !== b, ">": (a, b) => a > b, ">=": (a, b) => a >= b, "<": (a, b) => a < b, "<=": (a, b) => a <= b, in: (a, b) => b.includes(a), }; // Values at the path. An array is a candidate both as itself and through its elements. export function values(root, path) { let items = [root]; for (const name of path.split(".")) { const next = []; for (const d of items) for (const o of Array.isArray(d) ? d : [d]) if (o && typeof o === "object" && !Array.isArray(o) && name in o) next.push(o[name]); items = next; } return items.flatMap((v) => (Array.isArray(v) ? [v, ...v] : [v])); } // The arrays themselves at the path: element-level operators work on this. const arrays = (root, path) => values(root, path).filter(Array.isArray); export function matches(doc, condition, s = { compare: 0, element: 0 }) { for (const [name, expected] of Object.entries(condition)) { if (name === "and") { if (expected.every((k) => matches(doc, k, s))) continue; return false; } if (name === "or") { if (expected.some((k) => matches(doc, k, s))) continue; return false; } if (name === "not") { if (matches(doc, expected, s)) return false; continue; } const simple = expected === null || typeof expected !== "object" || Array.isArray(expected); const conditions = simple ? { "=": expected } : expected; for (const [operator, operand] of Object.entries(conditions)) { if (operator === "exists") { if (values(doc, name).length > 0 !== operand) return false; continue; } if (operator === "any" || operator === "all" || operator === "none") { const elements = arrays(doc, name).flat(); s.element += elements.length; const count = elements.filter((o) => matches(o, operand, s)).length; const ok = operator === "any" ? count > 0 : operator === "all" ? count === elements.length && elements.length > 0 : count === 0; if (ok) continue; return false; } const candidates = values(doc, name); s.compare += candidates.length; if (candidates.some((d) => COMPARE[operator](d, operand))) continue; return false; } } return true; } export const select = (items, condition, s) => items.filter((b) => matches(b, condition, s)); ``` #### Same Question, Two Semantics **NS7 (assumption):** the catalog is 20,000 book documents, each book has 1–5 copies and 2–4 tags, and the seed is 424242. **NS12 (assumption):** as a result of the flexible schema, one in forty documents has no `publication_year` field at all. The questions are asked first at the document level, then at the element level; each run prints the number of documents returned, the number of comparisons made, and the number of elements examined. ```js // operator-measurement.mjs — the same three questions are asked in two operator forms: // document-level conjunction and element-level matching. The number of documents // returned and comparisons made are counted. // operators.mjs is in the same directory. import { select } from "./operators.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"]; const CATALOG = []; for (let i = 1; i <= 20000; i += 1) { const copy = [], tag = []; 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: STATUS[Math.floor(random() * 3)] }); for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1) tag.push(TAGS[Math.floor(random() * 6)]); const b = { _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), tag, copy }; if (i % 40 === 0) delete b.publication_year; // flexible schema: a field can be missing CATALOG.push(b); } function run(name, condition) { const s = { compare: 0, element: 0 }; const result = select(CATALOG, condition, s); console.log(`${name.padEnd(34)} ${String(result.length).padStart(5)} documents ` + `comparisons ${String(s.compare).padStart(6)} elements examined ${String(s.element).padStart(6)}`); return result.length; } console.log(`catalog ${CATALOG.length} documents`); const a1 = run("document-level conjunction", { "copy.branch": "Kadikoy", "copy.status": "in_repair" }); const a2 = run("element-level matching", { copy: { any: { branch: "Kadikoy", status: "in_repair" } } }); console.log(` in ${a1 - a2} documents the conditions are satisfied by separate copies`); const b1 = run("copy.status <> checked_out", { "copy.status": { "<>": "checked_out" } }); const b2 = run("no copy is checked out", { copy: { none: { status: "checked_out" } } }); console.log(` in ${b1 - b2} documents at least one copy is checked out`); const c1 = run("tag in [history, science]", { tag: { in: ["history", "science"] } }); const c2 = run("both history and science", { and: [{ tag: "history" }, { tag: "science" }] }); const c3 = run("all copies shelved", { copy: { all: { status: "shelved" } } }); console.log(` difference between in and the two-condition conjunction ${c1 - c2} documents`); run("publication_year field missing", { publication_year: { exists: false } }); run("publication_year >= 2010", { publication_year: { ">=": 2010 } }); run("not publication_year < 2010", { not: { publication_year: { "<": 2010 } } }); ``` ``` catalog 20000 documents document-level conjunction 6033 documents comparisons 88749 elements examined 0 element-level matching 3340 documents comparisons 70018 elements examined 59494 in 2693 documents the conditions are satisfied by separate copies copy.status <> checked_out 17787 documents comparisons 59494 elements examined 0 no copy is checked out 7111 documents comparisons 59494 elements examined 59494 in 10676 documents at least one copy is checked out tag in [history, science] 14033 documents comparisons 79730 elements examined 0 both history and science 2777 documents comparisons 115287 elements examined 0 all copies shelved 1919 documents comparisons 59494 elements examined 59494 difference between in and the two-condition conjunction 11256 documents publication_year field missing 500 documents comparisons 0 elements examined 0 publication_year >= 2010 3891 documents comparisons 19500 elements examined 0 not publication_year < 2010 4391 documents comparisons 19500 elements examined 0 ``` #### What the Numbers Say The first pair is the lesson's core finding. The question "book with a copy under repair at the Kadikoy branch" returns 6,033 documents when asked at the document level, 3,340 when asked at the element level. In the 2,693 documents in between, there is a copy at Kadikoy and a copy under repair, but they are different copies — the one at Kadikoy is shelved, the one under repair is at a different branch. The document-level conjunction is not wrong; it asks a different question. What is wrong is asking an element-level question at the document level, and the result is 80.6% too many documents. The measurement produces this difference silently: both queries run, neither raises an error. The second pair shows how negation behaves on an array. The condition `copy.status <> "checked_out"` returns 17,787 documents; the intent here is almost always "book with no copy checked out," and the correct answer to that question is 7,111. The difference of 10,676 documents is books that have at least one copy checked out but also at least one copy that is not, and the existential rule makes the condition true. Negation on an array runs, against intuition, inclusively: "is not" does not mean "none of them is." The correct expression is the `none` operator, and because it works at the element level, it examines all 59,494 elements. The third pair shows the reverse direction of the same mistake. The `in` operator, applied to an array, means "any one of the listed values" and returns 14,033 documents; the question "book tagged with both history and science" is a two-condition conjunction and returns 2,777 documents. The difference is 11,256. Here the document-level conjunction **is** the right tool, because the tags are separate elements and the conditions are not meant to be satisfied by the same element. The two measurements together give the rule: what decides whether a conjunction should be built at the document level or the element level is the question itself, not the presence of an array. The `all` operator returns 1,919 documents: books whose every copy is shelved. This operator's definition in the evaluator carries a detail — `count === elements.length && elements.length > 0`. Without the second condition, a book with no copies at all would answer "yes" to "all copies shelved," because every proposition is true over an empty set. This behavior of the empty array creates, alongside a field being absent altogether in the document model, two separate kinds of emptiness, and each silently changes the query's answer. The last three lines are the flexible schema's trace on the query side. 500 documents have no `publication_year` field. `publication_year >= 2010` does not return these documents (3,891), but the same condition wrapped in `not` does (4,391): no comparison ever comes true over a missing field, so its negation comes true. The difference is exactly 500 — the number of documents without the field. A report's "books not from before 2010" line ends up including the 500 books that have no field at all. The comparison counts give the cost. Element-level matching makes 70,018 comparisons and examines 59,494 elements, the document-level conjunction makes 88,749 comparisons. Both read the entire collection: 20,000 documents. This means the choice of operator does not change how many documents are read — what changes that number is the index, and that is this topic's fifth lesson's subject. #### Summary - A field path descends into an array and reaches more than one value; the condition is true when any one of the reached values satisfies it. - The question "copy under repair at Kadikoy" returns 6,033 documents at the document level, 3,340 at the element level; in 2,693 documents the two conditions are satisfied by separate copies. - Negation on an array is inclusive: `copy.status <> "checked_out"` returns 17,787 documents, "no copy is checked out" returns 7,111; the difference is 10,676. - The `in` operator applied to an array means "any one" (14,033 documents); the "all" question is built as a two-condition document-level conjunction (2,777 documents). - A missing field satisfies no comparison, so its negation comes true: the 500 documents with no `publication_year` field fall into the negated form of the condition. #### Next Step Operators are enough to filter a question, but most of the library's questions do not end with filtering: "how many copies are under repair at each branch," "the five most-borrowed books," "the average copy count per author." All of these need grouping, counting, and sorting after the filtering, and it is not possible to state them in a single condition expression. The document model does this work with a pipeline made of stages: each stage takes a stream of records, transforms it, and hands it to the next. The order of the stages determines the length of the stream — depending on whether filtering comes first or last, the number of records the later stages process changes. The next lesson builds that pipeline and counts the effect of the ordering decision on the number of records processed. ### Aggregation Pipeline Source: https://academia.sh/en/courses/nosql/aggregation-pipeline Staged transformation built in its own implementation, and the same question answered under three different stage orders: records processed rising from 43,610 to 124,606, a blocking stage's records held in memory rising from 2,418 to 40,276, and the result staying the same across all three orders. The previous lesson built the evaluator that says whether a document satisfies a condition. Most of the library's questions do not end there: "how many copies of each author's books are under repair," "the five most-borrowed books," "the number of shelved copies per branch." What these questions have in common is that the answer sits not in individual documents but in the **aggregate** of documents, and a condition expression cannot aggregate. The document model does this work with an **aggregation pipeline**: a chain of ordered **stages**. Each stage takes a stream of records, transforms it, and hands it to the next. The word is the same one used for the pipeline that chains shell commands together, and the resemblance is real; where they part is the unit of the stream — what flows through a shell is bytes, what flows through here is records, and the stages operate on records. This lesson's question is not what the stages do, but what their **order** costs. #### Streaming Stage and Blocking Stage Stages split into two classes. A **streaming stage** takes a record, processes it, releases it: filtering, unwinding an array, and projection all work this way, holding a single record in memory at a time. A **blocking stage** must see the entire stream to produce its result: sorting holds the whole stream in memory, grouping holds the group table. A pipeline's memory cost is the number of records its blocking stages hold at any one time. ```js // pipeline.mjs — staged transformation. Each stage takes a stream of records, transforms // it, and hands it to the next. The records in/out per stage and the records that stage // holds in memory are counted. export function run(source, stages) { let stream = source, peak = 0, processed = 0; const report = []; for (const stage of stages) { const name = Object.keys(stage)[0], recordsIn = stream.length; let memory = 1; // streaming stage: holds a single record if (name === "filter") stream = stream.filter(stage.filter); else if (name === "unwind") { // opens an array into its elements const field = stage.unwind; stream = stream.flatMap((b) => (b[field] ?? []).map((o) => ({ ...b, [field]: o }))); } else if (name === "group") { const table = new Map(); for (const b of stream) { const key = stage.group.key(b); table.set(key, stage.group.combine(table.get(key) ?? stage.group.empty(key), b)); } stream = [...table.values()]; memory = table.size; // blocking: the group table sits in memory } else if (name === "sort") { memory = recordsIn; // blocking: the entire stream sits in memory stream = [...stream].sort(stage.sort); } else if (name === "limit") stream = stream.slice(0, stage.limit); else if (name === "project") stream = stream.map(stage.project); processed += recordsIn; peak = Math.max(peak, memory); report.push({ name, recordsIn, recordsOut: stream.length, memory }); } return { result: stream, report, processed, peak }; } export function print(label, stats) { console.log(`${label}: records processed ${stats.processed}, peak memory ${stats.peak} records`); for (const r of stats.report) console.log(` ${r.name.padEnd(8)} in ${String(r.recordsIn).padStart(6)}` + ` -> out ${String(r.recordsOut).padStart(6)} memory ${r.memory}`); } ``` The unwind stage is specific to the document model, and it is the pipeline's most expensive stage: a book document carrying a copy array turns into as many records as the array has elements. 20,000 book documents, once unwound, become 59,494 records. Every stage after this one processes about three times as many records. #### Same Question, Three Orders **NS7 (assumption):** the catalog is 20,000 book documents, each book has 1–5 copies and 2–4 tags, and the seed is 424242. The question is fixed: the five authors ranked highest by number of copies under repair at the Kadikoy branch. Three pipelines answer this question. A puts the filter at the very start; B unwinds the array first and filters afterward; C groups without filtering at all, and filters over the groups. All three must give the correct answer — what is measured is not correctness, but cost. ```js // order-measurement.mjs — the same question is answered with three different stage // orders. The result is the same, records processed and peak memory are not. // pipeline.mjs is in the same directory. import { run, print } from "./pipeline.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"]; const CATALOG = []; for (let i = 1; i <= 20000; i += 1) { const copy = [], tag = []; 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: STATUS[Math.floor(random() * 3)] }); for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1) tag.push(TAGS[Math.floor(random() * 6)]); CATALOG.push({ _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), tag, copy }); } console.log(`catalog ${CATALOG.length} books, ` + `${CATALOG.reduce((t, b) => t + b.copy.length, 0)} copies`); // Question: top 5 authors by number of copies under repair at the Kadikoy branch. const REPAIR = (k) => k.branch === "Kadikoy" && k.status === "in_repair"; const GROUP = { key: (b) => b.author, empty: (k) => ({ author: k, count: 0 }), combine: (g, b) => ({ ...g, count: g.count + 1 }) }; const SORT = (a, b) => b.count - a.count || (a.author < b.author ? -1 : 1); const A = run(CATALOG, [ { filter: (b) => b.copy.some(REPAIR) }, // filter first: at the book level { unwind: "copy" }, { filter: (b) => REPAIR(b.copy) }, // filter the unwound element { group: GROUP }, { sort: SORT }, { limit: 5 }, ]); const B = run(CATALOG, [ { unwind: "copy" }, { filter: (b) => REPAIR(b.copy) }, { group: GROUP }, { sort: SORT }, { limit: 5 }, ]); const C = run(CATALOG, [ { unwind: "copy" }, { group: { key: (b) => `${b.author}|${b.copy.branch}|${b.copy.status}`, empty: (k) => ({ author: k.split("|")[0], branch: k.split("|")[1], status: k.split("|")[2], count: 0 }), combine: (g, b) => ({ ...g, count: g.count + 1 }) } }, { filter: (g) => g.branch === "Kadikoy" && g.status === "in_repair" }, { sort: SORT }, { limit: 5 }, ]); print("A filter first", A); print("B unwind then filter", B); print("C group first then filter", C); const summary = (r) => r.result.map((g) => `${g.author}=${g.count}`).join(" "); console.log(`A result: ${summary(A)}`); console.log(`all three the same: ${summary(A) === summary(B) && summary(B) === summary(C)}`); console.log(`records processed A ${A.processed} B ${B.processed} C ${C.processed}` + ` B/A ${(B.processed / A.processed).toFixed(2)} C/A ${(C.processed / A.processed).toFixed(2)}`); console.log(`peak memory A ${A.peak} B ${B.peak} C ${C.peak}` + ` C/A ${(C.peak / A.peak).toFixed(1)}x`); ``` ``` catalog 20000 books, 59494 copies A filter first: records processed 43610, peak memory 2418 records filter in 20000 -> out 3340 memory 1 unwind in 3340 -> out 11926 memory 1 filter in 11926 -> out 3508 memory 1 group in 3508 -> out 2418 memory 2418 sort in 2418 -> out 2418 memory 2418 limit in 2418 -> out 5 memory 1 B unwind then filter: records processed 87838, peak memory 2418 records unwind in 20000 -> out 59494 memory 1 filter in 59494 -> out 3508 memory 1 group in 3508 -> out 2418 memory 2418 sort in 2418 -> out 2418 memory 2418 limit in 2418 -> out 5 memory 1 C group first then filter: records processed 124606, peak memory 40276 records unwind in 20000 -> out 59494 memory 1 group in 59494 -> out 40276 memory 40276 filter in 40276 -> out 2418 memory 1 sort in 2418 -> out 2418 memory 2418 limit in 2418 -> out 5 memory 1 A result: Author 1068=4 Author 111=4 Author 1530=4 Author 1580=4 Author 1618=4 all three the same: true records processed A 43610 B 87838 C 124606 B/A 2.01 C/A 2.86 peak memory A 2418 B 2418 C 40276 C/A 16.7x ``` #### The Cost of the Order The three pipelines return the same five authors with the same counts; the `all three the same` line confirms it. Where they part is cost, and cost is measured with two separate numbers. Records processed is 43,610 in A, 87,838 in B, 124,606 in C. The difference between A and B comes only from the first filter: A feeds the unwind stage 3,340 of the 20,000 books, B feeds it all of them. The unwind stage produces 11,926 records in A, 59,494 in B — five times as many. Against that, A runs one extra stage, and its first filter looks at 20,000 documents. Overall the ratio is 2.01. The rule is this: a filter is placed not where it will narrow the stream the most, but **before the stage that multiplies records**; unwind is a multiplier. A's first filter is at the document level, not the element level, and it is the loose form the previous lesson measured: it returns 3,340 documents. Of the 11,926 records that unwinding then produces, only 3,508 pass the second filter. This looseness is not a mistake, it is a deliberate choice — a document-level filter does not **miss** the correct result, it only lets extra records through. This is the only condition on a filter placed early in a pipeline: it must be inclusive, it does not need to be narrowing. The second number gives memory. Peak memory in A and B is 2,418 records — the size of the group table, that is, the number of distinct authors with a copy under repair at Kadikoy. In C the same number is 40,276, 16.7 times as many. C's mistake is placing the grouping before the filter: the grouping now holds not just the authors of interest, but every combination of the author–branch–status triple. This number grows with the product of the group key as the collection grows, and a blocking stage exceeding its memory limit leads to the pipeline spilling to disk or being rejected outright. The final `limit` stage sits in the same place in all three and reduces no work in any of them: sorting has already seen all 2,418 records. Limiting does not shrink the work of the blocking stage that precedes it — only a form of sorting that itself keeps just the top five can do that, and that is a decision inside the sort stage, not in the pipeline's order. #### Summary - An aggregation pipeline is made of ordered stages; streaming stages hold a single record, blocking stages (grouping, sorting) hold the entire stream or the group table in memory. - The unwind stage multiplies records: 20,000 book documents turn into 59,494 records. - The same question gives the same answer under three orders, but processes 43,610, 87,838, and 124,606 records; moving the filter before the multiplying stage roughly halves the records processed. - It is enough for an early filter to be inclusive; A's document-level filter lets 3,340 documents through, and of the 11,926 records that unwinding them produces, only 3,508 remain in the result. - Placing grouping before filtering raises peak memory from 2,418 records to 40,276 (16.7×). #### Next Step One thing the three pipelines have in common went unnoticed: all three read the entire collection, 20,000 documents, in their first stage. The stage order changed the records processed and the memory held, not the number of documents read. The only thing that changes that number is the index. In the document model, the index is not structurally different from the index measured in the relational course — but the data it is built over is different: an array field produces more than one entry for a document, an embedded field is addressed by a dotted path, and an index may be asked to cover only part of the documents. The next lesson builds these three cases and counts the index size and the write cost. ### Indexing Source: https://academia.sh/en/courses/nosql/indexing Indexing built over the document's structure: how many entries a single document produces through an array field, combining two array fields into one compound index raising the entry count from 20,000 to 120,042, a condition that must be satisfied by the same element reading 6,033 documents through two single-field indexes versus 3,340 through an element-level index, and a partial index giving the same answer while taking up 5.5% of the collection instead of 27.4%. The previous lesson's three pipelines produced the same answer at three different costs, but shared one thing: all three read the entire collection, 20,000 documents, in their first stage. The stage order changed the records processed and the memory held, not **the number of documents read**. The only structure that changes that is the index. The theory of indexing is not built here. The Relational Database Administration course's Indexes and Partitioning topic measured tree, hash, and inverted indexes, column order, and the gain from a partial index; those numbers still hold here. This lesson's question is the **data the index is built over**. A relational row's indexed column carries a single value; in the document model the same field can be an array, can sit inside a nested document, or can be present in only a portion of the documents. All three cases change the number of index entries, and the entry count determines both size and write cost. #### One Document, More Than One Entry An index entry consists of a key value and a reference to the document carrying that value. In a relational index this relationship is one-to-one: one row produces one entry. When a path descends into an array, the relationship becomes one-to-many — a book with five copies produces five entries in the `copy.branch` index. This is called a **multikey** entry, the storage-side counterpart of the existential rule from the previous lesson: if a path reaches more than one value, the index must address every one of them separately. When the same document produces the same key twice, the index holds a single entry; a book whose three copies are all at Kadikoy appears once in `copy.branch`. The implementation below carries all three decisions: multikey, compound key, and a partial condition. ```js // index.mjs — document index. When a path descends into an array, a single document // produces more than one entry: a multikey entry. Compound keys, element-level keys, and // a partial condition are all supported. Entry bytes come from lesson 01's encoding rule; // every entry also carries an 8-byte reference to the document. const REFERENCE = 8; export function bytes(d) { 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); } // Values at the path: if the path meets an array, it descends into its elements. export function values(root, path) { let items = [root]; for (const name of path.split(".")) { const next = []; for (const d of items) for (const o of Array.isArray(d) ? d : [d]) if (o && typeof o === "object" && !Array.isArray(o) && name in o) next.push(o[name]); items = next; } return items.flatMap((v) => (Array.isArray(v) ? v : [v])); } export class Index { // fields: the paths that build the key. element: if given, the key is built over that // path's ELEMENT and the fields are relative to the element. condition: if given, only // a document or element that satisfies it enters the index -- a partial index. constructor(name, { fields, element = null, condition = null }) { Object.assign(this, { name, fields, element, condition }); this.entries = new Map(); // key -> array of document keys this.raw = 0; // entries before deduplication this.scanned = 0; } keys(doc) { // the keys one document generates const source = this.element ? values(doc, this.element).filter((o) => !this.condition || this.condition(o)) : !this.condition || this.condition(doc) ? [doc] : []; const result = []; for (const k of source) { let product = [[]]; for (const field of this.fields) { const d = values(k, field); product = product.flatMap((prefix) => (d.length ? d : [null]).map((v) => [...prefix, v])); } result.push(...product); } return result; } build(docs) { for (const b of docs) { const generated = this.keys(b).map((a) => JSON.stringify(a)); this.raw += generated.length; for (const a of new Set(generated)) { // the same key counts once per document if (!this.entries.has(a)) this.entries.set(a, []); this.entries.get(a).push(b._k); } } return this; } get count() { return [...this.entries.values()].reduce((t, v) => t + v.length, 0); } get bytes() { let n = 0; for (const [a, k] of this.entries) n += k.length * (JSON.parse(a).reduce((t, v) => t + bytes(v), 0) + REFERENCE); return n; } lookup(...key) { // exact-key lookup const k = this.entries.get(JSON.stringify(key)) ?? []; this.scanned += k.length; return k; } } ``` The `element` option carries the distinction specific to the document model. A compound index built with `fields: ["copy.branch", "copy.status"]` resolves the two paths separately and takes the product of their values; one built with `element: "copy"` instead builds the key **inside each copy on its own**. Both carry the same two fields and answer a different question. #### Seven Indexes, One Catalog **NS7 (assumption):** the catalog is 20,000 book documents, each book has 1–5 copies and 2–4 tags, and the seed is 424242. **NS13 (assumption):** an index entry carries, besides the encoded key value, an 8-byte document reference, and node occupancy counts as full. Rationale: reference width and occupancy vary by engine; neither changes the **ratio** between indexes, they only scale the absolute bytes. The measured task is the previous two lessons' question: books with a copy under repair at the Kadikoy branch, retrieved four ways, each counting the index entries scanned and the documents read. Then the second lesson's third task, 5,000 copy status changes, runs under two index-maintenance decisions. ```js // index-measurement.mjs — seven indexes are built over the same catalog, the same // question is answered four ways, and the index maintenance for 5,000 status changes is // counted under two decisions. // index.mjs is in the same directory. import { Index, bytes } from "./index.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"]; const CATALOG = []; for (let i = 1; i <= 20000; i += 1) { const copy = [], tag = []; 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: STATUS[Math.floor(random() * 3)] }); for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1) tag.push(TAGS[Math.floor(random() * 6)]); CATALOG.push({ _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), tag, copy }); } const BY_KEY = new Map(CATALOG.map((b) => [b._k, b])); const COLLECTION_BYTES = CATALOG.reduce((t, b) => t + bytes(b), 0); const COPY_COUNT = CATALOG.reduce((t, b) => t + b.copy.length, 0); console.log(`catalog ${CATALOG.length} documents, ${COPY_COUNT} copies, collection ${COLLECTION_BYTES} bytes`); const [authorIdx, tagIdx, branchIdx, statusIdx, productIdx, elementIdx, partialIdx] = [ new Index("author", { fields: ["author"] }), new Index("tag", { fields: ["tag"] }), new Index("copy.branch", { fields: ["copy.branch"] }), new Index("copy.status", { fields: ["copy.status"] }), new Index("tag + copy.branch", { fields: ["tag", "copy.branch"] }), new Index("element(branch,status)", { fields: ["branch", "status"], element: "copy" }), new Index("partial element(branch)", { fields: ["branch"], element: "copy", condition: (o) => o.status === "in_repair" }), ].map((d) => d.build(CATALOG)); const INDEXES = [authorIdx, tagIdx, branchIdx, statusIdx, productIdx, elementIdx, partialIdx]; for (const d of INDEXES) console.log(`${d.name.padEnd(23)} raw ${String(d.raw).padStart(6)}` + ` entries ${String(d.count).padStart(6)} per document ${(d.count / 20000).toFixed(2)}` + ` ${String(d.bytes).padStart(7)} bytes %${(100 * d.bytes / COLLECTION_BYTES).toFixed(1)} of collection`); // Same question: books with a copy under repair at the Kadikoy branch. const REPAIR = (k) => k.branch === "Kadikoy" && k.status === "in_repair"; const correct = CATALOG.filter((b) => b.copy.some(REPAIR)).length; const countMatching = (keys) => keys.filter((k) => BY_KEY.get(k).copy.some(REPAIR)).length; console.log(`copies satisfying the condition ${CATALOG.reduce((t, b) => t + b.copy.filter(REPAIR).length, 0)}` + `, documents carrying those copies ${correct}`); const intersection = new Set(branchIdx.lookup("Kadikoy")); const B = statusIdx.lookup("in_repair").filter((k) => intersection.has(k)); const C = elementIdx.lookup("Kadikoy", "in_repair"); const D = partialIdx.lookup("Kadikoy"); const paths = [ ["A scan", 0, CATALOG.map((b) => b._k)], ["B two single-field indexes", branchIdx.scanned + statusIdx.scanned, B], ["C element-level compound", elementIdx.scanned, C], ["D partial element index", partialIdx.scanned, D], ]; for (const [label, scanned, keys] of paths) console.log(`${label.padEnd(28)} entries scanned ${String(scanned).padStart(6)}` + ` documents read ${String(keys.length).padStart(5)} result ${countMatching(keys)}`); // 5,000 copies change status: index maintenance counted under two decisions. const keySet = (d, b) => [...new Set(d.keys(b).map((a) => JSON.stringify(a)))]; const diff = (a, b) => a.filter((v) => !b.includes(v)).length + b.filter((v) => !a.includes(v)).length; let different = 0, full = 0, real = 0; for (let i = 0; i < 5000; i += 1) { const book = CATALOG[(i * 7) % CATALOG.length]; const target = book.copy[i % book.copy.length]; const before = INDEXES.map((d) => keySet(d, book)); if (target.status !== "shelved") real += 1; target.status = "shelved"; const after = INDEXES.map((d) => keySet(d, book)); for (let j = 0; j < INDEXES.length; j += 1) { different += diff(before[j], after[j]); full += before[j].length + after[j].length; } } console.log(`of 5,000 status changes, ${real} actually change the value`); console.log(` diff-based maintenance ${different} entry writes`); console.log(` full document reindexing ${full} entry writes, ${(full / different).toFixed(1)}x`); ``` ``` catalog 20000 documents, 59494 copies, collection 6983575 bytes author raw 20000 entries 20000 per document 1.00 474450 bytes %6.8 of collection tag raw 59730 entries 50179 per document 2.51 1020851 bytes %14.6 of collection copy.branch raw 59494 entries 47982 per document 2.40 984197 bytes %14.1 of collection copy.status raw 59494 entries 38997 per document 1.95 857376 bytes %12.3 of collection tag + copy.branch raw 177480 entries 120042 per document 6.00 3945348 bytes %56.5 of collection element(branch,status) raw 59494 entries 55516 per document 2.78 1914334 bytes %27.4 of collection partial element(branch) raw 20021 entries 18752 per document 0.94 385051 bytes %5.5 of collection copies satisfying the condition 3508, documents carrying those copies 3340 A scan entries scanned 0 documents read 20000 result 3340 B two single-field indexes entries scanned 21248 documents read 6033 result 3340 C element-level compound entries scanned 3340 documents read 3340 result 3340 D partial element index entries scanned 3340 documents read 3340 result 3340 of 5,000 status changes, 3311 actually change the value diff-based maintenance 10840 entry writes full document reindexing 173994 entry writes, 16.1x ``` #### The Cost of the Entry Count The first lines give the source of index size. The `author` index produces exactly one entry per document and takes up 6.8% of the collection — the ratio of a relational index. The `tag` index produces 59,730 raw entries, and after deduplication 50,179 remain — 2.51 per document. The 9,551 entries in between come from the same tag being written twice in one book, collapsed to a single entry. Deduplication is even stronger in the `copy.status` index: 59,494 raw entries drop to 38,997, because on a three-valued field it is ordinary for several copies of one book to share the same status. The fifth line is the lesson's harshest number. When `tag` and `copy.branch` are combined into a single compound index, the entry count is not a sum but a **product**: 177,480 raw entries, 120,042 unique entries, six per document. The index takes 3,945,348 bytes, 56.5% of the collection. This is why engines block two array fields from sharing a compound index — the block prevents this product, it is not a convenience. Kept in two separate indexes, the same two fields total 98,161 entries and 2,005,048 bytes — just over half. #### The Same-Element Condition All four paths return the same 3,340 documents; where they differ is the documents read to reach that answer. The scan reads 20,000 documents. The intersection of the two single-field indexes scans 21,248 entries and reads 6,033 documents — exactly the third lesson's document-level conjunction count. It intersects the set "has a copy at Kadikoy" with the set "has a copy under repair," and it cannot confirm the conditions are satisfied by **the same copy**; that confirmation has to come from reading the document, which is why the 2,693 extra documents are read. The element-level compound index does this work inside the index itself. Because the key is built from each copy's own branch and status, the lookup `("Kadikoy", "in_repair")` returns 3,340 document references directly, and entries scanned is also 3,340. Copies satisfying the condition number 3,508 — the 168 in between are a second copy under repair at the same branch of the same book, collapsed by the index to a single entry. Documents read drop to a sixth of the scan and to 1.8 times less than the index intersection, and every document read stays in the result. Its cost is size: this index takes 1,914,334 bytes, 27.4% of the collection. The partial index gives the same answer far more cheaply. Copies with `status` equal to `in_repair` are 20,021 of the 59,494; an index covering only those takes 18,752 entries and 385,051 bytes, 5.5% of the collection, returning the same 3,340 documents by scanning the same number of entries. Its limit is that the condition it covers must appear in the query: this index says nothing about "shelved copies at Kadikoy," because those copies are not in it. #### The Cost of Writing The last three lines are the other side of the index. 3,311 of the 5,000 copy status changes actually change the value. Maintenance that computes the changed keys and writes only those makes 10,840 entry writes across seven indexes — 2.17 per attempted change. Maintenance that does the same job by dropping and regenerating all of a document's entries makes 173,994 entry writes, 16.1 times as many. The difference shares its root with the second lesson's finding: in the embedded schema, changing one copy's status rewrites the entire book, and regenerating every index entry of a rewritten document is the easiest implementation. A store that knows which field changed avoids the full 16-fold cost; one that does not sees the write cost grow linearly with the index count. Looking at the share per index, the decision is clear: the seven indexes together take 9,581,607 bytes, 1.4 times the collection. In the document model, an index is charged not per field but **per entry**, and the schema itself determines that count. #### Summary - A path descending into an array makes a single document produce more than one index entry; `copy.branch` produces 59,494 raw entries from 20,000 documents, 47,982 after deduplication. - Combining two array fields into one compound index does not add the entries, it multiplies them: 120,042 entries and 56.5% of the collection's space. - The intersection of two single-field indexes cannot confirm that the conditions are satisfied by the same element; it reads 6,033 documents, and 2,693 of them do not stay in the result. - The element-level compound index gives the same answer by scanning 3,340 entries and reading 3,340 documents; the partial index gives the same answer while taking up 5.5% of the collection instead of 27.4%. - Maintenance that computes the changed key spends 10,840 entry writes on 5,000 updates; maintenance that fully reindexes the document spends 173,994 (16.1×). #### Next Step Every index in this lesson was built over fields that already existed, and none of them looked at what those fields carry. The `copy.status` index would just as quietly index a copy written as `repair` instead of `in_repair`; the publication years written as text that the first lesson measured also enter the `publication_year` index under their own type. A flexible schema does not bind whether a field is present, or its type, at write time — the first lesson counted this returning 5,991 or 3,491 documents instead of 3,990 in a range query, and left the question of how to place a rule to this topic. The next lesson writes that rule and measures two numbers: the broken-document classes it catches versus the ones it misses, and the violation count on an already-full collection against the documents a backfill touches. ### Schema Validation Source: https://academia.sh/en/courses/nosql/schema-validation Two measures of adding a rule to a flexible schema: a shallow rule catching two of four broken-document classes and missing two, the same rule placed on an already-full collection producing 3,900 violations across 3,200 documents, a backfill closing 3,000 violations by machine and leaving 900 to a decision, and 785 of 5,000 ordinary updates being rejected on the unfixed collection. Every index in the previous lesson was built over fields that already existed, and none of them looked at what those fields carry: the `copy.status` index silently indexes a value that is not in the dictionary, and the publication years written as text that the first lesson measured also enter the index under their own type. A flexible schema does not bind whether a field is present, or its type, at write time; the first lesson counted this returning 5,991 or 3,491 documents instead of 3,990 in a range query, and left the question of how to place a rule to this lesson. A rule can be placed. **Schema validation** is a rule set attached to a collection and evaluated at write time. This lesson produces two measures of that rule: the class of broken document it catches versus the class it misses, and the number of violations that appear when the rule is placed on an already-full collection, along with the cost of a backfill. #### The Scope of a Rule A validation rule carries three separate decisions. The first is **scope**: does the rule look only at top-level fields, or does it descend into nested documents and array elements. The second is **closedness**: does a field not listed in the rule count as a violation if it is present in the document. The third is **mode**: is a violating write rejected, or written and counted. All three decisions produce a measurable result. ```js // validator.mjs — a rule set attached to a collection. The rule is evaluated at write // time and returns violations along with their class: missing field, wrong type, // out-of-dictionary value, field not present in the rule. The rule can descend into // nested documents and array elements. export function typeName(d) { if (d === null) return "null"; if (Array.isArray(d)) return "array"; if (typeof d === "number") return Number.isInteger(d) ? "int" : "decimal"; return typeof d === "string" ? "text" : "document"; } export function bytes(d) { // lesson 01's encoding rule if (d === null || d === undefined) return 0; 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); } // rule: { fields: { name: { required, type, dictionary, element } }, closed } // closed=true means every field not in the fields list is a violation. export function validate(doc, rule, path = "") { const violation = []; for (const [name, spec] of Object.entries(rule.fields)) { const d = doc[name]; if (d === undefined) { if (spec.required) violation.push({ class: "missing", field: path + name }); continue; } if (typeName(d) !== spec.type) { violation.push({ class: "type", field: path + name }); continue; } if (spec.dictionary && !spec.dictionary.includes(d)) violation.push({ class: "dictionary", field: path + name }); if (spec.element) for (const o of d) violation.push(...validate(o, spec.element, `${path}${name}.`)); } if (rule.closed) for (const name of Object.keys(doc)) if (name !== "_k" && !(name in rule.fields)) violation.push({ class: "extra", field: path + name }); return violation; } export class Collection { // mode: "reject" reverses a violating write, "warn" writes and counts, null if no rule. constructor(rule = null, mode = "reject") { Object.assign(this, { rule, mode, doc: new Map() }); this.o = { written: 0, rejected: 0, warned: 0, bytesWritten: 0 }; } write(b) { const violation = this.rule ? validate(b, this.rule) : []; if (violation.length) { if (this.mode === "reject") { this.o.rejected += 1; return false; } this.o.warned += 1; } this.doc.set(b._k, b); this.o.written += 1; this.o.bytesWritten += bytes(b); return true; } audit() { // scanning a full collection against the rule const counts = new Map(); let broken = 0; for (const b of this.doc.values()) { const violation = validate(b, this.rule); if (violation.length) broken += 1; for (const v of violation) counts.set(v.class + " " + v.field, (counts.get(v.class + " " + v.field) ?? 0) + 1); } return { broken, counts }; } } ``` #### Four Broken Classes, Two Rules The measurement is done with the broken data the previous lessons left behind. **NS7 (assumption):** the catalog is 20,000 book documents, and the seed is 424242. **NS8 (assumption):** in one out of every eight records, the publication year is written as text. **NS12 (assumption):** in one out of every forty records, the publication year field is missing entirely. **NS28 (assumption):** in one out of every fifty records taken from an external source, one copy's status is written with a value not in the dictionary, and in one out of every twenty the publication year is repeated under a second field name. Rationale: all four classes come from the same source — the absence of a definition binding the field's name, type, and value set. The rule is built in two forms. A is shallow: it looks only at top-level fields and is not closed. B descends to the element level and is closed. Both run on the same collection. ```js // rule-measurement.mjs — the same catalog is audited with two rules: a shallow rule that // looks only at top-level fields, a full rule that descends into array elements and // forbids any field not in the rule. Broken-document classes caught and missed, the rule // placed on an already-full collection, and a backfill are all counted. // validator.mjs is in the same directory. import { Collection, validate, bytes } from "./validator.mjs"; let seed = 424242; // visible seed const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"]; const STATUS = ["shelved", "checked_out", "in_repair"]; const TAGS = ["fiction", "history", "children", "poetry", "science", "reference"]; const CATALOG = []; for (let i = 1; i <= 20000; i += 1) { const copy = [], tag = []; 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: STATUS[Math.floor(random() * 3)] }); for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1) tag.push(TAGS[Math.floor(random() * 6)]); const b = { _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), tag, copy }; if (i % 8 === 0) b.publication_year = String(b.publication_year); // NS8: year written as text if (i % 40 === 0) delete b.publication_year; // NS12: field absent if (i % 50 === 0) b.copy[0].status = "lost"; // NS28: out-of-dictionary status if (i % 20 === 0) b.publicationYear = 1950 + (i % 75); // NS28: field repeated under a second name CATALOG.push(b); } const FIELDS = { author: { required: true, type: "text" }, publication_year: { required: true, type: "int" }, tag: { required: true, type: "array" }, }; const RULE_A = { fields: FIELDS }; // shallow: top-level fields const RULE_B = { // full: descends into elements, closed fields: { ...FIELDS, copy: { required: true, type: "array", element: { fields: { barcode: { required: true, type: "text" }, branch: { required: true, type: "text", dictionary: BRANCH }, status: { required: true, type: "text", dictionary: STATUS } }, closed: true } } }, closed: true, }; const CLASS = { "missing year": (b) => b.publication_year === undefined, "text year": (b) => typeof b.publication_year === "string", "out-of-dictionary status": (b) => b.copy.some((k) => !STATUS.includes(k.status)), "duplicate field": (b) => "publicationYear" in b, }; console.log(`catalog ${CATALOG.length} documents, ${CATALOG.reduce((t, b) => t + bytes(b), 0)} bytes`); for (const [name, f] of Object.entries(CLASS)) console.log(` ${name.padEnd(25)} ${CATALOG.filter(f).length} documents`); console.log(` ${"unique broken documents".padEnd(25)} ` + `${CATALOG.filter((b) => Object.values(CLASS).some((f) => f(b))).length}`); // Which class each rule catches. for (const [name, rule] of [["A shallow", RULE_A], ["B full", RULE_B]]) { const row = Object.entries(CLASS).map(([cname, f]) => { const items = CATALOG.filter(f); return `${cname} ${items.filter((b) => validate(b, rule).length > 0).length}/${items.length}`; }); console.log(`${name.padEnd(11)} caught ` + `${CATALOG.filter((b) => validate(b, rule).length > 0).length} documents ${row.join(" ")}`); } // The rule is placed on an already-full collection: violations on existing documents are counted first. const collection = new Collection(RULE_B, "warn"); for (const b of CATALOG) collection.write(b); const { broken, counts } = collection.audit(); console.log(`rule placed after the fact: ${broken} documents violating, ` + `${[...counts.values()].reduce((t, v) => t + v, 0)} violations:`); for (const [name, n] of [...counts].sort((a, b) => b[1] - a[1])) console.log(` ${name.padEnd(22)} ${n}`); // The rule in "reject" mode, collection not yet fixed: what an ordinary update does. function update(mode) { const c = new Collection(RULE_B, mode); for (let i = 0; i < 5000; i += 1) { const book = CATALOG[(i * 7) % CATALOG.length]; const updated = { ...book, copy: book.copy.map((k) => ({ ...k })) }; updated.copy[i % updated.copy.length].status = "shelved"; c.write(updated); } return c.o; } const before = update("reject"); console.log(`5,000 status updates on the unfixed collection: ` + `${before.written} accepted, ${before.rejected} rejected`); // Backfill: which violations close by machine, which need a decision. let machine = 0, decision = 0, touched = 0, bytesWritten = 0; for (const b of CATALOG) { if (validate(b, RULE_B).length === 0) continue; if (typeof b.publication_year === "string") { b.publication_year = Number(b.publication_year); machine += 1; } if ("publicationYear" in b) { delete b.publicationYear; machine += 1; } if (b.publication_year === undefined) decision += 1; decision += b.copy.filter((k) => !STATUS.includes(k.status)).length; touched += 1; bytesWritten += bytes(b); } console.log(`backfill touched ${touched} documents, wrote ${bytesWritten} bytes`); console.log(` violations closed by machine ${machine}, violations needing a decision ${decision}`); console.log(` documents still violating after the backfill ${collection.audit().broken}`); const after = update("reject"); console.log(`same 5,000 updates on the fixed collection: ` + `${after.written} accepted, ${after.rejected} rejected`); ``` ``` catalog 20000 documents, 7001623 bytes missing year 500 documents text year 2000 documents out-of-dictionary status 400 documents duplicate field 1000 documents unique broken documents 3200 A shallow caught 2500 documents missing year 500/500 text year 2000/2000 out-of-dictionary status 100/400 duplicate field 500/1000 B full caught 3200 documents missing year 500/500 text year 2000/2000 out-of-dictionary status 400/400 duplicate field 1000/1000 rule placed after the fact: 3200 documents violating, 3900 violations: type publication_year 2000 extra publicationYear 1000 missing publication_year 500 dictionary copy.status 400 5,000 status updates on the unfixed collection: 4215 accepted, 785 rejected backfill touched 3200 documents, wrote 1103144 bytes violations closed by machine 3000, violations needing a decision 900 documents still violating after the backfill 800 same 5,000 updates on the fixed collection: 4821 accepted, 179 rejected ``` #### Caught and Missed The first five lines give the distribution of the breakage and carry a side finding: the year written as text is in 2,000 documents, not 2,500. One in five of the one-in-eight records written as text are also records that carry no year field at all, and if the field is absent, it has no type. The two broken classes overlap; the classes total 3,900, the distinct document count is 3,200. This is why a violation count and a document count differ in a validation report. The two rules produce different numbers on the same collection. Rule A, shallow, catches 2,500 documents; rule B, full, catches 3,200. The difference is in the rule's scope, and it can be read line by line. On the year classes the two rules agree: 500/500 and 2,000/2,000. On the out-of-dictionary status class, A catches only 100 of the 400 — and these 100 documents are caught not because of the copy status but because of a year violation present in the same document. The class A truly misses is the full one: rule A never looks inside an array element at all. The duplicate-field class shows the same illusion: A catches 500 of the 1,000, every one of them thanks to a different violation. From this comes how the rule should be read. The sentence "the rule caught 2,500 documents" is not a coverage measure; coverage only becomes visible when asked class by class. The shallow rule never touches the document model's most-used structure — a nested document inside an array — and because it is not closed, it does not count a field written under the wrong name as a violation. A field written under the wrong name is a silent class: the query does not read it, the index does not index it, the rule does not see it. #### The Rule Placed Late When a rule is placed on an empty collection, its cost is only the check on the write path. When it is placed on a full collection, three separate numbers appear. The first is the violation count: 3,200 documents, 3,900 violations. The second is what happens to ordinary updates while the rule is in `reject` mode and the collection has not been fixed. When the second lesson's third task, 5,000 copy status changes, runs on this collection, 785 are rejected. None of the rejected writes were introducing a new defect — they only wanted to set the status to `shelved`. The reason for rejection is that, in the embedded schema, an update rewrites the entire document, and the rewritten document still carries its own old violation. A rule placed without fixing the past stops today's work. The third number is the backfill itself. 3,200 documents are read and rewritten: 1,103,144 bytes, 15.8% of the collection. 3,000 of the backfill's violations close by machine — a text year can be converted to a number, a duplicate field can be deleted. The remaining 900 violations need a decision: the year of the 500 documents that have no year at all cannot be derived, and what the 400 out-of-dictionary statuses mean can only be known by asking the library itself — is `lost` a typo, or a real status that belongs in the dictionary. After the backfill, 800 documents still violate, and the same 5,000 updates' rejection count drops from 785 to 179. The rule for the decision follows from these three numbers. A validation rule is not a schema definition, it is a check on the write path; its coverage is measured class by class, and the order for placing it on a full collection is this: first measure in `warn` mode, then backfill, then switch to `reject` mode. The reverse order stops every task that touches an unfixed document. #### Summary - Schema validation is a rule attached to a collection and evaluated at write time; its scope, closedness, and mode are each chosen separately. - A shallow rule fully catches two of four broken classes; it catches 100 of the array element's 400 dictionary violations and 500 of the 1,000 duplicate-field violations, and it catches these documents not because of their own class but because of a different violation in the same document. - Violation count and document count differ: 3,900 violations spread across 3,200 documents, because the broken classes overlap. - When a rule is placed on a full collection in `reject` mode, 785 of 5,000 ordinary status updates are rejected; the rejected writes were not introducing a new defect. - A backfill touches 3,200 documents and writes 1,103,144 bytes; 3,000 violations close by machine, 900 need a decision, 800 documents remain violating, and the rejection count drops to 179. #### Next Step The backfill touched 3,200 documents one at a time, and this makes 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 — a write to one document happens either completely or not at all, but no such bond exists between two writes to two documents. If the backfill had been interrupted halfway, part of the collection would be fixed and part not, with no record saying which part was which. The same question shows up in the library's daily work: issuing one loan changes a copy's status, a member's loan count, and a loan record together. The next lesson counts where single-document atomicity is enough for this task and where it is not, by running the same task in two schemas, and measures the cost of a multi-document transaction. ### Transactions Source: https://academia.sh/en/courses/nosql/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. ## Distributed Behavior The decisions non-relational stores make in a distributed deployment: the primary-secondary topology and its election process, the imbalance risk in choosing a shard key, the acknowledgement-level settings of read and write concerns, how strong, eventual, and causal consistency show up in the application, stating the CAP and PACELC trade-offs correctly, and authentication, role modeling, and encryption configuration. ### Replica Sets Source: https://academia.sh/en/courses/nosql/replica-sets The document store's move beyond a single node: treating the primary-secondary topology not as replication mechanics but as the cluster's own election, translating the majority rule into a tolerated member loss that scales with cluster size, running the same failure across five cluster configurations and measuring whether an election happens, the number of turns without writes, and the number of rolled-back writes produced by the new primary's data gap, and showing how the candidate-selection rule can force a second election round. The previous topic carried the document model as far as single-document atomicity and stopped there. Every measurement up to this point was taken on a single node: how many requests an embedding decision cut the read path down to, where an index's scanned-entry count settled, what a multi-document transaction cost. Most of the document model's promises cannot be tested on a single node, though — horizontal scaling and a service surviving the loss of a machine both require more than one node. This topic covers the store's behavior in a distributed setup, and the first question is this: if the same data sits on more than one member, who decides which of them accepts writes. The library catalog and loan database remains the example domain for this topic; the work being measured is the writing of loan records. #### The Cluster's Own Election The arrangement that keeps the same data on more than one member is called a replica set. One member is the primary and accepts writes; the others are secondary, apply the same changes, and serve reads depending on the configuration. This is the same pattern as the primary-replica setup from the Scaling the Data Layer course; the two names label the same pattern, and there is no mechanical difference between them. The mechanics of replication were built in that course and in the Relational Database Administration course: log streaming, replication lag, the diminishing return of adding a replica, and stale reads were measured there. They are not repeated here. This lesson's question is the decision the cluster makes on its own: who takes over when the primary stops, decided among the members themselves, and the decision has two measurable consequences — no write is accepted for as long as the decision remains unmade, and once the new primary is behind the old one, writes equal to that gap are **rolled back**. The rule that binds the decision is the **majority rule** (quorum): a member can become primary only by winning the votes of more than half the membership. This rule keeps a cluster split in two from having both halves believe themselves the primary. Its cost sits inside the same rule: if a majority cannot assemble, no election starts at all. #### The Mechanism The mechanism below is a **model**: no real cluster, container, or cloud deployment is built, and members are just numbers. A turn is an abstract step; propagation delay, the detection threshold, and the election duration are parameters in turns, not measured time. The model's one realistic assumption is that propagation is **pull**-directed: the secondary reads the primary's log. Once the primary stops, any write that has not yet been read never reaches any member; that is where the rolled-back write comes from. **NS14 — per-member propagation delay is 2, 3, 3, and 5 turns.** Reason: the secondaries' distance from the primary is not equal. **NS15 — the detection threshold is 2 turns, the election is 2 turns.** Reason: deciding that the primary has stopped and collecting votes are separate steps. Both assumptions have a linear effect: if the delay doubles, the rolled-back write count roughly doubles as well. ```js // cluster/model.mjs — the replica set is a MODEL. A turn is an abstract step; propagation // delay, the detection threshold, and the election duration are parameters in turns, not // measured time. No real cluster is built. Propagation is PULL-directed: the secondary reads // the primary's log, so once the primary stops, any write not yet read never reaches any member. export function run({ members, delay, dropped = [], rule = "most-current", priority = 3, failure = 13, detection = 2, election = 2, rate = 3, turns: N = 24 }) { const majority = Math.floor(members / 2) + 1; const down = new Set(); const log = [0]; // turn -> the last seq the primary accepted that turn const applied = Array(members).fill(0); let primary = 0, seq = 0, wait = 0, threshold = detection + election, rejections = 0; let noWrite = 0, oldAccepted = null, newPrimary = null, rolledBack = null; for (let t = 1; t <= N; t += 1) { if (t === failure) { // the primary, and a second member if given, drop in the same turn oldAccepted = seq; for (const i of [primary, ...dropped]) down.add(i); primary = null; } if (primary === null) { noWrite += 1; wait += 1; const voters = [...Array(members).keys()].filter((i) => !down.has(i)); if (voters.length < majority || wait !== threshold) continue; // without a majority, no election ever starts const mostCurrent = voters.reduce((a, b) => (applied[b] > applied[a] ? b : a)); const candidate = rule === "priority" && rejections === 0 && !down.has(priority) ? priority : mostCurrent; if (voters.some((i) => applied[i] > applied[candidate])) { // the majority rule rejects the candidate rejections += 1; threshold += election; continue; // a second election round } newPrimary = candidate; rolledBack = oldAccepted - applied[newPrimary]; seq = applied[newPrimary]; for (let x = 0; x < log.length; x += 1) log[x] = Math.min(log[x], seq); // the log is truncated primary = newPrimary; continue; } seq += rate; // each turn writes `rate` loan records to the primary log[t] = seq; for (let i = 0; i < members; i += 1) { if (down.has(i)) continue; applied[i] = i === primary ? seq : Math.max(applied[i], log[t - delay[i]] ?? 0); } } return { majority, voters: members - down.size, noWrite, rolledBack, newPrimary, oldAccepted, rejections, applied }; } ``` One line of the model carries the whole trade-off: the candidate **cannot be behind any member that voted for it**. The majority rule's real job is not counting votes — it is guaranteeing that the elected member's own log is no older than the log of the majority that voted for it. ```js // cluster/measure.mjs — same failure, four cluster sizes; then two election rules in the same cluster import { run } from "./model.mjs"; const DELAY = [0, 2, 3, 3, 5]; // propagation delay per member (turns) const s = (x, n) => String(x).padStart(n); console.log("24 turns, 3 loan records per turn. The primary stops at turn 13; detection 2, election 2 turns."); console.log("36 records had been accepted before it stopped.\n"); console.log("cluster | dropped | majority | can vote | election | turns w/o write | rolled back | new primary"); console.log("--------|---------|----------|----------|----------|------------------|-------------|-------------"); const SETUP = [ [3, [], "u0"], [3, [1], "u0+u1"], [4, [1], "u0+u1"], [5, [1], "u0+u1"], [5, [4], "u0+u4"], ]; for (const [members, dropped, name] of SETUP) { const r = run({ members, delay: DELAY.slice(0, members), dropped }); console.log(`${s(members, 7)} | ${name.padEnd(7)} | ${s(r.majority, 8)} | ${s(r.voters, 8)} | ` + `${(r.newPrimary === null ? "no" : "yes").padStart(8)} | ${s(r.noWrite, 16)} | ` + `${s(r.rolledBack === null ? "-" : r.rolledBack, 11)} | ${r.newPrimary === null ? "none" : "u" + r.newPrimary}`); } console.log("\n5-member cluster, u0+u4 drop; the candidate-selection rule changes:"); console.log("rule | candidate rejected | election round | turns w/o write | rolled back | new primary"); console.log("--------------|--------------------|-----------------|------------------|-------------|-------------"); for (const rule of ["most-current", "priority"]) { const r = run({ members: 5, delay: DELAY, dropped: [4], rule, priority: 3 }); console.log(`${rule.padEnd(13)} | ${s(r.rejections, 18)} | ${s(r.rejections + 1, 15)} | ${s(r.noWrite, 16)} | ` + `${s(r.rolledBack, 11)} | u${r.newPrimary}`); } console.log("\nindependent of the run: majority = floor(n/2)+1, tolerated member loss = n - majority"); console.log("n : " + [3, 4, 5, 6, 7].map((n) => s(n, 3)).join("")); console.log("majority : " + [3, 4, 5, 6, 7].map((n) => s(Math.floor(n / 2) + 1, 3)).join("")); console.log("loss : " + [3, 4, 5, 6, 7].map((n) => s(n - (Math.floor(n / 2) + 1), 3)).join("")); ``` ``` 24 turns, 3 loan records per turn. The primary stops at turn 13; detection 2, election 2 turns. 36 records had been accepted before it stopped. cluster | dropped | majority | can vote | election | turns w/o write | rolled back | new primary --------|---------|----------|----------|----------|------------------|-------------|------------- 3 | u0 | 2 | 2 | yes | 4 | 6 | u1 3 | u0+u1 | 2 | 1 | no | 12 | - | none 4 | u0+u1 | 3 | 2 | no | 12 | - | none 5 | u0+u1 | 3 | 3 | yes | 4 | 9 | u2 5 | u0+u4 | 3 | 3 | yes | 4 | 6 | u1 5-member cluster, u0+u4 drop; the candidate-selection rule changes: rule | candidate rejected | election round | turns w/o write | rolled back | new primary --------------|--------------------|-----------------|------------------|-------------|------------- most-current | 0 | 1 | 4 | 6 | u1 priority | 1 | 2 | 6 | 6 | u1 independent of the run: majority = floor(n/2)+1, tolerated member loss = n - majority n : 3 4 5 6 7 majority : 2 3 3 4 4 loss : 1 1 2 2 3 ``` #### Reading the Numbers **An even-sized cluster adds nothing extra.** The last three rows of the final block are independent of the run and purely arithmetic: in a four-member cluster the majority is 3, in a three-member cluster it is 2; both rest on tolerating the loss of exactly one member. The fourth member raises the amount of data stored by one increment and never enlarges the tolerated loss. The table shows this directly: the three-member and four-member clusters give the same result when two members drop — no election, 12 turns without writes. **In the rows where no election happens, what is being measured is an outage.** In the three-member cluster where two members drop, exactly one member is left standing, and it may well hold the newest data; it still cannot become primary, because the majority is 2. This is not a missed opportunity — it is the rule itself: the surviving member cannot confirm that its neighbor did not accept a write it never saw. For the remaining 12 turns, not a single loan record is accepted. **Which member drops determines the number of rolled-back writes.** The five-member cluster's two rows show this on their own. When `u0+u1` drop, the most current surviving member is `u2`, and it has applied up to record 27: 36 − 27 = 9 loan records are rolled back. When `u0+u4` drop, `u1` is the one standing, and it has applied up to record 30: the rollback is 6. Same cluster, same outage duration, same majority — the only difference is the identity of the second dropped member, and the result is fifty percent more rolled-back writes. This number is the count of writes the primary accepted but that never reached any surviving member. A rolled-back write is not data loss; it is something sneakier: a loan record that was **accepted and reported successful** and is later disregarded. The member that wrote the request received a response; the loan transaction is not in the record. How this gap gets closed is not this lesson's subject — it is the subject of the acknowledgement-level settings. #### The Candidate Being Elected The second table runs the same failure in the same cluster under two candidate-selection rules. Under the `most-current` rule, the candidate is the most current member among the voters, and the majority rule accepts it in the first round. Under the `priority` rule, a specific member — say, one in the main building — is put forward as the candidate; the model takes this member as `u3`, and `u3` has applied up to record 27. The result shows exactly what the majority rule does: because member `u1` has applied up to record 30, `u3`'s candidacy is **rejected**. The rejected-candidate column reads 1, the election round becomes 2, and turns without writes rise from 4 to 6. The rolled-back write count is 6 under both rules, and that is no coincidence: because the rule never lets a candidate be behind, the most current member ends up as primary either way. What the priority setting pays for is not data — it is **two extra turns of outage**. An operating rule follows from this: a priority setting is free only as long as the promoted member can actually stay current. Promoting a member with high propagation delay means paying one extra election round on every failure. #### Summary - A replica set is a primary-secondary topology, and it is the same pattern as the primary-replica setup in the Scaling the Data Layer course; the two names label one mechanism. - The majority rule is `floor(n/2)+1` votes, and the tolerated member loss is `n − majority`: three- and four-member clusters tolerate a single loss, five- and six-member clusters tolerate two — adding an even-numbered member does not enlarge durability. - In the three- and four-member clusters where two members drop, no election ever started, and for the remaining 12 turns not one loan record was accepted; how current the surviving member's data is does not change this. - In the same outage, the identity of the dropped member determined the rolled-back write count: in the five-member cluster, 9 loan records were rolled back when `u0+u1` dropped, 6 when `u0+u4` dropped. - A rolled-back write is a write that was accepted and reported successful and is later disregarded; its source is that it never reached any surviving member. - When the majority rule rejected the priority candidate, it left the rolled-back write count unchanged but raised turns without writes from 4 to 6. #### Next Step This lesson measured what the cluster does when it loses a member, but every number it measured rested on the same implicit assumption: all the data sits on every member. That assumption carries a limit that replication can never resolve — adding members to the cluster splits reads, not writes or stored data. Once the catalog grows in document count and loan records no longer fit on a single member's disk, the data has to be **split** across members. The split decision itself comes down to choosing a single field, and that choice is made from inside the document. The next lesson counts the criteria for choosing that field: how the uniqueness of the chosen field unbalances the number of documents per shard, why a monotonically increasing field piles all writes onto a single shard, and how many shards the same query mix touches under two different choices. ### Sharding Source: https://academia.sh/en/courses/nosql/sharding Choosing the shard key from a document field: translating the key's presence-in-every-document and uniqueness requirements into an unroutable document count and an upper bound on shard count, measuring five candidate keys on the same twenty-thousand-document loan collection for placement balance and hot shards, counting how many shards the same query mix touches under each candidate, and showing how a compound key without a matching prefix scatters a query. The previous lesson showed what adding a member to the cluster solves and what it does not: when a member is lost, service continues, but every member keeps carrying the entirety of the same data. Once the catalog grows and loan records no longer fit on a single member's disk, replication has nothing left to offer; the data has to be split across members. The name for this split is sharding, and it comes down to a single decision: choosing the field that determines which shard each document goes to. That field is called the **shard key**. The arithmetic of data-splitting strategies — whether the split is range-based or hash-based, how much data a rebalance moves — was measured in the Scaling the Data Layer course and is not repeated here. The question here is specific to the document model: the key is a document field, and choosing that field is an expensive decision to reverse. #### The Key Comes From Inside the Document In a relational table, the partitioning column is part of the schema and is present in every row. The document model offers no such guarantee: documents in the same collection can carry different sets of fields. This places two conditions on the shard key. **The key field must be present in every document.** The router cannot send a document that lacks the field to any shard at all. In the library database this is not an abstract risk: some of the loan records migrated from the legacy system have no branch field at all. **The key's uniqueness bounds the shard count.** The smallest unit of sharding is a single key value; documents that share a value cannot be split apart. A field with six distinct values cannot be spread across more than six shards, and if one of those values carries half the documents, that pile never gets split. This is an upper bound that is independent of the run. The third condition is the one this lesson measures: the key has to spread writes across shards while still letting frequent queries route to a single shard. If a query pins the key's prefix, the router sends it to one shard; this is called a **targeted query**. If it does not, the router has to ask every shard; this is called a **scatter-gather query**. The difference between the two kinds is the number of shards touched, and it can be counted. #### The Mechanism **NS16 — the distribution of loan records across branches is 45, 18, 14, 11, 8, and 4 units.** Reason: the central branch carries the largest collection and the most members. **NS17 — 2 percent of the migrated legacy records have no branch field.** **NS18 — query mix: the member query is 45 percent, the branch end-of-day listing 20 percent, the last seven days' loans 15 percent, access by record id 15 percent, the overdue-loan scan 5 percent.** All three assumptions have a linear effect; if the weights in the mix change, the weighted average below shifts in the same direction. ```js // shard/model.mjs — loan document generator and shard placement. The generator is // handwritten and the seed is visible: every run produces the same document set. The // shard count P is a parameter; range- vs. hash-based placement was measured in the // Scaling the Data Layer course. Fixed here: every document routes by its KEY FIELD VALUE. export const BRANCH = [["central", 45], ["kadikoy", 18], ["besiktas", 14], ["uskudar", 11], ["sisli", 8], ["adalar", 4]]; export const DAY = 180, MEMBER = 6000; export function generate({ count = 20000, seed = 20260731, missingBranch = 0.02 } = {}) { let s = seed % 2147483647; const rand = () => (s = (s * 48271) % 2147483647) / 2147483647; const total = BRANCH.reduce((t, [, w]) => t + w, 0); const docs = []; for (let i = 1; i <= count; i += 1) { let x = rand() * total, branch = BRANCH[0][0]; for (const [name, w] of BRANCH) { if (x < w) { branch = name; break; } x -= w; } const d = { loan_id: i, member_id: 1 + Math.floor(rand() * MEMBER), borrow_day: 1 + Math.floor(rand() * DAY), returned: rand() < 0.82 }; if (rand() >= missingBranch) d.branch = branch; // some legacy records have no branch field docs.push(d); } return docs; } const compare = (a, b) => { // total ordering over key tuples for (let i = 0; i < a.length; i += 1) if (a[i] !== b[i]) return a[i] < b[i] ? -1 : 1; return 0; }; const hashValue = (m) => { let h = 2166136261; for (const c of m) h = Math.imul(h ^ c.charCodeAt(0), 16777619); return h >>> 0; }; // Shard placement: key values are sorted and split into P windows with an equal-doc-count target. // A single key value cannot be split — the smallest unit of sharding is one key value. export function place(docs, fields, P, hashed = false) { const key = (d) => fields.map((f) => d[f]); const complete = docs.filter((d) => fields.every((f) => d[f] !== undefined)); const counts = new Map(); for (const d of complete) { const k = JSON.stringify(hashed ? [hashValue(JSON.stringify(key(d)))] : key(d)); counts.set(k, (counts.get(k) ?? 0) + 1); } const sorted = [...counts.entries()].sort((a, b) => compare(JSON.parse(a[0]), JSON.parse(b[0]))); const target = complete.length / P; const placement = new Map(); let p = 0, cumulative = 0; for (const [k, n] of sorted) { placement.set(k, p); cumulative += n; if (cumulative >= target * (p + 1) && p < P - 1) p += 1; } const shardOf = (d) => placement.get(JSON.stringify(hashed ? [hashValue(JSON.stringify(key(d)))] : key(d))); const distribution = Array(P).fill(0); for (const d of complete) distribution[shardOf(d)] += 1; return { shardOf, distribution, complete, missing: docs.length - complete.length, distinct: counts.size }; } // A query can be routed if it pins a PREFIX of the key (targeted query); if it does not, the // router has to go to every shard (scatter-gather query). Under hash placement a range clause // cannot be used, because adjacent values do not land on adjacent shards. export function touched(query, fields, hashed, y, P) { const usable = []; for (const f of fields) { if (query.eq && f in query.eq) { usable.push({ field: f, type: "eq" }); continue; } if (query.range && query.range.field === f && hashed === false) usable.push({ field: f, type: "range" }); break; } if (usable.length === 0) return P; const matches = (d) => usable.every((u) => u.type === "eq" ? d[u.field] === query.eq[u.field] : d[u.field] >= query.range.min && d[u.field] <= query.range.max); return new Set(y.complete.filter(matches).map(y.shardOf)).size; } ``` ```js // shard/measure.mjs — five shard-key candidates: placement balance, hot shard, touched shards import { generate, place, touched, BRANCH, DAY, MEMBER } from "./model.mjs"; const P = 4, COUNT = 20000; const docs = generate({ count: COUNT }); const CANDIDATE = [["branch", ["branch"], false], ["borrow_day", ["borrow_day"], false], ["hash(borrow_day)", ["borrow_day"], true], ["member_id", ["member_id"], false], ["{branch,member_id}", ["branch", "member_id"], false]]; const QUERY = [ ["S1 member's open loans", 45, (i) => ({ eq: { member_id: 1 + (i * 137) % MEMBER } })], ["S2 branch end-of-day listing", 20, (i) => ({ eq: { branch: BRANCH[i % BRANCH.length][0], borrow_day: 1 + (i * 31) % DAY } })], ["S3 last 7 days' loans", 15, () => ({ range: { field: "borrow_day", min: DAY - 6, max: DAY } })], ["S4 loan record by id", 15, (i) => ({ eq: { loan_id: 1 + (i * 911) % COUNT } })], ["S5 overdue-loan scan", 5, () => ({ eq: {} })], ]; const s = (x, n) => String(x).padStart(n); const recent = docs.filter((d) => d.borrow_day > DAY - 7); console.log(`${COUNT} loan documents, ${P} shards, ${BRANCH.length} branches, ${MEMBER} members, ${DAY} days. Seed 20260731.`); console.log(`taken in the last 7 days: ${recent.length} documents\n`); console.log("shard key | distinct vals | unroutable | shard distribution | busiest/avg | last-7-day busiest shard"); console.log("--------------------|---------------|------------|-------------------------|-------------|-------------------------"); const placement = new Map(); for (const [name, fields, hashed] of CANDIDATE) { const y = place(docs, fields, P, hashed); placement.set(name, y); const fullest = Math.max(...y.distribution) / (y.complete.length / P); const rd = Array(P).fill(0); for (const d of recent) if (fields.every((f) => d[f] !== undefined)) rd[y.shardOf(d)] += 1; const share = Math.max(...rd) / rd.reduce((t, x) => t + x, 0); console.log(`${name.padEnd(19)} | ${s(y.distinct, 12)} | ${s(y.missing, 17)} | ` + `${y.distribution.map((x) => s(x, 5)).join(" ").padEnd(23)} | ${s(fullest.toFixed(2), 11)} | ` + `${s("%" + (100 * share).toFixed(1), 23)}`); } console.log("\nshards touched (per query, 1 = targeted, 4 = scatter-gather):"); console.log("shard key | S1 | S2 | S3 | S4 | S5 | weighted average"); console.log("--------------------|------|------|------|------|------|-----------------"); for (const [name, fields, hashed] of CANDIDATE) { const y = placement.get(name); const cell = [], weighted = []; for (const [, weight, example] of QUERY) { let t = 0; for (let i = 0; i < 12; i += 1) t += touched(example(i), fields, hashed, y, P); cell.push(t / 12); weighted.push((t / 12) * weight); } const avg = weighted.reduce((a, b) => a + b, 0) / QUERY.reduce((a, b) => a + b[1], 0); console.log(`${name.padEnd(19)} | ${cell.map((x) => s(x.toFixed(2), 4)).join(" | ")} | ${s(avg.toFixed(2), 16)}`); } console.log("\nquery mix: " + QUERY.map(([a, w]) => `${a.slice(0, 2)} %${w}`).join(", ")); console.log(`independent of the run: the number of distinct values of a key is the upper bound` + ` on shard count (${BRANCH.length} for branch).`); ``` ``` 20000 loan documents, 4 shards, 6 branches, 6000 members, 180 days. Seed 20260731. taken in the last 7 days: 782 documents shard key | distinct vals | unroutable | shard distribution | busiest/avg | last-7-day busiest shard --------------------|---------------|------------|-------------------------|-------------|------------------------- branch | 6 | 406 | 12328 3489 1597 2180 | 2.52 | %63.8 borrow_day | 180 | 0 | 5022 5031 5031 4916 | 1.01 | %100.0 hash(borrow_day) | 180 | 0 | 5034 4973 5002 4991 | 1.01 | %59.6 member_id | 5788 | 0 | 5000 5000 5002 4998 | 1.00 | %27.0 {branch,member_id} | 13443 | 406 | 4899 4898 4899 4898 | 1.00 | %25.8 shards touched (per query, 1 = targeted, 4 = scatter-gather): shard key | S1 | S2 | S3 | S4 | S5 | weighted average --------------------|------|------|------|------|------|----------------- branch | 4.00 | 1.00 | 4.00 | 4.00 | 4.00 | 3.40 borrow_day | 4.00 | 1.00 | 1.00 | 4.00 | 4.00 | 2.95 hash(borrow_day) | 4.00 | 1.00 | 4.00 | 4.00 | 4.00 | 3.40 member_id | 1.00 | 4.00 | 4.00 | 4.00 | 4.00 | 2.65 {branch,member_id} | 4.00 | 1.50 | 4.00 | 4.00 | 4.00 | 3.50 query mix: S1 %45, S2 %20, S3 %15, S4 %15, S5 %5 independent of the run: the number of distinct values of a key is the upper bound on shard count (6 for branch). ``` #### Placement Balance and Hot Shards **The most intuitive candidate gives the worst balance.** Splitting loan records by branch looks like it matches the operational structure; the measurement says something else. When six branches are squeezed into four shards, the shards end up with 12,328, 3,489, 1,597, and 2,180 documents: the busiest shard holds 2.52 times the average. The reason is uniqueness — the smallest grain a shard can carry is one branch, and the central branch alone produces 45 percent of all loan records. Adding more shards does not fix the imbalance either, because six distinct values are the upper bound for six shards. The row's second number is a warning of its own: 406 documents carry no branch field and cannot be routed to any shard. **A balanced placement is not enough on its own.** The `borrow_day` key splits documents almost perfectly — the busiest shard holds 1.01 times the average. The last column refutes this row: 100 percent of the 782 loans taken in the last seven days fall onto a single shard. When a monotonically increasing field is the key, past data spreads evenly, but every new write piles onto the shard carrying the most recent window. This is called a **hot shard**, and its only visible symptom in the store is that one member queues writes while the cluster's other three sit idle. **Hash placement trades the hot shard for something else.** Hashing the same field brings the hot shard's share down from 100 percent to 59.6 percent. The reason it does not drop to 25 percent is, again, uniqueness: when seven days' seven distinct values spread across four shards, some shards end up with two days. The cost sits in the second table, and it is large. **The candidate with the highest uniqueness gives the best balance.** Under the `member_id` key, the distribution is 5,000, 5,000, 5,002, 4,998, and the last-seven-days share is 27 percent — close to the 25 percent that is ideal for four shards. The compound key gives the same balance but brings back the 406 unroutable documents, because branch sits in its prefix. #### Targeted and Scatter-Gather Queries The second table runs the same query mix across all five candidates, and it reverses the decision that balance alone would suggest. The `member_id` key gives the best result on the weighted average, 2.65 shards, because the mix's heaviest query — the member query — pins the key exactly: 1.00 shard. Under the same key, the branch end-of-day listing rises to 4.00 — because it never pins the key at all, it goes to all four shards at once. The compound key `{branch,member_id}` is this lesson's most instructive row. Its placement balance is perfect (1.00) and the branch query drops to 1.50 shards; against that, the member query rises to 4.00. The reason is that a compound key works left to right: the member query pins the `member_id` field but does not pin the `branch` field in the prefix, so the router cannot tell which shard to go to. Its weighted average, 3.50, is the worst of the five candidates. Adding a compound key does not narrow access — it tightens the prefix condition. Comparing `borrow_day` against its hash placement shows the trade-off in a single column. Hash placement brought the hot shard down from 100 percent to 59.6 percent; in exchange, the last-seven-days query rose from 1.00 to 4.00 shards, and the weighted average climbed from 2.95 to 3.40. Because hash placement does not put adjacent values on adjacent shards, the range query cannot be routed. The thing that spreads writes and the thing that collects reads come into direct conflict here. The last line restates the bound that is independent of the run: the number of distinct values a key has is the upper bound on shard count. This bound does not depend on the machine, the data, or the configuration. #### Summary - The shard key is a document field, and a document that lacks the field cannot be routed: under the branch-based key, 406 of the 20,000 documents could not go to any shard. - The number of distinct values a key has is the upper bound on shard count; in the collection split across six branches, the busiest shard held 2.52 times the average, and adding more shards does not fix this. - A balanced placement does not prevent a hot shard: under the `borrow_day` key, placement was balanced to within 1.01 times even as 100 percent of the 782 loans from the last seven days fell onto a single shard. - Hash placement brought the hot shard's share down to 59.6 percent but raised the range query from 1.00 shard to 4.00 shards; the weighted average climbed from 2.95 to 3.40. - A compound key depends on the prefix condition: the `{branch,member_id}` placement balanced perfectly, but the member query, which does not pin its prefix, scattered across 4.00 shards and came out worst on the weighted average, 3.50. - In this mix, the best key was `member_id`: 1.00 times balance, a 27 percent hot share, and 2.65 weighted shards. The choice is made not by looking at balance but at the mix's heaviest query. #### Next Step This lesson resolved which shard a document goes to, but the shard itself is the previous lesson's replica set: every shard is made up of more than one member, and which of those members has to have seen a write is still open. Both lessons left the same gap — in the first lesson, 6 accepted loan records were rolled back, and how to prevent that was never said. How many members have to acknowledge a write for it to count as "successful" is a setting; in the same way, which member a read is answered from and with what verification is also a setting. The next lesson names these two settings and runs the same loan scenario under three of them: the number of turns an acknowledgement takes to arrive, the number of writes lost at the moment of failure, and how the version seen on a read changes. ### Read and Write Concerns Source: https://academia.sh/en/courses/nosql/read-and-write-concerns Measuring the acknowledgement level as a setting: running the same loan scenario under three write concerns and counting ack turns, acknowledged writes, and the number of writes lost at the moment of failure, separating rolled-back writes from lost writes, showing how requiring acknowledgement from every member turns the loss of a single member into a write outage, and comparing unanswered requests, stale reads, and the number of reads that see data still to be rolled back across four combinations of read concern and read direction. The previous two lessons left the same gap open. In the replica set, accepted loan records were rolled back after a failure, and how to prevent that was never said; the sharding lesson noted that every shard is its own replica set but left open how many members a write has to reach to count as delivered. These two questions are two faces of a single setting. The setting is called the **write concern**: how many members have to have applied a write before it is reported successful to the caller. Its counterpart on the read side is the **read concern**: what verification level a read is answered with. Both are settings that can be given per collection or per request; neither is a fixed property of the store or the cluster. #### Two Separate Settings The number carried by the write concern is called the **acknowledgement level**. `w=1` requires only the primary to apply the write; `w=majority` requires more than half the membership to apply it; `w=all` requires every member. As the acknowledgement level rises, the caller waits longer, because the acknowledgement comes back not from the nearest member but from the **farthest** member among the required count. Two settings of the read concern are measured here. A `local` read returns the value held by the selected member without verification. A `majority` read returns only data that has reached a majority — that is, data that cannot be rolled back. A third setting exists independently of the read concern and must not be confused with it: the **read direction** determines whether a request goes to the primary or to a secondary. The two are chosen separately and produce separate columns in the measurement. #### The Mechanism The mechanism below is again a **model**: no real cluster is built, a turn is an abstract step, and member distance is a parameter in turns. An acknowledgement is the primary **learning** that the required number of members have applied the write; its cost is therefore not a single leg but a round trip. **NS19 — member distance from the primary is 3, 5, 6, and 8 turns.** Reason: some of the secondaries are in the same building, some in a distant site. **NS20 — one loan record is written and one read arrives each turn.** Reason: write and read rates are assumed equal; if the ratio changes, the stale-read count changes linearly. The failure timetable is the same as the first lesson's: the primary stops, detection takes two turns, election two turns. ```js // concern/model.mjs — the acknowledgement level is a MODEL. A turn is an abstract step; the // per-member delay, the failure's turn, and the election duration are parameters in turns, not // measured time. No real cluster is built. A write is one loan record per turn; an ack is the // primary learning that w members have applied the write (round trip, i.e. twice the delay). export const DELAY = [0, 3, 5, 6, 8]; // distance to the primary, per member (turns) export const MEMBERS = 5, FAILURE = 21, DETECTION = 2, ELECTION = 2, TURNS = 48; const MAJORITY = Math.floor(MEMBERS / 2) + 1; export function run({ w, read = "local", direction = "primary" }) { const down = new Set(); const log = [0], applied = Array(MEMBERS).fill(0), writes = [], reads = []; let primary = 0, seq = 0, wait = 0, cutoff = null, handover = null; // standing secondaries' distance from the primary, smallest to largest const distance = () => [...Array(MEMBERS).keys()] .filter((i) => i !== primary && !down.has(i)) .map((i) => Math.abs(DELAY[i] - DELAY[primary])).sort((a, b) => a - b); const ackTime = (k) => { if (k <= 1) return 0; const u = distance(); return u.length >= k - 1 ? 2 * u[k - 2] : null; // without enough members, the ack never arrives }; // the largest seq acknowledged and not rolled back as of t: the threshold staleness is measured against const lastAcked = (t) => writes.reduce((m, y) => (y.ack !== null && y.ack <= t && y.rolledBack === false && y.seq > m ? y.seq : m), 0); for (let t = 1; t <= TURNS; t += 1) { if (t === FAILURE) { down.add(primary); primary = null; } if (primary === null) { wait += 1; const voters = [...Array(MEMBERS).keys()].filter((i) => !down.has(i)); if (voters.length >= MAJORITY && wait === DETECTION + ELECTION) { primary = voters.reduce((a, b) => (applied[b] > applied[a] ? b : a)); cutoff = applied[primary]; seq = cutoff; handover = t; for (let x = 0; x < log.length; x += 1) log[x] = Math.min(log[x], cutoff); for (const y of writes) if (y.seq > cutoff) y.rolledBack = true; // the log is truncated } } else { seq += 1; log[t] = seq; const s = ackTime(w); writes.push({ seq, arrival: t, ack: s === null ? null : t + s, rolledBack: false }); for (let i = 0; i < MEMBERS; i += 1) { if (down.has(i)) continue; applied[i] = i === primary ? seq : Math.max(applied[i], log[t - Math.abs(DELAY[i] - DELAY[primary])] ?? 0); } } // an ack not completed before the primary died never arrives if (t === FAILURE) for (const y of writes) if (y.ack !== null && y.ack >= t) y.ack = null; const secondary = [...Array(MEMBERS).keys()].filter((i) => i !== primary && !down.has(i)); const m = direction === "primary" ? primary : (secondary.length ? secondary[t % secondary.length] : null); if (m === null) { reads.push({ t, noResponse: true }); continue; } // no response while there is no primary const sc = ackTime(MAJORITY); const committed = sc === null ? lastAcked(t) : Math.min(lastAcked(t), log[t - sc] ?? 0); const value = read === "local" ? applied[m] : Math.min(applied[m], committed); reads.push({ t, member: m, value, actual: lastAcked(t), noResponse: false }); } const acked = writes.filter((y) => y.ack !== null && y.ack <= TURNS); const answered = reads.filter((o) => o.noResponse === false); return { ackTurns: writes[0].ack === null ? null : writes[0].ack - writes[0].arrival, acked: acked.length, unacked: writes.length - acked.length, rolledBack: writes.filter((y) => y.rolledBack).length, lost: acked.filter((y) => y.rolledBack).length, afterHandover: acked.filter((y) => y.arrival > handover).length, noResponse: reads.filter((o) => o.noResponse).length, stale: answered.filter((o) => o.value < o.actual).length, staleness: answered.reduce((a, o) => a + (o.actual - o.value), 0) / answered.length, // reads that see data still to be rolled back: only pre-failure reads are counted, because // after the truncation the same seq numbers are reused validly phantom: answered.filter((o) => o.t < FAILURE && cutoff !== null && o.value > cutoff).length, reads: answered.length, handover, cutoff, }; } ``` ```js // concern/measure.mjs — same loan scenario in three write concerns, then four read configurations import { run, MEMBERS, FAILURE, TURNS, DELAY } from "./model.mjs"; const s = (x, n) => String(x).padStart(n); const LABEL = { 1: "w=1", 3: "w=majority", 5: "w=all" }; console.log(`${MEMBERS}-member cluster, member distance ${DELAY.join("/")} turns. ${TURNS} turns, one`); console.log(`loan record per turn. The primary stops at turn ${FAILURE}; detection 2, election 2 turns.\n`); console.log("write concern | ack turns | acked | unacked | rolled back | LOST WRITES | acked after handover"); console.log("--------------|-----------|-------|---------|-------------|-------------|---------------------"); for (const w of [1, 3, 5]) { const r = run({ w }); console.log(`${LABEL[w].padEnd(13)} | ${s(r.ackTurns === null ? "none" : r.ackTurns, 9)} | ${s(r.acked, 5)} | ` + `${s(r.unacked, 7)} | ${s(r.rolledBack, 11)} | ${s(r.lost, 11)} | ${s(r.afterHandover, 21)}`); } console.log("\nread side (write concern fixed at w=1; truncation boundary: seq " + run({ w: 1 }).cutoff + "):"); console.log("read direction | read concern | no response | stale reads | average staleness | saw to-be-rolled-back data"); console.log("---------------|--------------|-------------|-------------|-------------------|---------------------------"); for (const direction of ["primary", "secondary"]) { for (const read of ["local", "majority"]) { const r = run({ w: 1, read, direction }); console.log(`${direction.padEnd(14)} | ${read.padEnd(12)} | ${s(r.noResponse, 11)} | ` + `${s(`${r.stale}/${r.reads}`, 11)} | ${s(r.staleness.toFixed(2), 18)} | ${s(r.phantom, 26)}`); } } const u = DELAY.slice(1).sort((a, b) => a - b); console.log("\nindependent of the run: ack turns is twice the (w-1)th value in the secondaries'"); console.log(`distance ranking. In this cluster the ranking is ${u.join(" < ")}, so as w grows,`); console.log(`ack turns takes the values ${u.map((x) => 2 * x).join(", ")}; it never decreases for any w.`); ``` ``` 5-member cluster, member distance 0/3/5/6/8 turns. 48 turns, one loan record per turn. The primary stops at turn 21; detection 2, election 2 turns. write concern | ack turns | acked | unacked | rolled back | LOST WRITES | acked after handover --------------|-----------|-------|---------|-------------|-------------|--------------------- w=1 | 0 | 44 | 0 | 3 | 3 | 24 w=majority | 10 | 28 | 16 | 3 | 0 | 18 w=all | 16 | 4 | 40 | 3 | 0 | 0 read side (write concern fixed at w=1; truncation boundary: seq 17): read direction | read concern | no response | stale reads | average staleness | saw to-be-rolled-back data ---------------|--------------|-------------|-------------|-------------------|--------------------------- primary | local | 3 | 0/45 | 0.00 | 3 primary | majority | 3 | 44/45 | 7.82 | 0 secondary | local | 0 | 48/48 | 4.06 | 0 secondary | majority | 0 | 48/48 | 8.69 | 0 independent of the run: ack turns is twice the (w-1)th value in the secondaries' distance ranking. In this cluster the ranking is 3 < 5 < 6 < 8, so as w grows, ack turns takes the values 6, 10, 12, 16; it never decreases for any w. ``` #### A Lost Write Is Not the Same as a Rolled-Back Write Two columns of the first table look alike and are not the same thing. The rolled-back write count is 3 under all three settings; this is a fact about the cluster and does not change with the setting, because there are three records the old primary wrote that never reached any surviving member. The lost write count is the subset of those that had already been reported successful to the caller, and it changes directly with the setting: 3 under `w=1`, 0 under `w=majority` and `w=all`. That `w=majority` zeroes out the lost-write count is not a coincidence; it is a direct consequence of the previous lesson's election rule. If a write has reached a majority, every member eligible to become the new primary comes from within that majority; because a candidate cannot be behind the majority that voted for it, that write is also present on the new primary. The write concern and the election rule are two ends of the same number. The cost sits in the ack-turns column: 0 turns against 10. This number does not depend on the run; the line in the final block derives it. Ack turns is twice the `(w-1)`th value in the secondaries' distance ranking. Because the ranking in this cluster is 3, 5, 6, 8, ack turns takes the values 6, 10, 12, 16 as w grows, and it never decreases at any step. Raising the acknowledgement level does not just slow writes down — it translates directly into which member is slow becoming how long the caller waits. #### The Cost of Requiring Acknowledgement From Everyone The `w=all` row gives the harshest result. Before the failure, only 4 of the 20 writes were acknowledged; after the failure, none were. The reason is arithmetic: while one member is down, the "every member" condition can never be satisfied. In a five-member cluster, the loss of a single member stops writes entirely under `w=all`. This row shows that the acknowledgement level cannot be read as "higher is better." `w=all` zeroes out lost writes, but it buys that with 40 unacknowledged writes and zero throughput after the failure. `w=majority` achieves the same zero loss with 16 unacknowledged writes and 18 acknowledged writes after the failure. The majority rule is the peak here too: raising the acknowledgement level above the majority adds no durability, only fragility. Writes left unacknowledged are not data loss; they are writes the caller does not know the outcome of. A loan record may or may not have posted to the member's account. Being retriable requires that the loan operation itself be designed to be idempotent. #### Read Direction and Read Concern The second table compares all four combinations in the same scenario, and each of the four pays a different cost. `primary` + `local`: none of the 45 responses is stale, average staleness 0.00. Against that, 3 reads saw data that was later rolled back, and 3 requests went unanswered during the outage window. This setting gives the most current answer and carries the greatest risk of being wrong: a record showing on the loan screen can turn out never to have existed a few turns later. `primary` + `majority`: reads that see data still to be rolled back drop to 0. The cost sits in the stale-reads column — 44 of the 45 responses are stale, average staleness 7.82 loan records. A majority read does not give the "correct" value; it gives the value that will not be rolled back, and it waits for the majority to catch up to get it. The shared gain of the two `secondary`-direction rows is in the no-response column: 0. A request reading from a secondary gets an answer even while the primary is down and an election is running. This is the right setting for library catalog searches. The cost in both rows is staleness: 4.06 records with `local`, 8.69 with `majority`. Combining the secondary direction with a majority read stacks two sources of delay on top of each other — the member's own lag plus the majority's commit delay. The rule that follows is to configure per operation. The loan-writing operation is written with `w=majority`, and the majority is awaited before the member is told "the book is yours"; the same record's reflection in the catalog is read with `secondary` + `local`, accepting a staleness of four records. #### Summary - Write concern and read concern are settings given per request; the acknowledgement level is the number of members required for a write to count as successful. - The rolled-back write count came out at 3 under all three settings — this is a fact about the cluster; the lost-write count changed with the setting: 3 under `w=1`, 0 under `w=majority` and `w=all`. - Ack turns is derived independently of the run: twice the `(w-1)`th value in the secondaries' distance ranking — 6, 10, 12, 16 in this cluster, and it never decreases at any step. - Under `w=all`, the loss of a single member stopped writes entirely: acknowledged writes after the failure, 0; total unacknowledged, 40. Going above the majority added no durability. - The four combinations of read settings paid four separate costs: `primary`+`local`, 3 unanswered requests and 3 reads that saw data still to be rolled back; `primary`+`majority`, 44/45 stale and 7.82 staleness; the `secondary` direction, 0 unanswered but 48/48 stale. - Read direction and read concern are separate settings; combining them stacks two sources of delay (4.06 against 8.69 staleness). #### Next Step There is something this lesson's tables leave unnamed. The guarantee given by `w=majority` together with a `majority` read does not carry the same name as the guarantee given by `w=1` with a `local` read; there are combinations standing between the two as well, and each of them promises something different. The names for these promises were defined in the Introduction to System Design course: strong consistency, eventual consistency, monotonic reads, and read-your-writes. The definitions stay there; what is missing here is which combination of settings delivers which promise. The next lesson builds that mapping, adds a model not on that list — causal consistency — and runs the same member session under six combinations of settings, counting the number of read-your-writes failures, monotonic violations, reads where the causal link breaks, and the wait turns that make up the cost of each guarantee. ### Consistency Models Source: https://academia.sh/en/courses/nosql/consistency-models Translating combinations of settings into consistency models: measuring which read and write concern gives which model by running the same member session under six settings, separating the settings that preserve session guarantees using read-your-writes failures and monotonic-violation counts, defining causal consistency over two collections that sit on separate shards and counting reads where the causal link breaks, and translating each guarantee's cost into a number of turns waited. The previous lesson's two tables counted settings but never named them. The promise `w=1` with a `local` read gives is not the promise `w=majority` with a `majority` read gives, and the combinations between the two promise separate things as well. The names for these promises — strong consistency, eventual consistency, monotonic reads, read-your-writes — were defined and measured in the Introduction to System Design course; the definitions are not repeated here. This lesson's job is translation. A store does not select a consistency model; it selects a setting. The triple of write concern, read concern, and read direction corresponds to a model name, and whether it earns that name can be counted. This lesson builds that mapping, adds a model off that list — causal consistency — and runs one member session under six settings. #### Causal Consistency There is a wide range between eventual and strong consistency, and its most useful point is **causal consistency**. Its promise: if a write was made after seeing another write's result, every read that sees the second also sees the first; unlinked writes can be seen in different orders. This is where it departs from strong consistency — it orders only the linked writes, not all of them. In the library database, the link is concrete: a loan record is written, and once acknowledged, the overdue fine tied to it is written, citing it because that loan's existence was seen. The break is one kind of read: **the fine is visible, the loan record it cites is not** — a fine whose source cannot be found. On a single replica set this cannot happen, because a secondary applies the primary's log in order: a member that has applied the fine has also applied the loan. The break comes from the two collections sitting on **separate shards** — the previous two lessons built this arrangement, the shard key chosen per collection, each shard its own replica set with its own member distances. The reading session reads the two collections from two different members; the ordering guarantee lives inside a cluster, not between clusters. #### The Mechanism The mechanism is again a model: no real cluster is built, a turn is an abstract step, member distance is a parameter in turns. **NS21 — member distances on the fine shard's replica set are 1, 2, 3, and 4 turns; the loan shard's cluster is NS19's (3, 5, 6, 8 turns).** Reason: the fine collection is kept in a single site, the loan collection is spread across branches. **NS22 — one loan transaction happens every eight turns, and the fine record is sent one turn after its loan record's acknowledgement.** Reason: a fine is written only after the record is seen processed. Both assumptions are linear: if the distances grow, the breach window grows in the same proportion. ```js // session/model.mjs — session guarantees and causality are a MODEL: a turn is an abstract step, // member distance is a parameter in turns, no real cluster is built. The loan collection and the // fine collection sit on SEPARATE SHARDS; each shard is its own replica set with its own // distances. A fine record is sent AFTER the loan record is ACKNOWLEDGED: the link is causal. export const DELAY = { loan: [0, 3, 5, 6, 8], fine: [0, 1, 2, 3, 4] }; export const OPS = 12, GAP = 8, TURNS = 108, MAJORITY = 3, SECONDARY = [1, 2, 3, 4]; // derived in Lesson 3: ack turns is twice the (w-1)th value in the secondaries' distance ranking export const ackTurns = (shard, w) => w <= 1 ? 0 : 2 * DELAY[shard].slice(1).sort((a, b) => a - b)[w - 2]; // The largest seq a member has seen as of turn t. A majority read is further bounded by the // point where the write reaches a majority and the primary learns it (Lesson 3's commit point). const visible = (writes, shard, member, t, read) => writes.reduce((s, y) => y.sent + DELAY[shard][member] <= t && (read !== "majority" || y.sent + ackTurns(shard, MAJORITY) <= t) ? y.seq : s, 0); // "primary" is a single member; "sticky" binds the session to the nearest secondary on both // shards; "rotating" goes to a different secondary each turn, crossing the two shards in opposite // directions. Every fourth turn the loan read jumps to the farthest secondary — where the monotonic violation appears. const pickMember = (direction, t, shard) => direction === "primary" ? 0 : direction === "sticky" ? SECONDARY[0] : shard === "fine" ? SECONDARY[t % 4] : SECONDARY[(3 * t) % 4]; export function run({ w, read = "local", direction = "primary", token = false }) { const ack = ackTurns("loan", w), loan = [], fine = []; for (let j = 1; j <= OPS; j += 1) { // the loan schedule is independent of the setting const g = 1 + (j - 1) * GAP; loan.push({ seq: j, sent: g, ack: g + ack }); fine.push({ seq: j, sent: g + ack + 1 }); } const sees = (y, p, u, t) => visible(y, p, u, t, read); // With the session token on, a read from a member that has not caught up is not answered: the // member is waited on until it does. The number of turns waited is the guarantee's cost. const catchUp = (y, p, u, t, target) => { let x = t; while (x <= TURNS && sees(y, p, u, x) < target) x += 1; return x - t; }; let rywMiss = 0, writeWait = 0; // the writing session: reads its own record back at ack time for (const y of loan) { const t = y.ack, m = pickMember(direction, t, "loan"); if (sees(loan, "loan", m, t) >= y.seq) continue; if (token) writeWait += catchUp(loan, "loan", m, t, y.seq); else rywMiss += 1; } // the reading session: each turn reads the fine collection first, then the loan record it cites let monoViol = 0, causalBreak = 0, stale = 0, readWait = 0, waited = 0, seenSeq = 0; for (let t = 1; t <= TURNS; t += 1) { const fc = sees(fine, "fine", pickMember(direction, t, "fine"), t); const m = pickMember(direction, t, "loan"); let lo = sees(loan, "loan", m, t), tr = t; // tr: the turn the answer is given if (token) { const b = catchUp(loan, "loan", m, t, Math.max(fc, seenSeq)); if (b > 0) { waited += 1; readWait += b; tr = t + b; lo = sees(loan, "loan", m, tr); } } if (lo < seenSeq) monoViol += 1; if (fc > lo) causalBreak += 1; // the fine is visible, the loan it cites is not if (lo < loan.filter((y) => y.ack <= tr).length) stale += 1; // measured against what was acked by answer time seenSeq = Math.max(seenSeq, lo); } return { rywMiss, monoViol, causalBreak, stale, wait: writeWait + readWait, writeWait, readWait, waited, ack }; } ``` ```js // session/measure.mjs — same member session under six settings: which setting gives which guarantee import { run, ackTurns, DELAY, SECONDARY, OPS, GAP, TURNS, MAJORITY } from "./model.mjs"; const s = (x, n) => String(x).padStart(n); const SETTING = [ ["w=1 / local / rotating", { w: 1, direction: "rotating" }], ["w=1 / local / sticky", { w: 1, direction: "sticky" }], ["w=1 / local / rotating + token", { w: 1, direction: "rotating", token: true }], ["w=1 / local / primary", { w: 1, direction: "primary" }], ["w=majority / majority / primary", { w: MAJORITY, read: "majority", direction: "primary" }], ["w=majority / majority / rotating", { w: MAJORITY, read: "majority", direction: "rotating" }], ]; console.log(`loan shard member distances ${DELAY.loan.join("/")}, fine shard's ` + `${DELAY.fine.join("/")} turns.\n${TURNS} turns, one loan record every ${GAP} turns (${OPS} ops); ` + `the fine record is sent one turn\nafter its own loan record's ack.\n`); console.log("setting (write concern / read concern / direction) | read-your- | monotonic | causal | stale | ack | wait"); console.log(" |writes miss | violation | break | reads | turns | (turns)"); console.log("-----------------------------------------------------|------------|------------|--------|--------|-------|--------"); for (const [name, choice] of SETTING) { const r = run(choice); console.log(`${name.padEnd(52)} | ${s(`${r.rywMiss}/${OPS}`, 10)} | ${s(r.monoViol, 10)} | ` + `${s(`${r.causalBreak}/${TURNS}`, 6)} | ${s(`${r.stale}/${TURNS}`, 6)} | ${s(r.ack, 5)} | ${s(r.wait, 6)}`); } const b = run({ w: 1, direction: "rotating", token: true }); console.log(`\nwait with the token on: ${b.writeWait} turns across ${OPS} read-backs, ` + `${b.readWait} turns in the reading session\n(${b.waited}/${TURNS} reads waited).`); // Independent of the run: the fine being visible while its loan is not can only happen if the // loan member's distance exceeds the fine member's distance by more than the gap between the two // writes (ack turns + 1). for (const w of [1, MAJORITY]) { const gap = ackTurns("loan", w) + 1; const n = SECONDARY.flatMap((lm) => SECONDARY.map((fm) => DELAY.loan[lm] > DELAY.fine[fm] + gap)).filter(Boolean).length; console.log(`independent of the run: the gap between the two writes at w=${w === 1 ? "1" : "majority"} ` + `is ${gap} turns;\n${n} of ${SECONDARY.length ** 2} member pairs break causality regardless of direction.`); } const farthest = Math.max(...DELAY.loan), mc = ackTurns("loan", MAJORITY); console.log(`independent of the run: the largest member distance is ${farthest} turns, the majority ack turns ${mc};` + `\nbecause ${farthest} < ${mc}, the value a majority read returns is independent of the member read from.`); ``` ``` loan shard member distances 0/3/5/6/8, fine shard's 0/1/2/3/4 turns. 108 turns, one loan record every 8 turns (12 ops); the fine record is sent one turn after its own loan record's ack. setting (write concern / read concern / direction) | read-your- | monotonic | causal | stale | ack | wait |writes miss | violation | break | reads | turns | (turns) -----------------------------------------------------|------------|------------|--------|--------|-------|-------- w=1 / local / rotating | 12/12 | 24 | 24/108 | 60/108 | 0 | 0 w=1 / local / sticky | 12/12 | 0 | 12/108 | 36/108 | 0 | 0 w=1 / local / rotating + token | 0/12 | 0 | 0/108 | 47/108 | 0 | 156 w=1 / local / primary | 0/12 | 0 | 0/108 | 0/108 | 0 | 0 w=majority / majority / primary | 0/12 | 0 | 0/108 | 0/108 | 10 | 0 w=majority / majority / rotating | 0/12 | 0 | 0/108 | 0/108 | 10 | 0 wait with the token on: 96 turns across 12 read-backs, 60 turns in the reading session (24/108 reads waited). independent of the run: the gap between the two writes at w=1 is 1 turns; 12 of 16 member pairs break causality regardless of direction. independent of the run: the gap between the two writes at w=majority is 11 turns; 0 of 16 member pairs break causality regardless of direction. independent of the run: the largest member distance is 8 turns, the majority ack turns 10; because 8 < 10, the value a majority read returns is independent of the member read from. ``` #### Which Setting Preserves Session Guarantees In row one, the loan desk cannot read its own writes at all: all 12 of 12 acknowledged writes were missing from the read-back at the turn of acknowledgement. This does not depend on the run: under `w=1`, ack turns is 0, while the nearest secondary is 3 turns behind, so a read-back to a secondary never finds the record. On the loan screen, the member's loan list appears empty right after the book was handed over. The same row has 24 monotonic violations: routing is rotating, so every fourth turn the read jumps from the nearest secondary to the farthest, which has not yet applied the write, and the loan count on screen goes backward. Row two applies the Caching, Queues and Asynchronous Processing course's sticky routing to reads: the session binds to one secondary. Monotonic violations drop from 24 to 0, since a member's sequence number never goes backward; stale reads drop from 60 to 36. The one unchanged column is read-your-writes, still 12/12 — stickiness binds the client to a secondary, and that secondary is still behind the primary. Row four gives both session guarantees for free: 0/12, 0 violations, 0 stale reads, 0 turns waited — pulling the read direction to the primary is the cheapest path to them. This setting's cost does not show here; the previous lesson measured it as 3 unanswered requests during the outage window and 3 reads that saw data later rolled back. #### The Causal Link Breaking The causal-break column shows where session guarantees fall short. Under rotating, 24 of 108 reads saw the fine while the loan record it cited was not visible; under sticky that falls to 12 but does not zero out, even though the same row shows 0 monotonic violations. This divergence is the lesson's main result: sticky routing preserves a member's own internal ordering, not the link between two shards' separate clusters. The fine shard's nearest secondary is 1 turn behind, the loan shard's is 3, and the fine write is sent only 1 turn after its loan's acknowledgement; the two-turn gap produces a break on every transaction. Row three shows the setting that closes the link. The session carries the furthest point it has seen in a session token; a read is not answered from a member lagging behind that point — it waits until the member catches up. All three violation columns drop to 0. The cost is in the wait column: 156 turns, 96 across 12 read-backs and 60 in the reading session, with 24 of 108 reads waiting. The same row's stale-reads column stays at 47/108, and this is not a flaw but the definition: causal consistency says the answer will not go backward, not that it will be current. The final two run-independent lines give the break's structure. A break happens when the loan member's distance exceeds the fine member's distance by more than the gap between the writes. Under `w=1` this gap is 1 turn, and 12 of 16 member pairs break causality regardless of direction. Under `w=majority` the gap widens to 11 turns and the count falls to 0 — raising the acknowledgement level does not lower the probability of a break, it removes it structurally. #### Translating the Setting Into a Model Name | Setting | Model given | Measured counterpart | |---|---|---| | `w=1`, `local`, rotating secondary | eventual consistency | 12/12 miss, 24 violations, 24/108 breaks | | `w=1`, `local`, sticky secondary | eventual consistency and monotonic reads | 0 violations, breaks still at 12/108 | | `w=1`, `local`, session token | causal consistency | all three at 0, 156 turns waited, 47/108 stale | | `w=majority`, `majority` | strong consistency | every column 0, 10 turns of ack per write | The last two rows give the same numbers: a majority read returns the same value from the primary or a rotating secondary. The reason is independent of the run — the largest member distance is 8 turns, the majority ack turns is 10, and 8 < 10 means no member can lag behind the commit point. A member 12 turns away in a distant site would break this inequality, making a majority read depend on which member it was read from. That rows four and five cannot be told apart is a limit of the table, not the settings. While the cluster is healthy, `primary` + `local` gives all of strong consistency's zeros for free. The previous lesson measured the difference: when the primary failed, `w=1` produced 3 lost writes, `w=majority` produced 0 — the 10 turns of ack per write is the price of that difference. #### Summary - A store does not select a consistency model, it selects a setting: the write concern, read concern, and read direction triple corresponds to a model name, and whether it earns that name can be counted. - Under `w=1`, every token-free setting reading from a secondary produced read-your-writes failures at 12/12; this does not depend on the run, since ack turns is 0 while the nearest secondary is 3 turns behind. - Sticky routing brought monotonic violations from 24 to 0 but causal breaks only from 24 to 12: a session guarantee preserves ordering inside one member, not the link between two shards' clusters. - Causal consistency was achieved with a session token; all three violation columns dropped to 0, its cost was 156 turns waited, and stale reads stayed at 47/108. - Pulling the acknowledgement level to the majority widened the gap between the two writes from 1 turn to 11 turns and brought breaking member pairs from 12 to 0; a structural change, not a change in probability. - On a healthy cluster, `primary` + `local` gave the same zeros as strong consistency for free; the difference shows only in the outage window, and its price is 10 turns per write. #### Next Step The measurements so far assumed the cluster was whole: members could see each other, and only delay changed. When the link breaks, the same settings mean something different: `w=majority` stops writes on the side that cannot assemble a majority, while a `local` read keeps answering. This trade-off was built and measured in the Introduction to System Design course under the names CAP and PACELC. In the context of a store, though, it is misstated: a store is said to be "CP" or "AP," as if that were a product property. The next lesson corrects this: the same cluster runs the same split under more than one setting, and the label is counted as a property of the setting, not the store. The 10 turns of ack measured here are paid even on a healthy cluster — that is the bill outside any split. ### CAP and PACELC Source: https://academia.sh/en/courses/nosql/cap-and-pacelc Stating the trade-off correctly: running the same replica set under the same split across four settings and comparing rejected writes, rolled-back writes, unanswered reads, and stale reads, showing that a single setting can choose consistency on the write path and availability on the read path, measuring that a choice is made even when no split ever happens, in wait turns and a staleness window, and separating the structural bound that comes from cluster size from the decision that comes from the setting. The previous lesson measured the cost of strong consistency as 10 turns of ack per write and closed on the note that this number is paid even while the cluster is healthy. This lesson opens that note. The second matter it takes up is a misstatement: when distributed stores are discussed, a store is said to be "CP" or "AP," as if that were a product property. The CAP theorem's three letters and PACELC's two branches were defined in the Introduction to System Design course; the same split scenario was run under two policies, stale responses and rejected requests were counted, the non-split latency trade-off was measured, and the theorem's common misreadings were sorted out. Those definitions and that discussion are not repeated here. The work here is to apply that same measurement layout to a store's setting and count where the label actually belongs. #### The Label Belongs to the Setting, Not the Product The previous three lessons showed the same thing over and over: write concern, read concern, and read direction are settings that can be given per request. If a store supports all of these settings, giving that store a single classification is a category error. The class is a property of the running **request**, not the store. Testing this is direct: same cluster, same split, same code, only the setting changes. If the class name changes, the label belongs to the setting. #### The Mechanism **NS23 — the split lasts 16 turns and divides the cluster in two: two members on the branch side, three on the central side.** Reason: the branch is connected to the central site by a single link, and when that link breaks, the two branch members are left alone. **NS24 — a primary that loses contact with the majority steps itself down after a timeout; this is 3 or 12 turns.** Reason: how long a primary keeps accepting writes after losing majority contact is a setting. The second assumption's effect is linear and is shown in the table with two values. ```js // cap/model.mjs — the split is a MODEL: a turn is an abstract step, member distance and the // split window are parameters in turns, no real network is built. A five-member replica set // splits in two: u0 (the current primary) and u1 on the branch side, u2, u3, u4 on the central // side. The branch client can never reach the central side. SAME CLUSTER, SAME CODE — only the setting changes. export const DELAY = [0, 3, 5, 6, 8], MEMBERS = 5, MAJORITY = 3; export const TURNS = 40, SPLIT = [11, 26], DETECTION = 2, ELECTION = 2; const RANKED = DELAY.slice(1).slice().sort((a, b) => a - b); export const ackTurns = (w) => (w <= 1 ? 0 : 2 * RANKED[w - 2]); export function run({ w, read, stepDown = 3, split = true }) { const s0 = split ? SPLIT[0] : TURNS + 1, s1 = split ? SPLIT[1] : TURNS + 1; const down = s0 + stepDown; // a primary that loses majority contact steps itself down const electAt = s0 + DETECTION + ELECTION; // the central side elects its own primary const ack = ackTurns(w); const writtenAt = [0]; // seq -> the turn it was written (branch side) let seq = 0, branchAccepted = 0, branchRejected = 0, centralAccepted = 0, provisional = []; let answered = 0, stale = 0, noResponse = 0, staleness = 0, wait = 0; for (let t = 1; t <= TURNS; t += 1) { const splitNow = t >= s0 && t <= s1; // branch write: one loan record per turn, always sent to that side's own primary const primaryUp = splitNow === false || t < down; const wOk = splitNow === false || w <= 1; // the minority side can never assemble a majority if (primaryUp && wOk) { seq += 1; writtenAt[seq] = t; branchAccepted += 1; wait += ack; if (splitNow) provisional.push(seq); // accepted in the minority: rolled back at rejoin } else branchRejected += 1; if (splitNow && t >= electAt) centralAccepted += 1; // the central side elects its own primary and keeps writing // branch read: a local concern is answered by that side's own secondary; a majority concern // cannot be confirmed on the minority side, so it goes unanswered if (read === "majority" && splitNow) { noResponse += 1; continue; } const seen = read === "majority" ? writtenAt.findLastIndex((x) => x + ackTurns(MAJORITY) <= t) : writtenAt.findLastIndex((x) => x + DELAY[1] <= t); answered += 1; if (seen < seq) { stale += 1; if (seen >= 1) staleness = Math.max(staleness, t - writtenAt[seen]); // not yet counted if there is no record } } return { branchAccepted, branchRejected, rolledBack: provisional.length, centralAccepted, answered, stale, noResponse, staleness, wait, ack }; } ``` ```js // cap/measure.mjs — same cluster, same split, four settings; then the same four settings with NO split import { run, ackTurns, DELAY, SPLIT, TURNS, MAJORITY } from "./model.mjs"; const s = (x, n) => String(x).padStart(n); const SETTING = [ ["w=majority · majority", { w: MAJORITY, read: "majority" }], ["w=1 · local (step-down 3)", { w: 1, read: "local", stepDown: 3 }], ["w=1 · local (step-down 12)", { w: 1, read: "local", stepDown: 12 }], ["w=majority · local", { w: MAJORITY, read: "local" }], ]; const window = SPLIT[1] - SPLIT[0] + 1; console.log(`${TURNS} turns, member distance ${DELAY.join("/")}. The link is cut on turns ${SPLIT[0]}-${SPLIT[1]}`); console.log(`(${window} turns): u0 and u1 on the branch side, u2, u3, u4 on the central side.`); console.log("One loan write and one catalog read arrive at the branch side every turn.\n"); console.log("setting | branch write accepted | rejected | rolled back | central write | read answered | stale | no response"); console.log("---------------------------|------------------------|----------|-------------|---------------|---------------|-------|------------"); for (const [name, p] of SETTING) { const r = run(p); console.log(`${name.padEnd(26)} | ${s(r.branchAccepted, 22)} | ${s(r.branchRejected, 8)} | ${s(r.rolledBack, 11)} | ` + `${s(r.centralAccepted, 13)} | ${s(r.answered, 13)} | ${s(r.stale, 5)} | ${s(r.noResponse, 10)}`); } console.log("\nsame four settings, with NO split at all:"); console.log("setting | ack turns | total wait | staleness window | stale reads | no response"); console.log("---------------------------|-----------|------------|-------------------|-------------|------------"); for (const [name, p] of SETTING) { const r = run({ ...p, split: false }); console.log(`${name.padEnd(26)} | ${s(r.ack, 9)} | ${s(r.wait, 10)} | ${s(r.staleness + " turns", 17)} | ` + `${s(`${r.stale}/${r.answered}`, 11)} | ${s(r.noResponse, 10)}`); } console.log("\nindependent of the run: the minority side keeps 2 members, majority threshold " + `${MAJORITY};`); console.log("2 < 3 means that side can never assemble a majority under any setting — this is not a setting"); console.log(`outcome, it is the cluster size's. Majority ack turns ${ackTurns(MAJORITY)}, local ack turns ${ackTurns(1)}.`); ``` ``` 40 turns, member distance 0/3/5/6/8. The link is cut on turns 11-26 (16 turns): u0 and u1 on the branch side, u2, u3, u4 on the central side. One loan write and one catalog read arrive at the branch side every turn. setting | branch write accepted | rejected | rolled back | central write | read answered | stale | no response ---------------------------|------------------------|----------|-------------|---------------|---------------|-------|------------ w=majority · majority | 24 | 16 | 0 | 12 | 24 | 24 | 16 w=1 · local (step-down 3) | 27 | 13 | 3 | 12 | 40 | 29 | 0 w=1 · local (step-down 12) | 36 | 4 | 12 | 12 | 40 | 38 | 0 w=majority · local | 24 | 16 | 0 | 12 | 40 | 26 | 0 same four settings, with NO split at all: setting | ack turns | total wait | staleness window | stale reads | no response ---------------------------|-----------|------------|-------------------|-------------|------------ w=majority · majority | 10 | 400 | 10 turns | 40/40 | 0 w=1 · local (step-down 3) | 0 | 0 | 3 turns | 40/40 | 0 w=1 · local (step-down 12) | 0 | 0 | 3 turns | 40/40 | 0 w=majority · local | 10 | 400 | 3 turns | 40/40 | 0 independent of the run: the minority side keeps 2 members, majority threshold 3; 2 < 3 means that side can never assemble a majority under any setting — this is not a setting outcome, it is the cluster size's. Majority ack turns 10, local ack turns 0. ``` #### Same Cluster, Four Settings, Four Behaviors The first table carries this lesson's argument on its own. All four rows use the same cluster, the same 16-turn split, and the same code; the only thing that differs is the setting, and four different behaviors come out. Row one chooses consistency: 16 writes on the branch side were rejected, 16 reads went unanswered, and 0 writes were rolled back. Row two chooses availability: no read went unanswered, the branch accepted 3 more writes — and those 3 writes were rolled back at rejoin. The relationship between the two rows is an exact equality, and it is no coincidence: every acceptance won on the minority side is a write that gets rolled back. 27 − 24 = 3, and in row three, 36 − 24 = 12. Raising the step-down timeout from 3 turns to 12 accepted 9 more writes and rolled back exactly 9 more. Availability here is not a trade-off but a **trade**: the exchange rate is one to one, and the setting itself does not set the rate, only the volume. Row four settles the label debate. Under `w=majority` combined with a `local` read, the write path behaves like row one — 16 rejections, 0 rolled back — and the read path behaves like row two: 40 answers, 0 unanswered. One store, one cluster, one setting; consistency on writes, service availability on reads. This row cannot be given a single-letter class. The class belongs to the path the operation takes. The central-write column reads 12 in all four rows, and it closes another misunderstanding. The store did not stop during the split; the central side assembled its majority, elected its own primary, and kept writing. The 16 rejected writes are what the client on the minority side sees, not what the store does. A classification has to say whose vantage point it is taken from. #### A Choice Is Made Even Without a Split The second table gives the run where the link is never cut, and the four rows diverge there too. The two `w=majority` settings waited 400 total turns across 40 turns; the two `w=1` settings waited 0. Those 400 turns have nothing to do with the split — they were spent, on every write, waiting for a majority acknowledgement to come back while the link was perfectly healthy. Likewise, the staleness window is 10 turns for a majority read and 3 for a local read, and that difference too was measured with no split at all. Row four stays mixed here too: 400 turns waited on the write path, a 3-turn staleness window on the read path. The setting does not fit a single letter on the non-split branch any more than it did on the split branch. | Setting | Under the split (P branch) | Outside the split (E branch) | Measured | |---|---|---|---| | `w=majority` · majority | consistency | consistency | 16 rejected, 16 unanswered; 400 wait turns, 10-turn staleness | | `w=1` · local, step-down 3 | availability | latency | 0 unanswered, 3 rolled back; 0 wait, 3-turn staleness | | `w=1` · local, step-down 12 | availability | latency | 0 unanswered, 12 rolled back; 0 wait, 3-turn staleness | | `w=majority` · local | consistency on writes, availability on reads | consistency on writes, latency on reads | 16 rejected but 0 unanswered; 400 wait, 3-turn staleness | In library operations, this table translates directly into a configuration. The loan-writing operation takes row one's setting: when the link breaks, the branch cannot lend books, but no loan record is ever later disregarded. The catalog search takes row four's read side: it keeps answering even when the link breaks, accepting a three-turn staleness. Both decisions are made on the same cluster, over the same collection, with separate requests. #### What Is Structural and What Depends on the Setting Not everything is a setting, and missing that distinction is a second misstatement. The final block's line is independent of the run: the minority side is left with two members, the majority threshold is three, and because 2 < 3, that side can never assemble a majority under any setting. This is not the result of a policy but of the cluster size and where the split falls. That is what a setting cannot change; what it can change is how long that side keeps accepting writes. This same distinction lines up with the first lesson's result: there, in the three-member cluster where two members dropped, no election ever started, and the surviving member's data currency did not change that. Structural bounds sit above the setting table; the setting table can only produce a decision inside the space that bound allows. #### Summary - The same cluster, the same 16-turn split, and the same code produced four different behaviors under four settings; the class name is a property of the setting and the operation's path, not the store. - Every acceptance won on the minority side is a write that gets rolled back: raising the step-down timeout from 3 to 12 turns took accepted writes from 27 to 36 and rolled-back writes from 3 to 12 — a difference of 9 in both columns. - The `w=majority` + `local` read combination chose consistency on the write path (16 rejected, 0 rolled back) and service availability on the read path (40 answered, 0 unanswered); this row cannot be given a single-letter class. - During the split, the central side accepted 12 writes under all four settings: the store did not stop — what stopped was the service the minority-side client saw. - A choice was paid for even without any split: the `w=majority` settings waited 400 turns across 40 turns, the majority read's staleness window came out at 10 turns, the local read's at 3. - There is a bound no setting can change: the minority side is left with two members while the majority threshold is three, and because 2 < 3, that side can never assemble a majority under any setting. #### Next Step Throughout this topic, every decision the cluster made was measured as a setting: how many members would acknowledge, where a read would go, how long a primary keeps accepting writes after losing majority contact. Everything measured shared one assumption that was never stated: that the sender of the request was authorized to make it. In the model, every write that reached the cluster wrote a loan record, every read got an answer; who the request came from was never asked. In a real deployment this is the first question asked, and its answer is a configuration too — one whose default is the most dangerous kind. The next lesson takes up the store's authentication, role-scope, and encryption settings: what a deployment with authorization turned off is exposed to, what narrowing a role's scope down to the collection level buys, and what cost transport and at-rest encryption each add. ### Security Configuration Source: https://academia.sh/en/courses/nosql/security-configuration Measuring authorization as a setting: counting the collections and records reachable in a deployment with authentication turned off, running the same five application identities under cluster-wide, database-level, and collection-level roles and comparing the totals of readable, writable, and personal-data-carrying records, naming the residue that least privilege cannot shrink, and pulling out the cost of transport and at-rest encryption as extra bytes and an extra processing step. The previous lesson ran the same cluster under the same split across four settings and counted the classification as a property of the request's path, not the store. In those runs, every write that reached the cluster was either accepted or rejected, every read either answered or left unanswered. Not once was it asked who the request came from. This lesson asks that question, and its answer is a configuration too. Authentication mechanics are not covered here; the subject is the store's own settings. Three things are measured: what a closed-off authorization setting is exposed to, how much narrowing role scope shrinks it, and which line item encryption adds cost to, and how much. #### Exposed Surface Is a Countable Quantity The adjectives used to describe a security configuration — strict, loose, adequate — carry no decision. Its measurable counterpart is the **exposed surface**: the total of records the identities defined in a configuration can read. Two more quantities stand beside it: writable records, and readable records that carry personal data. Its inputs are collection sizes, the identities the store recognizes, and the scope of the role assigned to each identity; the first two come from the deployment, the third is a decision. #### The Mechanism **NS31 — the deployment has seven collections, 154,540 records, and five application identities; each identity's job touches a specific handful of collections.** Reason: staff and audit collections are added to the catalog, member, loan, and fine collections used throughout the course; a search service, a loan endpoint, a fine job, a report job, and a backup job are a typical breakdown. **NS32 — in transport encryption, a frame carries at most 16,384 bytes and takes 29 bytes of overhead; connection setup is 5,200 bytes per connection.** Reason: the overhead is a header, a sequence counter, and an authentication tag; what determines the result is not the number itself but that it is **independent of response size**. **NS33 — at-rest encryption works on 4,096-byte blocks, keeps 28 bytes of metadata per block, and every block read is one extra decryption step.** The mechanism is a **model**: there is no real deployment, network, or identity provider. There is no measured number in the classes themselves; NS31–NS33 are assumptions, and every number in the output is a calculation derived from them. ```js // security/model.mjs — the store CONFIGURATION is the model: no real deployment, network, or // identity provider exists. Role scope and encryption cost are computed from the parameters. export const COLLECTION = [ // database, collection, records, bytes per record, carries personal data? ["library", "book", 20000, 368, false], ["library", "member", 12000, 214, true], ["library", "loan", 20000, 96, true], ["library", "fine", 4800, 72, true], ["library", "summary", 1560, 88, false], ["ops", "staff", 180, 260, true], ["ops", "audit", 96000, 128, false], ]; export const IDENTITY = ["catalog-search", "loan-endpoint", "fine-processing", "report", "backup"]; const grant = (db, coll, ...actions) => ({ db, coll, actions }); const ALL = [grant("*", "*", "read", "write")]; const sameForAll = (r) => Object.fromEntries(IDENTITY.map((k) => [k, r])); const DB_LEVEL = [grant("library", "*", "read", "write")]; const LEAST = { "catalog-search": [grant("library", "book", "read")], "loan-endpoint": [grant("library", "book", "read"), grant("library", "member", "read"), grant("library", "loan", "read", "write")], "fine-processing": [grant("library", "loan", "read"), grant("library", "fine", "read", "write")], report: [grant("library", "loan", "read"), grant("library", "fine", "read")], backup: [grant("*", "*", "read")], }; export const CONFIG = [ { name: "C0 authentication off", identity: "no", role: sameForAll(ALL) }, { name: "C1 cluster-wide single role", identity: "yes", role: sameForAll(ALL) }, { name: "C2 database-level role", identity: "yes", role: { ...sameForAll(DB_LEVEL), backup: LEAST.backup } }, { name: "C3 collection-level (least privilege)", identity: "yes", role: LEAST }, { name: "C4 collection-level + summary collection", identity: "yes", role: { ...LEAST, report: [grant("library", "summary", "read")] } }, ]; const matches = (i, d) => (i.db === "*" || i.db === d[0]) && (i.coll === "*" || i.coll === d[1]); export function surface(y) { const row = IDENTITY.map((k) => { let read = 0, write = 0, personal = 0; for (const d of COLLECTION) { const applicable = y.role[k].filter((i) => matches(i, d)); if (applicable.some((i) => i.actions.includes("read"))) { read += d[2]; if (d[4]) personal += d[2]; } if (applicable.some((i) => i.actions.includes("write"))) write += d[2]; } return { k, read, write, personal }; }); const total = (a) => row.reduce((s, r) => s + r[a], 0); const single = row.filter((r) => r.k !== "backup").map((r) => r.read); return { row, read: total("read"), write: total("write"), personal: total("personal"), widestSingle: Math.max(...single) }; } export const FRAME = 16384, FRAME_OVERHEAD = 29, HANDSHAKE = 5200, BLOCK = 4096, BLOCK_OVERHEAD = 28; export const frameCount = (b) => Math.ceil(b / FRAME); export const blockCount = (b) => Math.ceil(b / BLOCK); export const bytes = (d) => d[2] * d[3]; export const TOTAL_BYTES = COLLECTION.reduce((s, d) => s + bytes(d), 0); export const TOTAL_BLOCKS = COLLECTION.reduce((s, d) => s + blockCount(bytes(d)), 0); const SUMMARY_BYTES = bytes(COLLECTION.find((d) => d[1] === "summary")); export const WORKLOAD = [ // name, request count, bytes carried per request, blocks touched per request ["catalog-search point lookup", 180000, 1472, 1], ["loan-endpoint point lookup", 20000, 640, 1], ["fine-processing point lookup", 4800, 208, 1], ["report summary scan", 12, SUMMARY_BYTES, blockCount(SUMMARY_BYTES)], ["nightly backup", 1, TOTAL_BYTES, TOTAL_BLOCKS], ]; ``` ```js // security/measure.mjs — same collections, same five identities, five configurations; then the // same workload's transport and at-rest encryption cost import { COLLECTION, IDENTITY, CONFIG, WORKLOAD, surface, frameCount, blockCount, bytes, FRAME_OVERHEAD, HANDSHAKE, BLOCK_OVERHEAD, TOTAL_BYTES, TOTAL_BLOCKS } from "./model.mjs"; const n = (x) => String(x).replace(/\B(?=(\d{3})+(?!\d))/g, ","); const s = (x, w) => n(x).padStart(w); const pct = (x) => (x * 100).toFixed(2); const RECORDS = COLLECTION.reduce((a, d) => a + d[2], 0); console.log(`${COLLECTION.length} collections, ${n(RECORDS)} records, ${n(TOTAL_BYTES)} bytes, ` + `${IDENTITY.length} application identities; the record columns are totaled across five identities.\n`); console.log("configuration | identity | readable | widest single | writable | personal"); console.log("--------------------------------------------|----------|----------|----------------|----------|---------"); for (const cf of CONFIG) { const r = surface(cf); console.log(`${cf.name.padEnd(44)} | ${cf.identity.padEnd(8)} | ${s(r.read, 8)} | ` + `${s(r.widestSingle, 14)} | ${s(r.write, 8)} | ${s(r.personal, 7)}`); } const bk = CONFIG.map((cf) => surface(cf).row.find((r) => r.k === "backup")); console.log(`\nRecords the backup identity reads across the five configurations: ` + `${bk.map((r) => n(r.read)).join(", ")} (personal ${n(bk[4].personal)}).`); const requests = WORKLOAD.reduce((a, w) => a + w[1], 0); const load = WORKLOAD.reduce((a, w) => a + w[1] * w[2], 0); const frameEk = WORKLOAD.reduce((a, w) => a + w[1] * frameCount(w[2]) * FRAME_OVERHEAD, 0); console.log(`\nThe same day's workload: ${n(requests)} requests, ${n(load)} bytes carried.`); console.log("workload | requests | request bytes | frame overhead | ratio | decrypt steps"); console.log("------------------------------|----------|----------------|-----------------|--------|--------------"); for (const [name, count, b, bl] of WORKLOAD) { const ek = frameCount(b) * FRAME_OVERHEAD; console.log(`${name.padEnd(29)} | ${s(count, 8)} | ${s(b, 14)} | ${s(count * ek, 15)} | ` + `${("%" + pct(ek / b)).padStart(6)} | ${s(count * bl, 13)}`); } console.log(`${"total".padEnd(29)} | ${s(requests, 8)} | ${s(load, 14)} | ${s(frameEk, 15)} | ` + `${("%" + pct(frameEk / load)).padStart(6)} | ${s(WORKLOAD.reduce((a, w) => a + w[1] * w[3], 0), 13)}`); const POOL = 64, book = COLLECTION.find((d) => d[1] === "book"); console.log(`\nConnection setup ${n(HANDSHAKE)} bytes: with a ${POOL}-connection pool, ` + `${n(POOL * HANDSHAKE)} bytes (%${pct(POOL * HANDSHAKE / load)}); with one connection per ` + `request, ${n(requests * HANDSHAKE)} bytes (%${pct(requests * HANDSHAKE / load)}).`); console.log(`At-rest encryption: ${n(TOTAL_BLOCKS)} blocks x ${BLOCK_OVERHEAD} bytes = ` + `${n(TOTAL_BLOCKS * BLOCK_OVERHEAD)} bytes overhead (%${pct(TOTAL_BLOCKS * BLOCK_OVERHEAD / TOTAL_BYTES)}); ` + `a single point read decrypts 1 block, scanning the book collection decrypts ${n(blockCount(bytes(book)))}.`); console.log(`\nindependent of the run: the frame overhead is a fixed ${FRAME_OVERHEAD} bytes, its ratio` + ` depends on response size — %${pct(FRAME_OVERHEAD / 208)} on a 208-byte response, ` + `%${pct(FRAME_OVERHEAD / 16384)} on a full frame, ${(16384 / 208).toFixed(0)}x.`); ``` ``` 7 collections, 154,540 records, 24,665,680 bytes, 5 application identities; the record columns are totaled across five identities. configuration | identity | readable | widest single | writable | personal --------------------------------------------|----------|----------|----------------|----------|--------- C0 authentication off | no | 772,700 | 154,540 | 772,700 | 184,900 C1 cluster-wide single role | yes | 772,700 | 154,540 | 772,700 | 184,900 C2 database-level role | yes | 387,980 | 58,360 | 233,440 | 184,180 C3 collection-level (least privilege) | yes | 276,140 | 52,000 | 24,800 | 118,580 C4 collection-level + summary collection | yes | 252,900 | 52,000 | 24,800 | 93,780 Records the backup identity reads across the five configurations: 154,540, 154,540, 154,540, 154,540, 154,540 (personal 36,980). The same day's workload: 204,813 requests, 305,071,440 bytes carried. workload | requests | request bytes | frame overhead | ratio | decrypt steps ------------------------------|----------|----------------|-----------------|--------|-------------- catalog-search point lookup | 180,000 | 1,472 | 5,220,000 | %1.97 | 180,000 loan-endpoint point lookup | 20,000 | 640 | 580,000 | %4.53 | 20,000 fine-processing point lookup | 4,800 | 208 | 139,200 | %13.94 | 4,800 report summary scan | 12 | 137,280 | 3,132 | %0.19 | 408 nightly backup | 1 | 24,665,680 | 43,674 | %0.18 | 6,024 total | 204,813 | 305,071,440 | 5,986,006 | %1.96 | 211,232 Connection setup 5,200 bytes: with a 64-connection pool, 332,800 bytes (%0.11); with one connection per request, 1,065,027,600 bytes (%349.11). At-rest encryption: 6,024 blocks x 28 bytes = 168,672 bytes overhead (%0.68); a single point read decrypts 1 block, scanning the book collection decrypts 1,797. independent of the run: the frame overhead is a fixed 29 bytes, its ratio depends on response size — %13.94 on a 208-byte response, %0.18 on a full frame, 79x. ``` #### Authenticating Does Not Shrink the Surface, Scope Does The first table's first two rows are identical: 772,700 readable, 772,700 writable, 184,900 personal records. Turning authentication on did not shrink the exposed surface by a single record. The table does not show the difference, because it holds identity count fixed. Under C0 that count is not five: every client reaching the store behaves like one of these five rows, deletion included. C0's exposed surface is not 772,700 — it is the reachable-client count times 154,540. Authentication is not the setting that shrinks the surface; it is the setting that binds it to a **finite set of identities**. The shrinking is done by scope. The three levels of scope give three numbers: the database level brings readable records down to 387,980, the collection level to 276,140. The real difference is in writes — 772,700 → 233,440 → 24,800, a 31.2x factor — because only two of the five identities need to write at all. The `widest single` column shows what a single compromised identity would see: 154,540 → 58,360 → 52,000. But that column leaves the backup identity out; the row below it shows the backup's read count staying at 154,540 across all five configurations, 36,980 of it personal. Least privilege did not change the worst case — it confined it to a single identity, one whose job is to read everything. C4 shows the final step: when the report job is given a summary collection carrying no personal fields, readable records drop to 252,900, personal records to 93,780. Where narrowing authorization ends, narrowing the **data** begins. #### Encryption's Cost Is Fixed, Its Ratio Is Not The second table computes transport encryption over the same day's workload: the overall ratio is 1.96 percent, 5,986,006 bytes against 305,071,440. The spread is wide — 13.94 percent on the 208-byte fine response, 0.18 percent on the 24,665,680-byte backup transfer. The frame overhead is fixed at 29 bytes; what sets the ratio is not the encryption but how small the response is, and the last line gives this independent of the run: 79x. The real line item is below the table. Connection setup is 5,200 bytes per connection: with a 64-connection pool, 332,800 bytes a day, 0.11 percent of the load. The same workload opening a new connection per request runs to 1,065,027,600 bytes, 349 percent of the data carried. What makes transport encryption look expensive is usually how connections get established, not the encryption itself. At-rest encryption is a separate line item: 6,024 blocks × 28 bytes = 168,672 bytes, 0.68 percent of the data, independent of data size. The cost at rest is small; the real cost is a processing step, and it is measured not by record count but by **blocks touched**: 1 for a point read, 1,797 for a scan of the book collection. The day's 204,813 requests produce 211,232 decryption steps, 6,024 of them from a single nightly backup. #### Summary - Exposed surface is a countable quantity: the total records defined identities can read, alongside the totals of writable and personal records. - Turning authentication on did not shrink the exposed surface at all (772,700 → 772,700); that setting binds the surface to a finite set of identities. With it off, the exposed surface is the number of reachable clients times 154,540, writes and deletes included. - Narrowing scope from a cluster-wide role to the collection level brought readable records down to 276,140 and writable records down to 24,800 (a 31.2x factor). - Least privilege did not change the worst case: the backup identity read all 154,540 records under every one of the five configurations. Where narrowing authorization ends, narrowing data begins — giving the report job a summary collection brought personal records from 118,580 to 93,780. - Transport encryption's frame overhead is fixed at 29 bytes: its ratio is 13.94 percent on a 208-byte response, 0.18 percent on a full frame. Connection setup without a pool adds 349 percent of the data carried. - At-rest encryption costs 0.68 percent at rest; its processing cost is the number of blocks touched — 1 extra decryption step for a point read, 1,797 for a scan of the book collection. #### Course Wrap-Up This course asked one question across nineteen lessons: when the same work is run under two models or two decisions, what is the measured difference, and which guarantee was given up. | Lesson | Two models/decisions compared | Measured difference | Guarantee given up | |---|---|---|---| | Key-Value Stores | key access — index | penalty query 1 — 20,000 round trips | a condition on the field | | Document Databases | document — relational | nested record 1 — 4 round trips | write-time validation | | Wide-Column Stores | row layout — column-family layout | circulation summary 1,872 — 51 pages | one layout serving two access patterns | | Graph Databases | join — traversal | at the fifth degree, 14,190,839 — 217,544 | cost's independence from degree | | Time Series Stores | full timestamp — delta encoding | 9,331,200 — 329,013 bytes | the access unit becomes the segment | | Model Selection Criteria | single pattern — mix | the winner changes with the mix | scoring accounting for writes | | Document Data Types | explicit — short name — fixed schema | 7,652,469 — 6,319,047 — 3,236,623 bytes | the field name being stored | | Embedding and Referencing | embedded — referenced schema | branch query 6,450,690 — 825,072 bytes | the book page's single round trip | | Query Operators | document-level — element-level conjunction | 6,033 — 3,340 documents | conditions being met within the same element | | Aggregation Pipeline | filter first — group first | peak memory 2,418 — 40,276 | freedom of stage order | | Indexing | intersection — element-level compound index | 6,033 — 3,340 documents read | maintenance 10,840 — 173,994 entries | | Schema Validation | shallow — full rule, `reject` mode | 2,500 — 3,200 documents caught | ordinary writes going through | | Transactions | single document — multi-document transaction | 0/20 — 12/20 violations, 18 aborts | abort-freedom, a 637,044-byte undo image | | Replica Sets | three-/four-member — five-member cluster | 12 turns without writes, 9 — 6 rolled back | the durability of an accepted write | | Sharding | `borrow_day` — `hash(borrow_day)` — `member_id` | hot share 100% — 59.6% — 27.0% | balance preventing a hot shard | | Read and Write Concerns | `w=1` — `w=majority` — `w=all` | ack turns 0/10/16, lost writes 3/0/0 | write availability | | Consistency Models | sticky routing — session token | causal breaks 24 → 12 → 0 | stale reads staying at 47/108 | | CAP and PACELC | `w=majority`·majority — `w=1`·local | 16 rejected/16 unanswered — 0 unanswered | the durability of an acceptance in the minority | | Security Configuration | cluster-wide role — least privilege | writable 772,700 — 24,800 | a single identity handling every job | The two right-hand columns are this course's rule: it is not the family that gets chosen, it is the **access pattern**; every model buys a performance gain by giving up a guarantee. Picking a family by name is not a decision — the decision is writing down which work gets how many times cheaper and which guarantee drops. In none of the nineteen rows is a gain free. These nineteen rows share one more assumption, never stated. The key-value store wrote its value to disk, the wide-column store flushed its in-memory table to a file, the replica set acknowledged only after the write reached disk, and this lesson's at-rest encryption encrypted exactly that disk. Stores keeping all their data in memory, where durability itself turns into a setting, were never taken up. The next course — **In-Memory Stores and Caching Systems** — starts from there.