6.824 Lab 5: Distributed Ticker Tape

Due: Thursday, October 25, 2001 before class

Introduction

The City of Cambridge wishes to create an electronic stock exchange, and has hired you to build a prototype distributed ticker tape system. The City intends that each stock broker put a computer on the Internet that runs your ticker server. Whenever a broker buys or sells stock, the broker will submit a short description of that trade to the local ticker server. The ticker servers will exchange information about all trades, and each server will print out the description of every trade submitted to the system.

A key requirement is that all the servers must print out the trades in the same order. Brokers will get upset if it seems that they are not being given the same information as everyone else, because they make decisions about what to buy and sell based both on the latest prices and on price trends.

The larger purpose of this assignment is to learn about protocols for maintaining replicated data. If you have some data (a file system, for example) with identical replicas on a number of servers, you might want to perform updates on that data in a way that keeps the replicas identical. If you can arrange to perform the updates in the same order on all the replicas (and the updates are deterministic), then the data will remain identical. An important part of this is making sure all the replicas process the updates in the same order. That's what you'll do for this assignment, though with an unrealistically optimistic set of assumptions about network and failure behavior.

Requirements

Your server will take command-line arguments telling it its own port number, and the host names and port numbers of all the other servers in the system.

We supply you with a client program that submits new trades to the local server, using RPC. Each trade has a text tag. When a server sees a new trade submitted by a local client, it should tell all the other servers in the system about the trade. How this happens is up to you. We supply you with a prototype server that uses RPC (over UDP) to talk to the other servers; we suggest you start by modifying this server.

A server will receive notifications about trades from time to time from other servers. It should print each trade's tag on the standard output. All the servers should print the trade tags in the same order. The servers need not print the tags immediately when they arrive.

Here are some other rules you must follow:

Every live server must print out a trade within 7 seconds of when it was originally submitted by a client.
Your system must continue to operate even if some servers die (which you can simulate with ^C). Dead servers are not required to print trades. If a server originates a trade but dies less than 5 seconds later, other servers are not required to handle that trade correctly.
We will test your server with the client program we supply, so you should not change the submit RPC interface.
Your server must work when more than one server is running on the same machine (with different ports), and when when servers are running on different machines.
Except as noted above, all servers must print all trades in the same order.
Your server must pass the test-ticker.pl script (see below).

Here are some slightly unusual things you are allowed to assume about the system:

You are allowed to assume that the network will deliver your RPCs within five seconds of when you make the RPC, as long as the sending and receiving hosts are alive. The five seconds includes time required to retransmit lost RPCs, if required.
You are allowed to assume that the clocks (i.e. gettimeofday() and time()) on the different servers agree to within one second of each other.
If a computer or server fails, it will never come back to life.
The computers running your servers may fail, but you are allowed to assume fail-stop behavior.

These are optimistic assumptions; they should make your task easier. They are not likely to be true for real systems, which means your solution may not be very useful. In class we'll discuss some techniques that can cope with more general failure scenarios.

Getting Started

We supply you with a complete client, an RPC interface definition file, a skeleton server, and a test program: ticker-client.C, ticker.x, ticker-server.C, and test-ticker.pl. You can write your own makefile or use this one that should work on the class servers.

The server expects you to give it a unique numeric ID, a local port number on which to receive RPC/UDP packets, and (for each other server) a host name and port number. To test the server, run this on blood in one window:

blood% ./ticker-server 1 2001 sweat 2001

You may have to modify the port numbers in case someone else is running this test at the same time. Run this on sweat in another window:

sweat% ./ticker-server 2 2001 blood 2001

In a third window, submit a few trades:

blood% ./ticker-client localhost 2001 IBM-90
sweat% ./ticker-client localhost 2001 DELL-16

Ideally, both servers would print either

IBM-90
DELL-16

or else they would both print

DELL-16
IBM-90

Either is acceptable, unless 7 or more seconds passed between submitting the two trades, in which case they must appear in order of submission. In fact you'll notice that the server we supply you with doesn't work; only one of the servers prints each trade.

A reasonable first step would be to modify the server code to forward a copy of each submission to each of the other servers. You can use RPC to do this, borrowing code from ticker-client.C. You'll probably need to add a new procedure to ticker.x.

Testing your Server

Once you have a server that you think might work, you can do a quick test as follows. Start two servers as above. Then run the client program with these arguments:

% ./ticker-client -r 5 sweat 2001 blood 2001

This generates 5 submissions to each of the servers indicated, in rapid succession. (This isn't quite correct, since the client is only allowed to submit to the local server, but it's just for testing.) If your servers always agree on the order of outputs when you run the client this way, you're well on your way to finishing the lab.

We will use the test-ticker.pl program to decide whether your server works. You can run it as follows:

% ./test-ticker.pl ./ticker-server ./ticker-client
One server, one transaction: passed
Two servers, one transaction: passed
Two servers, two transactions: passed
Two servers, ten concurrent transactions: passed
Five servers, continuous transactions: passed
One of two servers fail: passed
Three of six servers fail: passed

Your server should pass all the tests.

Handin procedure

To turn in your assignment place a gzipped tar archive named ticker.tar.gz in the directory ~/handin/lab5. The tar archive should expand to a single directory named 'ticker' which contains all the files necessary to build your application by running the 'gmake' command in the directory. The resulting binaries should be named ticker-client and ticker-server.

The lab is due on Thursday, October 25 before class.