Improve performance of Ring.shuffleShard()#281
Conversation
| } | ||
|
|
||
| if !haveSeenGroupWithRemainingToken { | ||
| return merged |
There was a problem hiding this comment.
Note to reviewers: this should never happen, but I couldn't think of a nicer way to handle this - open to suggestions.
charleskorn
force-pushed
the
charleskorn/improve-shuffleshard-performance
branch
from
39c479a to
60e2e2a
Compare
This reduces CPU time for the shuffle sharding benchmarks by ~15%.
This saves ~5-7% of CPU time compared to using a loser tree for three groups.
pracucci
left a comment
pracucci
left a comment
There was a problem hiding this comment.
I'm assuming the loser tree implementation is correct, given it's getting copied from Loki and I also assume the fuzz test has been run manually given it doesn't run in CI. Based on these assumptions, I've checked the rest of the code and LGTM (modulo a couple of nits).
I have modified it slightly to not use an interface, but the tests exercise the same test cases, so I believe this hasn't broken anything.
Yep. |
This brings in grafana/dskit#280 and grafana/dskit#281.
* Upgrade to latest dskit version. This brings in grafana/dskit#280 and grafana/dskit#281. * Add changelog entry.
Upgrades to a newer version (v1.53.0) of google.golang.org/grpc that includes breaking changes to the resolver.Target type (see Cleanup usages of resolver.Target.Endpoint grpc/grpc-go#5796) Upgrade from v2.4.0 to v.4.0.0 of https://github.com/sercand/kuberesolver which is compatible to grpc to v1.53.0.
2 participants
What this PR does:
This PR improves the performance of
Ring.shuffleShard(), and specifically the evaluation of the list of all tokens in the shard. It also introduces a new benchmark for shuffle sharding,BenchmarkRing_ShuffleShard_LargeShardSize, which better mirrors the worst-case parameters we see in production Mimir cells.There are two main optimisations:
The loser tree implementation is based on @bboreham's implementation in Loki, which we are relicensing as part of this PR. I've modified it to work on slices directly, rather than
Sequenceinterfaces, as this improved overall shuffle shard computation performance by ~15%, and incorporated the fix in grafana/loki#9057.Benchmark results:
Which issue(s) this PR fixes:
(none)
Checklist
CHANGELOG.mdupdated - the order of entries should be[CHANGE],[FEATURE],[ENHANCEMENT],[BUGFIX]