java.lang.Object
net.i2p.router.util.DecayingBloomFilter
net.i2p.router.util.DecayingHashSet
public class DecayingHashSetextends DecayingBloomFilter
Double-buffered hash set with time-based decay for efficient data management.

Extends DecayingBloomFilter to provide dual-buffered hash sets with automatic decay switching between active and previous buffers. Optimized for high-throughput scenarios with frequent insertions and periodic cleanup operations.

Memory usage analysis shows significant optimization potential:

  • 32 bytes, peak 10 entries in 1m (320 on fast routers)
  • 4 bytes, peak 150 entries in 10s (1600 on fast routers)
  • 8 bytes, peak 1K entries in 2m (36K on fast routers)
  • 16 bytes, peak 15K entries in 10m (15K on fast routers)

Performance characteristics:

  • Zero false positive rate for ≤8 byte keys (lossy hash for larger keys)
  • Over 8 bytes entries are reduced to a 64 bit hash, so a false positive needs a hash collision: about 5.4E-20 per pair, so n^2/2^65 across n entries
  • About 1.93x faster than DecayingBloomFilter for 8 byte (long) entries and 2.46x faster for 16 byte entries
  • About 72 bytes of memory per 16 byte entry once loaded (measured: 9.01 MB for 131,000 entries), covering the map node, the ArrayWrapper and its share of the table. At the 128K soft cap that is roughly 9 MB as a floor, not a ceiling: getInsertedCount() spans both buffers, so a window deferred past the cap can take this to about twice that
  • Space-proportional traffic handling

