bloomfilter-redis

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

Latest on Hackage:0.1.0.3

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed and maintained by Tobias Markus <tobias AT miglix DOT eu>

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.

Changes

0.1.0.3

  • Compatibility with GHC 8.0/base-4.9

0.1.0.2

  • Fix bad Hackage upload of 0.1.0.2 (it accidentally contained a breaking API change to be released in a later version)

0.1.0.1

  • README improvements
  • Compatibility with GHC 7.8/base-4.7
  • Test suite improvements

0.1.0.0

Initial release

Used by 1 package:
comments powered byDisqus