known2.met: O(1) AICH SaveHashSet dedup (fixes #579) - #581
Merged
mrjimenez merged 1 commit intoMay 11, 2026
Merged
Conversation
) 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.
This was referenced May 11, 2026
This was referenced May 14, 2026
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Why
CAICHHashSet::SaveHashSet(src/SHAHashSet.cpp) is called once perCHashingTaskcompletion — 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 entireknown2.metto detect duplicates: read each 20-byte root hash, read the 4-byte block count, seek pastcount × 20bytes, 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
md5sumon 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:
std::hash<CAICHHash>specialization inSHAHashSet.h. Uses the first 8 bytes of the 20-byte root hash as thesize_t(root hashes already have ~uniform bit distribution — any 8 contiguous bytes are a perfectly fine hash).CAICHHashSet::s_rootHashCache(std::unordered_set<CAICHHash>) populated lazily on firstSaveHashSetcall: walksknown2.metonce, collecting every root hash. Subsequent calls do an O(1) hash-table lookup.SaveHashSet: cache miss → seek to end of file, append. Cache hit → returntruewithout writing (matches today's dedup contract). On append success, insert into cache. On append failure, the existingSetLength(nExistingSize)rollback runs before the cache insert, so disk and cache stay in sync.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
Compatibility
known2.metlayout is byte-identical to today — same root-hash + count + data-block tuples, same version header. Existing files load unchanged.known2.metis still a no-op write, exactly as before.s_rootHashCacheMutex) so the cache stays safe if hashing ever gets parallelised.Test
2.3.3-362-g2332a7296).amuledboots in a fresh config dir, writesknown2_64.met+ companion config files cleanly.Fixes #579.