EFFICIENT IMPLEMENTATIONS FOR MAPREDUCE SYSTEMS

• US 20150127649A1
• Filed: 10/31/2014
• Published: 05/07/2015
• Est. Priority Date: 11/01/2013
• Status: Abandoned Application

• Current Assignee: Cognitive Electronics, Inc.
• Original Assignee: Cognitive Electronics, Inc.
• Inventors: FELCH, ANDREW C.
• Application Number:
  US14/530,425
• Publication Number:
  US 20150127649A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0638 Combination of memories, e.g. ROM and RAM such as to permit replacement or supplementing of words in one module by words in another module address formation of the next microinstruction G06F9/26; masking faults in memories by using spares or by reconfiguring G11C29/70
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

In some embodiments, a processor configured to function as at least a first Reducer in a MapReduce system may receive a set of mapped [key, value] pairs output from a Mapper in the MapReduce system, identify within the set of mapped [key, value] pairs one or more [key, value] pairs for whose keys the first Reducer is not responsible, and transfer those [key, value] pairs to one or more other Reducers in the MapReduce system. In some embodiments, a system including at least one processor may receive a data packet including a set of mapped [key, value] pairs corresponding to a plurality of keys handled by a plurality of Reducers in a MapReduce system. For each mapped [key, value] pair, the system may identify the corresponding key and one of the Reducers responsible for that key, and provide the mapped [key, value] pair to the Reducer for processing.

Claims

1. Apparatus comprising:

a processor configured to function as at least a first Reducer in a MapReduce system; and

a processor-readable storage medium storing processor-executable instructions that, when executed by the processor, cause the processor to perform a method comprising;

receiving a set of mapped [key, value] pairs output from a Mapper in the MapReduce system;

identifying, within the set of mapped [key, value] pairs, one or more [key, value] pairs for whose keys the first Reducer is not responsible; and

transferring the one or more identified [key, value] pairs to one or more other Reducers in the MapReduce system.

2. The apparatus of claim 1, wherein the method further comprises executing a Reduce function on a subset of the set of mapped [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible.

3. The apparatus of claim 2, wherein the method further comprises:

receiving, from other Reducers in the MapReduce system, additional [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible; and

executing the Reduce function on the additional [key, value] pairs.

4. The apparatus of claim 3, wherein the method further comprises establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, in which additional [key, value] pairs from the respective other Reducer are received.

5. The apparatus of claim 1, wherein the method further comprises establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, from which mapped [key, value] pairs matched to the respective other Reducer are sent to the respective other Reducer.

6. A method comprising:

receiving, at a processor configured to function as at least a first Reducer in a MapReduce system, a set of mapped [key, value] pairs output from a Mapper in the MapReduce system;

identifying, by the processor configured to function as at least the first Reducer, within the set of mapped [key, value] pairs, one or more [key, value] pairs for whose keys the first Reducer is not responsible; and

transferring the one or more identified [key, value] pairs to one or more other Reducers in the MapReduce system.

7. The method of claim 6, further comprising executing a Reduce function, via the first Reducer, on a subset of the set of mapped [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible.

8. The method of claim 7, further comprising:

receiving, at the first Reducer, from other Reducers in the MapReduce system, additional [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible; and

executing the Reduce function, via the first Reducer, on the additional [key, value] pairs.

9. The method of claim 8, further comprising establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, in which additional [key, value] pairs from the respective other Reducer are received.

10. The method of claim 6, further comprising establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, from which mapped [key, value] pairs matched to the respective other Reducer are sent to the respective other Reducer.

11. Apparatus comprising:

at least one processor; and

at least one processor-readable storage medium storing processor-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform a method comprising;

receiving a data packet including a set of mapped [key, value] pairs corresponding to a plurality of keys handled by a plurality of Reducers in a MapReduce system; and

for each mapped [key, value] pair in the set of mapped [key, value] pairs;

identifying a key corresponding to the respective mapped [key, value] pair;

identifying a Reducer of the plurality of Reducers responsible for the identified key; and

providing the respective mapped [key, value] pair to the identified Reducer for processing.

12. The apparatus of claim 11, wherein the at least one processor is configured to function as at least a first Reducer in the MapReduce system, and wherein the method further comprises executing a Reduce function on a subset of the set of mapped [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible.

13. The apparatus of claim 12, wherein the method further comprises:

receiving, from other Reducers in the MapReduce system, additional [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible; and

executing the Reduce function on the additional [key, value] pairs.

14. The apparatus of claim 13, wherein the method further comprises establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, in which additional [key, value] pairs from the respective other Reducer are received.

15. The apparatus of claim 11, wherein the method further comprises establishing a set of buffers, each corresponding to a Reducer of a group of Reducers in the MapReduce system, from which mapped [key, value] pairs matched to the respective Reducer are sent to the respective Reducer.

16. The apparatus of claim 11, wherein the receiving comprises receiving the data packet from a Mapper in the MapReduce system that generated the mapped [key, value] pairs by executing a Map function on input data.

17. A method comprising:

receiving, at at least one processor, a data packet including a set of mapped [key, value] pairs corresponding to a plurality of keys handled by a plurality of Reducers in a MapReduce system; and

for each mapped [key, value] pair in the set of mapped [key, value] pairs;

identifying, via the at least one processor, a key corresponding to the respective mapped [key, value] pair;

identifying, via the at least one processor, a Reducer of the plurality of Reducers responsible for the identified key; and

providing the respective mapped [key, value] pair to the identified Reducer for processing.

18. The method of claim 17, wherein the at least one processor is configured to function as at least a first Reducer in the MapReduce system, and wherein the method further comprises executing, via the first Reducer, a Reduce function on a subset of the set of mapped [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible.

19. The method of claim 18, further comprising:

receiving, from other Reducers in the MapReduce system, additional [key, value] pairs corresponding to one or more keys for which the first Reducer is responsible; and

executing, via the first Reducer, the Reduce function on the additional [key, value] pairs.

20. The method of claim 19, further comprising establishing a set of buffers, each corresponding to another Reducer of a group of Reducers in the MapReduce system, in which additional [key, value] pairs from the respective other Reducer are received.

21. The method of claim 17, further comprising establishing a set of buffers, each corresponding to a Reducer of a group of Reducers in the MapReduce system, from which mapped [key, value] pairs matched to the respective Reducer are sent to the respective Reducer.

22. The method of claim 17, wherein the receiving comprises receiving the data packet from a Mapper in the MapReduce system that generated the mapped [key, value] pairs by executing a Map function on input data.