Weighted auto-sharding
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
8 Citations
18 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
-
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.
-
Specification