thanos: Deduplication returning deduped and non-deduped results in 0.31.0+

Got some time to think about this and fix it so hopefully this will get done soon.

Can confirm fix is working in our setup. Thank you @fpetkovski !

Thanks for reporting @diranged and reproducing @douglascamata, I will take a look later this week too. Sounds like we missed some edge cases, sorry for that.

To recap: dedup used to work by saving all storepb.SeriesResponse into a slice and then resorting everything so that series would be sorted by replica labels first. In 0.31.0 we added withoutReplicaLabels as per the proposal: https://thanos.io/tip/proposals-accepted/20221129-avoid-global-sort.md/. The idea was to remove replica labels before getting the response so that we could use k-way merge to merge everything in order.

However, we missed that a StoreAPI might start sending unsorted responses with this functionality. Consider the following:

a=1,b=1 a=1,b=2 a=2,b=1 a=2,b=2

If the replica label is a then the response becomes:

b=1 b=2 b=1 b=2

Because storage.SeriesSet is an iterator over a sorted series set, it means that to have lazy, in order evaluation of the iterator we’d need to buffer everything that comes between the two b=1 series in the response from a StoreAPI.

If a is an external label then the situation changes a bit. This means that the response would look like:

a=1,b=1 a=1,b=2 a=1,b=1 a=1,b=2

Since external labels always have the same value, it means that such a response is not possible and it would look something like this instead:

a=1,b=1,c=1 a=1,b=2,c=1 a=1,b=1 a=1,b=2

Deduplication on external labels makes it so that even with the removal of the external label, the response is sorted and we can use k-way merge directly.

This is the difference between deduplication on internal labels and external labels. Due to this, it seems like we would inevitably have to buffer everything to provide a general deduplication algorithm. But, we should avoid buffering as much as possible. The small ad-hoc benchmark in the original proposal shows a huge performance improvement.

Thus, my suggestion would be to:

• If deduplication works on internal labels (or internal+external labels) then we have to buffer + resort;
• If deduplication works only on external labels then everything can stay as is.

I also suggest removing this https://github.com/thanos-io/thanos/issues/6257#issuecomment-1514160495 hack because a StoreAPI must always send a sorted series set. If it doesn’t then that’s a bug in the StoreAPI implementation.

I filled https://github.com/thanos-io/thanos/issues/6563 and https://github.com/prometheus/prometheus/issues/12605 for these bugs. But these are other problems impacting deduplication since the beginning of Thanos, I think. So, let’s fix the original problem first.

@GiedriusS yesterday I could write some e2e tests that can show the bug. I’m adding one more scenario to it and will get a PR opened. 👍

I believe this comes from the stores not re-ordering the series after adding the external labels. You can replicate it by adding the metrics:

metric{}
metric{alocal="label"}

And an external label ext="label". Before the external label, metric{} < metric{alocal="label"} because it has fewer labels. However, after adding it, both sidecar and ruler returned this when I tested them:

metric{ext="label"}
metric{alocal="label", ext="label"}

and since alocal < ext, the order is incorrect. If we have two stores returning the same duplicated data, ProxyResponseHeap will yield the following:

metric{ext="label"}
metric{alocal="label", ext="label"}
metric{ext="label"}
metric{alocal="label", ext="label"}

Making dedupResponseHeap ignore the duplication. I tried to work out a solution in the ProxyResponseHeap Less function, but I think this should probably be re-sorted in the stores instead. The same incorrect order is in prometheus remote read response to the sidecar

Thus, my suggestion would be to:

If deduplication works on internal labels (or internal+external labels) then we have to buffer + resort; If deduplication works only on external labels then everything can stay as is.

Can we then adapt https://github.com/thanos-io/thanos/pull/6317 to resort in stores instead of doing it in the querier?

I think you are right, this could be one way the issue could happen. We should probably exclude external labels from the comparison because they interfere with the sorting order.

We are seeing this same issue without receive in the picture.

We’ve since rolled back but I can try and reproduce again in a dev environment next week.

We just have Prometheus + sidecar, store, and ruler. All behind the query servers.

@zhangrj do you have any replica labels that are stored in TSDB and are not external labels?