internal/tsdb/filter: add support for exact match filtering (without using Regexp)

[sebastianco]

Often times one knows the exact metric names or tag values which need to be accepted or blocked. In these cases is more efficient to not use regular expressions but just to lookup the metric name and the tag values of the evaluated point in a map of preconfigured values.

Here is an example of a configuration I've been already using (I named the filter OneOf however I am not 100% pleased with this name):

"Filter": [
    {
     "OneOf": {
       "Metrics": ["metricA", "metricB"],
       "Tags": { "cluster": ["x", "y", "z"], "anotherTag": ["value1", "value2"] }
     },
     "Block": true
    }
 ]

[masiulaniec]

I'm worried about making the language needlessly complex. I'm also skeptical that adding explicit map lookup hints into the language will yield amazing performance wins. Have you measured? What you're describing seems to me like exactly the kind of optimization that regex engines should already be implementing internally.

If an optimization of this kind had to go in, I would start by exploring the "ruleset optimizer" approach. In this approach, you keep the filtering language intact, and instead make the ruleset engine more clever by having it statically analyze the provided ruleset and replace certain patterns by efficient operations.

For example, it wouldn't be hard for a computer to spot this pattern:

...
{"Match": ["^foo$"]},
{"Match": ["^bar$"]},
{"Match": ["^baz$"]},
...

This run of Match rules can be replaced with a single map[string]bool lookup. The hardest aspect of this is determining if a given regexp pattern matches a unique string. Fortunately, this is already solved. Package regexp provides the required primitive in the form of (*Regexp).LiteralPrefix method.

In summary, prioritize solutions that don't require language additions. Treat the language like jvm bytecode: it is low-level and doesn't need to contain all possible operations so long as it can enable them in one form or another.

[sebastianco]

Thanks for feedback Jacek, I agree with you about the overall strategy of adding features.

At the moment I don't have solid proof for the performance gains, I will run some explicit tests. All I know is that before using it I remember we were seeing queue filling up at the publisher (worth mentioning that back then we were also running collect-site inside the aggregator).

I should also mention that now with one rule we filter out about 80% of the 100K (points / s) metrics stream. We are running it in production for more than a year and the configuration whitelists 60+ clusters. This new type of rule improves a bit the readability and maintainability of the configuration file (I am not using the controller to configure it so I believe keeping the local JSON configuration clean is also important). Imagine how it looks considering that "cluster" property has 60+ values:

...
"OneOf": { "Tags": { "cluster": ["one.live", "two.live", ..., "sixty.live"]} },
...

Once I have some performance measures I will explore more how we could use the current rules language to express the same configuration in a readable format and backed by an efficient implementation :)

[sebastianco]

I did a few low level benchmarks for comparing Regexp's FindSubmatchIndex with a lookp in a map[string]bool.

With a long regexp like "^(cluster1|cluster2|...|cluster60)$"

When the input was matched I got:

BenchmarkFindSubmatchIndex    500000     3005 ns/op       32 B/op     1 allocs/op
BenchmarkMapLookup          50000000       25.2 ns/op      0 B/op     0 allocs/op

When the input didn't match:

BenchmarkFindSubmatchIndex   500000        2825 ns/op       0 B/op      0 allocs/op
BenchmarkMapLookup         50000000       31.1 ns/op        0 B/op      0 allocs/op

If I use a shorter regexp e.g "^(cluster1|cluster2)$"

Input matched:

BenchmarkFindSubmatchIndex     5000000     406 ns/op       32 B/op        1 allocs/op
BenchmarkMapLookup           100000000     18.5 ns/op         0 B/op        0 allocs/op

Input didn't match:

BenchmarkFindSubmatchIndex     5000000      276 ns/op       0 B/op       0 allocs/op
BenchmarkMapLookup           100000000       15.9 ns/op       0 B/op     0 allocs/op