6.824 Lab 1 - MapReduce
- Lab
- PaperMapReduce
- Lecture Notes
- Code
- Run with
cd src/main && ./test-mr.sh
- Run with
- The map task creates
nReduceoutput files, each reduce job takes its (single) output file from the output of each map task. - What state does the coordinator need to store?
- Input files (this is also the number of map tasks)
- Number of reduce tasks
- Status of each map task
- Status of each reduce task
- What coordinator⇄worker messages need to be defined?
- Worker polls for a job, coordinator gives it a map or reduce job (or asks it to shut itself down). Args:
- Map: single input file for that map task
- Reduce: reduce task ID + intermediate paths (if any exist yet)
- Worker tells the coordinator that a map task is finished. Args:
- Locations of
nReduceintermediate files
- Locations of
- Coordinator tells reduce workers that new intermediate files are available. Args:
- Location of a single intermediate file (assuming no batching here to start with)
- Worker polls for a job, coordinator gives it a map or reduce job (or asks it to shut itself down). Args:
- Starting with fairly coarse locks; I’ll possibly make these more fine later.
- Go’s lack of enums is very annoying! I just used strings (
in-progress,idle,finished) for now. - The reduce task here doesn’t gain anything by pre-fetching intermediate files before all maps are done because there’s no network IO involved.
- Ran into an issue where using
rand.Intnacross many workers caused conflicts without an explicit seed. - Sort of a cop-out, but I wrote the reduce to just combine all intermediate data and sort in-memory. Something like merge-sort is going to be far more performant here, but I didn’t particularly want to waste time writing that up in Go.
- Looks like everything but the final three edge-case plugins is now passing! Actually reading the paper first made this a lot quicker (~3h) than I expected.
- The
early_exittest was failing because the Big Surbashversion doesn’t supportwait -n. Installing bash 5 via homebrew fixed this. - Crash safety was fun to implement; there’s a lot of depth here than I chose to ignore - my impl. is simply:
- The coordinator tracks when each task was started, and moves any tasks that are
in-progressfor longer than 5s back toidle - In some cases reduce jobs use up all workers waiting for all intermediate data to show up, and there’s no room for (retried) map jobs to run to actually produce that data. Deadlock! Fixed by having reduce tasks abort if they don’t receive their full intermediate dataset in 5 or fewer retries.
- The coordinator tracks when each task was started, and moves any tasks that are
