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.
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.
7 Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A 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.
-
-
19. 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.
-
Specification