阅读中文版本

Build an Incremental Backup Tool with Snapshot Catalogs

A backup CLI that takes content-defined chunked snapshots, stores new chunks only, and restores any snapshot exactly, with verification and pruning of unreferenced chunks.

incbackup/
├── bin/incbackup.js
├── src/
│   ├── chunker.js
│   ├── store.js
│   ├── manifest.js
│   └── commands/
│       ├── snapshot.js
│       ├── restore.js
│       ├── verify.js
│       └── prune.js
├── test/
│   ├── chunker.test.js
│   └── roundtrip.test.js
└── package.json

const MASK = (1 << 21) - 1; // ~2MB average with 4KB minimum
function boundaries(buffer, { min = 4096, mask = MASK } = {}) {
  const cuts = [];
  let hash = 0;
  for (let i = 0; i < buffer.length; i++) {
    hash = ((hash << 5) - hash + buffer[i]) & 0xffffffff;
    if (i >= min && (hash & mask) === 0) { cuts.push(i + 1); }
  }
  cuts.push(buffer.length);
  return cuts;
}

async function putChunk(digest, data) {
  const target = path.join(root, digest.slice(0, 2), digest.slice(2));
  if (await exists(target)) return { stored: false };
  await fs.mkdir(path.dirname(target), { recursive: true });
  await fs.writeFile(target + '.tmp', data);
  await fs.rename(target + '.tmp', target);
  return { stored: true };
}

for (const file of manifest.files) {
  const out = fs.createWriteStream(path.join(dest, file.path));
  for (const digest of file.chunks) {
    out.write(await store.getChunk(digest));
  }
  await finished(out);
  await fs.chmod(path.join(dest, file.path), file.mode);
}

async function* unreferenced(store, manifests) {
  const referenced = new Set();
  for (const m of manifests) for (const f of m.files) for (const c of f.chunks) referenced.add(c);
  for (const digest of store.listDigests()) {
    if (!referenced.has(digest)) yield digest;
  }
}

Project overview

A backup tool has one non-negotiable job: restore must reproduce the source exactly, months later, even after dozens of incremental snapshots and pruning runs. This project builds that guarantee from three primitives: content-defined chunking, a content-addressed store, and immutable manifests.

Everything else is policy on top. Deduplication is not a feature bolted on — it is a consequence of addressing chunks by their content. Pruning is just reference counting over manifests. Verification is recomputing digests. Each property is testable in isolation, which is what makes the whole trustworthy.

The finished tool delivers five capabilities:

• Content-defined chunking with a rolling-hash boundary, so chunk boundaries stay stable under insertions and unchanged data deduplicates across snapshots.
• A manifest per snapshot listing files, sizes, modes, symlink targets, and their ordered chunk digests.
• restore rebuilds any snapshot exactly, including empty files and symlinks.
• verify recomputes every chunk digest in the store and reports bit rot by name.
• prune deletes chunks unreferenced by any retained snapshot, with a dry-run report first.

The architecture is a pipeline of pure primitives: the chunker produces stable boundaries independent of position, the store is a content-addressed directory tree keyed by SHA-256, manifests are immutable JSON documents per snapshot, and the command layer composes snapshot, restore, verify, and prune over those primitives. Deduplication falls out of content addressing: an unchanged file produces the same chunk sequence, and the store already has those chunks.

Setup

Verify the prerequisites before starting: Node.js 20 LTS or later, comfort with binary data, Buffer, and streaming reads, and an understanding of why fixed-size chunking breaks under inserts.

The dependency footprint is one runtime package plus the test runner:

Create the project and install:

mkdir incbackup && cd incbackup
npm init -y
npm install commander@^12.0.0
npm install -D vitest@^2.1.0

Configure the environment in package.json — the bin entry and the test script; the store location defaults to ~/.incbackup-store and is overridden with the --store flag on every command:

{
  "name": "incbackup",
  "bin": { "incbackup": "bin/incbackup.js" },
  "scripts": { "test": "vitest run" }
}

The directory structure mirrors the primitives: chunker.js, store.js, and manifest.js are pure modules, and each command under commands/ composes them into one user-facing operation.

Phase 1: Content-defined chunker

The chunker is a rolling-hash scanner that emits boundaries where the hash of a sliding window hits a target mask, producing chunks between a minimum and maximum size.

// src/chunker.js
const MASK = (1 << 21) - 1; // ~2MB average with 4KB minimum

export function boundaries(buffer, { min = 4096, max = 8 * 1024 * 1024, mask = MASK } = {}) {
  const cuts = [];
  let hash = 0;
  let last = 0;
  for (let i = 0; i < buffer.length; i++) {
    hash = ((hash << 5) - hash + buffer[i]) & 0xffffffff;
    if (i - last >= min && (hash & mask) === 0) {
      cuts.push(i + 1);
      last = i + 1;
    } else if (i - last >= max) {
      cuts.push(i + 1);
      last = i + 1;
    }
  }
  cuts.push(buffer.length);
  return cuts;
}

