Automated load-balancing of partitions in arbitrarily imbalanced distributed mapreduce computations

• US 9,613,127 B1
• Filed: 06/30/2014
• Issued: 04/04/2017
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Quantcast
• Original Assignee: Quantcast
• Inventors: Jiang, Wei, Rus, Silvius V.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/320,373
• Time in Patent Office: 1,009 Days
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A distributed computing system executes a MapReduce job on streamed data that includes an arbitrary amount of imbalance with respect to the frequency distribution of the data keys in the dataset. A map task module maps the dataset to a coarse partitioning, and generates a list of the top K keys with the highest frequency among the dataset. A sort task module employs a plurality of sorters to read the coarse partitioning and sort the data into buckets by data key. The values for the top K most frequent keys are separated into single-key buckets. The other less frequently occurring keys are assigned to buckets that each have multiple keys assigned to it. Then, more than one worker is assigned to each single-key bucket. The output of the multiple workers assigned to each respective single-key bucket is stitched together.

Claims

1. A computer-implemented method of load-balancing in arbitrarily imbalanced MapReduce job in a distributed computing system, the method comprising:

identifying K data keys with the highest frequency among received data, the received data comprising pairings of data keys and data values to be processed in the MapReduce job;

assigning one respective reduce phase worker to process data values corresponding to the data keys of each multiple-key bucket, each multiple-key bucket comprising queued data items having several different keys;

assigning data for each of the K data keys to a single-key bucket and other data keys to multiple-key buckets;

assigning multiple reduce phase workers to process data values corresponding to the data key of each single-key bucket, wherein a number of multiple reduce phase workers to assign to a single-key bucket is determined according to a respective frequency of the data key assigned to the single-key bucket and a threshold level of acceptable imbalance in reduce phase worker loads across reduce phase workers; and

stitching together output of the assigned multiple reduce phase workers on each respective single-key bucket.

2. The method of claim 1, wherein the received data is a data stream.

3. The method of claim 1, wherein the identified K keys with the highest frequency among the received data fluctuates as additional data are received.

4. The method of claim 1, wherein K is a number selected to keep a maximum imbalance ratio under a threshold.

5. The method of claim 1, wherein K is selected based on a frequency distribution of the data keys.

6. The method of claim 1, further comprising reporting a frequency distribution of the K highest frequency data keys.

7. The method of claim 1, further comprising combining output across all reduce phase workers to obtain a result of a MapReduce computation.

8. The method of claim 1, wherein assigning each of the K data keys to a single-key bucket and other data keys to multiple-key buckets comprises a single sort step.

9. The method of claim 1, wherein the single-key bucket for a first data key of the identified K data keys is arbitrarily large compared to other buckets.

10. A nontransitory computer readable storage medium including computer program instructions that, when executed, cause a computer processor to perform operations comprising:

identifying K data keys with the highest frequency among received data, the received data comprising pairings of data keys and data values to be processed in the MapReduce job;

assigning one respective reduce phase worker to process data values corresponding to the data keys of each multiple-key bucket, each multiple-key bucket comprising queued data items having several different keys;

assigning data for each of the K data keys to a single-key bucket and other data keys to multiple-key buckets;

assigning multiple reduce phase workers to process data values corresponding to the data key of each single-key bucket, wherein a number of multiple reduce phase workers to assign to a single-key bucket is determined according to a respective frequency of the data key assigned to the single-key bucket and a threshold level of acceptable imbalance in reduce phase worker loads across reduce phase workers; and

stitching together output of the assigned multiple reduce phase workers on each respective single-key bucket.

11. The medium of claim 10, wherein the received data is a data stream.

12. The medium of claim 10, wherein the identified K keys with the highest frequency among the received data fluctuates as additional data are received.

13. The medium of claim 10, wherein K is a number selected to keep a maximum imbalance ratio under a threshold.

14. The medium of claim 10, wherein K is selected based on a frequency distribution of the data keys.

15. The medium of claim 10, wherein the operations further comprise reporting a frequency distribution of the K highest frequency data keys.

16. The medium of claim 10, wherein the operations further comprise combining output across all reduce phase workers to obtain a result of a MapReduce computation.

17. The medium of claim 10, wherein assigning each of the K data keys to a single-key bucket and other data keys to multiple-key buckets comprises a single sort step.

18. The medium of claim 10, wherein the single-key bucket for a first data key of the identified K data keys is arbitrarily large compared to other buckets.

19. A system comprising:

a computer processor; and

a computer readable storage medium storing processor-executable computer program instructions, the computer program instructions comprising instructions for;

identifying K data keys with the highest frequency among received data, the received data comprising pairings of data keys and data values to be processed in the MapReduce job;

assigning one respective reduce phase worker to process data values corresponding to the data keys of each multiple-key bucket, each multiple-key bucket comprising queued data items having several different keys;

assigning data for each of the K data keys to a single-key bucket and other data keys to multiple-key buckets;

assigning multiple reduce phase workers to process data values corresponding to the data key of each single-key bucket, wherein a number of multiple reduce phase workers to assign to a single-key bucket is determined according to a respective frequency of the data key assigned to the single-key bucket and a threshold level of acceptable imbalance in reduce phase worker loads across reduce phase workers; and

stitching together output of the assigned multiple reduce phase workers on each respective single-key bucket.