m3db
Support tagfiltertree for fast matching metricIDs to queries
This PR introduces a new data structure which we call "tagfiltertree". A query consists of several tag filters. A tag filter is nothing but a tag and value pair where the value is a pattern much like a regex. For instance, "service:foo" is a valid tag filter. A query is nothing but a list of such tag filters that need to be matched with Conjunction within an incoming metricID.
The key observation behind creating a tree structure is that the presence of a tag in a metricID and a query has the potential to drastically prune the search space of the possible queries going forward. So much so that within a couple comparisons we expect an incoming metricID to output the entire list of matched queries.
This package optimizes CPU and memory for match time as opposed to creation of the tree itself. It is not thread-safe so make sure to protect the tree appropriately if it is going to be used in a multithreaded context.
Refer to the README.md for more details.
What this PR does / why we need it: Use this data structure when you want to quickly match an input metricID to a list of queries.
Does this PR introduce a user-facing and/or backwards incompatible change?:
NONE
Does this PR require updating code package or user-facing documentation?:
NONE
