search

jbapple / libfilter

High-speed Bloom filters and taffy filters for C, C++, and Java
Apache License 2.0
32 stars 6 forks source link

Support multi-threading #14

Open jbapple opened 2 years ago

mavam commented 2 years ago

Even though it sounds nice, I would consider internal threading as an anti-feature. Threads don't scale modern applications use a task-based method for concurrency. That said, creating a library that can be acted upon in a concurrent fashion is very useful. But the mechanism shouldn't be threads. That should be up to the user. It would feel like jab from the side if a library spawns threads internally and I'm already running a thread pool that optimally pins its threads to cores.

For example, our use case of building a telemetry engine over structured data involves hundreds of filters being created and queried in parallel. The bottleneck is not making insertion or querying faster of each single filter instance. Given this embarrassingly parallel setup, much more important to us is a merge operation, so that we can roll up multiple filters—LSM-style. If this would be possible with Taffy filters, then you'd solve the number one challenge with tree-structured hierarchical filter structures, which is provisioning the size of the non-leaf instances.

jbapple commented 2 years ago

Thanks for your thoughts!

Taffy cuckoo filters do support a Union operation - is that not what you're looking for?

mavam commented 2 years ago

Taffy cuckoo filters do support a Union operation - is that not what you're looking for?

That's great, I wasn't aware of it. Looking at the implementation, it seems also that there are no strict requirements in terms of sizing, as it would be the case for Bloom filters.

Mechanically, TBFs should support union as well by performing it piece-wise, no? I would only be worried about the FP-rate getting out of control due to oversubscribing of bits in each component that would otherwise be prevented by "organic" growth.

And MTCFs? Would it be possible to support Union also? Or are the subtables making this impossible?

jbapple commented 2 years ago

With TBFs it should be possible by doing bitwise OR on the levels, just like you surmise.

With MTCFs Union should also be possible. The key operation if iterating over an MTCF, performing the permutations in reverse, to reconstruct as many bits of the original key as possible.