6.824 Lab 5: Final Project

Introduction

In this lab, you will work on a final project of your own choice. Unlike in previous labs, you will work in groups of 3-4 for the final project. You will be required to turn in both your code and a short write-up describing the design and implementation of your project, and to make a short in-class presentation about your work. We will post your write-up and code on the web site after the end of the semester, unless you explicitly talk to us about why you want to keep yours confidential.

The primary requirement is that your project be something interesting. Your project should also have something to do with distributed systems, but that's relatively easy, and it's much more important for your project to be interesting.

We encourage students to choose any project idea that you might think is interesting. If you are not sure, we provide you with two kinds of potential projects. First, we present a reasonably well-defined starting point for your project -- basically, a default project. Second, we give a list of half-baked ideas that we think could turn into an interesting project, but we haven't given them too much thought.

We encourage final projects that leverage multiple classes you might be taking, or that involve other research or projects you are already working on (e.g., MEng and AUP projects).

Deliverables

There are four concrete steps to the final project, as follows:

A well-defined starting point

Your goal for the default project is to build a persistent, fault-tolerant, high-performance key/value store, using lab 4 as a starting point. This means:

• Your servers should store data persistently on disk. You must handle the following cases:
  • Your replicated service should be able to recover from a single server crashing and restarting with its disk contents intact, by catching up the state of that server.
  • Your replicated service should be able to recover from a single server crashing and losing its disk contents. When the server comes back up, your service should bring the server up-to-date.
  • Your replicated service should be able to recover from a complete crash of all servers. (Of course, until a majority of them come back up, your service will not be able to handle client requests.)

  Note that making your service persistent implies that you will need to keep some Paxos state around on disk, in addition to your key/value state.

• You should write test cases that check whether your service operates correctly under a wide range of failure scenarios. A good starting point are the test cases from labs 3 and 4, but you will need to extend them to deal with persistence.
• Your service should be able to handle large amounts of data (e.g., hundreds of gigabytes per server), particularly when servers temporarily or permanently fail. Have a look at RAMCloud, Flat Datacenter Storage, Petal, and FAB for ideas.
• Your service should achieve high performance in terms of client requests per second, and in terms of client request latency. In particular, you should make two optimizations to your Paxos-based protocol: avoid 2 round-trips per agreement (e.g., by having a server issue Prepare messages ahead of time), and avoid dueling leaders under high client load (e.g., by using a designated leader like Multi-Paxos, using a striping approach like Mencius, or by using EPaxos).

  You can take a look at the source code for EPaxos here. Feel free to integrate it into your final project, although doing so may be quite non-trivial, and you may be better off implementing the above two optimizations yourself.

• You should write benchmarks to evaluate the throughput and latency of client operations on your service.
• You should identify the bottlenecks that are responsible for the throughput and latency results you observe.

Half-baked project ideas

Here's a list of ideas to get you started thinking -- but you should feel free to pursue your own ideas.

• Make the state synchronization protocol (DDP) in Meteor more efficient (e.g., send fewer bytes between server and client) and more fault-tolerant (e.g., a client should be able to tolerate server failures, as long as enough servers remain live).
• Build a fault-tolerant file service; on the client side, you could use FUSE to run your own client code, or you could have clients talk NFS to your server, as in Harp.
• Build a better fault-tolerant peer-to-peer tracker for BitTorrent.
• Build a system for making Node.js applications fault-tolerant, perhaps in the style of Hypervisor Fault Tolerance.
• Improve the Roost Javascript Zephyr client by replicating the backend to make it fault-tolerant.
• Use Mylar to build a secure webmail system with end-to-end encryption, contact lists, usable public key infrastructure, etc.
• Add cross-shard atomic transactions to Lab 4, using two-phase commit and/or snapshots.
• Build a system with asynchronous replication (like Dynamo or Ficus or Bayou). Perhaps add stronger consistency (as in COPS or Walter or Lynx).
• Build a file synchronizer (like Unison or Tra).
• Build a distributed shared memory (DSM) system, so that you can run multi-threaded shared memory parallel programs on a cluster of machines, using paging to give the appearance of real shared memory. When a thread tries to access a page that's on another machine, the page fault will give the DSM system a chance to fetch the page over the network from whatever machine currently stores.
• Build a distributed RAID in the style of FAB. Maybe you can get standard operating systems to talk to you network virtual disk using iSCSI or Linux's NBD (network block device).
• Build a coherent caching system for use by web sites (a bit like memcached), perhaps along the lines of TxCache.
• Build a distributed cooperative web cache, perhaps along the lines of Firecoral or Maygh.
• Build a collaborative editor like EtherPad.