MapReduce

• Distributed systems.
• Object-oriented programming.
• Educational only.

How to run

dotnet run -p src/MapReduce.Sample

How to use

• Example of master initiation: src/MapReduce.Sample/Program.cs.
• Example of workers initiation: src/MapReduce.Sample/Playbook/WorkerHelper.cs.
• Example of Custom Map and Reduce functions:
  • Word count - src/MapReduce.Sample/Playbook/WordCount.cs.
  • Inverted file index - src/MapReduce.Sample/Playbook/InvertedIndex.cs.

Principle

map():

part of object -> list<(key, value)>
return list<(key, value)>

• Interface.
• Implementation (WordCount).
• Implementation (InvertedIndex).

combine():

hash<key, list<value>>
foreach ((key,value) in list<(key, value)>)
{
    hash<key, list<value>>[key].Add(value)
}
return hash<key, list<value>>

• Implementation.

partition():

hash<partitionIndex, hash<key, list<value>>>

• Interface.
• Implementation.

reduce():

hash<key, valueAggregated>
foreach ((key,values) in hash<key, list<value>>)
{
    foreach (value in values)
    {
        hash<key, valueAggregated>[key] += value
    }
}
// foreach (key,value) in other list<(key, value)>
// omitted
return hash<key, valueAggregated>

• Interface.
• Implementation (WordCount).
• Implementation (InvertedIndex).

• each intermediate file is a partition.
• ith reducer take every ith partition in each mapper’s local disk.

Master Data Structure

• class master
  • List<MapTask>
  • List<ReduceTask>
  • List<Worker>
• relative data structures
  • enum state { idle, in-progress, completed }
    • idle:
      • task waiting to be scheduled.
      • the task is not done yet.
  • class MapTask { state, CompletedFile, ... }
  • class ReduceTask { state, CompletedFile, ... }
  • class CompletedFile { location, size }

Failure

• worker failure
  • master pings worker.
    • no response in amount of time -> worker failed.
• master failure
  • exception on user code.
  • master writes data structures in checkpoints periodically.
  • master gives the same task to a different worker.

Use Cases

• When map worker completes a map task
  1. worker —-{file names}—> master.
  2. master saves file names to data structure.
• When reduce worker completes a reduce task
  1. rename temp output file to final output file.
• Task processing
  • worker
    1. The workers talk to the master via RPC.
    2. worker ask the master for a task
    3. worker read the task’s input from one or more files,
    4. worker executes the task,
    5. worker writes the task’s output to one or more files.

Partitioning

• 
  • https://stackoverflow.com/questions/27595195/hadoop-partitioner
• each partition is a file.
• each partition has a dictionary.
• each partition might have 0, 1, or more keys.
  • those keys have the same value of key.GetHashCode() % numPartitions.
  • numPartitions := number of reduce tasks.
  • number of reduce tasks is preset in master.
• at each reduce task, the worker should read the ith partition of outputs of all mappers.
• worker can acquire more than one task.
• additional details - https://stackoverflow.com/q/17734468/9920172.

Assignment

Your job is to implement a distributed MapReduce, consisting of two programs, the master and the worker. There will be just one master process, and one or more worker processes executing in parallel. In a real system the workers would run on a bunch of different machines, but for this lab you’ll run them all on a single machine. The workers will talk to the master via RPC. Each worker process will ask the master for a task, read the task’s input from one or more files, execute the task, and write the task’s output to one or more files. The master should notice if a worker hasn’t completed its task in a reasonable amount of time (for this lab, use ten seconds), and give the same task to a different worker.