Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## net.i2p.util
Class DecayingHashSet

    java.lang.Object
      net.i2p.util.DecayingBloomFilter
          net.i2p.util.DecayingHashSet

    public class DecayingHashSet

extends DecayingBloomFilter

Double buffered hash set. Since DecayingBloomFilter was instantiated 4 times for a total memory usage of 8MB, it seemed like we could do a lot better, given these usage stats on a class L router: ./router/java/src/net/i2p/router/tunnel/BuildMessageProcessor.java: 32 bytes, peak 10 entries in 1m ./router/java/src/net/i2p/router/transport/udp/InboundMessageFragments.java: 4 bytes, peak 150 entries in 10s ./router/java/src/net/i2p/router/MessageValidator.java: 8 bytes, peak 1K entries in 2m ./router/java/src/net/i2p/router/tunnel/BloomFilterIVValidator.java: 16 bytes, peak 15K entries in 10m If the ArrayWrapper object in the HashSet is 50 bytes, and BloomSHA1(23, 11) is 1MB, then for less than 20K entries this is smaller. And this uses space proportional to traffiic, so it doesn't penalize small routers with a fixed 8MB. So let's try it for the first 2 or 3, for now. Also, DBF is syncrhonized, and uses SimpleTimer. Here we use a read/write lock, with synchronization only when switching double buffers, and we use SimpleScheduler. Yes, we could stare at stats all day, and try to calculate an acceptable false-positive rate for each of the above uses, then estimate the DBF size required to meet that rate for a given usage. Or even start adjusting the Bloom filter m and k values on a per-DBF basis. But it's a whole lot easier to implement something with a zero false positive rate, and uses less memory for almost all bandwidth classes. This has a strictly zero false positive rate for <= 8 byte keys. For larger keys, it is 1 / (2**64) ~= 5E-20, which is better than DBF for any entry count greater than about 14K. DBF has a zero false negative rate over the period 2 * durationMs. And a 100% false negative rate beyond that period. This has the same properties. This performs about twice as fast as DBF in the test below.

Author:
  zzz

Field Summary

Fields inherited from class net.i2p.util.DecayingBloomFilter
`_currentDuplicates`

Constructor Summary
`DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes)` Create a double-buffered hash set that will decay its entries over time.
`DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes, String name)`

Method Summary
`boolean` | `add(byte[] entry, int off, int len)`
`boolean` | `add(long entry)` return true if the entry added is a duplicate.
`void` | `clear()`
`double` | `getFalsePositiveRate()` pointless, only used for logging elsewhere
`int` | `getInsertedCount()` unsynchronized but only used for logging elsewhere
`boolean` | `isKnown(long entry)` return true if the entry is already known.
`static void` | `main(String[] args)` vs.
`void` | `stopDecaying()` super doesn't call clear, but neither do the users, so it seems like we should here

Methods inherited from class net.i2p.util.DecayingBloomFilter
`add, getCurrentDuplicateCount`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### DecayingHashSet

    public DecayingHashSet(I2PAppContext context,
                           int durationMs,
                           int entryBytes)

  Create a double-buffered hash set 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? 1 to 32 bytes

### DecayingHashSet

    public DecayingHashSet(I2PAppContext context,
                           int durationMs,
                           int entryBytes,
                           String name)

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

Method Detail

### getInsertedCount

    public int getInsertedCount()

  unsynchronized but only used for logging elsewhere

  Overrides:
    `getInsertedCount` in class `DecayingBloomFilter`

### getFalsePositiveRate

    public double getFalsePositiveRate()

  pointless, only used for logging elsewhere

  Overrides:
    `getFalsePositiveRate` in class `DecayingBloomFilter`

### add

    public boolean add(byte[] entry,
                       int off,
                       int len)

  Overrides:
    `add` in class `DecayingBloomFilter`
  Returns:
    true if the entry added is a duplicate

### add

    public boolean add(long entry)

  Description copied from class: `DecayingBloomFilter`
  return 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.

  Overrides:
    `add` in class `DecayingBloomFilter`
  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)

  Description copied from class: `DecayingBloomFilter`
  return true if the entry is already known. this does NOT add the entry however.

  Overrides:
    `isKnown` in class `DecayingBloomFilter`
  Returns:
    true if the entry is already known. this does NOT add the entry however.

### clear

    public void clear()

  Overrides:
    `clear` in class `DecayingBloomFilter`

### stopDecaying

    public void stopDecaying()

  super doesn't call clear, but neither do the users, so it seems like we should here

  Overrides:
    `stopDecaying` in class `DecayingBloomFilter`

### main

    public static void main(String[] args)

  vs. DBF, this measures 1.93x faster for testByLong and 2.46x faster for testByBytes.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD