Change file hash and extent hash to be a hash of hashes

[crass]

What problem would this solve?

This in itself should be a performance boost. Currently, a file checksum, for a fully mapped file, needs to process size(file) bytes, whereas under this proposal it would be 32 * num_extents bytes, which should be much less. Similar gains happen per extent.

Because there are 3 running checksums: file, extent, and block, oans is effectively hashing the data 3 times. With this change it will be much closer to hashing the data only once.

This issue is also an intermediary step to providing resume for large files (#159).

Proposed solution

Have the file hash be a hash of the extent hashes and the extent hash be a hash of the block hashes.

It will be desirable, though not strictly required, for the hash file database to be reconstructed. If its not reconstructed, things will still work, except that no deduplication will happen between data with the new and old digests.

It might be interesting to create a small program that takes a blocksize, number of blocks, and optional blocks per extent and outputs the runtime of 3 running checksums vs the solution proposed here.

Alternatives considered

No response

[martinus]

The observation here is right — by default two running checksums cover every byte (file_csum in csum_whole_file() and extent_csum in process_extents()), three with partial. But the proposed remedy would break whole-file dedupe, so I'm going to close this rather than implement it.

Making the file digest a hash of extent digests makes fragmentation part of file identity.

Two files, same 4 MiB of bytes. a.bin written in one go; b.bin written identically but fsync'd between 256 KiB chunks to force extent boundaries:

a.bin   1 extent    len=4194304  239C88C0...
b.bin  14 extents   len=262144   D1D6CDBC...
                    len=262144   9FA4283D...
                    len=262144   CB4C7DCA...
                    len=262144   233479BC...   (+10 more)

Their file digests today:

a.bin  X'239C88C083FA2DDB569B87563935E45D'
b.bin  X'239C88C083FA2DDB569B87563935E45D'   → 1 whole-file dup group

Under this proposal the file digest becomes a hash over the extent digest list — one entry for a.bin, fourteen for b.bin. Those cannot hash to the same value, so these two files would silently stop being detected as duplicates. Content and layout are independent, and dedupe itself fragments what it shares, so this would be worst exactly on the long-lived deduped trees oans is built for.

The extent-digest half has a related problem: allocate_hashes() notes that FIEMAP extents are filesystem-block aligned (~4K), not oans-blocksize aligned (128K default), so an extent routinely starts and ends mid-block. There's no well-defined block decomposition of an extent to hash. And block hashing is off by default, so there'd be nothing to build from unless it became mandatory — which cuts against #160 and #161.

The payoff would also be small. The hash phase is I/O-bound, not CPU-bound: in docs/benchmarks.md it's 7.83 s wall for 8.4 GiB at 3.37 s user CPU. Halving hashing CPU can't move a wall clock that's waiting on the disk.

Since #159 was built on this as its foundation, it needs a different approach — I've noted that there.

Thanks for writing it up in this much detail; the "we hash the data twice" point was worth checking properly even though the fix doesn't work out.

[crass]

Yep, I missed that aspect of fragmentation being part of the identity, good catch. Your detailed analysis is much appreciated.