Snapshot and Restore

Rollover reduced getting rid of old data to dropping a file. The same structure changes backups too: segments that never change once written turn what needs backing up from “a state constantly in flux” into a set of immutable files.

An in-memory store’s snapshot was measured earlier: the relationship between the interval and the loss window, the cost taking a snapshot places on the running store. That measurement is not repeated here. The question here is specific to the index. If segments are immutable, a snapshot can be incremental; what does a background merge do to that, and when the index has to come back, is moving it from the store cheaper, or reindexing from the source.

Segment-Level Snapshot

CO18. A segment file is immutable along with its name: a file with a given name in the store always carries the same content. An incremental snapshot is built on this — if that name already exists in the store, the file is not copied again.

CO19. The snapshot’s cost is copied bytes; what the store holds is the sum of its distinct segment files.

CO20. Reindexing assumes the source records are on hand, and that the same daily batches and the same merge policy are applied. Time depends on the run environment and so is not printed; instead, two run-independent quantities are counted: copied bytes, and documents and tokens processed.

The corpus is 8,000 book records, seed 20260731.

// backup.mjs — catalog corpus, analyzers, segmented index, and segment-level snapshot store
import { writeFileSync, existsSync, mkdirSync, statSync } from 'node:fs';

export function rng(seed) {                   // deterministic pseudo-random generator
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const ADJ = 'silent distant broken lost white black thin deep yellow long'.split(' ');
const NOUN = 'door sea road house city garden island notebook river well'.split(' ');
const TOPIC = ('juvenile fiction|short story|novel|essay|poetry|history|geography|philosophy|psychology|' +
  'economics|architecture|music|cinema|travel|biography|memoir|science fiction|mystery|folklore').split('|');
const ROOT = ('book author narrative story child city memory journey generation war migration family ' +
  'sea winter morning letter photograph train street school library wind silence hope island rain ' +
  'forest village mountain river border century woman soldier teacher doctor painter song verse cover').split(' ');
const FILLER = 'and with a or'.split(' ');

function form(root, i) {                      // surface form: eight suffix variants
  const SUF = ['', 's', "'s", 'less', 'like', 'ish', 'ward', 'ful'];
  return root + SUF[i];
}

export function corpusBuild(count, seed) {
  const r = rng(seed), list = [];
  for (let i = 0; i < count; i++) {
    const summary = [];
    for (let j = 0; j < 16; j++)
      summary.push(j % 4 === 3 ? FILLER[Math.floor(r() * 4)]
        : form(ROOT[Math.floor(r() ** 2 * ROOT.length)], Math.floor(r() ** 2 * 8)));
    list.push({ id: 'k' + String(i).padStart(5, '0'),
      title: `${ADJ[Math.floor(r() * 10)]} ${NOUN[Math.floor(r() * 10)]}`,
      summary: summary.join(' '), topic: TOPIC[Math.floor(r() * 19)] });
  }
  return list;
}

export const text = (b) => `${b.title} ${b.summary} ${b.topic}`;

const STOP = new Set(FILLER);
const SUFFIX = ['less', 'like', 'ward', 'ish', 'ful', "'s", 's'];  // longest suffix first
const stem = (t) => {                         // strips the longest matching known ending
  for (const e of SUFFIX) if (t.length > e.length + 2 && t.endsWith(e)) return t.slice(0, -e.length);
  return t;
};
export const basic = (s) =>                   // lowercase + split on non-letter/non-number
  s.toLocaleLowerCase('en').split(/[^\p{L}\p{N}]+/u).filter((t) => t.length > 1);
export const advanced = (s) =>                // + stop-word removal + stemming
  basic(s).filter((t) => !STOP.has(t)).map(stem);

let counter = 0;
export class Segment {                        // an immutable segment; its name never changes once written
  constructor(docs = [], analyze = basic) {
    this.name = 'b' + String(++counter).padStart(3, '0');
    this.dict = new Map(); this.docs = new Set();
    for (const b of docs) {
      this.docs.add(b.id);
      const count = new Map();
      for (const t of analyze(text(b))) count.set(t, (count.get(t) || 0) + 1);
      for (const [t, tf] of count) {
        if (!this.dict.has(t)) this.dict.set(t, []);
        this.dict.get(t).push([b.id, tf]);
      }
    }
  }
  serialize() {
    let s = '';
    for (const [t, g] of this.dict) s += t + '\t' + g.map(([i, f]) => i + ':' + f).join(' ') + '\n';
    return s;
  }
  get bytes() { return Buffer.byteLength(this.serialize()); }
}

export function tiers(factor = 4) {           // tiered merge heap
  const tier = [];
  let merges = 0;
  const place = (b, k) => {
    while (tier.length <= k) tier.push([]);
    tier[k].push(b);
    if (tier[k].length < factor) return;
    merges++;
    place(merge(tier[k].splice(0, factor)), k + 1);
  };
  return {
    add(docs, analyze) { merges = 0; place(new Segment(docs, analyze), 0); },
    get segments() { return tier.flat(); },
    get merges() { return merges; },
  };
}

export function merge(group) {
  const y = new Segment();
  for (const sg of group) {
    for (const id of sg.docs) y.docs.add(id);
    for (const [t, g] of sg.dict) {
      if (!y.dict.has(t)) y.dict.set(t, []);
      for (const p of g) y.dict.get(t).push(p);
    }
  }
  return y;
}

export function search(segments, terms, k = 10) {
  const scores = new Map();
  for (const sg of segments) {
    const N = sg.docs.size;
    for (const t of terms) {
      const g = sg.dict.get(t);
      if (!g) continue;
      const idf = Math.log(1 + N / g.length);
      for (const [id, tf] of g) scores.set(id, (scores.get(id) || 0) + tf * idf);
    }
  }
  const order = [...scores].sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
  return { top: order.slice(0, k).map(([id]) => id), matched: order.length };
}

// snapshot: a segment file not yet in the store is written; a non-incremental snapshot rewrites all of them
export function snapshot(segments, store, incremental) {
  mkdirSync(store, { recursive: true });
  let copied = 0, files = 0;
  for (const b of segments) {
    const path = `${store}/${b.name}`;
    if (incremental && existsSync(path)) continue;
    writeFileSync(path, b.serialize());
    copied += statSync(path).size; files++;
  }
  return { copied, files, list: segments.map((b) => b.name) };
}

Incremental Snapshots and What Merging Breaks

The catalog takes in 500 records a day for sixteen days, and a snapshot is taken at the end of each day. Each day is measured twice: a full snapshot that copies the whole index, and an incremental snapshot that copies only the segment files not yet in the store.

// snapshot.mjs — bytes copied by full and incremental snapshots over a sixteen-day index
import { corpusBuild, tiers, snapshot } from './backup.mjs';

const corpus = corpusBuild(8000, 20260731);
const y = tiers(4);
console.log('corpus: 8000 documents, seed 20260731 | one 500-document batch a day, factor 4');
console.log('day  segments  merges  full snapshot bytes  incremental bytes  incr. files  store total');
let fullTotal = 0, storeBytes = 0;
for (let day = 1; day <= 16; day++) {
  y.add(corpus.slice((day - 1) * 500, day * 500));
  const full = snapshot(y.segments, `full/d${day}`, false);
  const incr = snapshot(y.segments, 'store', true);
  fullTotal += full.copied; storeBytes += incr.copied;
  console.log(String(day).padStart(3), String(y.segments.length).padStart(8),
    String(y.merges).padStart(8), String(full.copied).padStart(19),
    String(incr.copied).padStart(18), String(incr.files).padStart(12),
    String(storeBytes).padStart(12));
}
console.log('total: full snapshots', fullTotal, 'bytes, incremental snapshots', storeBytes, 'bytes');

corpus: 8000 documents, seed 20260731 | one 500-document batch a day, factor 4
day  segments  merges  full snapshot bytes  incremental bytes  incr. files  store total
  1        1        0               76788              76788            1        76788
  2        2        0              153495              76707            1       153495
  3        3        0              230031              76536            1       230031
  4        1        1              297765             297765            1       527796
  5        2        0              374913              77148            1       604944
  6        3        0              451624              76711            1       681655
  7        4        0              528250              76626            1       758281
  8        2        1              596322             298557            1      1056838
  9        3        0              673056              76734            1      1133572
 10        4        0              749772              76716            1      1210288
 11        5        0              826992              77220            1      1287508
 12        3        1              894582             298260            1      1585768
 13        4        0              971235              76653            1      1662421
 14        5        0             1048455              77220            1      1739641
 15        6        0             1125135              76680            1      1816321
 16        1        2             1184013            1184013            1      3000334
total: full snapshots 10182428 bytes, incremental snapshots 3000334 bytes

On days without a merge, the incremental snapshot pays a fixed cost: roughly 76,800 bytes, the single segment added that day. The full snapshot, by contrast, copies the whole index every day, and by day fifteen a single backup reaches 1,125,135 bytes. Across the sixteen days the gap is more than threefold: 10,182,428 bytes against 3,000,334 bytes.

The critical rows are days 4, 8, 12, and 16. On a day when a merge runs, the incremental snapshot does as much work as the full snapshot, because the segment a merge produces is a new file: even though its content already sits entirely in the store, it is the file itself that gets copied, not its inputs. Day sixteen is the extreme case — two merges reduce the index to a single segment, and the incremental snapshot rewrites all 1,184,013 bytes. Incrementality is a gain that comes from segment immutability, and merging resets it at regular intervals precisely because it uses that same immutability to produce a new file.

The last column gives a third result. The store holds 3,000,334 bytes, while the live index is 1,184,013 bytes. The store holds about two and a half times the live index; the excess is segment files invalidated by merging but not deletable, because old snapshots still reference them. That space does not come back until the old snapshots are dropped. Lowering the merge factor — a small win on the query side in the previous lesson — directly grows both incremental snapshot traffic and store size here.

Restore or Reindex

When an index is lost, there are two paths. The files from the store’s last snapshot can be moved into place, or the 8,000 records at the catalog source can be reindexed. The second, at first glance, makes a backup unnecessary at all. The measurement separates what each path pays and what it delivers: in the third row, reindexing runs on a system whose analyzer chain has since changed.

// recovery.mjs — comparing restore from snapshot against reindexing from source
import { mkdirSync, readFileSync, writeFileSync, statSync } from 'node:fs';
import { corpusBuild, tiers, snapshot, search, text, basic, advanced } from './backup.mjs';

const corpus = corpusBuild(8000, 20260731);
const QUERIES = [['juvenile', 'fiction', 'story'], ['lost', 'doors'],
  ['library', 'memory'], ['seaward', 'island'], ['mystery', 'city']];

function build(analyze) {                     // same daily batches, same merge policy
  const y = tiers(4);
  let tokens = 0;
  for (let d = 0; d < 16; d++) {
    const batch = corpus.slice(d * 500, (d + 1) * 500);
    for (const b of batch) tokens += analyze(text(b)).length;
    y.add(batch, analyze);
  }
  return { segments: y.segments, tokens };
}

const original = build(basic);                 // original index and the content of its last snapshot
const snap = snapshot(original.segments, 'store', true);

mkdirSync('index', { recursive: true });        // restore: files from the store move into place
let restoredBytes = 0;
for (const name of snap.list) {
  writeFileSync(`index/${name}`, readFileSync(`store/${name}`));
  restoredBytes += statSync(`index/${name}`).size;
}

const measure = (segments, analyze) => {
  let bytes = 0, dict = 0, matched = 0;
  const top = [];
  for (const b of segments) { bytes += b.bytes; dict += b.dict.size; }
  for (const q of QUERIES) {
    const c = search(segments, analyze(q.join(' ')));
    matched += c.matched; top.push(c.top);
  }
  return { bytes, dict, matched, top };
};
const originalMeasure = measure(original.segments, basic);
const diff = (o) => {                           // top ten change against the original index
  let dropped = 0, shifted = 0;
  for (let q = 0; q < QUERIES.length; q++) {
    for (const id of originalMeasure.top[q]) if (!o.top[q].includes(id)) dropped++;
    for (let i = 0; i < 10; i++) if (o.top[q][i] !== originalMeasure.top[q][i]) shifted++;
  }
  return [dropped, shifted];
};

const reindexed = build(advanced);
const reindexedMeasure = measure(reindexed.segments, advanced);
console.log('corpus: 8000 documents, seed 20260731 | 5 queries, top ten: 50 ranks');
console.log('path                             copied  docs processed  tokens  index bytes  dict  matched  dropped  shifted');
const row = (name, copied, docs, tokens, o) => console.log(name.padEnd(32),
  String(copied).padStart(9), String(docs).padStart(14), String(tokens).padStart(9),
  String(o.bytes).padStart(11), String(o.dict).padStart(6), String(o.matched).padStart(8),
  String(diff(o)[0]).padStart(6), String(diff(o)[1]).padStart(8));
row('restore', restoredBytes, 0, 0, originalMeasure);
row('reindex (same analyzer)', 0, 8000, original.tokens, originalMeasure);
row('reindex (new analyzer)', 0, 8000, reindexed.tokens, reindexedMeasure);

corpus: 8000 documents, seed 20260731 | 5 queries, top ten: 50 ranks
path                             copied  docs processed  tokens  index bytes  dict  matched  dropped  shifted
restore                            1184013              0         0     1184013    319     9286      0        0
reindex (same analyzer)                  0           8000    145239     1184013    319     9286      0        0
reindex (new analyzer)                   0           8000    121252      913738     76    16517     40       50

The first two rows produce the identical index: 1,184,013 bytes, 319 terms, 9,286 matched documents across five queries, and not one rank different in the top ten. What the two paths to that same result pay, though, is entirely different. Restoring moves 1,184,013 bytes and touches no document; reindexing moves not one byte but reads 8,000 documents and produces 145,239 tokens. Time depends on the run environment and is not printed here; the decision is made by how these two quantities scale. Restoring’s cost grows with index size, reindexing’s with source document count and tokens per document. Reindexing also carries a silent condition: the source records have to still be complete. If the index also holds a field no longer present in the catalog, reindexing cannot bring it back.

The third row shows why reindexing does not stand in for a backup. Once the analyzer chain is extended with stop-word removal and stemming, the same 8,000 records produce a different index: 121,252 tokens instead of 145,239 (the 23,987-token gap is the discarded filler words), 76 terms instead of 319, 913,738 bytes instead of 1,184,013. The effect shows up in the response. The five queries’ total matched documents rises from 9,286 to 16,517, because “doors” now collapses onto the same term as “door” and inflected forms pool into one posting list — recall goes up. The order is rebuilt too: all fifty ranks across the top ten results change, and 40 documents drop out of the top ten entirely. This is not a malfunction; it is the decision itself, but it cannot be counted as the same operation as restoring. Restoring brings the index back as it was; reindexing rebuilds it under that day’s configuration.

Summary

• Because segments are immutable, a snapshot can be taken incrementally: on days without a merge, copied bytes are that day’s single segment (roughly 76,800), while a full snapshot copies the whole index.
• Across the sixteen days, full snapshots copied 10,182,428 bytes, incremental snapshots 3,000,334 bytes.
• Merging breaks incrementality: on a merge day the incremental snapshot does as much work as the full snapshot, because the merged segment is a new file; on day sixteen all 1,184,013 bytes were recopied.
• The store holds 3,000,334 bytes, the live index 1,184,013 bytes: the gap is invalidated segment files that cannot be deleted because old snapshots still reference them.
• Restoring moves 1,184,013 bytes and processes zero documents; reindexing moves zero bytes and processes 8,000 documents and 145,239 tokens; both produce the identical index.
• If the analyzer chain has changed, reindexing does not produce the same index: matched documents rose from 9,286 to 16,517, all fifty ranks of the top ten results changed, and 40 documents dropped out of the top ten.

Next Step

This lesson covered copying, moving, and rebuilding an index as a whole. All of it shared one assumption: that everyone with access to the cluster is authorized to see the entire index — the one taking the snapshot, the one restoring it, and the one querying it all saw the same documents. In a library catalog this is not true — personal loan records, acquisition notes, and donation correspondence can sit in the same index without being open to every user. The next lesson measures this distinction: how the returned set narrows when the same query runs under two different roles, what document- and field-level filtering does to the order, and what that filtering adds to query cost.