Why content-defined at all? Fixed-size chunking assigns boundaries by position, so a single byte inserted at the start of a large file shifts every boundary, every chunk becomes new, and deduplication is destroyed for the rest of the file. A rolling hash decides boundaries by content: a cut lands where a window of bytes hashes to the target mask, so one insertion moves at most one boundary and the remainder of the file chunks identically.

The rolling hash here is a deliberately simple hash * 31 + byte formulation over a trailing window — cryptographic strength is not needed for boundary selection, only determinism and reasonable distribution, and the SHA-256 digest computed per chunk afterward is what provides integrity. The min bound prevents pathological tiny chunks, and the max bound caps worst-case chunk size so a run of mask-missing bytes cannot produce a chunk of unbounded length.

The chunker tests make the stability property concrete: prepend one byte to a 10MB fixture, and the cut sets before and after must agree on nearly every boundary. That stability, not the average chunk size, is the property the tests protect.

Acceptance for this phase: inserting one byte at the front of a file leaves nearly all boundaries unchanged, asserted by comparing cut sets before and after a synthetic edit.

Phase 2: Content-addressed store and manifest

The store writes chunks into a two-level digest directory tree, and the manifest records per-file chunk lists with metadata.

// src/store.js
import { mkdir, writeFile, rename } from 'node:fs/promises';
import path from 'node:path';

export async function putChunk(root, digest, data) {
  const target = path.join(root, digest.slice(0, 2), digest.slice(2));
  if (await exists(target)) return { stored: false };   // dedup for free
  await mkdir(path.dirname(target), { recursive: true });
  await writeFile(target + '.tmp', data);
  await rename(target + '.tmp', target);                // atomic publish
  return { stored: true };
}

export async function getChunk(root, digest) {
  return readFile(path.join(root, digest.slice(0, 2), digest.slice(2)));
}

// src/manifest.js
export function buildManifest(files) {
  return {
    version: 1,
    createdAt: new Date().toISOString(),
    files: files.map((f) => ({
      path: f.path, size: f.size, mode: f.mode,
      symlink: f.symlink ?? null,
      chunks: f.chunks,
    })),
  };
}

Two details carry the correctness. Chunks publish atomically: the write goes to a .tmp sibling and a rename makes it visible, so a crash mid-write leaves a stray temp file rather than a half-chunk at its final address — and a half-chunk under a content address would be silently wrong forever. The digest is computed over chunk bytes only: no timestamp, no path, no metadata leaks into the hash, because any nondeterminism in the digest input breaks deduplication entirely, and the troubleshooting section covers that exact failure signature.

The manifest is the source of truth for a snapshot: immutable once written, restore is a pure function of a manifest plus the store, and retention policy is simply a question of which manifests you keep. Snapshotting the same tree twice stores zero new chunks and produces two manifests — that assertion is the phase’s acceptance test.

Acceptance for this phase: snapshotting the same tree twice stores zero new chunks and produces two manifests; a changed file stores only the affected chunks.

Phase 3: Restore

Restore rebuilds a snapshot by streaming chunks back in manifest order and recreating modes, empty files, and symlinks.

// src/commands/restore.js
import { createWriteStream } from 'node:fs';
import { chmod, symlink, mkdir } from 'node:fs/promises';
import { finished } from 'node:stream/promises';
import path from 'node:path';

export async function restore(manifest, store, dest) {
  for (const file of manifest.files) {
    const target = path.join(dest, file.path);
    await mkdir(path.dirname(target), { recursive: true });
    if (file.symlink) {
      await symlink(file.symlink, target);
      continue;
    }
    const out = createWriteStream(target);
    for (const digest of file.chunks) {
      out.write(await store.getChunk(digest));
    }
    await finished(out);
    await chmod(target, file.mode);      // after content, after symlinks
  }
}

The ordering rules in restore are the classic backup bugs, each worth naming. Symlinks are handled by branch, not by content — writing a symlink as a regular file containing the target path is the silent corruption that looks fine until someone follows it. Empty files restore as empty files: a chunk list of length zero must still create the file, and a naive “loop over chunks” skips the write-stream creation entirely. Modes are applied after content — chmod before writing lets a read-only mode block the restore — and after symlink handling, since chmod on a symlink follows the link on some platforms.

The round-trip test is the phase’s proof: restore a generated tree with mixed file sizes, an empty file, and a symlink, and every restored file hashes identically to the source.

Acceptance for this phase: a round-trip test restores a generated tree with mixed file sizes, an empty file, and a symlink, and every restored file hashes identically to the source.

Phase 4: Verify and prune

Verify recomputes digests of stored chunks to detect corruption, and prune deletes chunks no retained manifest references, with a dry-run listing first.

// src/commands/verify.js
export async function verify(store) {
  const bad = [];
  for (const digest of await store.listDigests()) {
    const actual = sha256(await store.getChunk(digest));
    if (actual !== digest) bad.push({ digest, expected: digest, actual });
  }
  return bad;
}

