阅读中文版本

Build a Content-Addressed File Deduplicator

A CLI that finds duplicate files by size, then partial hash, then full SHA-256, reports reclaimable space, and optionally replaces duplicates with hard links or a content-addressed store.

dedupe/
├── bin/dedupe.js
├── src/
│   ├── walk.js
│   ├── pipeline.js
│   ├── hash.js
│   └── actors/
│       ├── report.js
│       ├── link.js
│       └── store.js
├── test/
│   ├── pipeline.test.js
│   └── actors.test.js
└── package.json

async function* walk(root, { skip, crossDevice }) {
  const stack = [root];
  while (stack.length) {
    const dir = stack.pop();
    for (const entry of await fs.readdir(dir, { withFileTypes: true })) {
      const full = path.join(dir, entry.name);
      if (skip.some((p) => minimatch(full, p))) continue;
      if (entry.isSymbolicLink()) continue;
      if (entry.isDirectory()) stack.push(full);
      else if (entry.isFile()) {
        const st = await fs.stat(full);
        yield { path: full, size: st.size, dev: st.dev };
      }
    }
  }
}

async function fullHash(file) {
  const h = crypto.createHash('sha256');
  const stream = fs.createReadStream(file, { highWaterMark: 1024 * 1024 });
  stream.on('data', (c) => h.update(c));
  await once(stream, 'end');
  return h.digest('hex');
}

for (const dup of group.slice(1)) {
  const backup = dup + '.dedupe-bak';
  await fs.rename(dup, backup);
  await fs.link(group[0], dup);
  await fs.rm(backup);
}

const digest = group.digest;
const target = path.join(storeRoot, digest.slice(0, 2), digest.slice(2));
await fs.mkdir(path.dirname(target), { recursive: true });
await fs.rename(group[0], target);
await fs.writeFile(group[0] + '.pointer', target + '\n');

Project overview

Duplicate files are the quietest form of storage rot: photos copied twice, backups of backups, the same dataset in four project folders. A deduplicator that is safe to run is one that proves what it will do before doing it, and that is the shape of this project: a report first, actions second.

The safety comes from staging. Nothing is deleted or moved until a grouping has survived three independent comparisons, and every mutating actor writes a recovery artifact before it changes a path, so an interrupted run is resumable rather than regrettable.

The finished tool delivers five capabilities:

• Three-stage comparison — size, first-and-last 4KB hash, full SHA-256 — so large trees scan cheaply.
• A dry-run report listing duplicate groups, member paths, and reclaimable bytes, as plain JSON.
• A hard-link mode that collapses duplicates on the same filesystem without changing any path.
• A store mode that moves files into a content-addressed tree keyed by digest, with pointer files preserving the original layout.
• Skip rules for symlinks, mount-point crossings, and user-specified glob patterns.

The architecture is a lazy pipeline: a walker yields file metadata as it goes, a pipeline of filters narrows candidates from size groups to hash groups, and actors consume the final grouping in dry-run, link, or store mode. Hashing is deliberately staged — most files differ in size and cost nothing, same-size files usually differ in their first bytes, and only true candidates pay for a full read.

Setup

Verify the prerequisites before starting: Node.js 20 LTS or later, familiarity with streams and backpressure for hashing large files, and an understanding of hard links versus copies on one filesystem.

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

Create the project and install:

mkdir dedupe && cd dedupe
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 root is a CLI flag with a .dedupe-store/ default relative to the scan root:

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

The directory structure mirrors the data flow: walk.js and hash.js are pure I/O modules, pipeline.js composes them, and each actor under actors/ owns one mutation strategy.

Phase 1: Lazy walker

The walker traverses directory trees asynchronously, yielding file entries with size and path while skipping symlinks, other filesystems, and configured patterns.

// src/walk.js
import { readdir, stat } from 'node:fs/promises';
import path from 'node:path';

export async function* walk(root, { skip = [], crossDevice = false, rootDev } = {}) {
  const stack = [root];
  const dev = rootDev ?? (await stat(root)).dev;
  while (stack.length) {
    const dir = stack.pop();
    for (const entry of await readdir(dir, { withFileTypes: true })) {
      const full = path.join(dir, entry.name);
      if (skip.some((p) => matchesGlob(full, p))) continue;
      if (entry.isSymbolicLink()) continue;
      if (entry.isDirectory()) {
        const st = await stat(full);
        if (!crossDevice && st.dev !== dev) continue;   // mount point
        stack.push(full);
      } else if (entry.isFile()) {
        const st = await stat(full);
        yield { path: full, size: st.size, dev: st.dev };
      }
    }
  }
}

