Open andrii-korotkov-verkada opened 5 days ago
I'll try to implement this.
isParentOf
can't be directly used to construct a graph, since it'd result in quadratic time complexity. It does some backfill, not just UID-based check https://github.com/argoproj/gitops-engine/blob/master/pkg/cache/resource.go#L36-L52, so we need to have some map of nodes based on UID and based on kind + api version + name.
Here's a gitops-engine
PR https://github.com/argoproj/gitops-engine/pull/601. It's going to be the main PR with nearly all the logic, argo-cd
PR would just call a new API.
Looks really good on live cluster. ~300ms instead of ~4m to get process managed resources for the same application!
Summary
getResourceTree
has a loop through each of managed resources, callingIterateHierarchy
on state cache to go over children, which ends up callingIterateHierarchy
ingitops-engine
, which has a loop over resources in a namespace (https://github.com/argoproj/gitops-engine/blob/master/pkg/cache/cluster.go#L973), which callsiterateChildren
which has a similar loop (https://github.com/argoproj/gitops-engine/blob/master/pkg/cache/resource.go#L89). This is presumably since we only keep one-way track of child -> parent relationship, while effective traversal requires the opposite. Overall, this can result in a quadratic execution time ofO(tree_size * namespace_resources_count)
. If we pre-construct the graph with parent -> child edges, this can be reduced to linearO(namespace_resources_count)
.Motivation
getResourceTree
seems to be the slowest part of reconciliation for large apps, e.g. see timing data from a build with https://github.com/argoproj/argo-cd/pull/18926:Proposal
Pre-construct a graph from namespace resources parent -> child and do a linear dfs from each of managed resources, avoiding visiting same vertex twice.
gitops-engine
changes may not even be needed, but may be good to have anyways. Overall, this would reduce the time complexity from quadratic to linear.A sub-optimal fix can be to configure some resource groups and kinds as not having any children, so hierarchy iteration can be skipped for them.