Skip to content

hesiod/bloomfilter-redis

Repository files navigation

bloomfilter-redis Build Status

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.