bloomfilter-redis

Distributed bloom filters on Redis (using the Hedis client).

The hash family algorithm is partly inspired by Brian O'Sullivan's bloomfilter package.

Features

• Implementation of the FNV-1/FNV-1a hash function is included
• Automatic derivation of a hash family from a single hash function as described by Kirsch and Mitzenmacher
• The bloom filter is distributed without extra effort since Redis does the heavy lifting
• Every Hashable type can be added to the bloom filter
• Every Binary type can be hashed

Benchmark and Testing suite

A benchmark for the FNV hash function is included and can be invoked using cabal bench or stack bench. An HTML report is generated as report.html.

A testing suite using tasty is included.

Further Information

Todo

• Separate the FNV hash function into a separate package
• The actual operations (addBF, queryBF, etc) should ideally live in a MonadReader (Bloom a), but this requires some work on the Hedis side because of RedisCtx

Caveats

• The only supported FNV hash sizes are 32 and 64 bits. Support for larger widths is a matter of having a data type with instances for FiniteBits and Num.
• The offset basis (fnvOffsetBasis) is not correctly computed, although this has absolutely no effect on the performance of the hash function in practice.