net.i2p.router.util

Class DecayingBloomFilter

java.lang.Object

net.i2p.router.util.DecayingBloomFilter

Direct Known Subclasses:

DecayingHashSet

public class DecayingBloomFilter
extends 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:

DecayingHashSet, BloomFilterIVValidator

Field Summary

Fields

Modifier and Type	Field and Description
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

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) 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.
protected	DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context) only for extension by DHS

Method Summary

Modifier and Type	Method and Description
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

_currentDuplicates

protected long _currentDuplicates

_decayEvent

protected final SimpleTimer2.TimedEvent _decayEvent

_durationMs

protected final int _durationMs

_entryBytes

protected final int _entryBytes

_keepDecaying

protected volatile boolean _keepDecaying

_log

protected final Log _log

_name

protected final String _name

just for logging

_reorganizeLock

protected final ReentrantReadWriteLock _reorganizeLock

synchronize against this lock when switching double buffers

Constructor Detail

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

DecayingBloomFilter

protected DecayingBloomFilter(int durationMs,
                              int entryBytes,
                              String name,
                              I2PAppContext context)

only for extension by DHS

Method Detail

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.

clear

public void clear()

decay

protected void decay()

getCurrentDuplicateCount

public long getCurrentDuplicateCount()

getFalsePositiveRate

public double getFalsePositiveRate()

unsynchronized, only used for logging elsewhere

getInsertedCount

public int getInsertedCount()

unsynchronized but only used for logging elsewhere

getReadLock

protected void getReadLock()

getWriteLock

protected boolean getWriteLock()

Returns:

true if the lock was acquired

isKnown

public boolean isKnown(long entry)

Returns:

true if the entry is already known. this does NOT add the entry however.

releaseReadLock

protected void releaseReadLock()

releaseWriteLock

protected void releaseWriteLock()

stopDecaying

public void stopDecaying()