V22.0480-005 Lab 4: Ticker server

Due date: Thursday April 15, 3:30pm
Free extension to midnight if you attend lecture

Introduction

After the compensation scandal at the New York Stock Exchange, the City of New York has hired you to prototype an alternative, more decentralized stock exchange. 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:

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

These are optimistic assumptions, which you might not be able to make about a real system; they should make your task easier.

Getting Started

We supply you with a complete client, an RPC interface definition file, a skeleton server, and a test program, in ~class/src/ticker.tar.gz. To unpack, run:
% tar xvfz ~class/src/ticker.tgz
ticker
ticker/minirpc.c
ticker/server.c
ticker/minirpc.h
ticker/ticker_prot.x
ticker/client.c
ticker/.cvsignore
ticker/Makefile
% cd ticker
% gmake
rpcgen -C -h -o ticker_prot.h ticker_prot.x
cc -c -ansi -Wall -g client.c
...
cc -ansi -Wall -g -o ticker-server server.o ticker_prot_xdr.o ticker_prot_svc.o ticker_prot_clnt.o minirpc.o -L/usr/local/lib -ldmalloc
% 

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, you might run the following on class6:

class6% ./ticker-server 1 2001 class8 2002
And this on class8:
class8% ./ticker-server 2 2002 class6 2001
You may have to modify the port numbers in case someone else is running this test at the same time. You can also run multiple copies on the same machine, using different UDP port numbers. Now running on class6, type this: In a third window (on either machine), submit a few trades. For example:
class6% ./ticker-client localhost 2001 IBM-90
class6% ./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.

Interfaces and hints

You will need to modify the files server.c and ticker_prot.x to complete this lab. You should not modify the TICKER_PROC procedure, as this is used by the ticker-client program. Instead, you will probably want to add at least one procedure to the TICKER_PROG RPC interface, for ticker servers to use when contacting each other. You can do this by adding appropriate structures to the ticker_prot.x protocol definition file. For instance, you might add something along the lines of the green text here:
struct xaction_args {
  /* XXX - You must place fields you want in the argument here */
};

program TICKER_PROG {
  version TICKER_VERS {
    submit_result TICKER_SUBMIT (submit_args) = 1;
    void TICKER_XACTION (xaction_args) = 2;
  } = 1;
} = 400001;
For each procedure that you add, you must add a server side dispatch routine. This function will be named by the procedure name you have chosen (translated into lower case), with the version number (1) and svc appended, separated by underscores. In the example above, you would want to add the following procedure to your program:
void *
ticker_xaction_1_svc (xaction_args *argp, struct svc_req *rqstp)
{
  /*
   * XXX - You must write this code
   * Arguments are in argp.  (You can ignore the rqstp parameter.)
   */

  return NULL;
}

Note that one thing you probably don't want to do is block waiting for RPCs to other servers. If, for example, when your ticker server received a trade it made synchronous RPCs to every other ticker server when you got a trade, you could easily end up with deadlock when two servers receive trades simultaneously. (Each will be waiting for an RPC to return from another server before servicing any other RPCs.)

Instead, we have supplied you with two functions for making asynchronous RPCs. These functions make an RPC and return immediately, without waiting for the response, but keep retrying in the background in case a UDP packet is lost. These functions are declared in the header file minirpc.h:

Because you may want to wait around for a while before printing a trade (to make sure there aren't any previous trades you haven't heard of), server.c contains a skeletal function timer that you can ask to have called once per second. The following variables (declared in minirpc.h) are useful for timer:

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 class6 2001 class8 2002
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.

Your lab will be graded with the test-ticker program. You should run manually to see if your server works before handing it in. You can run it as follows:

% test-ticker ./ticker-server
One server, one transaction (no points): passed
Two servers, one transaction (1 point): passed
Two servers, two transactions (1 point): passed
Two servers, ten concurrent transactions (2 points): passed
Five servers, continuous transactions (3 points): passed
One of two servers fail (1 point): passed
Three of six servers fail (2 points): passed
FINAL SCORE: 10/10
[internal use only: student:10:1081213431:78d892ccade421ccf638:9a26ed763484f3407f98]
% 
(Ignore the last line, it is just for use in grading.)

Turning in the assignment

In order to turn in the assignment, you just need to run the command gmake handin. You should see output like the following:

% gmake handin
gmake clean
...
`echo ~class`/bin/test-ticker ./ticker-server | tee score
One server, one transaction (no points): passed
Two servers, one transaction (1 point): passed
Two servers, two transactions (1 point): passed
Two servers, ten concurrent transactions (2 points): passed
Five servers, continuous transactions (3 points): passed
One of two servers fail (1 point): passed
Three of six servers fail (2 points): passed
FINAL SCORE: 10/10
[internal use only: student:10:1081214349:78d892ccade421ccf638:fc5504adf0f2a980dd76]
cp ticker-0.tar.gz score ticker-server `echo ~class`/handin/lab4/$USER/
================================================================
Your assignment has been turned in Mon Apr  5 21:19:09 2004.
Your final score is 10 point(s).
================================================================
% 
Make sure the last four lines look similar to the above. In particular, the output must say "Your assignment as been turned in". If you have any problems with submitting the assignment, please contact the TA or instructor.

Extra credit

For two points of extra credit, if your ticker server passes all the tests, you can modify your server so that in the ordinary case (no network partitions and no failed servers) trades print almost immediately on all terminals. Put a text description of how you implemented this, and exactly how your protocol works, in a text file called extra-credit.txt, and copy this file to your handin directory, ~class/handin/lab4/`logname`/. Obviously the enhanced server must still pass all the tests in test-ticker.

References

The following references may be useful in completing this assignment: