net.i2p.router.util
Class DecayingBloomFilter

java.lang.Object
  extended by 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 Also:
BloomFilterIVValidator, DecayingHashSet

Field Summary
protected  I2PAppContext _context
           
protected  long _currentDuplicates
           
protected  SimpleTimer2.TimedEvent _decayEvent
           
protected  int _durationMs
           
protected  int _entryBytes
           
protected  boolean _keepDecaying
           
protected  Log _log
           
protected  String _name
          just for logging
protected  ReentrantReadWriteLock _reorganizeLock
          synchronize against this lock when switching double buffers
 
Constructor Summary
  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
 boolean add(byte[] entry)
           
 boolean add(byte[] entry, int off, int len)
           
 boolean add(long entry)
           
 void clear()
           
protected  void decay()
           
 long getCurrentDuplicateCount()
           
 double getFalsePositiveRate()
          unsynchronized, only used for logging elsewhere
 int getInsertedCount()
          unsynchronized but only used for logging elsewhere
protected  void getReadLock()
           
protected  boolean getWriteLock()
           
 boolean isKnown(long entry)
           
protected  void releaseReadLock()
           
protected  void releaseWriteLock()
           
 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 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 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, max is 29
Method Detail

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