// src/commands/prune.js
export async function* unreferenced(store, manifests) {
  const referenced = new Set();
  for (const m of manifests) {
    for (const f of m.files) {
      for (const c of f.chunks) referenced.add(c);
    }
  }
  for (const digest of store.listDigests()) {
    if (!referenced.has(digest)) yield digest;
  }
}

Backups rot silently: a flipped bit in the store invalidates a chunk that no one reads until restore fails at the worst possible moment. verify walks the store, recomputes every digest, and names the exact chunks that no longer match their address — a chunk stored under digest X whose content hashes to Y is named with both, which is the difference between “verification failed” and an actionable repair list. Running it on a schedule converts silent rot into an alert.

prune never inspects files, only manifests: a chunk is garbage exactly when no retained manifest lists it. The dry-run report lists candidate digests before anything is deleted, and the reference set is built from every retained manifest before the first deletion — the ordering that the troubleshooting entry exists for, because deleting while still enumerating references is how referenced chunks get reclaimed.

Acceptance for this phase: corrupting one byte of a stored chunk makes verify name exactly that digest, and prune dry-run lists precisely the chunks from a deleted snapshot.

Design trade-offs

Content-defined chunking over fixed-size. Fixed-size is simpler and faster per byte; it also destroys dedup on any insertion, which is the normal shape of data change. The rolling hash costs a multiply per byte and buys boundary stability, and the boundary-stability test is the invariant that justifies it.

Whole-file manifests over per-block indexes. A block-level index with chunk-level dedup trees (like restic’s pack model) scales to enormous repositories; a flat manifest per snapshot keeps restore a one-file read and makes retention deletion trivial. For single-machine data volumes, the flat model is the right size, and the limitation is documented rather than compensated.

Per-chunk storage over pack files. One file per chunk wastes some filesystem space to metadata but makes verify a directory walk, rsync to cold storage a cheap delta, and corruption detection exact — pack files would need index reconstruction before anything can be verified.

Serial snapshot over parallel. Parallel chunking is safe and faster on SSDs; it also multiplies the failure modes a crash can produce. The failure model stays simple deliberately, and the limitation names the upgrade path.

Testing strategy

Run npx vitest. Chunker tests assert boundary stability under prepend, append, and mid-file edits, and min/max chunk bounds on random data — the bounds test matters because random data exercises the mask uniformly, while real text can mask-miss for long runs. Store and manifest tests snapshot a generated tree twice and assert zero stored chunks on the second run, plus the changed-file case storing only the affected chunks.

Round-trip tests restore snapshots including empty files and symlinks and compare full-tree hashes — the empty file and symlink cases are the classic restore bugs that checksums alone never catch, because both restore “successfully” as the wrong thing. Verify and prune tests inject corruption and a deleted snapshot and assert the exact digests reported and reclaimed, which keeps both commands’ reports honest rather than approximately right.

Troubleshooting playbook

Second snapshot stores everything again. Dedup silently vanishes — every run writes new chunks. The cause is a digest computed over something nondeterministic: a timestamp, the file path, a mode flag leaking into the hash input. The fix is hashing chunk bytes only, and the double-snapshot test is the tripwire — it fails loudly the moment any nondeterminism enters the pipeline.

Restore produces files with changed permissions. Restored files are all mode 644 regardless of source. The cause is ordering: chmod applied before content writes gets overridden by the write, or applied to symlinks follows the link on some platforms. The fix is the phase 3 sequence — content first, symlinks by branch, chmod last.

Prune deleted chunks still referenced. A restore after prune fails on missing chunks. The cause is incremental deletion: deleting an unreferenced chunk while still enumerating references from manifests not yet read. The fix is building the complete referenced set before the first deletion, and the operational rule that prune runs only after verify passes, so the manifests being used for reference counting match the store’s reality.

Extending the project

The primitives compose into the obvious next features. Compression is a per-chunk transform inserted before putChunk — global compression across files is the documented boundary, with chunk-level dedup carrying the cross-file redundancy instead. Encryption is a per-chunk AEAD wrapper with the key stored outside the store, and content addressing still works because the digest is computed before encryption. Parallel chunking is a worker pool over the file list, safe because chunk writes are already atomic and content-addressed. Snapshot policies — daily, weekly retention — are manifest selection feeding prune, which already speaks in manifests.

For deployment, run from cron or a systemd timer against user data directories, keeping the store on a separate disk or mounted volume from the source. Ship the store directory to cold storage with rsync, which efficiently skips unchanged digest files. Monitor verify output for bit rot, and run prune after retention policy changes — always reading the dry-run report first. One operational practice completes the reliability story: restore drills. A backup that has never been restored is a hypothesis, and the cheapest experiment is a scheduled restore into a scratch directory followed by a full-tree hash comparison against the source — the same round-trip assertion the test suite runs, executed against real data on real hardware. The drill catches the failure modes tests cannot simulate: a store volume that silently truncates writes, a filesystem that mangles permissions on rename, or an operator who rotated the store directory without updating the tool’s configuration. Teams that run monthly restore drills discover these during the drill; teams that do not discover them during the incident. The verify command covers the store side of the equation, and the drill covers the restore path — together they are the whole trust model of any backup system.