bloomfilter-rb

When initializing BloomFilter::Native.new, you can provide the following options:

• :size: The size of the bit array.
• :hashes: The number of hash functions to use.
• :seed: The initial seed for the CRC32 hash.
• :bucket: The size of the counter bucket.
• :raise: Boolean indicating whether to raise errors.

To use the bloomfilter-rb library, require it in your Ruby application. The library provides several implementations of Bloom filters, including native C-based filters, Redis-backed filters, and counting Bloom filters with TTL support.

Depending on your needs, you can use:

• BloomFilter::Filter: Standard Bloom filter implementation.
• BloomFilter::Native: High-performance native implementation (requires cbloomfilter).
• BloomFilter::Redis: Redis-backed Bloom filter using setbit/getbit.
• BloomFilter::CountingRedis: Redis-backed counting Bloom filter with TTL support.

require 'bloomfilter-rb'

The BloomFilter::Native implementation provides an in-memory counting bloom filter using a C extension. It is suitable for high-performance, local use cases where the filter can be saved to and reloaded from disk. It supports a hash-like interface for checking membership.

require 'bloomfilter-rb'

# Initialize a native filter
bf = BloomFilter::Native.new(:size => 100, :hashes => 2, :seed => 1, :bucket => 3, :raise => false)

bf.insert("test")
bf.include?("test")     # => true
bf.include?("blah")     # => false

# Deleting an element (counting filter)
bf.delete("test")
bf.include?("test")     # => false

# Hash-like interface
bf["test2"] = "bar"
bf["test2"]             # => true

# Retrieve statistics
bf.stats

The BloomFilter::Redis implementation uses Redis getbit and setbit commands on Redis strings. This approach is efficient, fast, and allows the bloom filter to be shared across multiple concurrent processes.

require 'bloomfilter-rb'

bf = BloomFilter::Redis.new

bf.insert('test')
bf.include?('test')     # => true
bf.include?('blah')     # => false

bf.delete('test')
bf.include?('test')     # => false

The BloomFilter::CountingRedis implementation uses standard Redis get/set counters. This allows for a counting bloom filter with optional Time-To-Live (TTL) expiry for elements.

Note on Memory: Because each 'bit' is implemented as its own key in Redis, this method incurs a significantly larger memory overhead compared to the getbit/setbit approach.

require 'bloomfilter-rb'

# Initialize with a TTL of 2 seconds
bf = BloomFilter::CountingRedis.new(:ttl => 2)

bf.insert('test')
bf.include?('test')     # => true

sleep(2)
bf.include?('test')     # => false

Use delete(key) to remove a key from the filter. This decrements the count at the calculated bit indexes. If a count reaches zero or less, the corresponding Redis key is deleted.

filter = BloomFilter::CountingRedis.new
filter.insert("my_key")
filter.delete("my_key")

To reset the filter, use the clear method. This clears the bitset associated with the configured :namespace in Redis.

filter = BloomFilter::Redis.new(namespace: 'my_filter')
filter.clear

You can persist a BloomFilter::Native instance using Ruby's Marshal format via the save and load methods.

filter = BloomFilter::Native.new(size: 500)
filter.insert("data")

# Save to a file
filter.save("filter.dat")

# Load from a file
new_filter = BloomFilter::Native.load("filter.dat")

Use insert(key, ttl=nil) to add a key to the bloom filter. This increments the count at the calculated bit indexes in Redis.

• key: The value to insert.
• ttl: (Optional) An integer representing seconds until expiration. If not provided, the filter's default :ttl (set during initialization) is used.

Note: []= is an alias for insert.

If a ttl is provided, expire is called on the specific Redis indexes.

filter = BloomFilter::CountingRedis.new(ttl: 3600)

# Insert with default TTL
filter.insert("my_key")
filter["my_key"] = true

# Insert with a specific TTL
filter.insert("temporary_key", 60)

The BloomFilter::Native class provides an in-memory counting bloom filter implementation using a native C extension. You can initialize it with an options hash to configure its capacity and behavior.

Available options:

• :size (m): Number of buckets in the bloom filter (default: 100).
• :hashes (k): Number of hash functions (default: 4).
• :seed (s): Seed for the hash functions (default: current time Time.now.to_i).
• :bucket (b): Number of bits in a bloom filter bucket (default: 3).
• :raise (r): Whether to raise an error on bucket overflow (default: false).

filter = BloomFilter::Native.new(
  size: 1000,
  hashes: 5,
  seed: 12345,
  bucket: 4,
  raise: true
)

The stats method provides a summary of the current Bloom Filter's configuration and its theoretical performance. It outputs the following metrics to stdout:

• Number of filter buckets (m): The total size of the bit array/filter.
• Number of bits per bucket (b): The number of bits allocated per bucket.
• Number of filter elements (n): The current number of elements stored in the filter.
• Number of filter hashes (k): The number of hash functions used.
• Raise on overflow? (r): Whether the filter is configured to raise an error when it reaches capacity.
• Predicted false positive rate: The calculated probability of a false positive based on current parameters.

# Assuming 'filter' is an instance of a BloomFilter::Filter subclass
filter.stats