java.lang.Object
net.i2p.router.util.DecayingBloomFilter
Direct Known Subclasses:
DecayingHashSet
public class DecayingBloomFilterextends Object
Time-decaying Bloom filter series for efficient data management.

Provides a series of Bloom filters with automatic time-based decay to handle time-sensitive data with minimal false positive rates. Uses fixed-size buffers with periodic switching to maintain consistent memory usage while allowing high-throughput operations.

Optimized for scenarios requiring hundreds of entries per second with virtually no false positive rate. Memory usage is carefully controlled through configurable filter parameters and buffer sizes.

Performance characteristics:

  • Configurable m and k parameters for optimal false positive rates
  • Automatic buffer switching and decay operations
  • Thread-safe with read/write lock coordination
  • Comprehensive statistics tracking and performance monitoring

Suitable for high-throughput applications like message validation, tunnel IV filtering, and router message processing where memory efficiency and low false positive rates are critical.

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private class 
    DecayingBloomFilter.DecayEvent
    Rotates the filter to a fresh hour on a schedule.
    private class 
    DecayingBloomFilter.DecayHourlyEvent
    Decays at 5 minutes after the top of the hour.
    private class 
    DecayingBloomFilter.Shutdown
    Saves filter state when the router shuts down.

  • Field Summary

    Modifier and Type
    Field
    Description
    protected final I2PAppContext
    _context
    The I2P app context.
    private BloomSHA1
    _current
    Current bloom filter.
    protected final AtomicLong
    _currentDuplicates
    Counter for current duplicates.
    protected final SimpleTimer2.TimedEvent
    _decayEvent
    The decay timer event.
    protected final int
    _durationMs
    Duration of each filter in ms.
    protected final int
    _entryBytes
    Size of entries in bytes.
    private final ThreadLocal<byte[]>
    _extendedBuf
    Thread-local buffer for extended entries.
    private final byte[][]
    _extenders
    Extender arrays for small entries.
    protected boolean
    _keepDecaying
    Whether decay is still running.
    private int
    _lastWindowCount
    Entries seen in the most recently completed decay window, written under the write lock.
    protected final Log
    _log
    The logger.
    private final ThreadLocal<byte[]>
    _longToEntryBuf
    Thread-local buffer for the long-to-entry conversion, sized _entryBytes.
    private final long
    _longToEntryMask
    Mask for converting longs to entries.
    private final int
    _m
    Filter size exponent: each buffer holds 2^m bits.
    protected final String
    _name
    Name for logging.
    private BloomSHA1
    _previous
    Previous bloom filter.
    protected final ReentrantReadWriteLock
    _reorganizeLock
    Synchronize against this lock when switching double buffers.
    private static final boolean
    ALWAYS_MISS
    True for debugging.
    private static final int
    DEFAULT_K
    Hash functions used per entry by default.
    private static final int
    DEFAULT_M
    Default sizing rationale.
    static final int
    MAX_M
    Largest exponent usable for a 32 byte key.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)
    Only for extension by DecayingHashSet, which validates entryBytes itself and never stretches entries, so it is deliberately not checked here.
    DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes)
    Create a bloom filter that will decay its entries over time.
    DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name)
    Uses default m of 23, memory usage is 2 MB.
    DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m)
    Memory usage is 2 * (2**m) bits or 2**(m-2) bytes, allocated up front for both buffers, so it does not grow with traffic.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(byte[] entry)
    Add a byte array entry to the filter.
    boolean
    add(byte[] entry, int off, int len)
    Add a byte array entry at the specified offset and length.
    boolean
    add(long entry)
    Add a long entry to the filter.
    private static int
    calcNumExtenders(int entryBytes)
    How many extender blocks are needed to stretch an entryBytes entry out to the 32 bytes that are hashed.
    protected static void
    checkEntryBytes(int entryBytes)
    Validate an entry size for a bloom filter.
    void
    clear()
    Clear all filters and reset counts.
    protected void
    decay()
    Decay the filter, moving the current buffer to the previous.
    private byte[]
    encodeLong(long entry)
    Encode a long entry into the byte array that gets hashed.
    long
    getCurrentDuplicateCount()
    Current number of duplicates detected.
    double
    getFalsePositiveRate()
    Estimated chance that a lookup of an entry never added reports a hit.
    int
    getInsertedCount()
    Unsynchronized; DecayingHashSet also reads this on the add() path.
    int
    getLastWindowCount()
    Entries seen in the most recently completed decay window, which is the count this filter has to be sized against.
    int
    getM()
    Filter size exponent.
    long
    getMemoryBytes()
    Bytes of memory this filter occupies, for both buffers.
    protected void
    getReadLock()
    Acquire the read lock.
    protected boolean
    getWriteLock()
    Acquire the write lock.
    boolean
    isKnown(byte[] entry, int off, int len)
    Check whether a byte array entry is already known, without adding it.
    boolean
    isKnown(long entry)
    Check if an entry is already known without adding it
    private boolean
    locked_add(byte[] entry, int offset, int len, boolean addIfNew)
    Adds or tests an entry with the lock already held.
    static int
    mForBudget(long budgetBytes)
    Largest exponent whose pair of buffers fits in the given byte budget, capped at the largest a 32 byte key can be hashed into.
    static int
    mForEntries(int entries, double targetFpr)
    Smallest exponent whose false positive rate stays at or under the target for the given number of entries, at the optimal k for that exponent.
    protected void
    releaseReadLock()
    Release the read lock.
    protected void
    releaseWriteLock()
    Release the write lock.
    void
    stopDecaying()
    Stop the decay process.

    Methods inherited from class Object

    clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • _context

      protected final I2PAppContext _context
      The I2P app context.

    • _log

      protected final Log _log
      The logger.

    • _m

      private final int _m
      Filter size exponent: each buffer holds 2^m bits.

    • _lastWindowCount

      private volatile int _lastWindowCount
      Entries seen in the most recently completed decay window, written under the write lock. This is the quantity a filter has to be sized against, and decay() already computes it, so tracking it is free.

    • _current

      private BloomSHA1 _current
      Current bloom filter.

    • _previous

      private BloomSHA1 _previous
      Previous bloom filter.

    • _durationMs

      protected final int _durationMs
      Duration of each filter in ms.

    • _entryBytes

      protected final int _entryBytes
      Size of entries in bytes.

    • _extenders

      private final byte[][] _extenders
      Extender arrays for small entries.

    • _longToEntryMask

      private final long _longToEntryMask
      Mask for converting longs to entries.

    • _extendedBuf

      private final ThreadLocal<byte[]> _extendedBuf
      Thread-local buffer for extended entries.

    • _longToEntryBuf

      private final ThreadLocal<byte[]> _longToEntryBuf
      Thread-local buffer for the long-to-entry conversion, sized _entryBytes. Only the long overloads of add()/isKnown(long) use it, so it is null when the entries are too wide to hold a long.

    • _currentDuplicates

      protected final AtomicLong _currentDuplicates
      Counter for current duplicates.

    • _keepDecaying

      protected volatile boolean _keepDecaying
      Whether decay is still running.

    • _decayEvent

      protected final SimpleTimer2.TimedEvent _decayEvent
      The decay timer event.

    • _name

      protected final String _name
      Name for logging.

    • _reorganizeLock

      protected final ReentrantReadWriteLock _reorganizeLock
      Synchronize against this lock when switching double buffers.

    • DEFAULT_M

      private static final int DEFAULT_M
      Default sizing rationale.

      The rates below are theoretical false positive rates for a filter of 2^m bits with k hash functions, (1 - e^(-k*n/m))^k, evaluated at n = 600 * KBps entries: one message per second per KBps of share, accumulated over a 600 second decay window. They are not measurements. The formula understates the rate once the filter is close to full, so treat the high figures at the end of each line as optimistic.

      The larger m values are chosen by the caller, which also steps k down to hold k*ln(2) roughly constant: 23/11, then 10 above m=23, then 9 above m=26. m is capped at 29, which is where KeySelector's offset formula stops fitting in a 32 byte key.

       m=23, k=11:
 Theoretical false positive rate for   16 KBps: 1.17E-21
 Theoretical false positive rate for   24 KBps: 9.81E-20
 Theoretical false positive rate for   32 KBps: 2.24E-18
 Theoretical false positive rate for  256 KBps: 7.45E-9
 Theoretical false positive rate for  512 KBps: 5.32E-6
 Theoretical false positive rate for 1024 KBps: 1.48E-3
 Then it gets bad: 1280 .67%; 1536 2.0%; 1792 4.4%; 2048 8.2%.

