Conquering Load Balancing: Experiences from ScyllaDB Drivers

Load balancing seems simple on the surface, with algorithms like round-robin, but the real world loves throwing curveballs. Join me in this session as we delve into the intricacies of load balancing within ScyllaDB Drivers. Discover firsthand experiences from our journey in driver development, where we employed the Power of Two Choices algorithm, optimized the implementation of load balancing in Rust Driver, mitigated cloud costs through zone-aware load balancing and combated the issue of overloading a particular core of ScyllaDB. Be prepared to delve into the practical and theoretical aspects of load balancing, gaining valuable insights along the way.

1. Conquering Load Balancing: Experiences from ScyllaDB Drivers Piotr Grabowski Software Team Leader at ScyllaDB

2. Piotr Grabowski he / him Software Team Leader at ScyllaDB Software Team Leader at ScyllaDB responsible for all ScyllaDB drivers, ScyllaDB Kafka Connectors (ScyllaDB Sink Connector and ScyllaDB CDC Source Connector) Joined ScyllaDB 3 years ago

3. Load balancing in ScyllaDB

4. Load balancing in ScyllaDB SELECT * FROM table WHERE partition_key = “R1250GS” hash(“R1250GS”) = replica nodes

5. Naïve load balancing policy SELECT * FROM table WHERE partition_key = “R1250GS”

6. Naïve load balancing policy SELECT * FROM table WHERE partition_key = “R1250GS”

7. Round-robin policy A very basic load balancing policy algorithm Maintain a incrementing counter N When sending a query: S end it to replica number N Increment counter (modulo number of replicas) The load will be equally distributed between the nodes

8. Random choice policy A very basic load balancing policy algorithm When sending a query: Send the query to a random replica

9. Problems!

10. Slow node SELECT * FROM table WHERE partition_key = “R1250GS” Slow node F aulty network T emporary overload

11. Slow node SELECT * FROM table WHERE partition_key = “R1250GS” Slow node F aulty network T emporary overload + 10 ms latency

12. Slow core SELECT * FROM table WHERE partition_key = “R1250GS”

13. Inflight requests per node+shard Inflight requests

14. Inflight requests per node+shard Inflight requests

15. Slow core (synthetic scenario) 5 node i3.4xlarge Scylla cluster P urposefully severely overloaded a single core on one of the nodes That’s only 1/80 of the cluster! The results were staggering!

16. Slow core (synthetic scenario)

17. Slow core (synthetic scenario)

18. Slow core (synthetic scenario)

19. Least Inflight load balancing? One potential solution to that problem Instead of choosing any of the replicas, send the request to the least loaded one (as measured by number of inflight requests) Works well for a single client, but is susceptible to overloading a node in case of many clients

20. Power of Two Choices load balancing A simple algorithm that aims to ignore the slowest replica while avoid the problem of many clients overloading the same node When selecting the replica: Randomize 2 replicas Select the replica with a fewer number of inflight requests

21. Sending requests to a wrong shard A counterintuitive approach to dealing with an overloaded shard If you send the request to the wrong shard: Initial processing of the request happens on the wrong shard The wrong shard moves the processing to the correct shard The correct shard didn’t have to do the initial processing, reducing its load!

22. Sending requests to a wrong shard

23. Zone awareness in the Cloud

24. Zone awareness in the Cloud

25. Zone awareness in the Cloud

26. Zone awareness in the Cloud Instead of sending the request to any replica, prefer the replica in the local AZ Potential issues: A common setup is to use Replication Factor equal to 3 If the cluster is deployed in 3 AZs, there will be only a single replica in each of the AZs This severely limits the choices a load balancing algorithm has A problem with many solutions - a tradeoff between latencies and cost

27. Optimizing load balancing in ScyllaDB Rust Driver Benchmarks of ScyllaDB Rust Driver have shown that load balancing computation is a significant part of sending a query Main goal: reduce number of allocations and atomic operations while building the query plan, especially on the happy path: Plan function was split to pick() and fallback() methods. This allowed to better optimize the most common case, where only one node from the load balancing plan is needed Precomputation of replica sets: A struct introduced that precomputes replica lists of a given strategies, and provides O(1) access to desired replica slices

28. Optimizing load balancing in ScyllaDB Rust Driver Inserts: ---------- allocs/req: 15.00 reallocs/req: 8.00 frees/req: 15.00 bytes allocated/req: 2458.05 bytes reallocated/req: 269.06 bytes freed/req: 2456.80 (allocated - freed)/req: 1.25 Inserts: ---------- allocs/req: 6.01 reallocs/req: 6.00 frees/req: 6.00 bytes allocated/req: 381.80 bytes reallocated/req: 173.05 bytes freed/req: 380.62 (allocated - freed)/req: 1.18 Before After

29. Optimizing load balancing in ScyllaDB Rust Driver Inserts: ---------- allocs/req: 15.00 reallocs/req: 8.00 frees/req: 15.00 bytes allocated/req: 2458.05 bytes reallocated/req: 269.06 bytes freed/req: 2456.80 (allocated - freed)/req: 1.25 Inserts: ---------- allocs/req: 6.01 reallocs/req: 6.00 frees/req: 6.00 bytes allocated/req: 381.80 bytes reallocated/req: 173.05 bytes freed/req: 380.62 (allocated - freed)/req: 1.18 Before After 9 fewer allocations (-60%)

30. Optimizing load balancing in ScyllaDB Rust Driver Inserts: ---------- allocs/req: 15.00 reallocs/req: 8.00 frees/req: 15.00 bytes allocated/req: 2458.05 bytes reallocated/req: 269.06 bytes freed/req: 2456.80 (allocated - freed)/req: 1.25 Inserts: ---------- allocs/req: 6.01 reallocs/req: 6.00 frees/req: 6.00 bytes allocated/req: 381.80 bytes reallocated/req: 173.05 bytes freed/req: 380.62 (allocated - freed)/req: 1.18 Before After 84% fewer bytes allocated

31. Piotr Grabowski [email protected] Thank you! Let’s connect.