Idea: Bloom Filter - CPU usage reduction

[sfc-gh-chli]

What is the problem you are trying to solve?

Our Grafana Mimir has been suffering from high CPU usage from query path, and one solution to lower CPU usage is through CPU/Bloom filter.

Which solution do you envision (roughly)?

1. An existing well-established solution would be incorporating Bloom Filter, which is a probabilistic data structure returning instantly for non-existing timeseries data and already well implemented in Loki, Thanos, M3DB etc.

In a very similar set up TSDB Thanos (also a multi-tenant Prometheus Inside), we have incorporated Cuckoo filter (a relative to Bloom filter) just on metric names, and we can see the CPU usage instantly dropped from 50% to <20%, which is 30% reduction through this simple feature, see this PR for refence for implementation.

I have also extensively worked with M3DB, which has a more robust bloom filter bitset of all series contained in this fileset for quick knowledge of whether to attempt retrieving a series for this fileset volume. Working with M3DB makes us never have a problem with CPU usage.

2. A second approach, orthogonal to the Bloom filter would be separation of Storage and Query Engine, Right now ingester is handling both write and read traffic, which makes it super heavy and critical. A solution to separate write and read path would be so much helpful not only for resource usage management, but also for better isolation and less chance of failures on both read an write path.

Have you considered any alternatives?

No response

Any additional context to share?

No response

How long do you think this would take to be developed?

Small (<= 1 month dev)

What are the documentation dependencies?

No response

Proposer?

No response

[bboreham]

Hello, and thanks for your interest in the Mimir project.
To diagnose the source of high CPU usage, it would be helpful to supply CPU profile(s) and details on what operations were being run at the time.

Regarding Bloom filters:
At present, we distribute series to all ingesters by hashing all label values for the timeseries, therefore we expect any metric name to exist on every ingester. Under that condition, a Bloom filter would have limited value.

Maybe your suggestion stems from some different circumstance, or different set of assumptions?
If so, please explain.

Bloom filters were added to Loki for "needle in a haystack" queries, where we expect most blocks do not contain the string being sought. This is the opposite expectation to Mimir. I can't speak for why Thanos and M3DB found it useful.

It would be interesting to investigate different distribution schemes for Mimir, which do not have this property. But even then, we know how we distributed the series; it should not be necessary to build a new data structure which learns the same information.