Extending the Load Balancing for Cadence: Load Balancing in Cadence’s Shard Distributor
Authors
Holt, Andreas Worm ; Mathiassen, Theis Randeris
Term
4. term
Education
Publication year
2026
Submitted on
2026-06-04
Pages
108
Abstract
This is a 10th-semester computer science project at AAU, conducted in collaboration with Uber. Building on our prior work, we design and test three extensions to the Cadence open-source codebase: 1) support for heterogeneous Matching executors (different types of components that perform matching), 2) swap-moves (exchanging two shards, i.e., system partitions, for better balance), and 3) cost-aware scoring (considering costs to limit disruptive shard moves). We evaluate by combining algorithm replay (replaying previous decisions) with a Kubernetes test environment driven by production traces (data from a live system). Under increasing load, latency-aware balancing (balancing that accounts for response time) completes 105% more workflows than our earlier contribution and 80% more than CPU-time–aware correction (balancing based on CPU time). When cost-aware scoring is added to latency-aware balancing, the amount of moved shard load drops by 25%, but completed workflows decrease by 7.5%. Swap-moves had only marginal impact on results with Uber’s production traces.
Dette er et 10.-semesterprojekt i datalogi ved AAU, udført i samarbejde med Uber. Med udgangspunkt i vores tidligere arbejde designer og tester vi tre udvidelser til Cadence open-source-kodebasen: 1) understøttelse af heterogene Matching-executors (forskellige typer komponenter, der udfører matching), 2) swap-moves (at bytte to shards, dvs. systempartitioner, for bedre balance), og 3) cost-aware scoring (at tage højde for omkostninger for at begrænse forstyrrende flytninger af shards). Vi evaluerer ved at kombinere algorithm replay (at genafspille tidligere beslutninger) med et Kubernetes-testmiljø baseret på produktionstraces (data fra et driftssystem). Under stigende belastning fuldfører latency-aware balancing (balancering, der tager højde for svartid) 105% flere workflows end vores tidligere bidrag og 80% flere end CPU-time aware correction (balancering baseret på CPU-tid). Når cost-aware scoring tilføjes til latency-aware balancing, reduceres den flyttede shard-load med 25%, men antallet af fuldførte workflows falder med 7,5%. Swap-moves havde kun marginal effekt på resultaterne med Ubers produktionstraces.
[This apstract has been rewritten with the help of AI based on the project's original abstract]