net.i2p.util

## Class DecayingBloomFilter

- java.lang.Object
- - net.i2p.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 (currently 1MB per decay 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, but a fixed 2MB overhead isn't that bad. NOTE: At 1MBps, the tunnel IVV will see an unacceptable false positive rate of almost 0.1% with the current m and k values; however using DHS instead will use 30MB. Further analysis and tweaking for the tunnel IVV may be required.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected I2PAppContext` | `_context`
    `protected long` | `_currentDuplicates`
    `protected SimpleTimer.TimedEvent` | `_decayEvent`
    `protected int` | `_durationMs`
    `protected int` | `_entryBytes`
    `protected boolean` | `_keepDecaying`
    `protected Log` | `_log`
    `protected String` | `_name` just for logging

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `` | `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)`
    `` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m)`
    `protected` | `DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)` only for extension by DHS

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `boolean` | `add(byte[] entry)`
    `boolean` | `add(byte[] entry, int off, int len)`
    `boolean` | `add(long entry)`
    `void` | `clear()`
    `long` | `getCurrentDuplicateCount()`
    `double` | `getFalsePositiveRate()`
    `int` | `getInsertedCount()`
    `boolean` | `isKnown(long entry)`
    `static void` | `main(String[] args)` This filter is used only for participants and OBEPs, not IBGWs, so depending on your assumptions of avg.
    `void` | `stopDecaying()`

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### _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 SimpleTimer.TimedEvent _decayEvent

    - #### _name

          protected final String _name

      just for logging

  - ### Constructor Detail

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

      Parameters:
        `name` - just for logging / debugging / stats

    - #### DecayingBloomFilter

          public DecayingBloomFilter(I2PAppContext context,
                             int durationMs,
                             int entryBytes,
                             String name,
                             int m)

      Parameters:
        `m` - filter size exponent

  - ### Method Detail

    - #### getCurrentDuplicateCount

          public long getCurrentDuplicateCount()

    - #### getInsertedCount

          public int getInsertedCount()

    - #### getFalsePositiveRate

          public double getFalsePositiveRate()

    - #### 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()

    - #### main

          public static void main(String[] args)

      This filter is used only for participants and OBEPs, not IBGWs, so depending on your assumptions of avg. tunnel length, the performance is somewhat better than the gross share BW would indicate. Following stats for 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%. Following stats for m=24, k=10: 1280 4.5E-5; 1792 5.6E-4; 2048 0.14% Following stats for m=25, k=10: 1792 2.4E-6; 4096 0.14%