4 ms·

This is an interesting structure. It’s important to note that it’s an immutable structure so it’s more comparable to xor filters rather than bloom in that aspe

This is an interesting structure. It’s important to note that it’s an immutable structure so it’s more comparable to xor filters rather than bloom in that aspect. 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.

hirsin 5y ago
Immutable here meaning that all keys need to be known ahead of time of the construction? Certainly that's been one of the nice features of our use of bloom filters - we can safely add keys over time on demand, sharding every hour and giving all callers an up-to-the-second filter when they call. We could do a ribbon/minute and send that series out, but you lose efficiency by forcing checks across eg 24*60 filters. 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 https://news.ycombinator.com/item?id=27800788
- gwittel 5y ago
  Correct. I've been going deep into this looking for a unicorn implementation friendly to distributed environments: * 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).

hirsin 5y ago

Immutable here meaning that all keys need to be known ahead of time of the construction? Certainly that's been one of the nice features of our use of bloom filters - we can safely add keys over time on demand, sharding every hour and giving all callers an up-to-the-second filter when they call. We could do a ribbon/minute and send that series out, but you lose efficiency by forcing checks across eg 24*60 filters. 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 https://news.ycombinator.com/item?id=27800788

gwittel 5y ago
Correct. I've been going deep into this looking for a unicorn implementation friendly to distributed environments: * 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).