Wide-Column Stores

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.

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

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

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