sfdupes/README.md

# sfdupes

## Description

`sfdupes` is an MIT-licensed Go CLI tool by
[@sneak](https://sneak.berlin) that quickly identifies *candidate*
duplicate files — and, ultimately, entire duplicate directory trees —
across very large filesystems without reading full file contents. Files
are considered duplicates when they have identical size, identical
SHA-256 of their first 1024 bytes, and identical SHA-256 of their last
1024 bytes. This is a strong candidate signal, not proof of identical
content (the middle of the file is never read); the intended use is
finding duplicate downloads and duplicated directory trees on
multi-terabyte ZFS servers where reading every byte is prohibitively
expensive.

This README is the complete and authoritative specification.

## Getting Started

```sh
make build
./sfdupes scan /srv > files.dat
./sfdupes report files.dat > dupes.tsv
./sfdupes trees files.dat > dupetrees.tsv
```

`scan` walks one or more filesystem trees and emits one record per
regular file (path, size, mtime, head hash, tail hash). `report`
ingests that stream and prints the file-level duplicates report.
`trees` ingests the same stream and prints the duplicate-tree report. A
missing/invalid subcommand — or a `scan` invocation with no `PATH`
operand — prints a usage message and exits 2.

## Rationale

Duplicate finders that hash entire files do not scale to the target
environment: ~10 million files and ~150 TB on possibly slow or busy
disks (a ZFS pool under resilver). Reading at most 2 KiB per file makes
a full-filesystem sweep tractable, and the resulting scan stream is
self-contained, so the expensive filesystem pass runs exactly once and
all analysis happens offline. The end goal is not individual files but
whole duplicated trees — duplicate extractions, duplicate downloads,
copied project trees — which an operator can consider removing as a
unit.

## Design

Goals, in order:

1.  **Find whole duplicate trees, not just files.** The end goal is to
    identify places where the exact same set of files and directories
    exists at two or more paths (duplicate extractions, duplicate
    downloads, copied project trees), so the operator can consider
    removing an entire subtree at once. File-level duplicate detection is
    the foundation; tree-level detection is built on top of it.
2.  **Never read full file contents.** At most 2 KiB is read per file
    (first and last 1024 bytes). Scale target: ~10 million files, ~150 TB
    filesystem, possibly slow or busy disks (ZFS pool under resilver).
    Holding the full file list in memory is acceptable; reading file
    contents beyond 2 KiB per file is not.
3.  **Scan once, analyze offline.** The expensive filesystem scan
    produces a self-contained stream; all analysis (`report`, `trees`)
    works from that stream alone and must never touch the scanned
    filesystem again.
4.  **Clean stream separation.** Everything on stdout is machine-readable
    data. All progress, warnings, and summaries go to stderr. Never mix
    them.

### Constraints

-   Language: Go (module `sneak.berlin/go/sfdupes`). Binary name:
    `sfdupes`.
-   Dependencies: standard library, `github.com/spf13/cobra` for the CLI,
    and **one progress-bar library**
    (`github.com/schollz/progressbar/v3`). `github.com/spf13/viper` is
    permitted if configuration-file support is ever needed, but is not
    currently used. No other third-party deps.
-   Cross-compilation is not a concern. Builds run with cgo disabled (the
    `Makefile` exports `CGO_ENABLED=0`); the code must remain pure Go.
-   Analysis modes (`report`, `trees`) must be deterministic: identical
    input stream, identical output, regardless of record order.

### Subcommands

Three subcommands, all implemented:

1.  `scan` — walk the filesystem and emit one signature record per
    regular file.
2.  `report` — file-level duplicate report from the scan stream.
3.  `trees` — tree-level duplicate report: reconstruct the directory
    hierarchy from the scan stream, compute a Merkle-style digest per
    directory, and report maximal groups of identical trees.

```
sfdupes scan [--workers N] [-x] PATH... > files.dat
sfdupes report [files.dat|-] > dupes.tsv
sfdupes trees [files.dat|-] > dupetrees.tsv
```

### `scan` mode

`scan` requires one or more `PATH` operands naming the trees to scan.
There is no default path; invoking `scan` with no operand is a usage
error (usage message on stderr, exit 2). An operand may be a directory
or a regular file; an operand that does not exist is a fatal error
(exit 1). Operands are walked in the order given; overlapping operands
(one containing another) emit their common files once per operand, so
callers should pass disjoint paths.

`scan` runs **three sequential passes**, in this order, so that every
expensive pass has an exact total for meaningful progress and ETA:

1.  **walk** — recursively enumerate the tree under each `PATH` in
    turn, collecting the list of regular-file paths. Total unknown
    while running: show a live count, not a percentage.
2.  **stat** — `lstat` every collected path, recording size and mtime.
3.  **hash** — for each file, read the first `min(1024, size)` bytes and
    the last `min(1024, size)` bytes (the two reads overlap when
    `size < 2048`; for `size == 0` hash the empty input) and compute the
    SHA-256 of each. Emit the output record.

Rules for the walk:

-   Only regular files. Skip directories, symlinks (do not follow,
    including symlink operands), sockets, FIFOs, and device nodes.
-   Never descend into a directory named `.zfs` (ZFS snapshot pseudo-dirs;
    walking them would list every file once per snapshot).
-   Filesystem boundaries are crossed by default. With `-x`
    (long form `--one-file-system`, following the GNU `du`/`rsync`
    convention), never descend into a directory on a different
    filesystem than its `PATH` operand; each operand is bounded by its
    own filesystem.
-   On any per-path error (permission denied, file vanished between
    passes, unreadable): print a one-line warning to stderr, skip the
    path, and continue. Per-file errors never abort the run; the final
    summary reports how many were skipped.

Concurrency: the stat and hash passes use a worker pool (`--workers`,
default `runtime.NumCPU()`). The main goroutine owns stdout writing and
progress rendering; progress display must never block the workers.

#### Output record format

One record per file on stdout, NUL-terminated (`\x00`), with
tab-separated fields, **path last** so tabs or newlines embedded in
paths cannot corrupt the record structure:

```
<size>\t<mtime_unix>\t<sha256_first1k_hex>\t<sha256_last1k_hex>\t<path>\x00
```

-   `size`: decimal bytes, from the stat pass.
-   `mtime_unix`: decimal Unix seconds. Informational only; not part of
    the duplicate key.
-   Hashes: lowercase hex, 64 chars each.
-   Record order is unspecified (workers complete out of order); the
    analysis modes must not depend on ordering.

### `report` mode

`report` reads the scan stream from the file named in its first
positional argument, or from stdin if the argument is absent or `-`.

**`report` must never touch the filesystem being analyzed.** It does not
stat, open, or otherwise access any path that appears in the records; its
only I/O is reading the scan file/stdin and writing stdout/stderr. It must
produce identical output whether or not the scanned filesystem is still
mounted.

Processing:

-   Parse records; a record that does not have exactly 5 fields or whose
    size is non-numeric is counted as malformed and skipped (warn once
    with the total malformed count in the summary, not per record).
-   Group records by the key `(size, head_hash, tail_hash)`.
-   Every group with two or more paths is a duplicate group.
-   Within each group, sort paths lexicographically (byte order). The
    first path is the group's `first`; every other path is a `dupe`.
-   Order groups by size descending (biggest reclaimable space first),
    tie-broken by `first` path ascending. Output must be fully
    deterministic for a given input.

#### Report output format

TSV on stdout: a header line, then one row per duplicate file (N-1 rows
for a group of N):

```
first	dupe	size
/srv/a/big.iso	/srv/b/big-copy.iso	4294967296
/srv/a/big.iso	/srv/c/big-copy2.iso	4294967296
```

Summary to stderr: records read, malformed count (if any), number of
duplicate groups, number of dupe files, and total reclaimable bytes
(sum of `size` over all dupe rows) in human units.

### `trees` mode

`trees` reads the same scan stream as `report` (same argument handling,
same parsing and malformed-record rules) and reports **entire duplicate
directory trees**: directories under which the exact same set of relative
paths exists with the exact same file signatures.

**`trees` must never touch the filesystem being analyzed** — the same
rule as `report`. The directory hierarchy is reconstructed purely from
the paths in the records, split on `/`.

Definitions:

-   A file's **signature** is `(size, head_hash, tail_hash)` — mtime is
    informational and excluded.
-   A directory's **digest** is a SHA-256 Merkle digest computed
    bottom-up: serialize the directory's child entries — for a file
    child, its name and signature; for a subdirectory child, its name
    and that subdirectory's digest — sort the serialized entries
    byte-lexicographically, and hash the concatenation. Names are part
    of the digest: two trees whose files differ only in name are *not*
    duplicates.
-   Two directories are **duplicate trees** when their digests are
    equal. Equal digests imply equal recursive file count and equal
    total byte size.

Known limitation (accepted): only regular files that appear in the scan
stream define a tree. Empty directories are invisible, and a file skipped
during the scan (e.g. permission error) in one copy but not the other
will make otherwise-identical trees compare as different.

Processing:

-   Build the hierarchy, compute every directory's digest, and group
    directories by digest. Every group with two or more directories is a
    duplicate-tree group.
-   **Report only maximal trees.** A group is suppressed when its
    members' parents are pairwise distinct directories that all share a
    single digest — such a group is wholly implied by its parents' (or a
    further ancestor's) group. Groups containing sibling directories, or
    members whose parents differ, are always reported.
-   Within each group, sort paths lexicographically (byte order); the
    first path is `first`, every other path is a `dupe`.
-   Order groups by total tree size descending, tie-broken by `first`
    path ascending. Output must be fully deterministic for a given
    input.

#### Trees output format

TSV on stdout: a header line, then one row per duplicate tree (N-1 rows
for a group of N). `files` is the recursive regular-file count of one
copy of the tree; `size` is the recursive total byte size of one copy:

```
first	dupe	files	size
/srv/a/project	/srv/backup/project	3417	104857600
```

Summary to stderr: records read, malformed count (if any), number of
duplicate-tree groups, number of dupe trees, and total reclaimable bytes
(sum of `size` over all dupe rows) in human units.

### Progress

Use the progress-bar library for all scan-pass progress; rendering in the
style of `pv` is the model. All progress goes to stderr.

Each scan pass gets its own bar. Required elements for the stat and hash
passes (known totals):

-   elapsed time
-   estimated time remaining
-   a `[m/n] x%` display (files processed / total files, percent)
-   current rate (files/s)

Example shape (exact layout is flexible, content is not):

```
hash: [1234567/9876543] 12% |████      | 8123 files/s elapsed 2:32 eta 17:54
```

The walk pass has no known total: show a live file count and elapsed time
(spinner-style, no percentage or ETA).

Additional requirements:

-   When stderr is not a TTY, do not emit ANSI redraws: print a plain
    one-line progress update no more often than every 5 seconds instead.
-   Progress updates are driven from the main goroutine and must be
    non-blocking with respect to the worker pool.
-   `report` and `trees` modes need no progress display, only their
    stderr summaries.

### Error handling and exit codes

-   `0`: success, even if individual files were skipped with warnings.
-   `1`: fatal error (e.g., a `PATH` operand does not exist, cannot
    read the scan input, stdout write failure).
-   `2`: usage error (including `scan` with no `PATH` operand).

## Build

The `Makefile` is the single source of truth for all operations:

-   `make build` — build the `sfdupes` binary (cgo disabled).
-   `make test` — run the test suite (30-second timeout; reruns with
    `-v` on failure).
-   `make lint` — run `golangci-lint` with the repo config.
-   `make fmt` / `make fmt-check` — format Go sources / verify
    formatting without writing.
-   `make check` — `test`, `lint`, and `fmt-check`; modifies nothing.
-   `make docker` — build the Docker image, which runs `make check` as
    a build stage.
-   `make hooks` — install the pre-commit hook.
-   `make clean` — remove the binary and any local `files.dat`.

### Definition of done

All of the following, run in this directory, must pass:

1.  `make check` passes (tests, lint, `gofmt`).
2.  `make docker` succeeds.
3.  Smoke test — create a throwaway tree in a temp dir (never test
    against real data):

    ```sh
    d=$(mktemp -d)
    mkdir -p "$d/a" "$d/b"
    head -c 2000 /dev/urandom > "$d/a/one.bin"
    cp "$d/a/one.bin" "$d/b/copy.bin"
    cp "$d/a/one.bin" "$d/b/copy2.bin"
    head -c 2000 /dev/urandom > "$d/a/unique.bin"     # same size, different content
    printf 'x' > "$d/tiny1"; printf 'x' > "$d/tiny2"  # 1-byte duplicates
    printf 'y' > "$d/tiny3"                           # 1-byte non-duplicate
    : > "$d/empty1"; : > "$d/empty2"                  # empty duplicates
    # duplicate trees: t1 and t2 are identical; t3 differs by one filename
    mkdir -p "$d/t1/sub" "$d/t2/sub" "$d/t3/sub"
    head -c 3000 /dev/urandom > "$d/t1/f1"
    head -c 100  /dev/urandom > "$d/t1/sub/f2"
    cp "$d/t1/f1" "$d/t2/f1"
    cp "$d/t1/sub/f2" "$d/t2/sub/f2"
    cp "$d/t1/f1" "$d/t3/f1"
    cp "$d/t1/sub/f2" "$d/t3/sub/f2renamed"
    ./sfdupes scan "$d" > files.dat
    ./sfdupes report files.dat
    ./sfdupes trees files.dat
    ```

    Expected from `report`: `one.bin`/`copy.bin`/`copy2.bin` form one
    group (two dupe rows, `first` is the lexicographically smallest
    path); `t1/f1`/`t2/f1`/`t3/f1` form one group; `t1/sub/f2`/
    `t2/sub/f2`/`t3/sub/f2renamed` form one group; `tiny1`/`tiny2` pair;
    `empty1`/`empty2` pair; `unique.bin` and `tiny3` appear nowhere;
    groups ordered by size descending; piping scan directly into report
    (`./sfdupes scan "$d" | ./sfdupes report`) gives the same
    rows.

    Expected from `trees`: exactly one row — `first` `$d/t1`, `dupe`
    `$d/t2`, 2 files, 3100 bytes. `$d/t1/sub` vs `$d/t2/sub` is
    suppressed as non-maximal (implied by the `t1`/`t2` group), and `t3`
    appears nowhere (its file set differs by name).

    The test suite automates this scenario (see `scan_test.go`), plus a
    negative check: `report` and `trees` operate on the captured stream
    alone and never touch the scanned filesystem.

## TODO

Tracked in [TODO.md](TODO.md).

## Non-goals

-   No full-content verification, no byte-for-byte compare, no deletion
    or linking of duplicates. The reports are advisory; acting on them is
    the user's job.
-   No persistence formats beyond the scan stream described above.

## License

MIT. See [LICENSE](LICENSE).

## Author

[@sneak](https://sneak.berlin)