Ribbon filter: Practically smaller than Bloom and Xor
engineering.fb.com
engineering.fb.com
Use a hash function b(x) to transform keys into fixed length bitvectors.
Now we want to build a function b'(x) such that b'(x) = b(x) for any keys in our set, and such that b'(x) is a random value for other keys. Checking if b' and b agree will be our membership test.
They construct b'(x) as h(x)· Z, where h is a vector with binary entries and Z is a matrix with binary entries.
By taking all the elements we want and computing h(x) for each of them we get a bunch of vectors that we can arrange into a matrix H. Z can be found by gaussian elimination on that matrix.
The name ribbon filter comes from the fact that H is constructed in a particular way that gives it a ribbon shape. That shape makes the whole thing efficient in time and space.
As something related HN might find interesting: Ethereum uses Bloom filters internally within each block to allow users to easily watch for specific "events" that are fired off by transactions. So, for example, you can just look at the Bloom filter in a block and check if your address is in it, and this will tell you if certain types of tokens might have been transferred to your address within this block. As a user, this might allow you to not look at all the transactions in a block if you're just trying to watch for transactions relevant to you.
But the system is a bit broken. Because Bloom filters only do probabilistic checks of set membership (so it might say inclusion when there's nothing included), and because Bloom filters use hashing internally, you can pretty easily fill up the entire Bloom filter and potentially minorly DOS a few clients. A friend and I have a write-up about our attack (here.)[1] We ended up deciding it wasn't high severity, but it was still pretty fun.
[1] https://medium.com/@naterush1997/eth-goes-bloom-filling-up-e...)
I think it’s reasonable to expect that there are many structures out there that can achieve the same API in less space (time?) and that at least a few of those can achieve a better API in the same space, even if it means giving up some gains to store extra metadata.
Example: linked list hashmaps, which store two extra pointers to remember insertion order.
That being said, I haven't read it. Even parts of the blog post's implementation summary were over my head. That paper would be surely more of a "study" than a "read" for me
I’ve been looking for a simple but more efficient than bloom structure but many of the alternatives are quite complex (so hard to reimplement/port) or less performant. Still quite interesting. Will need to read this more closely.
E: yes, self-confirming that's what's meant. This is a great low-maths explanation from downthread which helped - https://news.ycombinator.com/item?id=27800788
* Mutable - streaming applications
* Mergable - so you can avoid querying N filters all the time or share slices.
* Scalable - so you don't have to pre-size
* Performant
* Serialize to bytes
* Language - Implemented in multiple languages. Many are in C only which is suboptimal (and often too complicated to easily port).
* Bonus: Thread safe implementation
Typically you can get some of these, but not all. Sometimes its not just possible with the structure (e.g. mutability in xor filter), sometimes its an implementation gap (serialization, etc.)
In my case finding the magical combination in Java has been quite difficult. The only way was to do custom, and relax some requirements (like auto scalable structures).
After doing a lot of testing I ended up with pre-sized bloom filters behind an MPSC model. The tradeoff of having to monitor/pre-size filters is one I'm not happy with but weighed against other tradeoffs it made sense.
Cuckoo was far too slow (and merging was iffy), and I can get a huge speed increase switching and customizing implementations (Guava -> spark -> fastfilter), and also big boost using xx3 (or xxh) rather then murmur which is pretty popular in off the shelf implementations.
Porting CQF, and much of the latest research was just too much (and many implementations lack merging, etc so you have to really understand the structure to do it right).
GPLv2 or Apache 2.0
TFA article shows that they do share your worries, but they believe this approach is indeed simple enough to be worth it.
Sure you need to trust the authors. I'm sure we regularly do such leap of faith all the time we use various software components we surely don't review on a daily basis, not sure why this particular tool should be judged a different standard (provided that is indeed straightforward to operate)
I was looking more for "I can understand/implement/debug it myself" practicability, avoiding black boxes.
Even in the FB case there is the bus factor of course. When the author at some point moves on to greener pastures they can only hope that it still fits into the brain of whoever replaces him.
Or if you know that your key is always included in the dataset, it is pure overhead.
??
And the title seems to be a reference to it too, "Cuckoo Filters, Practically Better Than Bloom"
I would have factored in the code size with it too.
Basically using code size as a proxy for code complexity
(which is not always the case of course)
E.g., from [0]:
Compressors are ranked by the compressed size of enwik9 (109 bytes) plus the size of a zip archive containing the decompresser.
If you find yourself rolling dice to figure out if something is in a set or not, you may want to step back and look at how you track membership and identity things.
Determinism (testability) is such a wonderful thing. Sure, you can make these filters appear deterministic in controlled setting (i.e. a recorded log of system inputs), but there's no way you could tell me how the execution would flow in a real world situation with live data wherein you cannot anticipate future events.
Bloom filters for example can serve as a filter: to work only on 50% of the data to effectively speed up your calculations by 100%.
If 50% of your misses are bloom filtered away, you got rid of 50% of your lookups to storage.
---------
In fact, most cryptography only works off of probability. Not only keys or RNG, but also on routine algorithms like finding a prime number.
Usually in cryptography problems when we assume that our assumptions hold (e.g. there's no better method than a semi sophisticated brute force), you get that probability down to a negligible number. And I recall learning that some key generating systems will even have a list of known cracked large primes, and check to make sure what it generates isn't in that list (in case the systems RNG is biased.)
Imagine your mailbox out in your yard has a slightly faulty indicator: Sometimes when it's ON, there's actually no mail. But you know for a fact that when it's OFF, you definitely have no mail. So you can look out your window to determine whether you might have mail.
If the indicator saves you more unnecessary trips to the mailbox than it causes by failing to indicate, it's a good thing to have overall.
That's what bloom filters do. They sometimes save you needless work. The fact that "sometimes" isn't deterministic doesn't detract from its usefulness.
At the set sizes they are useful for, you simply have to make trade offs for performance reasons, and the trade off you are making is explicit.
If you are are using a bloom filter, you know upfront that false positives will happen. That is a fundamental part of the code you will write, it isn’t something you will discover at a later date. You will write tests for false positives. It is well understood what the probabilities are for false positives.
If you can’t live with that in your code, you might not be able to work on the sorts of workloads that bloom filters are good for.