Weighted auto-sharding

• US 10,530,844 B2
• Filed: 02/09/2017
• Issued: 01/07/2020
• Est. Priority Date: 06/03/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Shraer, Alexander, Lev-Ari, Kfir, Merchant, Arif Abdulhusein, Khemani, Vishesh, Adya, Atul
• Primary Examiner(s): Bates, Kevin T
• Assistant Examiner(s): McCray, Clarence D
• Application Number:
  US15/428,844
• Publication Number:
  US 20170353536A1
• Time in Patent Office: 1,062 Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/148 Migration or transfer of sessions

Abstract

Methods, systems, and apparatus for automatic sharding and load balancing in a distributed data processing system. In one aspect, a method includes determining workload distribution for an application across worker computers and in response to determining a load balancing operation is required: selecting a first worker computer having a highest load measure relative to respective load measure of the other work computers; determining one or more move operations for a partition of data assigned to the first worker computer and a weight for each move operation; and selecting the move operation with a highest weight the selected move operation.

Claims

1. A system, comprising:

a data processing apparatus that includes one or more processors; and

a non-transitory computer readable medium in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that when executed cause the data processing apparatus to perform operations comprising;

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

wherein the weight for each move is based on a benefit determined for the move and a cost determined for the move.

2. The system of claim 1, wherein determining one or more move operations for the partition, and, for each move operation, a weight based on benefits and costs determined for the move comprises, for each of the one or more partitions:

determining a migration move that migrates the partition from the first worker computer to a second worker computer;

if the partition is not replicated on the second worker computer, determining a replication move that replicates the partition on the second worker computer; and

if the partition is replicated on another worker computer, determining a de-replication move that eliminates the partition on the first worker computer.

3. The system of claim 2, wherein determining the migration move comprises selecting a worker computer having a lowest load measure relative to respective load measure of the other work computers.

4. The system of claim 1, wherein determining, for each move operation, the weight based on benefits and costs of the determined for the move operation comprises:

determining a benefit that is proportional to a reduction in load measure in the worker computer that will result from the move operation;

determining a cost that is proportional to an amount of key values that will be reassigned from the move operation; and

determining the weight based on a ratio of the benefit to the cost.

5. A system, comprising:

a data processing apparatus that includes one or more processors; and

a non-transitory computer readable medium in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that when executed cause the data processing apparatus to perform operations comprising;

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

wherein determining whether the load balancing operation is require based on the workload distribution comprises;

determining that at least one worker computer has a load measure that meets a maximum load measure threshold.

6. A system, comprising:

a data processing apparatus that includes one or more processors; and

a non-transitory computer readable medium in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that when executed cause the data processing apparatus to perform operations comprising;

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

the operations further comprising, for each worker computer;

determining, for each partition of the worker computer, a constituent load measure for the partition;

determining pairs of adjacent partitions, where each pair is two partitions that collectively have a contiguous range of key values; and

for each pair of adjacent partitions for which a sum of the constituent load measures of the partition does not meet load measure merger threshold, merging the adjacent partitions into a single partition.

7. The system of claim 6, wherein merging the adjacent partitions into a single partition occurs prior to an iteration to determine the workload distribution for the application job.

8. The system of claim 6, wherein:

determining pairs of adjacent partitions includes determining one or more pairs of adjacent partitions that includes a first partition on a first worker computer and a second partition on a second worker computer; and

merging the adjacent partitions into a single partition includes merging the adjacent partitions that includes the first partition on the first worker computer and the second partition on the second worker computer into the single partition onto the worker computer of the first and second worker computer that has a lowest load measure.

9. The system of claim 6, wherein the load measure merger threshold is an average of constituent load measures of all partitions.

10. The system of claim 6, wherein merging the adjacent partitions into a single partition comprises merging the partition into a single partition only if the merger will not result in a number of partitions on the worker computer being less than a minimum partition threshold that is greater than unity.

11. A system, comprising:

a data processing apparatus that includes one or more processors; and

a non-transitory computer readable medium in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that when executed cause the data processing apparatus to perform operations comprising;

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

the operations further comprising, for each worker computer;

determining, for each partition of the worker computer, a constituent load measure for the partition;

determining, for each partition, whether the constituent load measure exceeds a load measure split threshold; and

for each partition for which the constituent load measure exceeds the load measure split threshold, splitting the partition into two separate partitions.

12. The system of claim 11, wherein splitting the partition occurs after implementing the selected move operation.

13. The system of claim 11, wherein the load measure split threshold is a double of an average of constituent load measures of all partitions.

14. The system of claim 11, wherein splitting the partition occurs only if the splitting will not result in a number of partitions on the worker computer being greater than a maximum partition threshold.

15. The system of claim 11, determining one or more move operations for one or more partitions assigned to the first worker computer comprises determining the one or more move operations for only the partition with the highest constituent load measure.

16. A system, comprising:

a data processing apparatus that includes one or more processors; and

a non-transitory computer readable medium in data communication with the data processing apparatus and storing instructions executable by the data processing apparatus and that when executed cause the data processing apparatus to perform operations comprising;

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

wherein implementing the selected move operation on the partition for which the move operation with the highest weight was determined comprises implementing the selected move operation only if a determined benefit for the move meets a minimum benefit threshold.

17. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

wherein the weight for each move is based on a benefit determined for the move and a cost determined for the move.

18. A computer implemented method, comprising:

partitioning a data set for an application job into a plurality of partitions according to values of a key, wherein the key is an atomic unit of work placement;

assigning, to each worker computer in a set of worker computers, partitions of the data set to the worker computer, wherein each worker computer receives a different set of partitions of the data set;

iteratively determining workload distribution for the application job across the worker computers and determining whether a load balancing operation is require based on the workload distribution;

in response to determining a load balancing operation is required;

selecting a first worker computer having a highest load measure relative to a respective load measure of at least one other worker computer;

for one or more partitions assigned to the first worker computer, determining one or more move operations for the partition, and, for each move operation, a weight for the move operation; and

selecting the move operation with a highest weight relative to the weights of each of the other move operations and implementing the selected move operation on the partition for which the move operation with the highest weight was determined;

wherein the weight for each move is based on a benefit determined for the move and a cost determined for the move.