Method for shard assignment in a large-scale data processing job

• US 9,298,760 B1
• Filed: 08/03/2012
• Issued: 03/29/2016
• Est. Priority Date: 08/03/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Xiaozhou, Dvorsky, Marian, Zhao, Yonggang, Gheorghioiu, Ovidiu
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Rayyan, Susan F
• Application Number:
  US13/566,793
• Time in Patent Office: 1,334 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

A method for shard assignment in a large-scale data processing job is provided. Datasets are divided into a plurality of shards and the shards are indexed and aggregated into one or more groups. A worker process is initially assigned an indexed shard from a group. The initial assignment can assigned based on a simple algorithm. The worker'"'"'s subsequent shard assignment is based on the index of the initially assigned shard.

Claims

1. A system for shard assignment in a distributed data processing system, the system comprising:

one or more processing devices;

one or more storage devices storing instructions that, when executed by the one or more processing devices, cause the one or more processing devices to implement;

a plurality of worker processes and

a master process for coordinating a data processing job that;

divides an input dataset into a plurality of shards;

indexes the plurality of shards;

aggregates the plurality of shards into one or more groups based on the shards'"'"' indices;

initially assigns an indexed shard from each group to a worker process; and

in response to a worker having processed its initially assigned indexed shard, assigns subsequent shards from the same group as the initially assigned shard to the worker process based on the index of the previously-assigned shard.

2. The system of claim 1, wherein indexing the plurality of shards, aggregating the shards into one or more groups, and initially assigning an indexed shard from each group to a worker process comprises:

sequentially indexing the plurality of shards;

aggregating the plurality of shards into one or more groups based on the shards'"'"' indices;

identifying one or more of the indexed shards as a seed shard; and

initially assigning the one or more seed shards to one or more worker processes.

3. The system of claim 1, wherein assigning subsequent shards to a worker comprises:

receiving an indication of the index of the previously-received shard from the worker and

assigning a subsequent indexed shard based on the received index.

4. The system of claim 1, wherein the input dataset includes data from a plurality of input data files, and wherein indexing the plurality of shards, aggregating the shards into one or more groups and initially assigning an indexed shard from each group to a worker process comprises:

sequentially indexing shards from the same data file;

aggregating the shards into one or more groups based on the shards'"'"' indices;

identifying the first shard from each data file as a seed shard; and

assigning each of the seed shards to a worker process.

5. The system of claim 1, wherein data within a group is indexed contiguously.

6. The system of claim 2, wherein initially assigning the one or more seed shards to a worker process includes using a simple indexing algorithm to choose the seed shard.

19. The system of claim 1, wherein initially assigning the indexed shard to a worker process includes matching region information between a shard and a worker process when shards and worker processes are in different data centers.

7. A computer-implemented method for shard assignment in a distributed data processing system, comprising:

dividing an input dataset into a plurality of shards;

indexing the plurality of shards;

aggregating the plurality of shards into one or more groups based on the shards'"'"' indices;

initially assigning an indexed shard from each group to a worker process; and

in response to a worker having processed its initially assigned indexed shard, assigning subsequent shards from the same group as the initially assigned shard to the worker based on the index of the previously-assigned shard.

8. The computer-implemented method of claim 7, wherein indexing the plurality of shards, aggregating the plurality of shards into one or more groups, and initially assigning an indexed shard from each group to a worker process comprises:

sequentially indexing the plurality of shards;

aggregating the plurality of shards into one or more groups based on the shards'"'"' indices;

identifying one or more of the indexed shards as a seed shard; and

initially assigning the one or more seed shards to one or more worker processes.

9. The computer-implemented method of claim 7, wherein assigning subsequent shards to a worker comprises:

receiving an indication of the index of the previously received shard from the worker and

assigning a subsequent indexed shard based on the received index.

10. The computer-implemented method of claim 7, wherein the input dataset includes data from a plurality of input data files, and wherein indexing the plurality of shards and aggregating the shards into one or more groups comprises:

sequentially indexing shards from the same data file;

aggregating shards into one or more groups based on the shards'"'"' indices;

identifying the first shard from each data file as a seed shard; and

assigning each of the seed shards to a worker process.

11. The computer-implemented method of claim 7, wherein data within a group is indexed contiguously.

12. The computer-implemented method of claim 8, wherein initially assigning the one or more seed shards to a worker process includes using a simple indexing algorithm to choose the seed shard.

20. The computer-implemented method of claim 7, wherein initially assigning the indexed shard to a worker process includes matching region information between a shard and a worker process when shards and worker processes are in different data centers.

13. A non-transitory computer-readable medium having stored therein computer executable code that causes one or more processors to execute the steps of:

dividing an input dataset into a plurality of shards;

indexing the plurality of shards;

aggregating the plurality of shards into one or more groups based on the shards'"'"' indices;

initially assigning an indexed shard from each group to a worker process; and

in response to a worker having processed its initially assigned indexed shard, assigning subsequent shards from the same group as the initially assigned shard to the to a-worker based on the index of the previously-assigned shard.

14. The non-transitory computer-readable medium of claim 13, wherein indexing the plurality of shards, aggregating the plurality of shards into one or more groups, and initially assigning an indexed shard from each group to a worker process comprises:

sequentially indexing the plurality of shards;

aggregating the plurality of shards into one or more groups based on the shards'"'"' indices;

identifying one or more of the indexed shards as a seed shard;

initially assigning the one or more seed shards to one or more worker processes.

15. The non-transitory computer-readable medium of claim 13, wherein assigning subsequent shards to a worker comprises:

receiving an indication of the index of the previously-received shard from the worker and

assigning a subsequent indexed shard based on the received index.

16. The non-transitory computer-readable medium of claim 13, wherein the input dataset includes data from a plurality of input data files, and wherein indexing the plurality of shards and aggregating the shards into one or more groups comprises:

sequentially indexing shards from the same data file;

aggregating the shards into one or more groups based on the shards'"'"' indices;

identifying the first shard from each data file as a seed shard; and

assigning each of the seed shards to a worker process.

17. The non-transitory computer-readable medium of claim 13, wherein data within a group is indexed contiguously.

18. The non-transitory computer-readable medium of claim 14, wherein initially assigning the one or more seed shards to a worker process includes using a simple indexing algorithm to choose the seed shard.

21. The non-transitory computer-readable medium of claim 13, wherein initially assigning the indexed shard to a worker process includes matching region information between a shard and a worker process when shards and worker processes are in different data centers.