Bloom filters

Note: This is a fork of github.com/willf/bloom that provides a read only bloom filter and a concurrent read only bloom filter that can both be instantiated from a mmap'd bytes ref and also limits the scope of the API.

A Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item is a member of a set.

A Bloom filter has two parameters: m, a maximum size (typically a reasonably large multiple of the cardinality of the set to represent) and k, the number of hashing functions on elements of the set. (The actual hashing functions are important, too, but this is not a parameter for this implementation). A Bloom filter is backed by a BitSet; a key is represented in the filter by setting the bits at each value of the hashing functions (modulo m). Set membership is done by testing whether the bits at each value of the hashing functions (again, modulo m) are set. If so, the item is in the set. If the item is actually in the set, a Bloom filter will never fail (the true positive rate is 1.0); but it is susceptible to false positives. The art is to choose k and m correctly.

In this implementation, the hashing functions used is murmurhash, a non-cryptographic hashing function.

This implementation accepts keys for setting and testing as []byte. Thus, to add a string item, "Love":

n := uint(1000)
filter := bloom.NewBloomFilter(20*n, 5) // load of 20, 5 keys
filter.Add([]byte("Love"))

Similarly, to test if "Love" is in bloom:

if filter.Test([]byte("Love"))

Godoc documentation: https://godoc.org/github.com/m3db/bloom

Performance

• macOS 10.13.6
• go version go1.10 darwin/amd64

$ GOMAXPROCS=1 go test github.com/m3db/bloom -bench=.
goos: darwin
goarch: amd64
pkg: github.com/m3db/bloom
BenchmarkAddX10kX5              10000000               174 ns/op
BenchmarkContains1kX10kX5       10000000               139 ns/op
BenchmarkContains100kX10BX20     5000000               271 ns/op

Installation

go get -u github.com/m3db/bloom

Running all tests

Before committing the code, please check if it passes all tests using (note: this will install some dependencies):

make deps
make qa