Skip to content

kad: add popularity decay so saturated m_filenames can still rotate - #799

Merged
mrjimenez merged 1 commit into
amule-project:masterfrom
got3nks:feat/kad-popularity-decay
Jun 1, 2026
Merged

kad: add popularity decay so saturated m_filenames can still rotate#799
mrjimenez merged 1 commit into
amule-project:masterfrom
got3nks:feat/kad-popularity-decay

Conversation

@got3nks

@got3nks got3nks commented Jun 1, 2026

Copy link
Copy Markdown
Contributor

Follow-up to #795 addressing irwir's review.

Problem

Once CKeyEntry::m_filenames saturates at the 100-entry cap and every survivor has popularity ≥ 2, a fresh popularity-1 candidate can never break in. pushBounded's strict > drops them on the floor. Pre-existing behaviour from #314 (the original sort + resize had the same algorithmic semantic); #795 just made it visible. Cap stays — it's the RAM lever that bounds the keyword index — so rotation needs an independent mechanism.

Three pieces

Per-CKeyEntry merge counter. m_mergeCounter (uint32_t) increments on every real merge (fromEntry != NULL; the IP-init no-op path doesn't count).

Decay tick. Every MERGES_PER_DECAY_TICK (= 20) real merges, every entry's m_popularityIndex is decremented by 1 (floored at 0). Gated on m_filenames.size() >= MAX_FILENAMES: under the cap there's nothing to rotate, and decay would just drag popularity numbers down before the list is even full. Once saturated the list never shrinks (pushBounded only ever replaces in place), so the gate is "off until first saturation, then always on" for the lifetime of the entry.

Zero-popularity escape hatch in pushBounded. If the weakest slot has decayed to 0, any candidate replaces it. Stagnant incumbents age out as their popularity decays; popular names hold position because matching publishes bump them faster than decay drops them. One-shot variants drift to 0 within a few dozen publish cycles to the same hash.

Robustness fix in GetCommonFileName

The original loop initialised the running max to 0 and used a strict > highestPopularityIndex comparison, so an all-zero m_filenames (which decay can produce on diffusely-published keys with no clear winner) would leave the result iterator at end() and return an empty string. Silently breaks every downstream consumer:

  • GetTagCount drops TAG_FILENAME from the count
  • WriteTagListInc omits the name on the wire
  • SearchTermsMatch returns false for every search term
  • CIndexed::AddKeyword rejects the entry via the GetCommonFileName().IsEmpty() guard

Seed the running max from the first entry (and switch to a "pick the first if all tied" fallback) — preserves the protocol invariant "non-empty m_filenames yields a non-empty common name" without changing behaviour for any case where a real winner exists.

Tuning

MERGES_PER_DECAY_TICK = 20 is a reasonable starter. Observed on a real publishing-heavy production node: ~12.8 merges/min across ~1800 indexed keys → power-law-weighted hot keys see decay every ~20 min to ~7 h depending on traffic. Cold keys never saturate, so the gate skips them.

On-disk format

Unchanged. m_mergeCounter is not serialised; decay phase resets per key on restart, which just means a one-time grace period before decay resumes — first decay tick on any active key still fires within minutes of restart.

Refs #765, #795.

@got3nks
kad: add popularity decay so saturated m_filenames can still rotate
2192d5d 
irwir's review on amule-project#795 caught that once CKeyEntry::m_filenames hits
the 100-entry cap and every survivor has popularity >= 2, a fresh
popularity-1 candidate can never break in. The cap stays -- it's
the RAM lever that bounds the keyword index on busy publishing
nodes (amule-project#314) -- but rotation needs an independent mechanism.

Three pieces:

1. Per-CKeyEntry m_mergeCounter. Incremented on every real merge
   (fromEntry != NULL; the IP-init no-op path does not count).

2. Decay tick. Every MERGES_PER_DECAY_TICK real merges, decrement
   every entry's m_popularityIndex by 1 (floored at 0). Gated on
   m_filenames.size() >= MAX_FILENAMES: under the cap there's
   nothing to rotate, and decay would only drag popularity numbers
   down before the list is even full. Once saturated the list
   never shrinks below the cap (pushBounded only ever replaces),
   so the gate is "off until first saturation, then always on".

3. Zero-popularity escape hatch in pushBounded. If the weakest
   slot has decayed to popularity 0, any candidate (including a
   fresh popularity-1 entry) replaces it. Stagnant incumbents age
   out as their popularity decays away; genuinely-popular names
   hold position because matching publishes bump them faster than
   decay drops them.

Plus a robustness fix in CEntry::GetCommonFileName.  Before this
commit, the loop initialised the running max with 0 and used a
strict `>` comparison, so an all-zero m_filenames (which decay can
produce on diffusely-published keys with no clear winner) would
leave the result iterator at end() and return an empty string.
That would silently break callers downstream: GetTagCount drops
TAG_FILENAME from the count, WriteTagListInc omits it on the wire,
SearchTermsMatch returns false for every term, and
CIndexed::AddKeyword rejects the entry via the
GetCommonFileName().IsEmpty() guard.  Seeding the running max
from the first entry (and switching to a "pick the first if all
tied" fallback) preserves the protocol invariant
"non-empty m_filenames yields a non-empty common name" without
changing behaviour for any case where a real winner exists.

Starting MERGES_PER_DECAY_TICK = 20 is a reasonable guess; tunable
later if rotation half-lives in production turn out to need it.
On-disk format unchanged -- m_mergeCounter is not serialised; the
decay phase resets per key on restart, which just means a one-time
grace period before decay resumes (first decay tick on any active
key still fires within minutes of restart).

Refs amule-project#765, amule-project#795.
@got3nks got3nks mentioned this pull request Jun 1, 2026
Merged
2 tasks
@mrjimenez
mrjimenez merged commit df10aa8 into amule-project:master Jun 1, 2026
7 checks passed
got3nks added a commit to got3nks/amule that referenced this pull request Jun 1, 2026
@got3nks
kad: revert popularity decay; keep GetCommonFileName all-zero robustness
686b727 
Reverts the decay tick + zero-popularity escape hatch landed in
df10aa8 ("kad: add popularity decay so saturated m_filenames can
still rotate") and addressed in PR amule-project#799.

Discussion on amule-project#795 with @irwir after amule-project#799 landed surfaced the
existing entry-lifetime cleanup that already handles the
"publisher offline => entry invalidation" case the decay was
targeting:

  - CKeyEntry::CleanUpTrackedPublishers ages out individual
    publisher IPs from m_publishingIPs after
    KADEMLIAREPUBLISHTIMEK (24 h) of silence.
  - CIndexed::Clean deletes the whole CKeyEntry when its
    m_tLifeTime expires (same 24 h horizon, extended on every
    publisher refresh).

So "publisher went offline" is handled at both the per-IP and
per-entry granularities.  The only thing left uncleaned is a
single name variant within an active CKeyEntry, which is
exclusively a saturated-m_filenames concern.  Empirical data from
a live HighID production node (~4000 merges over ~4 h across
~1800 indexed keys) shows the saturated-key count never lifts
off zero -- so the regime decay was designed for doesn't appear
in practice on a healthy node.  At the rare saturated cases the
"freeze at the cap" behaviour the decay was overriding is now
the correct behaviour: bounded RAM, no spurious rotation of
legitimate vote winners when traffic dips.

The 100-entry cap from amule-project#795 / amule-project#314 stays.  It protects against a
different case from the whole-entry TTL: an *active* CKeyEntry
that adversarial or pathological publishers feed unbounded
variant names under the same hash.  As @irwir noted in this
thread, "setting a limit would be reasonable to prevent attacks
and misuse."  The cap is a single integer comparison on insert
and lines up with the m_publishingIPs cap right next to it.

Concretely reverted:

  - CKeyEntry::MERGES_PER_DECAY_TICK static + m_mergeCounter
    member.
  - The decay tick block at the end of MergeIPsAndFilenames.
  - The "weakest->m_popularityIndex == 0" escape hatch in
    pushBounded -- back to the original strict `>` comparison
    from amule-project#795.

Deliberately kept: the GetCommonFileName robustness fix from
df10aa8.  Our own code no longer produces popularity-0 entries
after this revert, but two paths we don't control can still land
them in m_filenames: on-disk data from any node that ran the
decay build (it could have written 0-popularity entries to
known2.met before this revert lands), and malformed/adversarial
publishes that send popularity = 0 over the wire.  The picker's
seed-from-first / "pick first on tie" fallback closes a sharp
edge in a function whose output is on the wire (TAG_FILENAME,
SearchTermsMatch, CIndexed::AddKeyword reject path) for
essentially no cost.

Refs amule-project#795.
@got3nks got3nks mentioned this pull request Jun 1, 2026
Merged
mrjimenez pushed a commit that referenced this pull request Jun 1, 2026
@got3nks @mrjimenez
kad: revert popularity decay; keep GetCommonFileName all-zero robustness
683b98a 
Reverts the decay tick + zero-popularity escape hatch landed in
df10aa8 ("kad: add popularity decay so saturated m_filenames can
still rotate") and addressed in PR #799.

Discussion on #795 with @irwir after #799 landed surfaced the
existing entry-lifetime cleanup that already handles the
"publisher offline => entry invalidation" case the decay was
targeting:

  - CKeyEntry::CleanUpTrackedPublishers ages out individual
    publisher IPs from m_publishingIPs after
    KADEMLIAREPUBLISHTIMEK (24 h) of silence.
  - CIndexed::Clean deletes the whole CKeyEntry when its
    m_tLifeTime expires (same 24 h horizon, extended on every
    publisher refresh).

So "publisher went offline" is handled at both the per-IP and
per-entry granularities.  The only thing left uncleaned is a
single name variant within an active CKeyEntry, which is
exclusively a saturated-m_filenames concern.  Empirical data from
a live HighID production node (~4000 merges over ~4 h across
~1800 indexed keys) shows the saturated-key count never lifts
off zero -- so the regime decay was designed for doesn't appear
in practice on a healthy node.  At the rare saturated cases the
"freeze at the cap" behaviour the decay was overriding is now
the correct behaviour: bounded RAM, no spurious rotation of
legitimate vote winners when traffic dips.

The 100-entry cap from #795 / #314 stays.  It protects against a
different case from the whole-entry TTL: an *active* CKeyEntry
that adversarial or pathological publishers feed unbounded
variant names under the same hash.  As @irwir noted in this
thread, "setting a limit would be reasonable to prevent attacks
and misuse."  The cap is a single integer comparison on insert
and lines up with the m_publishingIPs cap right next to it.

Concretely reverted:

  - CKeyEntry::MERGES_PER_DECAY_TICK static + m_mergeCounter
    member.
  - The decay tick block at the end of MergeIPsAndFilenames.
  - The "weakest->m_popularityIndex == 0" escape hatch in
    pushBounded -- back to the original strict `>` comparison
    from #795.

Deliberately kept: the GetCommonFileName robustness fix from
df10aa8.  Our own code no longer produces popularity-0 entries
after this revert, but two paths we don't control can still land
them in m_filenames: on-disk data from any node that ran the
decay build (it could have written 0-popularity entries to
known2.met before this revert lands), and malformed/adversarial
publishes that send popularity = 0 over the wire.  The picker's
seed-from-first / "pick first on tie" fallback closes a sharp
edge in a function whose output is on the wire (TAG_FILENAME,
SearchTermsMatch, CIndexed::AddKeyword reject path) for
essentially no cost.

Refs #795.
@got3nks
got3nks deleted the feat/kad-popularity-decay branch June 3, 2026 14:16
@got3nks got3nks mentioned this pull request Jun 4, 2026
Merged
1 task
got3nks added a commit to got3nks/amule that referenced this pull request Jun 4, 2026
@got3nks
docs(changelog): cover post-amule-project#747 wave + extend flat PR i…
9397f01 
…ndex

Adds 55+ merged PRs to the 3.0.0 changelog since the last update
(amule-project#747, 2026-05-27). Narrative additions cover:

- Packaging: expanded the top list to include the macOS per-arch .app
  bundles and the Windows NSIS installer alongside the existing
  AppImage / Flatpak / .dmg / .zip entries. New bullets for amule-project#785
  (alc/alcc/cas/wxcas everywhere + Windows amuleweb), amule-project#794 (.dmg
  amuleweb path), amule-project#789 (<OS>-<arch> artifact naming), amule-project#780 / amule-project#796
  (Windows DPI + comctl32 manifest), amule-project#784 (FHS share/amule paths).

- Bug Fixes & Stability: post-amule-project#744 fixes including EC notification
  leak (amule-project#797), big-library scaling (amule-project#736, amule-project#840 superseding amule-project#728),
  amulegui ghost entries (amule-project#810, amule-project#819, amule-project#841, amule-project#824, amule-project#830, amule-project#760),
  PartFile early hash (amule-project#762), server protocol fixes (amule-project#835, amule-project#788,
  amule-project#721, amule-project#787), crypto stream UB (amule-project#779), UAF prevention (amule-project#756),
  Kad rotation (amule-project#795, amule-project#799/amule-project#805), GTK warning silencing (amule-project#833,
  amule-project#826/amule-project#836), and the clang-tidy worklist (amule-project#770, amule-project#772-amule-project#774).

- Translations: late-cycle wave covering French/Turkish manpages
  (amule-project#753/amule-project#754/amule-project#776), Galician (amule-project#763), Slovenian (amule-project#771), pt-BR
  (amule-project#768/amule-project#775/amule-project#812), French (amule-project#811), plus man-page tooling for
  date+version drift (amule-project#802).

- Contributors: added ngosang for UX feedback on the late-3.0
  cycle (amule-project#817/amule-project#818/amule-project#821/amule-project#828/amule-project#844) and ongoing work on the
  user-facing manual at amule-org.github.io.

- Merged PRs flat index: extended with amule-project#746-amule-project#845 + amule-project#841.
got3nks added a commit to got3nks/amule that referenced this pull request Jun 4, 2026
@got3nks
docs(changelog): cover post-amule-project#747 wave + extend flat PR i…
de8dbcb 
…ndex

Adds 55+ merged PRs to the 3.0.0 changelog since the last update
(amule-project#747, 2026-05-27). Narrative additions cover:

- Packaging: expanded the top list to include the macOS per-arch .app
  bundles and the Windows NSIS installer alongside the existing
  AppImage / Flatpak / .dmg / .zip entries. New bullets for amule-project#785
  (alc/alcc/cas/wxcas everywhere + Windows amuleweb), amule-project#794 (.dmg
  amuleweb path), amule-project#789 (<OS>-<arch> artifact naming), amule-project#780 / amule-project#796
  (Windows DPI + comctl32 manifest), amule-project#784 (FHS share/amule paths).

- Bug Fixes & Stability: post-amule-project#744 fixes including EC notification
  leak (amule-project#797), big-library scaling (amule-project#736, amule-project#840 superseding amule-project#728),
  amulegui ghost entries (amule-project#810, amule-project#819, amule-project#841, amule-project#824, amule-project#830, amule-project#760),
  PartFile early hash (amule-project#762), server protocol fixes (amule-project#835, amule-project#788,
  amule-project#721, amule-project#787), crypto stream UB (amule-project#779), UAF prevention (amule-project#756),
  Kad rotation (amule-project#795, amule-project#799/amule-project#805), GTK warning silencing (amule-project#833,
  amule-project#826/amule-project#836), and the clang-tidy worklist (amule-project#770, amule-project#772-amule-project#774).

- Translations: late-cycle wave covering French/Turkish manpages
  (amule-project#753/amule-project#754/amule-project#776), Galician (amule-project#763), Slovenian (amule-project#771), pt-BR
  (amule-project#768/amule-project#775/amule-project#812), French (amule-project#811), plus man-page tooling for
  date+version drift (amule-project#802).

- Contributors: added ngosang for UX feedback on the late-3.0
  cycle (amule-project#817/amule-project#818/amule-project#821/amule-project#828/amule-project#844) and ongoing work on the
  user-facing manual at amule-org.github.io.

- Merged PRs flat index: extended with amule-project#746-amule-project#845 + amule-project#841.
mrjimenez pushed a commit that referenced this pull request Jun 4, 2026
@got3nks @mrjimenez
docs(changelog): cover post-#747 wave + extend flat PR index
f1c3bc0 
Adds 55+ merged PRs to the 3.0.0 changelog since the last update
(#747, 2026-05-27). Narrative additions cover:

- Packaging: expanded the top list to include the macOS per-arch .app
  bundles and the Windows NSIS installer alongside the existing
  AppImage / Flatpak / .dmg / .zip entries. New bullets for #785
  (alc/alcc/cas/wxcas everywhere + Windows amuleweb), #794 (.dmg
  amuleweb path), #789 (<OS>-<arch> artifact naming), #780 / #796
  (Windows DPI + comctl32 manifest), #784 (FHS share/amule paths).

- Bug Fixes & Stability: post-#744 fixes including EC notification
  leak (#797), big-library scaling (#736, #840 superseding #728),
  amulegui ghost entries (#810, #819, #841, #824, #830, #760),
  PartFile early hash (#762), server protocol fixes (#835, #788,
  #721, #787), crypto stream UB (#779), UAF prevention (#756),
  Kad rotation (#795, #799/#805), GTK warning silencing (#833,
  #826/#836), and the clang-tidy worklist (#770, #772-#774).

- Translations: late-cycle wave covering French/Turkish manpages
  (#753/#754/#776), Galician (#763), Slovenian (#771), pt-BR
  (#768/#775/#812), French (#811), plus man-page tooling for
  date+version drift (#802).

- Contributors: added ngosang for UX feedback on the late-3.0
  cycle (#817/#818/#821/#828/#844) and ongoing work on the
  user-facing manual at amule-org.github.io.

- Merged PRs flat index: extended with #746-#845 + #841.
mrjimenez pushed a commit to mrjimenez/amule that referenced this pull request Aug 5, 2026
@dependabot
chore(deps): bump actions/setup-node from 4 to 7 (amule-project#799)
def6198 
Bumps [actions/setup-node](https://github.com/actions/setup-node) from 4 to 7.
- [Release notes](https://github.com/actions/setup-node/releases)
- [Commits](actions/setup-node@v4...v7)

---
updated-dependencies:
- dependency-name: actions/setup-node
  dependency-version: '7'
  dependency-type: direct:production
  update-type: version-update:semver-major
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@got3nks @mrjimenez