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

    • 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:

  • 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:
      the false positive rate

    • 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.

    • 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