SYSTEM AND/OR METHOD FOR BALANCING ALLOCATION OF DATA AMONG REDUCE PROCESSES BY REALLOCATION

• US 20090313635A1
• Filed: 06/12/2008
• Published: 12/17/2009
• Est. Priority Date: 06/12/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Dasdan, Ali
• Granted Patent: US 8,726,290 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

The subject matter disclosed herein relates to a system and/or method for allocating data among reduce processes.

Claims

1. A method comprising:

executing a map process via a computing platform to provide intermediate data associating key/value pairs with input data;

allocating said intermediate data among a plurality of reduce processes; and

re-allocating at least a portion of said intermediate data initially allocated to one or more of said reduce processes based, at least in part, on a load factor associated with said one or more reduce processes.

2. The method of claim 1, and further comprising determining said load factor based, at least in part, on an estimated time of completion of processing of said portion by said one or more reduce processes.

3. The method of claim 2, and further comprising determining said estimated time of completion based, at least in part, on one or more histograms of behavior associated with said at least one of said one or more reduce processes.

4. The method of claim 3, wherein at least one of said one or more histograms represents run time per byte.

5. The method of claim 3, wherein at least one of said one or more histograms represents run time per value of key/value pairs.

6. The method of claim 3, wherein at least one of said one or more histograms represents run time per key of key/value pairs.

7. The method of claim 3, wherein at least one of said one or more histograms represents transfer time per byte.

8. The method of claim 3, wherein at least one of said one or more histograms represents transfer time per value of key/value pairs.

9. The method of claim 3, wherein at least one of said one or more histograms represents transfer time per key of key/value pairs.

10. The method of claim 1, wherein said allocating said intermediate data among said plurality of said reduce processes comprises allocating said intermediate data based, at least in part, on said key/value pairs.

11. The method of claim 1, wherein said re-allocating at least a portion of said intermediate data comprises allocating said portion to one or more helper reduce processes.

12. The method of claim 11, wherein said one or more helper reduce processes executes a function defined by a user as a reduce function.

13. The method of claim 11, wherein said one or more helper reduce processes executes a function defined by a user as a helper reduce function.

14. The method of claim 11, wherein said one or more helper reduce processes executes a function defined by a MapReduce system as a helper reduce function.

15. The method of claim 11, and further comprising:

merging output data provided by said one or more helper reduce processes from processing said allocated portion.

16. The method of claim 11, and further comprising not merging output data provided by said one or more helper reduce processes from processing said allocated portion based upon a user selection.

17. The method of claim 1, wherein said load factor is based, at least in part, on key-value pairs associated with said portion of intermediate data.

18. An article comprising:

a storage medium having machine-readable instructions stored thereon which, if executed by a computing platform, are adapted to enable said computing platform to;

initiate execution of a map process to provide intermediate data associating key/value pairs with input data;

allocate said intermediate data among a plurality of reduce processes; and

re-allocate at least a portion of said intermediate data initially allocated to one or more of said reduce processes based, at least in part, on a load factor associated with said one or more of said reduce processes.

19. The article of claim 18, wherein said instructions, if executed by said computing platform, are further adapted to enable said computing platform to determine said load factor based, at least in part, on an estimated time of completion of processing of said portion by at least one of said one or more reduce processes.

20. An apparatus comprising:

a computing platform, said computing platform being adapted to;

initiate execution of a map process to provide intermediate data associating key/value pairs with input data;

allocate said intermediate data among a plurality of reduce processes; and

re-allocate at least a portion of said intermediate data initially allocated to at least one of said reduce processes based, at least in part, on a load factor associated with said at least one reduce process.

21. The apparatus of claim 20, wherein said computing platform is further adapted to determine said load factor based, at least in part, on an estimated time of completion of processing of said portion by at least one of said one or more reduce processes.

22. The apparatus of claim 21, wherein said computing platform is further adapted to determine said estimated time of completion based, at least in part, on one or more histograms of behavior associated with said at least one of said one or more reduce processes.