Uses read/write locks with SimpleTimer2 for thread safety and efficient buffer switching without synchronization overhead.

  • Field Details

    • _current

      private ConcurrentHashSet<DecayingHashSet.ArrayWrapper> _current
      The entries of the current period.

    • _previous

      private ConcurrentHashSet<DecayingHashSet.ArrayWrapper> _previous
      The entries of the previous period.

    • DEFAULT_MAX_ENTRIES

      static final int DEFAULT_MAX_ENTRIES
      Maximum entries before a forced early decay is attempted. This is a soft target, not a hard ceiling: memory is bounded by roughly two windows of traffic rather than by this number, because forcing a decay sooner than an entry's lifetime would drop live entries.

      Measured cost at this cap with 16 byte entries: about 9 MB, roughly 72 bytes per entry including the map node and the wrapper.

      See Also:

    • BYTES_PER_ENTRY

      public static final long BYTES_PER_ENTRY
      Measured retained cost per entry for 16 byte keys: about 72 bytes, covering the map node, the ArrayWrapper and its share of the table. Measured 9.01 MB for 131,000 entries.
      See Also:

    • _maxEntries

      private volatile int _maxEntries
      The cap actually in force: DEFAULT_MAX_ENTRIES unless a test asked for a smaller one so it can cross the threshold cheaply, or the router lowered it to hold memory down.

      A set has no fixed memory cost, so unlike a bloom filter it can only be bounded by refusing growth: reaching the cap retires the older buffer even if its entries have not expired. That trades duplicate detection for a memory ceiling, so it is only the right call where the memory ceiling is the harder constraint. Volatile so the setter can change it while the router is running.

    • _hardCap

      private volatile boolean _hardCap
      True once setMaxEntries(int) has been used, meaning a caller has declared a memory ceiling to be the harder constraint. The default cap stays soft: it is only a backstop, and preferring duplicate detection over an early retirement is the right default.

    • _lastDecayNanos

      private volatile long _lastDecayNanos
      Nanotime of the last decay, used to space decays at least one interval apart. Volatile so the over-cap path can test it without taking the write lock. Monotonic on purpose: a wall clock jump must not be able to force an early decay, which would drop entries that are still live.

    • _lastOverCapWarnNanos

      private volatile long _lastOverCapWarnNanos
      Nanotime of the last over-cap warning, so that a sustained flood does not log once per entry. Same clock as _lastDecayNanos on purpose, so one policy decision never mixes a monotonic and a wall clock reading. Volatile because the warn is reached from the unlocked pre-check in forceDecayIfOverCap(); a lost update here only costs an extra log line.

  • Constructor Details

    • DecayingHashSet

      public DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes)
      Create a double-buffered hash set that will decay its entries over time.
      Parameters:
      context - the app context supplying the log and the clock
      durationMs - entries last for at least this long, but no more than twice this long
      entryBytes - how large are the entries to be added? 1 to 32 bytes
      Throws:
      IllegalArgumentException - if entryBytes is not 1-32

    • DecayingHashSet

      public DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes, String name)
      Decaying hash set with a custom name.
      Parameters:
      context - the app context supplying the log and the clock
      durationMs - entries last for at least this long, but no more than twice this long
      entryBytes - how large are the entries to be added? 1 to 32 bytes
      name - the instance name, used only in log messages and stats
      Throws:
      IllegalArgumentException - if entryBytes is not 1-32

    • DecayingHashSet

      DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes, String name, int maxEntries)
      As above, with an explicit cap. Only for tests, which need to cross the over-cap path without inserting the full DEFAULT_MAX_ENTRIES entries.
      Parameters:
      context - the app context supplying the log and the clock
      durationMs - entries last for at least this long, but no more than twice this long
      entryBytes - how large are the entries to be added? 1 to 32 bytes
      name - the instance name, used only in log messages and stats
      maxEntries - hard cap on entries across both buffers

  • Method Details

    • getInsertedCount

      public int getInsertedCount()
      Unsynchronized. Read on the add() path by forceDecayIfOverCap(), as well as for logging, so it is a hot call.
      Overrides:
      getInsertedCount in class DecayingBloomFilter
      Returns:
      how many entries are held across both generations of the filter

    • getMaxEntries

      public int getMaxEntries()
      The entry cap currently in force, across both buffers.
      Returns:
      the maximum number of entries held across both buffers before a decay is triggered

    • setMaxEntries

      public void setMaxEntries(int maxEntries)
      Change the entry cap while running, for the router's low-memory path.

      Lowering it takes effect at once: the next add() over the new cap triggers a decay, which may retire entries that have not yet expired. Raising it does not resurrect anything already retired.

      Parameters:
      maxEntries - the new cap, must be positive
      Throws:
      IllegalArgumentException - if maxEntries is not positive

    • getEstimatedMemoryBytes

      public long getEstimatedMemoryBytes()
      Bytes of memory the current contents occupy, at the measured rate of about 72 bytes per entry for 16 byte keys. Reported so a caller sizing against a memory budget can see the cost it is actually paying.
      Returns:
      estimated retained bytes

    • getFalsePositiveRate

      public double getFalsePositiveRate()
      Stubbed rate; only used for logging elsewhere.
      Overrides:
      getFalsePositiveRate in class DecayingBloomFilter
      Returns:
      a probability from 0.0 to 1.0, computed for the current generation

    • add

      public boolean add(byte[] entry, int off, int len)
      Add the entry, returning whether it was a duplicate.
      Overrides:
      add in class DecayingBloomFilter
      Parameters:
      entry - the entry data
      off - index in entry of the first byte to filter
      len - number of bytes to filter, must equal _entryBytes
      Returns:
      true if the entry added is a duplicate

    • add

      public boolean add(long entry)
      Add the long entry, returning whether it was a duplicate.
      Overrides:
      add in class DecayingBloomFilter
      Parameters:
      entry - the long value to add
      Returns:
      true if the entry added is a duplicate. the number of low order bits used is determined by the entryBytes parameter used on creation of the filter.

    • isKnown

      public boolean isKnown(long entry)
      Check whether the entry is already known, without adding it.
      Overrides:
      isKnown in class DecayingBloomFilter
      Parameters:
      entry - the long value to check
      Returns:
      true if the entry is already known. this does NOT add the entry however.

    • isKnown

      public boolean isKnown(byte[] entry, int off, int len)
      Check whether a byte array entry is already known, without adding it.
      Overrides:
      isKnown in class DecayingBloomFilter
      Parameters:
      entry - the entry data
      off - index in entry of the first byte to filter
      len - number of bytes to filter, must equal _entryBytes
      Returns:
      true if the entry is already known. This does NOT add the entry however.

    • add

      private boolean add(long entry, boolean addIfNew)
      Adds one entry to the set.
      Parameters:
      entry - the entry to add
      addIfNew - true to add only when absent
      Returns:
      true if the entry was added

    • forceDecayIfOverCap

      private void forceDecayIfOverCap()
      Force a decay cycle if the entry count exceeds the soft cap.

      A decay must never run more often than the decay interval: the swap in decay() drops the older buffer, and doing that before that buffer has aged out would forget entries that are still live, turning this duplicate/replay filter into a source of false negatives. So when the cap is exceeded we decay only if at least one interval has passed since the last decay, and otherwise leave it to the scheduled event.

      Best-effort: races are harmless (an extra decay, or a one-entry overshoot). Under sustained overload this holds up to about two windows of entries rather than the cap.

    • maybeWarnOverCap

      private void maybeWarnOverCap()
      Rate limited to once per decay interval, so a flood cannot spam the log.

    • locked_add

      private boolean locked_add(DecayingHashSet.ArrayWrapper w, boolean addIfNew)
      Add the entry to the current set if new, or check membership only.
      Parameters:
      w - the wrapped entry to add or test for membership
      addIfNew - if true, add the element to current if it is not already there or in previous; if false, only check
      Returns:
      if the element is in either the current or previous set

    • clear

      public void clear()
      Description copied from class: DecayingBloomFilter
      Clear all filters and reset counts.
      Overrides:
      clear in class DecayingBloomFilter

    • stopDecaying

      public void stopDecaying()
      Super doesn't call clear, but neither do the users, so it seems like we should here.
      Overrides:
      stopDecaying in class DecayingBloomFilter

    • decay

      protected void decay()
      Description copied from class: DecayingBloomFilter
      Decay the filter, moving the current buffer to the previous.

      The buffer that becomes the new current one is reset to a freshly allocated array rather than zeroed in place. Zeroing in place is a memset of the whole filter held under the write lock, and every add() takes the read lock, so it stalls all inserts for its duration: measured at about 2.6ms at m=29. Allocating the replacement does the same zeroing without the lock and is in fact slightly cheaper at that size, so the lock is held only for the pointer swap. See BloomSHA1.prepareReset() for the allocation/GC tradeoff this accepts.

      Overrides:
      decay in class DecayingBloomFilter

    • swapBuffers

      private DecayingHashSet.DecayCounters swapBuffers()
      Retire the older buffer and clear the recycled one. Caller must hold the write lock. Does no logging, so the lock is held only for the swap.
      Returns:
      what was in the retiring buffer, for logging once unlocked

    • logDecay

      private void logDecay(DecayingHashSet.DecayCounters counters)
      Caller must not hold the write lock.
      Parameters:
      counters - the element and duplicate counts carried out of the decay, to log