Weighted auto-sharding
AssigneeGoogle Inc.
InventorsAlexander Shraer, Kfir Lev-Ari, Arif Abdulhusein Merchant, Vishesh Khemani, Atul Adya
Life of this patent
Estimating the term…
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.
Claims20
A computer-implemented method executed by data processing hardware that causes the data processing hardware to perform operations comprising:
- partitioning a data set for an application job into a plurality of partitions based on a key;
- assigning, to each worker computer in a set of worker computers, one or more partitions of the plurality of partitions;
- receiving, from each respective worker computer in the set of worker computers, a respective load measure indicating a computational load of the respective worker computer;
- selecting, based on the respective load measure of each respective worker computer, a first worker computer in the set of worker computers for a replication operation for replicating at least one partition from the first worker computer to a second worker computer in the set of worker computers;
- replicating, the at least one partition from the first worker computer to the second worker computer;
- after replicating the at least one partition from the first worker computer to the second worker computer, distributing requests for a workload associated with the at least one partition between the first worker computer and the second worker computer such that the first worker computer and the second worker computer share the workload for the at least one partition;
- and
- in response to distributing the requests for the workload associated with the at least one partition between the first worker computer and the second worker computer, de-replicating the at least one partition from the second worker computer by deleting the at least one partition from the second worker computer.
A system comprising:
- data processing hardware;
- and
- memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
- partitioning a data set for an application job into a plurality of partitions based on a key;
- assigning, to each worker computer in a set of worker computers, one or more partitions of the plurality of partitions;
- receiving, from each respective worker computer in the set of worker computers, a respective load measure indicating a computational load of the respective worker computer;
- selecting, based on the respective load measure of each respective worker computer, a first worker computer in the set of worker computers for a replication operation for replicating at least one partition from the first worker computer to a second worker computer in the set of worker computers;
- replicating, the at least one partition from the first worker computer to the second worker computer;
- after replicating the at least one partition from the first worker computer to the second worker computer, distributing requests for a workload associated with the at least one partition between the first worker computer and the second worker computer such that the first worker computer and the second worker computer share the workload for the at least one partition;
- and
- in response to distributing the requests for the workload associated with the at least one partition between the first worker computer and the second worker computer, de-replicating the at least one partition from the second worker computer by deleting the at least one partition from the second worker computer.
Dependencies are inferred from the claim text.