Implement the core MetaCache and MetaCacheProvider

[hiltontj]

See the proposal for the metadata cache here.

An InfluxDB instance can have many metadata caches, i.e., the MetaCache type, configured across the various databases/tables. These will be managed by a MetaCacheProvider which will provide access to the underlying caches in various parts of the system.

MetaCache

The metadata cache is a hierarchical structure with a level in the hierarchy for each column in the cache. For this, we can use a BTree, since having the columns in order is a key aspect of the metadata cache.

Individual nodes in the tree hold a value and a last seen time that is used to age entries out of the cache on eviction. For multi-level hierarchies, branch nodes also hold a nested BTree for related values in the next column. For example:

Here, the MetaCache was defined with the columns region, followed by host. The first level down from root holds values for the region column and the second for the host. If a user was to query for metadata values of host where region is equal to "us-east", then they would get the values "a" and "b".

Each cache has a maximum cardinality, and therefore needs to track the number of values it is holding. Pruning values when it exceeds this can be decoupled from insertion. There should be an API to prune a cache by removing its oldest entries.

Caches can also have a maximum age for entries, beyond which they are evicted regardless of the current cardinality of the cache. This max age is optional though.

MetaCacheProvider

There needs to be a type that holds all the metadata caches for the instance. This will provide an API for cache creation, deletion, insertion of values, and pruning.