MIT's 6.824 Distributed Systems, Lab 1: MapReduceFri Feb 05 2021
Here I talk about what Lab 1 was about, what problems I faced when implementing it, and what I learned doing the lab.
The task in Lab 1 was to implement MapReduce more-or-less faithfully as it was described in the original paper in Golang. The key difference is that all workers run on the same computer and all files are on the same local disk. One other difference is that while the original MapReduce paper describes the master pushing tasks to workers, we were told to have workers call the master using remote procedure calls (RPCs) to ask for tasks instead.
We were given scaffolding code and testing code which helped a great deal. All we had to do was write the master and worker code.
Reading the paper and grokking it took me around two hours, and implementing it took me about 6 hours. Overall, it wasn't too hard.
Here's an overview of the process:
- Periodically, workers call the Master with a RequestJob RPC.
- Master checks current job status:
- if all jobs done: assign "exit" job
- elif there are idle Map jobs: assign Map job
- elif all Map jobs completed and there are idle Reduce jobs: assign Reduce job
- else: assign "null" job
- When a worker receives a reply from RequestJob:
- if "exit": exit
- if "map": perform Map job on
file at fileLocation.
Save intermediate files as "mr-X-Y"
Xis the index of the map job and
Yis the (modded) hash of the key. When this job is done, call Master with ReceiveFileLocation RPC, giving the location of the intermediate files.
- if "reduce": perform Reduce job on
all files at fileLocations,
then save file as "mr-0-Y"
Yis the index of the reduce job.
- if "null": sleep(1), then RequestJob again.
When the master receives a ReceiveFileLocation RPC, it takes the file locations contained therein and saves them so that it can then pass them to the reduce workers.
The master does some bookkeeping to check when tasks are complete/have stalled, save file locations returned by ReceiveFileLocation, and so on.
Problems I faced, and how I solved them
Concurrency is the biggest challenge. The master is constantly receiving lots of different RPCs, each in a different thread. You can very easily have a race condition. For instance, the ReceiveFileLocation RPC causes the master to update its list of intermediate files. But these intermediate files might be read when responding to a RequestJob RPC. Since each RPC runs on a different thread, it's possible that the RequestJob RPC might read while the ReceiveFileLocation RPC is writing, which would result in inconsistent state.
Segfault because I didn't initialise arrays of objects
This was due to my lack of knowledge with Go.
So I was declaring
a := string
and then doing
a[i] which throws a segfault,
because the slice hasn't yet been initialised.
Instead one should do
a := make(string, N)
When Liang Jun explained deadlocks to me I thought only an idiot would get into deadlocks. I guess that makes me an idiot 🙃.
The way he explained it is that deadlock happens when there's a function A holding the lock and is waiting for B to finish in order to unlock, while B is waiting for A to unlock so that it can start running. I thought "I'll never write code where this happens". Well--it turns out that you can easily do that with nested calls.
// do something ...
f will acquire a lock, call
g will try to acquire the same lock.
But it can't because
f is still holding on to it.
f will never release the lock because it's
g to complete! So we have a deadlock.
In this lab,
f there was a call
reply.MapFileLocations = GrabAllFileNamesForReduceJob(..).
It was very easy to make this mistake,
because I thought "OK, so g() is reading state, we need to lock it".
And if you do call it from a function that doesn't lock then you
would indeed have to have a lock in
But in this case since
f locks, you cannot lock in
What I learned
This was a good warm-up exercise just to get to know Go better. Lab 2 is going to be very hard, so this practice is definitely welcome.
I didn't know what an RPC was until I took this course. I wish someone had told me this earlier, because my Python library I wrote for work is basically just reinventing an RPC library. I suppose this means that I can now write "designed and implemented custom RPC library with TCP sockets" in my resume...
I also went down the rabbit hole a little bit.
In order to do this lab
I had to learn about concurrency and mutexes.
But in order to learn that I had to learn what
the difference is between a thread and a process.
And in order to learn that I had to know what
a process even was -- which brought me back to
operating systems and
And, of course, I learned about MapReduce at a level that you just don't get from passively listening or reading alone. There's no substitute for implementation.
What I should have done better
Not a mistake per se, but I tried to stick very closely to the spec given in the actual MapReduce paper, but after doing a code review of Liang Jun's code I realised the code can be much cleaner if you don't follow it strictly. For instance, one thing Liang Jun did that I didn't was to make workers send an acknowledgement after a successful reduce task. I deliberately didn't do this because the paper says
"When a map task completes, the worker sends a message to the master... When a reduce task completes, the reduce worker atomically renames its temporary output file to the final output file",
implying that the reduce worker should not send a message back to the master. This entails extra complexity on the master because it has to have response handling code for the map workers, and file-checking code for the reduce workers. But as far as I can tell there's no good reason for reduce workers not to send back a completion too: having all workers send back a completion makes the implementation much cleaner.
Overall, I learned a lot from this lab. It wasn't too hard and I quite enjoyed writing in Go. I do kind of miss list comprehensions from Python, but I do like the simplicity of Golang. (There's a lot more to learn, of course!)
What I want to learn more about: Golang, Go's channels, interfaces, concurrent programming.