Map reduce

paper link

https://drive.google.com/file/d/1hkJUhaqSXYscBMIaloEWGCG4Q5OMINRT/view?usp=sharing

my implementation:

https://github.com/thevoid12/distributed_map_reduce

my thoughts

what a phenomenal paper, revolutionary. jeff dean and sanjay ghemawat are the real goats. this is such an influential paper, it truly embodies divide and conquer. putting myself in the shoes of someone reading it in 2004, when it was published, this paper still makes a lot of sense even today, despite there being better, improved papers built on top of this og mapreduce paper. I took some time to reimplement this paper including worker failures, and this taught me a lot about parallel data processing, where two different phases eventually need to become sequential at some point. I think there are a lot of papers built on top of this handling master fault tolerance, cause this paper assumes a single master node will never fail.

high level idea

worker mapper reducer

shortcomings

from this paper these were the straightaway shortcomings I could see (all of these are fixed later, apache spark embodies a lot of mapreduce’s ideas but fixes the shortcomings):

too much I/O, which will pull the rug on performance. my first instinct was that they were writing all the intermediate data to disk because ram wasn’t sophisticated enough back then, but that’s not really it, the paper does it for fault tolerance: if a worker dies, the master can just re-run its task since the input is durable, and disk also lets you process datasets way bigger than what fits in ram.
each mapper partitions its output into one file per reducer, so with 1000 mappers and 100 reducers you end up with 100,000 intermediate files. this is inherent to the design because you can’t merge partial reduces on the fly, the reduce function needs to see the full set of values for a key, and since mappers run in parallel with no coordination between them, nobody can decide early which values belong together.
a reducer only starts running the user’s reduce function once it has all the intermediate data for its partition, which means it has to wait for every mapper to finish, so the map and reduce phases aren’t truly overlapped.
doesn’t talk about master fault tolerance, the paper explicitly punts on it and just aborts the whole job if the master dies, reasoning that a single machine failing is unlikely.
works only for niche usecases but these cases were very painful problems in google that needed to be solved
there is insanely skewing issue which can occur in this implementation for example common words like the will have crazy high occurance so its hash function will always direct it to a worker that will definitely overwork