Two skip rules are correctness rather than performance. Symlinks are never followed — a symlink to a file in the same tree would appear as a duplicate of its target, and the link actor would happily “deduplicate” a pointer. Mount-point crossings are off by default because a walk that silently crosses into a network mount can cost hours and, worse, the device check downstream is what makes hard-link mode safe; the walker records dev per entry so the actor can verify linkability without a second stat.

The walk is an async generator rather than a collected array: a million-file tree streams through the pipeline with constant memory, and traversal order is deliberately irrelevant — the yielded set is the contract, not the sequence.

Acceptance for this phase: walker tests generate a tree with symlinks and nested directories and assert the yielded set is exact.

Phase 2: Staged hash pipeline

The pipeline groups by size, hashes head and tail 4KB for same-size groups, and only then computes full SHA-256 of survivors, streaming each file.

// src/hash.js
import { createHash } from 'node:crypto';
import { createReadStream } from 'node:fs';
import { once } from 'node:events';

export async function fullHash(file) {
  const h = createHash('sha256');
  const stream = createReadStream(file, { highWaterMark: 1024 * 1024 });
  stream.on('data', (c) => h.update(c));
  await once(stream, 'end');
  return h.digest('hex');
}

export async function partialHash(file, size, chunk = 4096) {
  const head = createReadStream(file, { start: 0, end: Math.min(chunk, size) - 1 });
  const tail = createReadStream(file, { start: Math.max(0, size - chunk) });
  const h = createHash('sha256');
  for (const s of [head, tail]) {
    s.on('data', (c) => h.update(c));
    await once(s, 'end');
  }
  return h.digest('hex');
}

Why three stages? Because naive dedup hashes every file fully, which on a media library means reading terabytes to discover what a size comparison already knew. Different sizes cannot be equal, and grouping by size costs one stat per file — already paid by the walker. Same-size files then get a head-plus-tail hash over 8KB, which resolves almost every accidental size collision cheaply: files that share a size usually differ in their first bytes, and reading both ends catches both prefixed and suffixed variants of the same data. Only files that survive both stages pay for a full SHA-256.

The test suite proves the staging with a byte-counting stream substitute: the test asserts exactly how many bytes were read in total, so a refactor that accidentally promotes everything to full hashing fails a number, not a stopwatch. Hashing streams in 1MB chunks with backpressure, so a 4GB video never materializes in memory.

Acceptance for this phase: a tree with ten copies of a 100MB file hashes the full content of all ten but reads only 8KB for each same-size different file, asserted with a byte-counting test stream.

Phase 3: Report and link actors

The report actor renders the duplicate report with reclaimable bytes, and the link actor replaces all but one copy per group with hard links.

// src/actors/report.js
export function renderReport(groups) {
  return JSON.stringify({
    groups: groups.map((g) => ({
      digest: g.digest,
      members: g.files.map((f) => f.path),
      reclaimableBytes: (g.files.length - 1) * g.files[0].size,
    })),
    totalReclaimableBytes: groups.reduce((n, g) => n + (g.files.length - 1) * g.files[0].size, 0),
  }, null, 2);
}

// src/actors/link.js
import { rename, link, rm } from 'node:fs/promises';

export async function linkGroup(group) {
  const [keeper, ...duplicates] = group.files;
  if (duplicates.some((d) => d.dev !== keeper.dev)) {
    throw new Error('hard link across devices refused: ' + keeper.path);
  }
  for (const dup of duplicates) {
    const backup = dup.path + '.dedupe-bak';
    await rename(dup.path, backup);
    await link(keeper.path, dup.path);
    await rm(backup);
  }
}

The link actor’s sequence is the crash-safety lesson: rename to a backup, create the link, then remove the backup. Each step is recoverable — a leftover .dedupe-bak file marks an incomplete operation, and the resume flag walks the tree completing or reverting them, because a crash between rename and link leaves the original bytes intact in the backup rather than nowhere at all.

The device-number check runs before any mutation: cross-device hard links are refused with a clear error rather than attempted and half-failed, because a deduplicator that destroys data once is never trusted again. And after linking, every path still reads the original bytes — the inode count shows one link target — which is the acceptance test at the filesystem level rather than the string level.

Acceptance for this phase: after linking, every path still reads the original bytes, inode counts show one link target, and a crash between rename and link leaves the backup recoverable.

Phase 4: Content-addressed store actor

The store actor moves files into a store tree keyed by digest prefix and keeps a small pointer file at the original path, recording the mapping for undo.

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

export async function storeGroup(group, storeRoot, undoLog) {
  const digest = group.digest;
  const target = path.join(storeRoot, digest.slice(0, 2), digest.slice(2));
  await mkdir(path.dirname(target), { recursive: true });
  await rename(group.files[0].path, target);
  for (const f of group.files) {
    await writeFile(f.path + '.pointer', target + '\n');
    undoLog.push({ original: f.path, stored: target });
  }
}

