MemPostings is a performance bottleneck for some scenarios

What did you do?

As noted a while ago on #13642 MemPostings, which implements the index for in-memory series, can be a performance bottleneck because it's simply a very large Go map with a single mutex.
This single mutex serialises all writes to that map and so there's a limit to the speed at which we can insert new series into the map.
Since the index is used for all reads (queries) and writes (scrapes) the performance here is pretty important. This is further complicated by the requirement that the list of series IDs must be always returned as sorted, so it's sorted on write.
It is usually is fast enough, mostly because by nature of metrics the vast majority of operations are read, not write, but there are cases where it is super slow - this is mostly when we need to quickly append a huge number of series to the index. This is when:

• We replay the WAL on startup - we need to write IDs of all series in the WAL
• A new scrape job is added with tons of series, or existing job adds tons of new series - we need to append IDs of new series
• We start with no WAL - after first scrape of each target we will need to append IDs of all scraped series

The most common scenario is probably replaying the WAL and this is why WAL replay disables sorting on append, instead it sorts everything once replay is done. While WAL is replayed nobody can query the index so that' fine. WAL replay also hides a lot of issues with performance of the index - if it's slow replay takes longer but there's no impact on queries or scrapes (because they cannot happen at this point).

But for less common scenarios that result in a big batch of writes the performance is pretty poor. The easiest way to reproduce it is to take a Prometheus instance that scrape a large pool of targets and scrapes ~30M time series, stop it, remove all WAL files and start it. You will see that it takes 30-60M for such instance to full write all series from initial scrapes and stabilise append rate. During that time any alerting rules might fire with false positives because the data in the index is incomplete until all series are written.

#13642 tried to improve this via sharding, but it was pointed out that sharding would break atomicity of writes of a labels set, since different labels would end up on different shard, so there could be races when we query data back.

Would be great if MemPostings performance was improved but given the requirements of:

• Returned data must be sorted
• Atomicity of writes must be preserved

it's hard to solve this easily. Especially that there might be other requirements.
For example: we could buffer writes via a channel and a background goroutine that does the actual write, but would that be ok?

What did you expect to see?

No response

What did you see instead? Under which circumstances?

Prometheus started with no WAL files is very slow for the first N minutes

System information

No response

Prometheus version

Prometheus configuration file

Alertmanager version

Alertmanager configuration file

Logs

Start by reading MemPostings and the WAL replay path described in the issue, focusing on the single-mutex map, sorted returns, and atomic writes. Reproduce the slow startup scenario with a large series set and no WAL files. Done means improving bulk-write performance without breaking sorted results or write atomicity.