Package net.i2p.router.util

Class DecayingBloomFilter

java.lang.Object
net.i2p.router.util.DecayingBloomFilter
Direct Known Subclasses:
DecayingHashSet
public class DecayingBloomFilter extends Object
Series of bloom filters which decay over time, allowing their continual use for time sensitive data. This has a fixed size (per period, using two periods overall), allowing this to pump through hundreds of entries per second with virtually no false positive rate. Down the line, this may be refactored to allow tighter control of the size necessary for the contained bloom filters. See main() for an analysis of false positive rate. See BloomFilterIVValidator for instantiation parameters. See DecayingHashSet for a smaller and simpler version. See net.i2p.router.tunnel.BloomFilterIVValidator
See Also:

  • Field Details

    • _context

      protected final I2PAppContext _context

    • _log

      protected final Log _log

    • _durationMs

      protected final int _durationMs

    • _entryBytes

      protected final int _entryBytes

    • _currentDuplicates

      protected long _currentDuplicates

    • _keepDecaying

      protected volatile boolean _keepDecaying

    • _decayEvent

      protected final SimpleTimer2.TimedEvent _decayEvent

    • _name

      protected final String _name
      just for logging

    • _reorganizeLock

      protected final ReentrantReadWriteLock _reorganizeLock
      synchronize against this lock when switching double buffers

  • Constructor Details

    • DecayingBloomFilter

      protected DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)
      only for extension by DHS

    • 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:
      durationMs - entries last for at least this long, but no more than twice this long
      entryBytes - how large are the entries to be added? if this is less than 32 bytes, the entries added will be expanded by concatenating their XORing against with sufficient random values.

    • DecayingBloomFilter

      public DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name)
      Uses default m of 23, memory usage is 2 MB.
      Parameters:
      name - just for logging / debugging / stats

    • 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.
      Parameters:
      m - filter size exponent, max is 29

  • Method Details

    • getCurrentDuplicateCount

      public long getCurrentDuplicateCount()

    • getInsertedCount

      public int getInsertedCount()
      unsynchronized but only used for logging elsewhere

    • getFalsePositiveRate

      public double getFalsePositiveRate()
      unsynchronized, only used for logging elsewhere

    • add

      public boolean add(byte[] entry)
      Returns:
      true if the entry added is a duplicate

    • add

      public boolean add(byte[] entry, int off, int len)
      Returns:
      true if the entry added is a duplicate

    • add

      public boolean add(long entry)
      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)
      Returns:
      true if the entry is already known. this does NOT add the entry however.

    • clear

      public void clear()

    • stopDecaying

      public void stopDecaying()

    • decay

      protected void decay()

    • getReadLock

      protected void getReadLock()
      Since:
      0.8.11 moved from DecayingHashSet

    • releaseReadLock

      protected void releaseReadLock()
      Since:
      0.8.11 moved from DecayingHashSet

    • getWriteLock

      protected boolean getWriteLock()
      Returns:
      true if the lock was acquired
      Since:
      0.8.11 moved from DecayingHashSet

    • releaseWriteLock

      protected void releaseWriteLock()
      Since:
      0.8.11 moved from DecayingHashSet