Skip to content

known2.met: O(1) AICH SaveHashSet dedup (fixes #579) - #581

Merged
mrjimenez merged 1 commit into
amule-project:masterfrom
got3nks:fix/known2-met-savehashset-quadratic
May 11, 2026
Merged

known2.met: O(1) AICH SaveHashSet dedup (fixes #579)#581
mrjimenez merged 1 commit into
amule-project:masterfrom
got3nks:fix/known2-met-savehashset-quadratic

Conversation

@got3nks

@got3nks got3nks commented May 11, 2026

Copy link
Copy Markdown
Contributor

Why

CAICHHashSet::SaveHashSet (src/SHAHashSet.cpp) is called once per CHashingTask completion — startup bulk-hash, completed download moving to incoming, user adding a shared dir, AICH rehash. Before appending a new AICH hashset, it linearly walked the entire known2.met to detect duplicates: read each 20-byte root hash, read the 4-byte block count, seek past count × 20 bytes, repeat. For file N that's ≈ N reads/seeks, and the aggregate over a bulk-hash of N files is Σ k for k=0..N-1 ≈ N²/2.

@danim7's repro from #579 — 70 000 tiny shared files — turns this into ~2.45 billion file ops, ~1 hour wall-clock. Raw md5sum on the same tree finishes in ~6 seconds, so the gap is entirely the dedup walk.

What

Replace the implicit "linear scan of file content" dedup structure with an in-memory hash table:

  • New std::hash<CAICHHash> specialization in SHAHashSet.h. Uses the first 8 bytes of the 20-byte root hash as the size_t (root hashes already have ~uniform bit distribution — any 8 contiguous bytes are a perfectly fine hash).
  • New static CAICHHashSet::s_rootHashCache (std::unordered_set<CAICHHash>) populated lazily on first SaveHashSet call: walks known2.met once, collecting every root hash. Subsequent calls do an O(1) hash-table lookup.
  • SaveHashSet: cache miss → seek to end of file, append. Cache hit → return true without writing (matches today's dedup contract). On append success, insert into cache. On append failure, the existing SetLength(nExistingSize) rollback runs before the cache insert, so disk and cache stay in sync.
  • New static CAICHHashSet::InvalidateRootHashCache(). CAICHSyncTask::Entry's corruption-truncation path (SetLength(nLastVerifiedPos)) calls it so the cache doesn't hold ghost entries pointing past the truncated tail.

Complexity

Op Before After
Per-call dedup check O(N) disk walk O(1) hash lookup
Append on miss walk-then-append seek-to-end, append
Bulk add of N files O(N²) O(N)
70 k files (#579 repro) ~2.45 B file ops, ~1 h one walk + 70 k O(1) hits

Compatibility

  • No on-disk format change. known2.met layout is byte-identical to today — same root-hash + count + data-block tuples, same version header. Existing files load unchanged.
  • No EC / wire / protocol change.
  • Dedup semantics preserved: re-hashing a file whose root hash is already in known2.met is still a no-op write, exactly as before.
  • Single-threaded callers today; mutex added (s_rootHashCacheMutex) so the cache stays safe if hashing ever gets parallelised.

Test

  • macOS Apple Silicon: amule, amulegui, amuled, amulecmd, amuleweb all compile clean (build banner 2.3.3-362-g2332a7296).
  • amuled boots in a fresh config dir, writes known2_64.met + companion config files cleanly.
  • @danim7 invited to re-run the 70 k-file repro off this branch — instructions posted to performance: hashing 70000 small files takes 1 hour #579.

Fixes #579.

)

CAICHHashSet::SaveHashSet is invoked once per CHashingTask completion
(startup bulk-hash, download completion, new shared dir, AICH rehash).
Before appending a new AICH hashset it linearly scanned the entire
known2.met to detect duplicates: per-file cost ~N reads/seeks, so the
aggregate over a bulk-hash of N files was O(N^2). danim7's repro of
70 000 small files (amule-project#579) lands at ~1 hour on master while raw md5sum
of the same tree takes ~6 seconds.

Swap the implicit "linear scan of file content" dedup structure for an
in-memory std::unordered_set<CAICHHash> populated lazily on first
SaveHashSet call:

  * std::hash<CAICHHash> specialization uses the first 8 bytes of the
    20-byte SHA1-derived root hash (root hashes already have uniform
    bit distribution).
  * Cache populated by a single walk of known2.met; subsequent calls
    do an O(1) lookup. Per-call cost: O(1). Bulk-add of N files: O(N).
  * On append success, SaveHashSet inserts into the cache; the
    rollback path (SetLength(nExistingSize)) runs before the cache
    insert so disk and cache stay in sync on failure.
  * CAICHSyncTask::Entry's corruption-truncation path now calls
    CAICHHashSet::InvalidateRootHashCache(), so any cached entries
    that the truncation just removed don't become ghost dedup hits.

On-disk format of known2.met is unchanged. No migration. No protocol
change. The dedup contract is preserved: rehashing a file whose root
hash is already in known2.met is still a no-op write, exactly as
before.

Build: amule, amulegui, amuled, amulecmd, amuleweb all compile clean
on macOS Apple Silicon.
@mrjimenez
mrjimenez merged commit e55e560 into amule-project:master May 11, 2026
12 checks passed
@got3nks
got3nks deleted the fix/known2-met-savehashset-quadratic branch May 12, 2026 08:15
mrjimenez pushed a commit that referenced this pull request May 14, 2026
known2_64.met is the AICH (Advanced Intelligent Corruption Handling)
hashset cache: a Merkle tree of SHA-1 hashes per shared file, used
by peers to recover from sub-part-granularity corruption. Each entry
is keyed by its AICH root hash; ngosang's #597 report had it at
1.1 GB. The file has no mtime-touch bloat (entries are
content-addressed, dedup is already in place since #581), but it
never shrinks: once a hashset is cached, the entry stays even after
the underlying file leaves the user's library.

After #598's known.met TTL prune drops ~14 k orphaned live entries
on a long-lived profile, those hashes' AICH entries in
known2_64.met are dead weight and should follow them out.

Add CKnownFileList::CollectLiveAICHRoots() -- walks
m_knownFileMap and m_duplicateFileList under list_mut, returns the
set of AICH master hashes still referenced by either. Both lists
need to be scanned: Append's demote branch parks a record (with its
hashset) on the duplicate list while the new record takes the live
slot, and an mtime-restore can re-promote the duplicate later.
Dropping a duplicate's hashset would silently lose it on re-promote.

Extend CAICHSyncTask::Entry()'s existing known2_64.met walk: open a
"<name>.new" temp file via CFile::write_safe, and for each entry
read from the source, either copy it through to the temp (if its
root hash is in liveRoots) or skip it. On clean walk completion the
Close() atomic-renames .new over the original; on corruption catch
or IO error the temp is removed without finalising, leaving the
source's existing truncation-recovery path intact. Hashset bytes
are streamed through a 64 KB buffer rather than slurped, so a
single large-file entry can't dominate the working set.

The dedup root-hash cache (s_rootHashCache, #581) mirrored the old
file; invalidate it after a non-zero drop so the next SaveHashSet
rebuilds against the rewritten known2_64.met.

Effective TTL is inherited from known.met: a record evicted there
by PruneDuplicates ages out of liveRoots and its hashset gets
dropped on the next AICH sync. Decoupled lifecycles would require
bumping KNOWN2_MET_VERSION to add a per-entry timestamp (the file
format is positional, not tag-based), which is out of scope here.

Defensive: if knownfiles isn't yet populated (empty liveRoots), the
prune is skipped -- we don't wipe everything on a misconfigured
start.
ngosang pushed a commit to ngosang/amule that referenced this pull request Jul 24, 2026
…oltip (amule-project#581)

Two IP-filter UX fixes from issue amule-project#580:

- LoadFromFile treated a 0-byte ipfilter.dat as a load failure ("unknown
  format encountered"), because the archive/format detector does not
  recognise an empty file. An empty file is a valid "no ranges" list
  (a user who cleared it, or an auto-update that has not populated it
  yet), so return 0 quietly instead.

- Reword the "Paranoid handling of non-matching IPs" tooltip. The old
  "Use with caution" gave no hint whether caution applied to enabling or
  disabling; the new text says what the check does (anti-spoofing) and
  that disabling it is the risk. Catalogs regenerated via update-po.sh.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

performance: hashing 70000 small files takes 1 hour

2 participants