4 ms·

Fleur – A bloom filter implementation in C

83 points by adulau 4y ago

lambdaloop 4y ago
I love that name! Based on the metrics at the bottom, is it right that it's 3 times faster than the Go implementation? What makes it so fast?
- FreakLegion 4y ago
  Without looking at the implementations I'd guess it's Go's bounds checking.
drfuchs 4y ago
Could be faster still if it didn't calloc/free a "Fingerprint" buffer each time you add or query an entry. Since its individual BloomFilters are not thread-safe anyway, it could allocate the buffer once at BloomFilter creation time and be done with it.
mitchellh 4y ago
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
jstrieb 4y ago
I appreciate the Go-style docstring comments in the code! For anyone trying to understand Bloom filters who may be interested in checking out an alternative C implementation (designed to be compiled to WebAssembly), I'll link mine below. I used it to build a Bloom filter of every Hacker News submission ever for a privacy-preserving browser extension that tells you if the page you're currently on has been submitted before. https://github.com/jstrieb/hackernews-button/blob/master/bloom-filter/bloom.c https://github.com/jstrieb/hackernews-button/blob/master/blo...
malkia 4y ago
Sorry to be pedant, but using good prefix, or even suffix for C library is a must, and come up with something unique (and "fleur" is kind of cool), probably good idea to prefix with it, and then it can be used without any current or future symbol clashes.
khoobid_shoma 4y ago
Was it necessary to use Ninja?
- glouwbug 4y ago
  The best approach is bash + cmake + ninja + github actions with a single main.c /s
eis 4y ago
Sorry if this is a bit negative but from a cursory look I wouldn't use this. An efficient Bloom Filter should only allocate on heap exactly once: when allocating the initial bitmap. This implementation seems to be not very efficient as it allocates even during a simple query. The usage of `static` variables makes the BloomFilter code unnecessarily dangerous to use when multiple threads are used even if every thread just wants to allocate and use totally separate bloom filters. Actually it could even cause issues with two bloom filters created after each other since even `Initialize` just returns a pointer to a single static `BloomFilter` :o I can't come up with a reason why you'd consider making anything in there `static`. There is also strange code like this loop https://github.com/hashlookup/fleur/blob/4ee2644a850381d928ad86fce8b2357f21102eee/fleurcli/fleurcli.c#L102 https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a... that jumped into my eye. Oh and btw I believe bloom_path can cause memory safety issues because it is not terminated with a null after strncopy. I would additionally suggest to use some code formatting tool as it's a bit all over the place. But the variable/function names mix various styles as well.
- shric 4y ago
  > There is also strange code like this loop https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a... that jumped into my eye. The line below that is worse: strncpy(bloom_path , argv[optind], 128); If you pass something >= 128 chars then bloom_path won't be null terminated. In general strncpy should never be used for copying strings. For expansion on that: https://ramblings.implicit.net/c/2014/05/02/c-functions-that-should-be-avoided-part-2.html https://ramblings.implicit.net/c/2014/05/02/c-functions-that...
  - metadat 4y ago
    tl;dr: use strlcpy instead.
  - shric 4y ago
    And I just realised the GP already mentioned the bloom_path issue. Sorry, too late to edit.
- 4y ago
gallypette 4y ago
Ho wow, I did not expect an hacker news front page code review today. As you can see I am not a seasoned C developer so that was very welcome :)

83 points by adulau 4y ago

I love that name! Based on the metrics at the bottom, is it right that it's 3 times faster than the Go implementation? What makes it so fast?

FreakLegion 4y ago
Without looking at the implementations I'd guess it's Go's bounds checking.

drfuchs 4y ago

Could be faster still if it didn't calloc/free a "Fingerprint" buffer each time you add or query an entry. Since its individual BloomFilters are not thread-safe anyway, it could allocate the buffer once at BloomFilter creation time and be done with it.

mitchellh 4y ago

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

jstrieb 4y ago

I appreciate the Go-style docstring comments in the code! For anyone trying to understand Bloom filters who may be interested in checking out an alternative C implementation (designed to be compiled to WebAssembly), I'll link mine below. I used it to build a Bloom filter of every Hacker News submission ever for a privacy-preserving browser extension that tells you if the page you're currently on has been submitted before. https://github.com/jstrieb/hackernews-button/blob/master/bloom-filter/bloom.c https://github.com/jstrieb/hackernews-button/blob/master/blo...

malkia 4y ago

Sorry to be pedant, but using good prefix, or even suffix for C library is a must, and come up with something unique (and "fleur" is kind of cool), probably good idea to prefix with it, and then it can be used without any current or future symbol clashes.

khoobid_shoma 4y ago

Was it necessary to use Ninja?

glouwbug 4y ago
The best approach is bash + cmake + ninja + github actions with a single main.c /s

eis 4y ago

Sorry if this is a bit negative but from a cursory look I wouldn't use this. An efficient Bloom Filter should only allocate on heap exactly once: when allocating the initial bitmap. This implementation seems to be not very efficient as it allocates even during a simple query. The usage of `static` variables makes the BloomFilter code unnecessarily dangerous to use when multiple threads are used even if every thread just wants to allocate and use totally separate bloom filters. Actually it could even cause issues with two bloom filters created after each other since even `Initialize` just returns a pointer to a single static `BloomFilter` :o I can't come up with a reason why you'd consider making anything in there `static`. There is also strange code like this loop https://github.com/hashlookup/fleur/blob/4ee2644a850381d928ad86fce8b2357f21102eee/fleurcli/fleurcli.c#L102 https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a... that jumped into my eye. Oh and btw I believe bloom_path can cause memory safety issues because it is not terminated with a null after strncopy. I would additionally suggest to use some code formatting tool as it's a bit all over the place. But the variable/function names mix various styles as well.

shric 4y ago
> There is also strange code like this loop https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a https://github.com/hashlookup/fleur/blob/4ee2644a850381d928a... that jumped into my eye. The line below that is worse: strncpy(bloom_path , argv[optind], 128); If you pass something >= 128 chars then bloom_path won't be null terminated. In general strncpy should never be used for copying strings. For expansion on that: https://ramblings.implicit.net/c/2014/05/02/c-functions-that-should-be-avoided-part-2.html https://ramblings.implicit.net/c/2014/05/02/c-functions-that...
- metadat 4y ago
  tl;dr: use strlcpy instead.
- shric 4y ago
  And I just realised the GP already mentioned the bloom_path issue. Sorry, too late to edit.
4y ago

gallypette 4y ago

Ho wow, I did not expect an hacker news front page code review today. As you can see I am not a seasoned C developer so that was very welcome :)