Bottleneck MapReduce Framework Assignment

credit for this assignment: Finn Voichick and Dennis Cosgrove

Motivation

Dealing with big data is Hansel-level hot right now. We will build two implementations to better understand the inner workings of Hadoop and Spark-like frameworks. Your frameworks will actually be more general than just MapReduce.

The Matrix implementation gives us experience with dividing the work up into thread confined tasks whose results are then combined together.

Background

wikipedia article on MapReduce

As the name suggests, MapReduce refers to the process of mapping then reducing some stream of data. At its core, all a MapReduce algorithm entails is transforming a list of one kind of item before collecting those items and reducing them down to a single values per key using some computation. As you can probably tell, the concept of MapReduce is extremely general and can apply to a wide berth of problems. In this assignment, we will use MapReduce to simulate the Facebook mutual friends algorithm (finding the mutual friends between all friend pairs) as well as pinpointing the offending well in the 1854 Soho Cholera Outbreak.

For more information on the general concept of MapReduce, refer to this article.

Java Advice

Use map.entrySet()

Prefer the use of map.entrySet() over map.keySet() followed by looking up the value with map.get(key).

Use the appropriate version of join_fork_loop

there are many overloaded versions of join_fork_loop including:

• range of ints from min to maxExclusive
• array
• Iterable

choose the correct one for each situation where "correct" is often the one that produces the cleanest code.

A Path To Victory

• Int Sum MR App Exercise
• Reducer Exercise
• Mutual Friends MR App Exercise
• Card Only Sequential Map Reduce Framework Warm Up
• Word Count Only Parallel MapReduce Framework Warm Up
• This Exercise

Warm Ups

Card Only Sequential Map Reduce Framework

Word Count Only Parallel MapReduce Framework

Code To Implement

Bottlenecked MapReduce Framework

class:	BottleneckedMapReduceFramework.java
methods:	mapAll accumulateAll toArrayOfReductions toReductionMap
package:	mapreduce.framework.lab.bottlenecked
source folder:	student/src/main/java

Navigate to the BottleneckedMapReduceFramework.java class and there will be three methods for you to complete: mapAll, accumulateAll, and finishAll. These frameworks are meant to be extremely general and applied to more specific uses of MapReduce. Whereas the warm ups for this lab serve to prepare you to build this required section of the lab, this bottlenecked framework is in many ways a warm up for the matrix implementation.

mapAll

NOTE: If you struggle to get through this method, you are strongly encouraged to try the warm-ups.

method: List<List<KeyValuePair<K, V>>> mapAll(E[] input) (parallel implementation required)

With this method, you will map all of the elements of an array of data into a new array of equivalent size consisting of Lists of key value pairs. We will leverage the Mapper which is a field/instance variable on this BottleneckedFramework instance. When invoking the mapper's map method with an element of the input array and a BiConsumer which will accept each key and value passed to it, adding a KeyValuePair to its List. This list should then be added to the array of lists you previously defined, therefore completing the mapping stage of MapReduce. This should all be done in parallel.

Hint: you should create an array of lists equivalent in size to the original array. Each list will contain all of the emitted (key,value) pairs for its item.

slide

Example: Mutual Friends

Input

Result of mapAll(input)

accumulateAll

method: Map<K, A> accumulateAll(List<KeyValuePair<K, V>>[] mapAllResults) (sequential implementation only)

This middle step is often excluded in more advanced MapReduce applications. When run in parallel, it is the only step of the framework that must be completed sequentially. In the matrix framework implementation, we will do away with this step altogether for the sake of performance.

In this method, you will take in the array of lists you previously created and accumulate the key value pairs in the lists into a newly defined map. To help deal with this issue, you must make use of the Collector provided to you. More specifically, access the accumulator in the collector by calling the accumulator() method and accept the key/value pair when you add it to the map. You probably noticed that the method must return a map of <K, A>, which differs from the <K, V> generics fed into the method. The framework is designed this way as the data originally fed into the mapping stage can be collected into a mutable container before reaching the finish/reduce stage. In order to access the correct value for the map if the key has no associated value yet, use the supplier associated with the Collector with the supplier() method.

slide

toArrayOfReductions and toReductionMap

method: R[] toArrayOfReductions(Entry<K, A>[] entries) (parallel implementation required)

method: Map<K, R> toReductionMap(Entry<K, A>[] entries, R[] reducedValues) (sequential implementation only)

This final step reduces the accumulated data and returns the final map in its reduced form. Again, you may notice that the method returns a map of <K, R> instead of the <K, A> which was returned in the accumulateAll method. This happens for the exact same reason as the accumulateAll method, as the framework is designed to handle cases in which the reduced data differs in type from the accumulated data.

To reduce the data down, use the map returned from the accumulateAll stage and put the results of the reduction into a new map. The provided Reducer will come in extremely handy for this stage, more specifically the finisher which can be called using the reduce() method. This step should run in parallel and will probably be the easiest of the three methods.

slide

Testing Your Solution

Correctness

class:	BottleneckedFrameworkTestSuite.java
package:	mapreduce.framework.lab.bottlenecked
source folder:	testing/src/test/java

MapAll

class:	BottleneckedFrameworkTestSuite.java
package:	mapreduce.framework.lab.bottlenecked
source folder:	testing/src/test/java

AccumulateAll

class:	BottleneckedAccumulateAllTestSuite.java
package:	mapreduce.framework.lab.bottlenecked
source folder:	testing/src/test/java

ReduceAll

class:	BottleneckedFinishAllTestSuite.java
package:	mapreduce.framework.lab.bottlenecked
source folder:	testing/src/test/java

Holistic

class:	BottleneckedHolisticTestSuite.java
package:	mapreduce.framework.lab.bottlenecked
source folder:	testing/src/test/java