4 ms·
Show HN: BloomSearch – Keyword search with hierarchical Bloom filters
Hey HN! I got nerd-sniped by Bloom Filters this weekend, specifically for searching datasets with high "cardinality" (number of unique items).
They're an _amazing_ data structure that, at a fixed size, tracks potential set membership. That means unlike normal b-tree indexes, they don't grow with the number of unique items in the dataset.
This makes them great for "needle in a haystack" search (logs, document) as implementations like VictoriaMetrics and Bing's BitFunnel show.
I've used them in the past, but they've never been center-stage in my projects.
I wanted high cardinality keyword search for ANOTHER project... and, well, down the yak-shaving rabbit hole we go!
BloomSearch brings this into an extensible Go package:
- Very memory efficient via bloom filters and streaming row scans
- DataStore and MetaStore interfaces for any backend (can be same or separate)
- Hierarchical pruning via partitions, minmax indexes, and of course bloom filters
- Search by field, token, or field:token with complex combinators
- Disaggregated storage and compute for unbound ingest and query throughput
And of course, you know I had to make a custom file format ^-^ (FILE_FORMAT.MD)
BloomSearch is optimized for massive concurrency, arbitrary cardinality and dataset size, and super low memory usage.
There's still a lot on the table too in terms of size and performance optimizations, but I'm already super pleased with it. With distributed query processing I'm targeting >100B rows/s over large datasets.
I'm also excited to replace our big logging bill ~$0.003/GB for log storage with infinite retention and guilt-free querying :P
- deleted 1y ago[deleted]
- SwiftyBug 1y agoHow do you use Bloom filters to replace your current logs? Bloom filters are very good at knowing for sure that something does not exist in a set. What exactly is your set in this case? In other words, how can you query a dataset that's behind a bloom filter?
- dangoodmanUT 1y agoThere are three kinds of queries supported for keywords: - field - term - term in field Each file, and each row group within the file, has 3 bloom filters to handle these queries. So something like: {"user": {"name": "John", "tags": [{"type": "user"}, {"role": "admin"}]}} Gets turned into queryable pairs of: [{Path: "user.name", Values: ["John"]}, {Path: "user.tags.type", Values: ["user"]}, {Path: "user.tags.role", Values: ["admin"]}] Then you can search for: - any record that has "john" in it - any record that has the "user.tags.type" key - any record that has "user.tags.type"="user" and "user.tags.role"="admin" Which bloom filters are used depends on how you build the query, but they test for whether a row matching the condition(s) is in the file/row group
- EGreg 1y agoDoesnt this mean you have to do a row scan though? With BTREE you have O(log N) index query and that’s it
- dangoodmanUT 1y agoTo actually retrieve the row, yeah, but a btree index size scales ~linearly with the dataset size. You can prune based on partitions, minmax indexes, then bloom filters first. By that point the row group scan, if all other cheks suggest that the row you are after is in the block, is a very small amount of data. https://itnext.io/how-do-open-source-solutions-for-logs-work-elasticsearch-loki-and-victorialogs-9f7097ecbc2f https://itnext.io/how-do-open-source-solutions-for-logs-work... covers this very well
- SwiftyBug 1y agoDoes that mean that you can't query substrings or do fuzzy searches?
- panic 1y agoIf you want to adapt the technique to full-text search, you can index trigrams instead of full keywords.
- hztar 1y agoSuper ! Bloom filters are smart. Created a hierchial bloom filter for a revisit log for an indexer almost 20 years ago. Saved us $$$ and a still kind of proud of it
- ianred 1y agoLibrary/package with AGPL license, not a great thing even for a lot of FOSS projects.
- dangoodmanUT 1y agoNot true, its very permissive as long as it's not a "feature" of a product you're building, or offering as a service. Otherwise you can happily use it in indirect backend services (e.g. your own logging) without license concerns.
- another_twist 1y agoI have a question about using HBFs for logs - how do you determine the hierarchy ?