The store layout is a two-level fan-out — first two hex characters as the directory, the rest as the filename — which keeps any single directory manageable at store scale and makes the tree browsable by eye. The pointer file at each original path preserves the layout contract other tools depend on, and the undo log is written as the migration proceeds, so the whole operation is reversible: replaying the log moves each blob back and removes the pointers.

Storing a group leaves one blob in the store and pointer files at every original path, including the first — a group of four becomes one blob and four pointers, which is the honest accounting the report promised.

Acceptance for this phase: storing a group leaves one blob in the store, pointer files at every original path, and the undo log restores the exact original layout.

Design trade-offs

Staged comparison over hash-everything. Full hashing is simpler and detects byte-identical files with one pass; it also reads the entire tree, which is the operation users notice on a media library. The three-stage pipeline reads full content only for true candidates, and the byte-counting test keeps the staging honest across refactors.

Hard links over copies or deletes. Links preserve every path and make reclaimed space immediate; the cost is subtlety — tools that watch one path and expect independent writes see shared inodes, and the limitation is documented. Deleting is irreversible and copying costs the space it saves.

Pointer files over symlinks in store mode. Symlinks would be transparent to readers, but they break tools that reject symlinks (tar without -h, some static file servers) and they encode the store location irreversibly. Pointer files are explicit, portable, and undoable through the log.

JSON report over pretty output. The report is meant to be reviewed and diffed and alerted on, and JSON feeds all three without a parser per consumer.

Testing strategy

Run npx vitest. Walker tests generate fixture trees with symlinks, skipped patterns, and nested directories, asserting the yielded set exactly. Pipeline tests use a byte-counting ReadStream substitute to prove the staged strategy reads full content only for true candidates — the byte totals are the assertions, so a promotion bug fails as arithmetic, not timing.

Actor tests create real duplicate trees in temp directories and verify at the filesystem level: hard links are confirmed by inode identity, not just equal content; store pointers resolve back to the original bytes; and the crash-restore path recovers a group from a deliberately planted backup file. The crash test is the one that separates a demo from a tool — anyone can move files, and the value is surviving the process dying mid-move.

One fixture detail earns its keep across the whole suite: a pair of files that differ only in their final 4KB. Size comparison passes them to the partial-hash stage, the head hash matches, and only the tail read separates them — which is exactly why the partial hash reads both ends instead of the first block alone. A pipeline that read only file heads would deduplicate these two files as identical, and the fixture catches that regression in one assertion.

Troubleshooting playbook

Deduped files across two filesystems lose data. The symptom appears after a run over a tree spanning a mount point. The cause is a hard-link attempt across devices, which the kernel refuses — but only after some renames have already happened. The fix is the st.dev equality check in the link actor, before any mutation, with a fallback to store mode or a hard error. The walker recording dev per entry makes the check free.

Hashing huge trees takes forever. A run that used to take minutes now takes hours. The cause is almost always a pipeline refactor that collapsed the stages — full hashing promoted to the default path. The fix is restoring the size-first, partial-second order, and the byte-counter test is the tripwire: it fails with the exact inflated read total, naming the regression without a profiler.

A crash leaves .dedupe-bak files behind. An interrupted link run leaves stray backups across the tree. The backup file is the recovery record, not garbage: the resume flag scans for backups and completes or rolls back each one, and the documented workflow is to run with --resume rather than delete them by hand.

Extending the project

The pipeline stages are composable filters, so new comparison stages slot in: an extended-attribute check before hashing, or a size-bucket refinement for gigantic same-size groups. Block-level deduplication — rsync-style chunking within files — is the documented boundary: whole-file comparison covers the dominant real-world cases, and chunking is a different project with different failure modes. The report actor is the integration point for everything downstream: a --format ndjson streaming variant feeds monitoring one group at a time, and alerting on reclaimable-bytes trends is a jq pipeline, not a feature.

For deployment, run as a local CLI against user directories or as a scheduled job on storage volumes — always with dry-run first, since the report is the review artifact. The report output is plain JSON, so alerting on reclaimable bytes integrates with any monitoring pipeline. Keep the store-mode store directory on the same filesystem as the source trees to keep pointer semantics cheap. Running the tool on a schedule changes the report’s meaning in a way worth planning for: a weekly dry-run produces a time series of reclaimable bytes, and the trend is the actionable signal — a flat line means the tree is deduplicated and the schedule can slow down, while a jump means a backup process or a dataset sync duplicated something upstream, and the report’s group members name exactly which paths. Feeding the JSON report into a monitoring system with one jq expression (jq .totalReclaimableBytes) turns the tool into a storage-hygiene sensor rather than a one-off cleanup, and the group member paths in the report double as the investigation starting point when the trend line moves. Storage teams that adopt this pattern typically run the full action modes only after a trend has been confirmed, which keeps every mutation deliberate.