m=24, k=10:
 1280 4.5E-5; 1792 5.6E-4; 2048 0.14%

m=25, k=10:
 1792 2.4E-6; 4096 0.14%; 5120 0.6%; 6144 1.7%; 8192 6.8%; 10240 15%

m=26, k=10:
 4096 7.3E-6; 5120 4.5E-5; 6144 1.8E-4; 8192 0.14%; 10240 0.6%, 12288 1.7%

m=27, k=9:
 8192 1.1E-5; 10240 5.6E-5; 12288 2.0E-4; 14336 5.8E-4; 16384 0.14%
      See Also:

    • DEFAULT_K

      private static final int DEFAULT_K
      Hash functions used per entry by default.
      See Also:

    • ALWAYS_MISS

      private static final boolean ALWAYS_MISS
      True for debugging.
      See Also:

    • MAX_M

      public static final int MAX_M
      Largest exponent usable for a 32 byte key. Above this the offset arithmetic in KeySelector runs past the end of the key.
      See Also:

  • Constructor Details

    • DecayingBloomFilter

      protected DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)
      Only for extension by DecayingHashSet, which validates entryBytes itself and never stretches entries, so it is deliberately not checked here.
      Parameters:
      durationMs - entries last for at least this long
      entryBytes - how large are the entries
      name - filter name for logging
      context - the I2P app context

    • DecayingBloomFilter

      public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes)
      Create a bloom filter that will decay its entries over time. Uses default m of 23, memory usage is 2 MB.
      Parameters:
      context - the I2P app context
      durationMs - entries last for at least this long, but no more than twice this long
      entryBytes - how large are the entries to be added? must be 1-16, or 32. Entries narrower than 32 bytes are expanded to 32 by concatenating their XORing against random values; 17-31 cannot reach 32 in whole blocks and are refused.
      Throws:
      IllegalArgumentException - if entryBytes is not 1-16 or 32
      See Also:

    • DecayingBloomFilter

      public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name)
      Uses default m of 23, memory usage is 2 MB.
      Parameters:
      context - the I2P app context
      durationMs - entries last for at least this long
      entryBytes - how large are the entries, 1-16 or 32
      name - just for logging / debugging / stats
      Throws:
      IllegalArgumentException - if entryBytes is not 1-16 or 32

    • DecayingBloomFilter

      public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m)
      Memory usage is 2 * (2**m) bits or 2**(m-2) bytes, allocated up front for both buffers, so it does not grow with traffic.
      Parameters:
      context - the I2P app context
      durationMs - entries last for at least this long
      entryBytes - how large are the entries, 1-16 or 32
      name - filter name for logging
      m - filter size exponent, max is 29
      Throws:
      IllegalArgumentException - if entryBytes is not 1-16 or 32, or if m is over 29

  • Method Details

    • checkEntryBytes

      protected static void checkEntryBytes(int entryBytes)
      Validate an entry size for a bloom filter. Entries are stretched to exactly 32 bytes for hashing, in uniform blocks of entryBytes, so only sizes that can reach 32 bytes without overrunning are usable: 1-16, and 32 itself. Sizes 17-31 would need a partial trailing block, which the extender loop does not support, and hashing them unextended overruns KeySelector. This does not apply to DecayingHashSet, which hashes entries directly and accepts the full 1-32 range.
      Parameters:
      entryBytes - how large are the entries
      Throws:
      IllegalArgumentException - if entryBytes is not 1-16 or 32

    • calcNumExtenders

      private static int calcNumExtenders(int entryBytes)
      How many extender blocks are needed to stretch an entryBytes entry out to the 32 bytes that are hashed. This is the largest count that still fits without overrunning the buffer, so a non-divisor size such as 6 yields the most extenders that are safe (4, using 30 of the 32 bytes).
      Parameters:
      entryBytes - how large are the entries, already validated to 1-16 or 32, so for anything below 32 the result is always at least 1
      Returns:
      the number of extenders; 0 only for a full 32 byte entry

    • getCurrentDuplicateCount

      public long getCurrentDuplicateCount()
      Current number of duplicates detected.
      Returns:
      the current duplicate count

    • getM

      public int getM()
      Filter size exponent. Each of the two buffers holds 2^m bits, so the pair occupies 2^(m-2) bytes.
      Returns:
      the exponent this filter was built with, 0 if it keeps no bits

    • getMemoryBytes

      public long getMemoryBytes()
      Bytes of memory this filter occupies, for both buffers.
      Returns:
      2^(m-2), or 0 for a subclass that keeps no bits

    • getLastWindowCount

      public int getLastWindowCount()
      Entries seen in the most recently completed decay window, which is the count this filter has to be sized against. Zero until the first decay.
      Returns:
      entries in the last window, or 0 if none has completed

    • mForEntries

      public static int mForEntries(int entries, double targetFpr)
      Smallest exponent whose false positive rate stays at or under the target for the given number of entries, at the optimal k for that exponent.

      Uses p ~= exp(-(ln2)^2/2 * 2^m / n), which is the standard optimal-k Bloom bound. It reproduces the table in DEFAULT_M: for n=614400 it gives m=24 for a 1.48E-3 target, against 23 measured.

      Parameters:
      entries - entries expected in a decay window, non-negative
      targetFpr - wanted false positive rate, in (0,1)
      Returns:
      the exponent, never negative

    • mForBudget

      public static int mForBudget(long budgetBytes)
      Largest exponent whose pair of buffers fits in the given byte budget, capped at the largest a 32 byte key can be hashed into.
      Parameters:
      budgetBytes - memory available for the filter, non-negative
      Returns:
      the exponent, never negative

    • getInsertedCount

      public int getInsertedCount()
      Unsynchronized; DecayingHashSet also reads this on the add() path.
      Returns:
      how many entries are held across both generations of the filter

    • getFalsePositiveRate

      public double getFalsePositiveRate()
      Estimated chance that a lookup of an entry never added reports a hit.
      Returns:
      a probability from 0.0 to 1.0, computed for the current generation

    • add

      public boolean add(byte[] entry)
      Add a byte array entry to the filter.
      Parameters:
      entry - the entry to add
      Returns:
      true if the entry added is a duplicate

    • add

      public boolean add(byte[] entry, int off, int len)
      Add a byte array entry at the specified offset and length.
      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

    • encodeLong

      private byte[] encodeLong(long entry)
      Encode a long entry into the byte array that gets hashed. Negative values are stored as their magnitude with the top bit of the first byte set as the sign, so a long and its negation stay distinct.

      Single source of truth for the long-to-entry conversion, shared by add(long) and isKnown(long) so the two cannot drift apart.

      Parameters:
      entry - the value to encode
      Returns:
      the thread's scratch array of exactly _entryBytes bytes. The caller must consume it before the next call on the same thread.
      Throws:
      IllegalArgumentException - if entryBytes is over 8, since DataHelper.toLong(int, long) cannot write more than 8 bytes; use the byte array form of add() for wider entries

    • add

      public boolean add(long entry)
      Add a long entry to the filter. The number of low order bits used is determined by the entryBytes parameter used on creation of the filter.

      Only for filters built with 8 or fewer bytes per entry, since a long cannot be encoded any wider. Use add(byte[], int, int) otherwise.

      Parameters:
      entry - the long value to add
      Returns:
      true if the entry added is a duplicate

    • isKnown

      public boolean isKnown(long entry)
      Check if an entry is already known without adding it

      Only for filters built with 8 or fewer bytes per entry, since a long cannot be encoded any wider.

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

    • locked_add

      private boolean locked_add(byte[] entry, int offset, int len, boolean addIfNew)
      Adds or tests an entry with the lock already held.
      Parameters:
      entry - the entry bytes
      offset - where the entry starts
      len - the entry length
      addIfNew - true to add when not already present
      Returns:
      true if the entry may be new

    • clear

      public void clear()
      Clear all filters and reset counts.

    • stopDecaying

      public void stopDecaying()
      Stop the decay process.

    • decay

      protected void decay()
      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.

    • getReadLock

      protected void getReadLock()
      Acquire the read lock.

    • releaseReadLock

      protected void releaseReadLock()
      Release the read lock.

    • getWriteLock

      protected boolean getWriteLock()
      Acquire the write lock.
      Returns:
      true if the lock was acquired

    • releaseWriteLock

      protected void releaseWriteLock()
      Release the write lock.