3 ms·

If you want a networked version (note: not based on Fleur): https://github.com/armon/bloomd https://github.com/armon/bloomd In the source there is a "libbloom"

If you want a networked version (note: not based on Fleur): https://github.com/armon/bloomd https://github.com/armon/bloomd In the source there is a "libbloom" as well that you could copy directly into your codebase if you wanted an embedded version. The networked version has a simple Redis-like text protocol so you can just use `telnet` to play around with it, too. Also written in C, with great performance (no comparison to this one, I haven't done it), and has been used in production by many companies for many years (since ~2012 or 2013). Just pointing out other implementations if anyone is curious!

llimllib 4y ago
Neat! Because it's a thing I do[1], the hash algorithms in use: Fleur (and DCSO/bloom and DCSO/flor): fnv bloomd: a combination of SpookyHash and murmur[2] [1]: https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/ (I'll update it to add bloomd and spooky) [2]: https://github.com/armon/bloomd/blob/23c19a7f5cbb35d7c3d970bef13bc2bfbe3625f6/src/libbloom/bloom.c#L306 https://github.com/armon/bloomd/blob/23c19a7f5cbb35d7c3d970b... [3]: I have a vague recollection of somebody telling me why combining two hashes in the way bloomd does for k >= 4 is a good idea but I can't remember - anybody have a good reference for me to link to? (edit: nvm, I already link the paper on my page! sheesh)
- FreakLegion 4y ago
  It's in the source, Less Hashing, Same Performance: Building a Better Bloom Filter: https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.p... I've used this trick at scale on network gear and it works great.
  - llimllib 4y ago
    hah yeah I noticed a minute later, the link is right in the comments, and I'd already linked the paper in my article! I feel like this is one of those things I re-learn every 5 years
  - ascar 4y ago
    I vaguely remember having read about multiple hashes for bloom filters in the past, but I have trouble extracting the actual approach from the linked paper. Could you give a summary? The paper is quite mathematical and seems to lack a clear description of how to actually use the two hashes without reading in depth.
    - FreakLegion 4y ago
      The basic idea of a Bloom filter is that you represent each item in the filter by setting k bits, and you set and query these bits using k hash functions. The bits need to be independent and uniformly distributed, so the hash functions need to output suitably random values for the same input. Even fast hash functions like Murmur add overhead, though, and the lower the desired false positive rate, the more hash functions you need (x hash functions for 2^-x false positive rate). The conclusion of the paper is roughly that you can create new hash functions by recombining the outputs of two initial hash functions without compromising the statistical integrity of the filter, and this makes querying the filter a lot faster. To be clear, even the two initial hash functions can be halves or quarters of a single hash function with an output larger than the filter needs, e.g. a filter that needs 64-bit hashes can run entirely on Murmur-128 using its bottom and top halves as the two hash functions.
    - llimllib 4y ago
      The bloomd source I linked above provides an excellent simple practical implementation

llimllib 4y ago

Neat! Because it's a thing I do[1], the hash algorithms in use: Fleur (and DCSO/bloom and DCSO/flor): fnv bloomd: a combination of SpookyHash and murmur[2] [1]: https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/ (I'll update it to add bloomd and spooky) [2]: https://github.com/armon/bloomd/blob/23c19a7f5cbb35d7c3d970bef13bc2bfbe3625f6/src/libbloom/bloom.c#L306 https://github.com/armon/bloomd/blob/23c19a7f5cbb35d7c3d970b... [3]: I have a vague recollection of somebody telling me why combining two hashes in the way bloomd does for k >= 4 is a good idea but I can't remember - anybody have a good reference for me to link to? (edit: nvm, I already link the paper on my page! sheesh)

FreakLegion 4y ago
It's in the source, Less Hashing, Same Performance: Building a Better Bloom Filter: https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.p... I've used this trick at scale on network gear and it works great.
- llimllib 4y ago
  hah yeah I noticed a minute later, the link is right in the comments, and I'd already linked the paper in my article! I feel like this is one of those things I re-learn every 5 years
- ascar 4y ago
  I vaguely remember having read about multiple hashes for bloom filters in the past, but I have trouble extracting the actual approach from the linked paper. Could you give a summary? The paper is quite mathematical and seems to lack a clear description of how to actually use the two hashes without reading in depth.
  - FreakLegion 4y ago
    The basic idea of a Bloom filter is that you represent each item in the filter by setting k bits, and you set and query these bits using k hash functions. The bits need to be independent and uniformly distributed, so the hash functions need to output suitably random values for the same input. Even fast hash functions like Murmur add overhead, though, and the lower the desired false positive rate, the more hash functions you need (x hash functions for 2^-x false positive rate). The conclusion of the paper is roughly that you can create new hash functions by recombining the outputs of two initial hash functions without compromising the statistical integrity of the filter, and this makes querying the filter a lot faster. To be clear, even the two initial hash functions can be halves or quarters of a single hash function with an output larger than the filter needs, e.g. a filter that needs 64-bit hashes can run entirely on Murmur-128 using its bottom and top halves as the two hash functions.
  - llimllib 4y ago
    The bloomd source I linked above provides an excellent simple practical implementation