java.lang.Object
org.xlattice.crypto.filters.BloomSHA1
public class BloomSHA1extends Object
A Bloom filter for sets of SHA1 digests. A Bloom filter uses a set of k hash functions to determine set membership. Each hash function produces a value in the range 0..M-1. The filter is of size M. To add a member to the set, apply each function to the new member and set the corresponding bit in the filter. For M very large relative to k, this will normally set k bits in the filter. To check whether x is a member of the set, apply each of the k hash functions to x and check whether the corresponding bits are set in the filter. If any are not set, x is definitely not a member. If all are set, x may be a member. The probability of error (the false positive rate) is f = (1 - e^(-kN/M))^k, where N is the number of set members. This class takes advantage of the fact that SHA1 digests are good- quality pseudo-random numbers. The k hash functions are the values of distinct sets of bits taken from the 20-byte SHA1 hash. The number of bits in the filter, M, is constrained to be a power of 2; M == 2^m. The number of bits in each hash function may not exceed floor(m/k). This class is designed to be thread-safe, but this has not been exhaustively tested. BloomSHA1.java and KeySelector.java are BSD licensed from the xlattice app - http://xlattice.sourceforge.net/ minor tweaks by jrandom, exposing unsynchronized access and allowing larger M and K. changes released into the public domain. Note that this is used only by DecayingBloomFilter, which uses only the unsynchronized locked_foo() methods. Deprecated for use outside of the router; to be moved to router.jar. As of 0.8.11, the locked_foo() methods are thread-safe, in that they work, but there is a minor risk of false-negatives if two threads are accessing the same bloom filter integer.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    BloomSHA1.FilterKey
    Stores the (opaque) bloom filter offsets for reuse.
    static final class 
    BloomSHA1.Reset
    A pre-zeroed bit array waiting to be installed, so the memset can happen away from the lock that guards the filter.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final ThreadLocal<ArrayDeque<int[]>>
    bufPool
    Per-thread pool of offset scratch arrays, so that hashing a key does not allocate its scratch space or contend on a shared queue.
    private int
    count
    Items added to the filter.
    private int[]
    filter
    The words holding the filter bits.
    private final int
    filterBits
    Bits in the filter array.
    private final int
    filterWords
    Words holding the filter bits.
    private final int
    k
    Keys set per added item.
    private final KeySelector
    ks
    Selector of the hash keys for an item.
    private final int
    m
    Bits in the filter.
    private static final int
    POOL_DEPTH
    Maximum scratch arrays retained per thread.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BloomSHA1()
    Creates a filter of 2^20 bits with k defaulting to 8.
    BloomSHA1(int m)
    Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8.
    BloomSHA1(int m, int k)
    Creates a filter with 2^m bits and k 'hash functions', where each hash function is portion of the 160-bit SHA1 hash.

  • Method Summary

    Modifier and Type
    Method
    Description
    private int[]
    acquire()
    Acquires offset arrays from the buffer pool.
    void
    applyReset(BloomSHA1.Reset reset)
    Install a prepared reset.
    final int
    capacity()
    Returns the number of bits in the filter.
    void
    clear()
    Clears the filter, synchronized.
    final double
    falsePositives()
    Calculates the approximate false positive rate for the current number of set members.
    final double
    falsePositives(int n)
    Calculates the approximate false positive rate for a given number of set members.
    BloomSHA1.FilterKey
    getFilterKey(byte[] b, int offset, int len)
    Get the bloom filter offsets for reuse.
    void
    insert(byte[] b)
    Add a key to the set represented by the filter.
    void
    insert(byte[] b, int offset, int len)
    Add a key to the set represented by the filter.
    private final boolean
    isMember(byte[] b)
    Checks if a key is in the filter.
    private final boolean
    isMember(byte[] b, int offset, int len)
    Checks if a key is in the filter.
    final void
    locked_insert(byte[] b)
    Add a key to the filter without synchronization.
    final void
    locked_insert(byte[] b, int offset, int len)
    Add a key to the filter without synchronization.
    void
    locked_insert(BloomSHA1.FilterKey fk)
    Add the key to the filter.
    final boolean
    locked_member(byte[] b)
    Checks if a key is in the filter without synchronization.
    final boolean
    locked_member(byte[] b, int offset, int len)
    Checks if a key is in the filter without synchronization.
    boolean
    locked_member(BloomSHA1.FilterKey fk)
    Is the key in the filter.
    final boolean
    member(byte[] b)
    Is a key in the filter.
    final boolean
    member(byte[] b, int offset, int len)
    Is a key in the filter.
    BloomSHA1.Reset
    prepareReset()
    Allocate a zeroed bit array of this filter's size, away from whatever lock protects the filter.
    private void
    recycle(int[] arr)
    Returns a scratch array to this thread's pool, dropping it if the pool is already full so that a burst cannot retain an unbounded number.
    void
    release(BloomSHA1.FilterKey fk)
    Releases filter key arrays back to the buffer pool.
    final int
    size()
    Returns the number of keys which have been inserted.

    Methods inherited from class Object

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

  • Field Details

    • m

      private final int m
      Bits in the filter.

    • k

      private final int k
      Keys set per added item.

    • count

      private int count
      Items added to the filter.

    • filter

      private int[] filter
      The words holding the filter bits.

    • ks

      private final KeySelector ks
      Selector of the hash keys for an item.

    • filterBits

      private final int filterBits
      Bits in the filter array.

    • filterWords

      private final int filterWords
      Words holding the filter bits.

    • POOL_DEPTH

      private static final int POOL_DEPTH
      Maximum scratch arrays retained per thread.
      See Also:

    • bufPool

      private final ThreadLocal<ArrayDeque<int[]>> bufPool
      Per-thread pool of offset scratch arrays, so that hashing a key does not allocate its scratch space or contend on a shared queue. Thread confined, so no locking is needed: a FilterKey is always created and released by the same thread. Deques rather than single slots so nested use stays correct. The FilterKey itself is still allocated per getFilterKey() call, which is a small object holding the two arrays.

  • Constructor Details

    • BloomSHA1

      public BloomSHA1(int m, int k)
      Creates a filter with 2^m bits and k 'hash functions', where each hash function is portion of the 160-bit SHA1 hash.
      Parameters:
      m - determines number of bits in filter
      k - number of hash functions See KeySelector for important restriction on max m and k

    • BloomSHA1

      public BloomSHA1(int m)
      Creates a filter of 2^m bits, with the number of 'hash functions" k defaulting to 8.
      Parameters:
      m - determines size of filter

    • BloomSHA1

      public BloomSHA1()
      Creates a filter of 2^20 bits with k defaulting to 8.

  • Method Details

    • prepareReset

      public BloomSHA1.Reset prepareReset()
      Allocate a zeroed bit array of this filter's size, away from whatever lock protects the filter. Zeroing is the expensive part of a reset, so doing it here keeps a decay from stalling every concurrent insert.

      Pair with applyReset(Reset), which is O(1).

      Tradeoff: this allocates a whole filter's worth of array per reset rather than reusing it, so it costs more total work than an in-place fill on a cache-resident filter, and leaves the collector a large short-lived array to account for. That is the right trade at the sizes where the stall would hurt: measured at m=29 an in-place fill under the lock runs about 2.6ms against about 1.4ms to allocate, and the ordering only reverses below m=28, where the whole operation is already under 0.6ms. Reusing the array on a background thread would avoid both costs, but needs a spare buffer held permanently, which is another 50% of the filter's memory.

      Returns:
      a reset token holding a fresh zeroed array

    • applyReset

      public void applyReset(BloomSHA1.Reset reset)
      Install a prepared reset. O(1), because the caller has already paid for the zeroed array. The caller must hold exclusive access to this filter, which for the decaying filters means holding their write lock.
      Parameters:
      reset - a token from prepareReset() for this filter
      Throws:
      IllegalArgumentException - if the token is not for this filter

    • clear

      public void clear()
      Clears the filter, synchronized.

      On a latency path prefer prepareReset() plus applyReset(Reset), which moves the memset off the lock.

    • size

      public final int size()
      Returns the number of keys which have been inserted. This class (BloomSHA1) does not guarantee uniqueness in any sense; if the same key is added N times, the number of set members reported will increase by N.
      Returns:
      number of set members

    • capacity

      public final int capacity()
      Returns the number of bits in the filter.
      Returns:
      number of bits in filter

    • insert

      public void insert(byte[] b)
      Add a key to the set represented by the filter. This version does not maintain 4-bit counters, it is not a counting Bloom filter.
      Parameters:
      b - byte array representing a key (SHA1 digest)

    • insert

      public void insert(byte[] b, int offset, int len)
      Add a key to the set represented by the filter. This version does not maintain 4-bit counters, it is not a counting Bloom filter.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use

    • locked_insert

      public final void locked_insert(byte[] b)
      Add a key to the filter without synchronization.
      Parameters:
      b - byte array representing a key (SHA1 digest)

    • locked_insert

      public final void locked_insert(byte[] b, int offset, int len)
      Add a key to the filter without synchronization.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use

    • isMember

      private final boolean isMember(byte[] b)
      Checks if a key is in the filter. Sets up the bit and word offset arrays.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      Returns:
      true if b is in the filter

    • isMember

      private final boolean isMember(byte[] b, int offset, int len)
      Checks if a key is in the filter. Sets up the bit and word offset arrays.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use
      Returns:
      true if b is in the filter

    • locked_member

      public final boolean locked_member(byte[] b)
      Checks if a key is in the filter without synchronization.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      Returns:
      true if b is in the filter

    • locked_member

      public final boolean locked_member(byte[] b, int offset, int len)
      Checks if a key is in the filter without synchronization.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use
      Returns:
      true if b is in the filter

    • member

      public final boolean member(byte[] b)
      Is a key in the filter. External interface, internally synchronized.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      Returns:
      true if b is in the filter

    • member

      public final boolean member(byte[] b, int offset, int len)
      Is a key in the filter. External interface, internally synchronized.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use
      Returns:
      true if b is in the filter

    • getFilterKey

      public BloomSHA1.FilterKey getFilterKey(byte[] b, int offset, int len)
      Get the bloom filter offsets for reuse. Caller should call release(rv) when done with it.
      Parameters:
      b - byte array representing a key (SHA1 digest)
      offset - starting offset in the byte array
      len - number of bytes to use
      Returns:
      filter key containing the offsets

    • locked_insert

      public void locked_insert(BloomSHA1.FilterKey fk)
      Add the key to the filter.
      Parameters:
      fk - filter key containing offsets

    • locked_member

      public boolean locked_member(BloomSHA1.FilterKey fk)
      Is the key in the filter.
      Parameters:
      fk - filter key containing offsets
      Returns:
      true if the key is in the filter

    • acquire

      private int[] acquire()
      Acquires offset arrays from the buffer pool.
      Returns:
      int array of size k containing bit offsets

    • recycle

      private void recycle(int[] arr)
      Returns a scratch array to this thread's pool, dropping it if the pool is already full so that a burst cannot retain an unbounded number.
      Parameters:
      arr - the array to recycle

    • release

      public void release(BloomSHA1.FilterKey fk)
      Releases filter key arrays back to the buffer pool.
      Parameters:
      fk - filter key to release

    • falsePositives

      public final double falsePositives(int n)
      Calculates the approximate false positive rate for a given number of set members.
      Parameters:
      n - number of set members
      Returns:
      approximate false positive rate

    • falsePositives

      public final double falsePositives()
      Calculates the approximate false positive rate for the current number of set members.
      Returns:
      approximate false positive rate