Flamegraph stability

[kolesnikovae]

Currently, if max_nodes parameter is set, and the returned flamegraph has truncated nodes (named "other"), its structure may be unstable. The cause is the fact that flamegraphs are merged in non-deterministic order and therefore the set of truncated nodes varies. This should be fixed by ensuring that flamegraphs are sorted (e.g by request time) before the merge:

https://github.com/grafana/pyroscope/blob/8e158f44094cce241605a63e1717746080f967ed/pkg/frontend/frontend_select_merge_stacktraces.go#L60-L67

[simonswine]

I do think consistently ordering the merge will fix the stability problem, but it will be not be enough for correctness.

Essential during merge queries we have a distributed top-k problem, which we currently do not solve correctly. Once the querier reaches out to ingesters/store-gateways we are working on overlapping time slots and we just assume that the top-k from each of the instances are including everything that will be in the (correct) final top-k, that is obviously not true in all cases.

I dug myself a bit into a whole in terms of paper/library research, I do think there could be quite elegant and efficient ways to solve this, in particular this looks very promising:

https://github.com/axiomhq/topk/blob/b18ffa887c505328d3a880e94357ee4c352cd479/topk.go#L1-L17

I think this mostly goes beyond this issue description, but I thought I share my research here.

[petethepig]

@simonswine That distributed top-k problem solution you linked looks very promising. The API looks good and I think it has all functionally we need to add it to our system:

• inserting into streams
• merging streams
• encoding / decoding the state of the counter

I haven't looked much at the implementation, not sure how performant / correct it is though.