What's wrong?

It's possible to trigger a case where the prometheus WAL contains multiple RefIDs for the same series. When this happens the WAL can only GC one of the series leaving all the rest in memory forever. This happens because of the disconnect between segment checkpointing and series gc'ing.

The problem,

• The WAL assumes a RefID is unique across the WAL
• When a series is deleted via the GC process the most recent WAL segment is tracked with the SeriesID to ensure we don't delete a series that still exists on the WAL.
• We use this map as an input to a keep function for checkpointing, when the series exists in the deleted map with a segment that's newer than the one we are checkpointing we will keep it

This growth is rather slow but in our case we have accumulated tens of millions of active series that cannot be gc'ed from the WAL active series.

Steps to reproduce

1. Truncate the WAL GC'ing a series (RefID1) but making sure it stays in the checkpoint
2. Recreate the series in the WAL (RefID2)
3. Before RefID1 is removed from the checkpoint alloy is restarted (this can take multiple rounds of checkpointing over many hours so very liable to happen)
4. On startup alloy will now have RefID1 and RefID2 as active series breaking the "RefIDs must be unique rule" (RefID1 still exists in the checkpoint and RefID 2 exists in the segments so both are loaded)
5. RefID1 cannot be GC'ed because GC'ing goes based on hash and a hash can only point to a singular RefID which in this case will be RefID2
6. If RefID2 is GC'ed fully, a restart of alloy can allow RefID1 to be freed but we are more than likely to see this repeat over and over slowly accumulating active series

Test which shows it in action: 01f6937

Visual representation of the issue

Consider a series foo with label bar which received a few samples stored in the WAL at 10:15, then stopped. The samples for foo are in WAL segment C with 1 currently active series. Series in memory contains SeriesRef 10 and hashes contains the label hash of bar mapped to SeriesRef 10.

           10:00        12:00
Segments   A- B- C- D- E-- F- G-


Series in Memory
SeriesRefs: 10
Hashes: bar->10
Active Series: 1

At approx 13:00, WAL Truncation happens.

Series foo is garbage-collected and is no longer stored in memory. The wal notes in its 'deleted' map that SeriesRef 10 might be needed until segment G has been dropped.

A checkpoint is created from the first two thirds of the segments, A-D. This checkpoint has no samples, since any samples before 12:00 are excluded. WAL segments A-D are removed from disk. Since WAL segment G is not dropped, series foo is written to the checkpoint with SeriesRef 10.

           10:00        12:00
Segments                  E-- F- G-     
Checkpoint   ┌────────────┐
             └────────────┘
SeriesRefs: 10


Series in Memory
SeriesRefs: 
Hashes: 
Active Series: 0

Series foo received a few more samples with label bar stored in the WAL at 12:15, then stopped. The samples for series foo are in WAL segment F with 1 currently active series. Series in memory contains SeriesRef 11 and hashes contains the label hash of bar mapped to SeriesRef 11.

           10:00        12:00
Segments                  E-- F- G-     
Checkpoint   ┌────────────┐
             └────────────┘
SeriesRefs: 10


Series in Memory
SeriesRefs: 11
Hashes: bar->11
Active Series: 1

A restart occurs before the truncation can run (the time this occurs is not important for the timeline). Upon restart, series foo is loaded from the checkpoint with SeriesRef 10 and then from Segment G with SeriesRef 11. Since their labels are the same they will have the same hash, both series will be considered to be active, since a unique set of labels can only point to to 1 SeriesRef Hashes will only contain the label hash of bar mapped to SeriesRef 11.

           10:00        12:00
Segments                  E-- F- G-     
Checkpoint   ┌────────────┐
             └────────────┘
SeriesRefs: 10


Series in Memory
SeriesRefs: 10,11
Hashes: bar->11
Active Series: 2

Before the truncation happens, the built up WAL looks like this:

           10:00        12:00        14:00
Segments                  E-- F- G- H I- J-- K-
Checkpoint   ┌────────────┐
             └────────────┘
SeriesRefs: 10


Series in Memory
SeriesRefs: 10,11
Hashes: bar->11
Active Series: 2

At approx 15:00, truncation happens again.

Series foo represented by SeriesRef 11 is garbage-collected and is no longer stored in memory. The wal notes in its 'deleted' map that SeriesRef 11 might be needed until WAL segment I has been dropped. Series foo represented by SeriesRef 10 is retained in memory because garbage-collection works through hashes and the hash for SeriesRef 10 points to SeriesRef 11.

Since WAL segment I is not dropped, series foo represented by SeriesRef 11 is kept in the checkpoint. The SeriesRef 10 representation of foo also qualifies to keep because it can be found in the in memory series by id 10.

           10:00        12:00        14:00
Segments                             I- J- K-
Checkpoint ┌────────────┬────────────┐
           └────────────┴────────────┘
SeriesRefs 10,11


Series in Memory
SeriesRefs: 10
Hashes: 
Active Series: 1

SeriesRef 10 can never be freed by the current process. It can only ever be freed if SeriesRef 11 is dropped from the checkpoint and the process is restarted. This can lead to a lot of inactive series being retained in memory over a long enough period of time.