MIT's 6.824 Distributed Systems, Lab 1: MapReduce

Fri Feb 05 2021

tags: programming computer science self study notes public 6.824 MIT distributed systems lab

Introduction

Here I talk about what Lab 1 was about, what problems I faced when implementing it, and what I learned doing the lab.

This is part of my self-study of 6.824 with NUS SoC folks. It may or may not be part of my goal to finish a Stanford CS degree in a year.

The task

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.

My implementation

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" where X is the index of the map job and Y is 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" where Y is 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)

Deadlocks

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.

g() {
    m.mu.Lock()
    // do something ...
    m.mu.Unlock()
    return
}

f() {
    m.mu.Lock()
    g()
    m.mu.Unlock()
    return
}

Here f will acquire a lock, call g, then g will try to acquire the same lock. But it can't because f is still holding on to it. But f will never release the lock because it's waiting for g to complete! So we have a deadlock.

In this lab, g was GrabAllFileNamesForReduceJob and f was AssignReduceJobToWorker. Inside 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 g. But in this case since f locks, you cannot lock in g.

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 fork().

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.

Conclusion

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.