Shift from a per-tenant to a per-querier in-memory index cache in the blocks storage

[pracucci]

In the blocks storage implementation, we currently instance a new Thanos in-memory index cache for each tenant:
https://github.com/cortexproject/cortex/blob/master/pkg/querier/block_store.go#L355-L358

This causes the in-memory index cache max size to be unpredictable, given each tenant index cache has a max size, but the number of tenants may grow over the time.

We should shift from a per-tenant to a per-querier in-memory index cache. The only downside is that we do loose the strong guarantee that caches are isolated by tenant, because the cache key is based on the block ID and, theoretically, we may have two tenants with a clashing block ID. For this reason, we should:

1. Investigate how the block ID generation entropy works, to better understand how likely is we get clashing IDs (two blocks with a clashing ID must be generated the same exact nanosecond and have the same random generated value, so we should verify how the entropy is implemented)
2. If it's unrealistic having clashing IDs, we should go on with a single instance of the in-memory index cache, otherwise we should open an issue in Thanos and investigate the feasibility to add multi-tenancy support to the index cache

[pstibrany]

1. Investigate how the block ID generation entropy works, to better understand how likely is we get clashing IDs (two blocks with a clashing ID must be generated the same exact nanosecond and have the same random generated value, so we should verify how the entropy is implemented)

From what I can see in Promethus/Thanos source code, it's usually this:

	entropy := rand.New(rand.NewSource(time.Now().UnixNano()))
	uid = ulid.MustNew(ulid.Now(), entropy)

Not very safe at all.

[pracucci]

So, the block ID is composed by two components: timestamp and a random value. The seed for the random value is based on the timestamp, so it looks the value of the entropy is pretty low being always the same for the same timestamp.

@codesome Are you aware of this? May we improve the entropy seed in TSDB, to actually have a different block ID if 2 blocks are compacted at the same nanosecond (by different processes, which could theoretically happen in the case of Cortex/Thanos)? /cc @bwplotka

[pstibrany]

It would be best if we could pass our own reader with random values. While doing that, it would be great to fix the naming, as this is not "entropy" – it's just object returning random values – "entropy" means something completely different.

[pracucci]

So, the plan could be:

1. Proposed a change to TSDB to pass entropy reader used to generate new block IDs (ULID)
2. Once 1 is done, update the vendored Prometheus and update Cortex to:
   a. Pass a custom entropy source
   b. Have a single per-querier instance of the in-memory cache

@pstibrany @codesome Makes sense to you?

[bwplotka]

I was working with Prometheus like 4 years already and never seen clashing ID. I think what you are spending time on here is highly unlikely to happen.

May we improve the entropy seed in TSDB, to actually have a different block ID if 2 blocks are compacted at the same nanosecond

Still, it depends on time AND random value based on seed generated on the ~start time of the process. This means 1.21e+24 unique ULIDs per millisecond as per: https://github.com/ulid/spec

And again, what does Cortex do special for this to become a problem? In Thanos, we saw deployments that generate like 1k blocks / 2h (~500 Prometheus-es + sidecars + compactors). And even block cutting is in the same second/millisecond across processes, so if that would be possible, we would hit that already. So yea, I don't see the value (: But sure, we can. @codesome @pracucci @brancz

[pstibrany]

Still, it depends on time AND random value based on seed generated on the ~start time of the process.

I don't see this in the code. When two ULIDs are created in the same nanosecond, they will have same value, regardless of process start time. Calling time.Now() twice adds some jitter to the process.

You're right that the chance of collisions happening is miniscule. I'd still prefer to see Reader from crypto/rand package to be used as a source of randomness though. Better safe than sorry :)

(I don't think we need configurable randomness source, if this reader is used everywhere.).

[bwplotka]

You are right @pstibrany I somehow thought we used global rand. Let's improve it on Prometheus side.

[pracucci]

Change ULID entropy generator in Prometheus:
prometheus/prometheus#6867