The bloomfilter-redis package

[Tags:benchmark, bsd3, library, test]

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

The hash family algorithm is partly inspired by Brian O'Sullivan's bloomfilter package at https://hackage.haskell.org/package/bloomfilter.


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.0.3 (info)
Change log CHANGELOG.md
Dependencies arithmoi (>=0.3 && <0.5), base (>=4.7 && <4.10), binary (>=0.7 && <0.9), bytestring (>=0.9 && <0.11), hashable (==1.2.*), hedis (>=0.5 && <0.10) [details]
License BSD3
Copyright Copyright 2016 Tobias Markus <tobias AT miglix DOT eu>
Author Tobias Markus <tobias AT miglix DOT eu>
Maintainer Tobias Markus <tobias AT miglix DOT eu>
Stability Experimental
Category Data
Source repository head: git clone https://github.com/hesiod/bloomfilter-redis.git
Uploaded Sat Jun 4 15:58:42 UTC 2016 by hesiod
Distributions NixOS:0.1.0.3
Downloads 139 total (8 in the last 30 days)
Votes
1 []
Status Docs available [build log]
Last success reported on 2016-06-04 [all 1 reports]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for bloomfilter-redis

Readme for bloomfilter-redis-0.1.0.3

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.