jaeger-ui
jaeger-ui copied to clipboard
jaegertracing
[Bug]: Critical path is taxing on CPU when expanding span tags
What happened?
We upgraded from v1.46 to v1.54 and some users noticed slowness when expanding tags. With some CPU tracing I was able to pinpoint #1871 as the culprit.
Steps to reproduce
- Run Jaeger v1.54
- Load a large trace
- Try expanding/collapsing spans
- Observe slowness
Expected behavior
Everything is snappy as it was.
Relevant log output
No response
Screenshot
Additional context
No response
Jaeger backend version
v1.54
SDK
No response
Pipeline
No response
Stogage backend
No response
Operating system
No response
Deployment model
No response
Deployment configs
No response
This is happening because mergeChildrenCritialPath has a recursive function findAllDescendants that keeps calling descendents (children) of the span. In the wort case, each span could be checked once and hence the time complexity here is already O(n^2). And then filtering and merging adds some extra time.
We could simplify this by using a map, that stores the spans. This will take O(n) to create, but once created search operations would be processed in constant time. Now, using a stack we can push all the spans into the stack. If they have a child, they are pushed as well. In O(n) time we can evaluate the stack, and an O(m) time to filter and merge. Makes the time complexity better than the previous approach.
I can give a detailed explanation in the PR, if this idea sounds good and I can proceed.
cc: @yurishkuro
@BenzeneAlcohol pre-building a map makes total sense. However, you may notice that we already build a tree when loading a trace (packages/jaeger-ui/src/selectors/trace.tsx). I would really like to have a way where that tree is not thrown away but reused for critical path and any other visitors. I think we keep rebuilding this tree multiple times for every trace.
Yeah, I looked into it. I'll come up with an algo later today or tomorrow and post it here.