Replica based load balancing in multitenant databases
View Patent ↗A swap-based multitenant database load balancing (SWAT) invention finds an optimal swap set that eliminates hotspots, and finds a sequencing and parallelization of swap executions for the multitenant database.
1. A load balancing method for multi-tenant database system, load balancing method comprising:
a. generating a replica swap operator to achieve a load transfer with minimal service interruption;
b. determining an optimal set of swap operators that minimizes a total cost; and
c. sequencing swap operators to minimize or avoid temporary overloads; wherein the sequencing includes swap operators SW i , 1≦i≦N sw and servers S sink involved in SW i , 1≦i≦Ns and outputs a swap sequence for j←1 to N s where if Si has no outgoing edge swap then S j is added to the set S sink , and while S sink ≈0 an incoming edge swap SW i is picked and appended to the swap sequence, SW i is removed from its destination server Sj and the source server S j2 , if S j has no incoming edge it is removed from Ssink and if S j2 has no outgoing edge, it is added to S sink .
2. The method of claim 1 , wherein the determining the optimal set of swap operators comprises defining a cost of a swap operator based on write workload service interruption.
3. The method of claim 1 , wherein the determining the optimal set of swap operators comprises formulating the optimal swap set as an integer linear programming (ILP) problem.
4. The method of claim 3 , comprising formulating and solving a proactive load balancing problem.
5. The method of claim 3 , comprising formulating and solving an ideal load fitting problem.
6. The method of claim 3 , comprising formulating and solving a best-effort load fitting problem.
7. The method of claim 1 , wherein the sequencing comprises formulating a traversal on a swap-server graph.
8. The method of claim 7 , comprising generating a swap sequence that creates no temporary hotspots if there is no cycle in the swap server graph.
9. The method of claim 7 , comprising detecting and breaking cycles in the swap-server graph to minimize a temporary hotspot.
10. The method of claim 1 , comprising eliminating hotspots by finding a set of swaps that resolve the hotspots given a threshold, while minimizing a sum of secondary replicas' workload for swapped tenants.