CS223 Project 1
Due at the end of quarter

• Overview
• Getting Started
• Implementation Hints
• How to submit

---

Project1 Overview

In this project, you are to implement a simple Resource Manager (RM) that supports concurrent transactions with the ACID properties. Specifically, the RM stores data about flights, rental cars, hotel rooms, and customers. Multiple clients access this RM concurrently to query and update the data through a transactional interface. It is the responsibility of the RM to ensure that these concurrent transactions are executed correctly, i.e., in accordance with the ACID requirements.

Conceptually, the RM stores the following tables:

FLIGHTS(String flightNum, int price, int numSeats, numAvail)
HOTELS(String location, int price, int numRooms, int numAvail)
CARS(String location, int price, int numCars, int numAvail)
CUSTOMERS(String custName)
RESERVATIONS(String custName, int resvType, String resvKey)

To keep things simple, we'll make some assumptions:

• There is only one airline, and all seats on a given flight have the same price; flightNum is a primary key for FLIGHTS.
• All hotel rooms in a given location cost the same; location is a primary key for HOTELS.
• All rental cars in a given location cost the same; location is a primary key for CARS.
• custName is a primary key for CUSTOMERS.
• The RESERVATIONS table contains an entry corresponding to each reservation made by a customer for a flight, car, or hotel, as follows: resvType indicates the type of reservation (1 for a flight, 2 for a hotel room, and 3 for a car), and resvKey is the primary key of the corresponding reserved item.
• In the FLIGHTS table, numAvail is the number of seats available to be booked on a given flight. For a given flightNum, one of the database consistency conditions is that the total number of reservations for a flight (in the RESERVATIONS table) plus the number of available seats must add up to the total number of seats in the flight. Similar conditions hold for the CARS and HOTELS tables.

We provide the standard interface for the ResourceManager (ResourceManager API). Among other things, the interface allows rows to be added, deleted, and modified for each of the tables the RM stores. Your job is to write the implementation for the interface we provide.

The RM supports transactions. A transaction calls the start() method of ResourceManager to get a unique transaction id. All subsequent calls to the RM include the transaction id. Finally, the transaction calls commit() or abort(). A typical client transaction might look something like the following: (Of course in reality you should be checking for return values and catch exceptions). Also look at Client.java for another simple example.

int xid = rm.start();
// If it's cheap enough and there're seats left
if (rm.queryFlightPrice(xid, "223") < 300 && rm.queryFlight(xid, "223") > 0) {
   rm.reserveFlight(xid, "John", "223");
}
rm.commit(xid);

Concurrency control is done through two-phase locking. In particular, when a client requests to query or update information, your RM implementation is responsible for locking things appropriately, and releasing all locks only when a transaction commits or aborts. We have provided a lock manager to help with this task. The lock manager supports the following API (this is pseudo-code, the actual LockManager API is here).

• lock(xid, thingBeingLocked, read|write) throws DeadlockException
• unlockAll(xid)

As before, xid is the unique transaction identifier. The lock manager handles deadlocks by a timeout mechanism (currently set at 10 sec). A failed (deadlocked) lock operation throws a DeadlockException. The lock manager also handles lock conversion (also known as lock upgrade). Lock upgrade happens when a transaction that has a read lock on an item needs a write lock on the same item.

lock(xid, foo, read); // read foo
lock(xid, foo, write); // write foo

Other transactions may have read locks on, so deadlock is possible when you upgrade locks.

---

Getting Started

Your code is expected to work on any Java-compatible environment with a Java 2 SDK. You are free to work on any machine, including your own PC, where you can find a Java environment.

The supplied codebase (here) has two packages: lockmgr and transaction. The lockmgr package implements the class LockManager (API). You won't need to modify the contents of this package. The transaction package has some basic classes to get you started with your implementation. It contains the interface ResourceManager (API). Note that you are NOT to modify this file. Your implementation of the RM goes into the class called ResourceManagerImpl (plus additional new classes that you define as necessary), which implements the ResourceManager interface. The current ResourceManagerImpl.java contains a toy implementation which you will replace.

The transaction directory also contains a simple client in Client.java. During your implementation, you may want to write more sophisticated clients to test against your RM, but you're not required to turn these in. In fact, for grading, we will link your code with our own version of Client.java and see if you RM handles all cases correctly.

The client communicates with the RM via Java RMI (Remote Method Invocation). You can find a tutorial on RMI here. However, our toy ResourceManagerImpl and Client already have all the necessary RMI code for this part. The only thing you have to do is to modify the first line in transaction/Makefile to give yourself a unique port number for the RMI registry, so that you don't conflict with other CS223 students who happen to work on the same machine as you (see later).

You will turn in all your source files plus a README file for submission. Grading will be based largely on correct functionality. The readme file should meet the following requirements: (1) Briefly explain your design and implementation. It should include enough details for the grading. (2) Write the file in about 2-3 pages. In addition, you should make sure that your code should work following the instructions. Don't send me your own instructions to test the code.

We have provided test cases to help you design and test your program. Use the following steps to get started.

• Download the tarball.
• Put the tarball in a directory you've created for this class, say, ~/cs223
• cd ~/cs223
• gunzip project1.tar.gz
• tar xvf project1.tar
• cd project/lockmgr
• make
• copy your submissions directory to ./submissions
• cd ../transaction
• Think of a random number between 2000 and 5000, say, 2100, and change the value of RMIREGPORT in first line of Makefile from 1099 to this number. This is the port number where your rmiresgistry will be listening. Giving it a random number will ensure that your rmiresgistry doesn't conflict with somebody else's.
• cd ../test.part1
• cp -r ../../submissions/* ../transaction
• rm -r ../transaction/Client.java
• cp -f Client.java ../transaction/
• cd ../transaction
• make clean
• make server
• make client
• rmiregistry -J-classpath -J.. 2100 &
• cd ../test.part1
• setenv CLASSPATH .:gnujaxp.jar
• /usr/bin/javac RunTests.java
• java -DrmiPort=2100 RunTests MASTER.xml

Make sure the "java" command and the "rm" command in RunTests.java and Client.java are properly set based on your shell environment. The results will be put in ./results/grades.txt. If you want, you can modify the file project/test.part1/MASTER.xml to change the scripts you want to test. You are STRONGLY suggested to run the scripts ONE BY ONE.

Structure: (1) RunTest.java parses the file MASTER.xml. For each line, it activates "Client.java" by passing the script name under the "scripts" directory. (2) Client.java starts the necessary RMI modules. Then it reads and parses the script file, and interpret each line to take the corresponding action.

---

Implementation hints

Here is a suggested approach to implementing the required functionality in an iterative manner (note that the steps below may not all require the same programming effort; some steps are harder than others):

• Step 1. Basic RM. Ignore atomicity to start with. Ignore persistence and assume that the data is stored in memory. One possible implementation is to store the data in one or more hashtables. You could have one hashtable per database table, or combine all database tables into a single hashtable. Each row in a table would then be a hashtable entry, keyed by the row's primary key. You might consider using a Java class to represent each kind of row e.g., a class corresponding to a FLIGHT row might have data members for flightNum, price, numSeats, and numAvail, and perhaps some additional meta-data needed to implement transactional properties.

The RESERVATIONS table doesn't have a primary key, but it's mostly looked up by the custName; so one possible implementation is to combine it with the CUSTOMERS table. That is, have a hashtable indexed by custName, with each hashtable entry containing a list of (resvType, resvKey) pairs.

Note that in our simple data model, you can have only one price per location, so the net effect of

 
addCars(T1, "Irvine", 4, $52);
addCars(T2, "Irvine", 7, $54);

should leave 11 cars at $54, not 7 cars at $54 and 4 cars at $52.

• Step 2. Atomicity. Now add atomicity to the RM using shadowing. Keep two copies of the in-memory database, with a pointer to the active copy. Keep each active transaction's updates in a separate hashtable. When the transaction commits, merge the transaction's updates into the non-active database copy and then swap the active database pointer.

In the current system, the only failure to handle is an abort. Since the memory image is lost when the process terminates, there doesn't need to be any recover() method at this stage.

• Step 3. Isolation. The RM should lock data appropriately for each transaction, and unlock data when the transaction commits or aborts. You might experiment with different locking granularities at this stage. In general, we would prefer that you lock data at the finest granularity possible for any operation, thus ensuring the maximum concurrency. The RM needs to handle deadlocks properly: when a transaction is deadlocked (as indicated by DeadlockException thrown by the LockManager), the RM should forcibly abort the transaction.
• Step 4. Durability. Add persistence and recovery to the Resource Manager. All state is stored on disk. (You might find Java's java.io.ObjectOutputStream class handy; it allows you to output a stream of objects to a file on disk and the corresponding ObjectInputStream can read the objects back into memory). The disk image is updated when a transaction commits. Shadowing is used to ensure atomicity: two copies of the database are maintained on disk, as well as a pointer to the active database. On startup, the RM must implement a recover() method to restore its state from the state on disk, and gracefully handle various exceptions, such as operations called with unknown (or forgotten) transaction ids.

Testing
We will test the Simple RM using multiple clients and a single resource manager. The Technical Interface methods in ResourceManager are defined to make it easier to test for faults. The shutDown() method implies that the RM should shut down gracefully. In this case, that means waiting for all running transactions to terminate, and cleaning up its files, so that the next time it starts up, it does not attempt to recover its state. The dieNow() method makes the RM call System.exit() immediately, to simulate a system failure, leaving the database in its current state. When the RM next starts up, it will have to recover to a consistent state. Instead of killing the RM immediately, the dieBeforePointerSwitch() and dieAfterPointerSwitch() methods set flags so that the RM will call System.exit() in the middle of the next commit operation. See the API for details.

---

How to Submit

Make sure:

• You have not modified WorkflowController.java or the LockManager code.
• All your code is confined to the project/transaction directory (and possible subdirectories).
• Your server puts all files in a directory called data. If the directory does not already exist, your server creates it.
• In project/transaction, after a "make clean", your server compiles without errors with "make server".
• You can compile Client.java with "make client".
• You can start components of the system with the commands given in the original Makefile distributed to you. For example
  java -classpath .. -DrmiPort=1234 -DrmiName=RMFlights -Djava.security.policy=./security-policy transaction.ResourceManagerImpl
  starts the RM for flights, where 1234 is the port of the running rmiregistry.
• You create a file named README. Use the same requirements of the file as part 1.

Steps to submit:

1. On your machine, cd to your project/transaction directory.
2. Make sure you "make clean" to get rid of all .class files.
3. tar cvf - * | gzip > ../cs223-project1.tar.gz (for project 1) which will tar all the files under the current directory (including subdirectories) into a tar file, then compress it into a zipped file.
4. Use eee.uci.edu to submit your file.

Notes

• You should use a Java-compatible environment with a Java 2 SDK. If you do "java -version", you should see the version of your java environment.
• Put all files that your RM creates (database files, master pointer files, transaction lists...) in a directory called "data" in the project/test.part1 directory. This way one can simply do a "rm -rf data" to remove the entire database state. When your RM starts up, it will 1) check if "data" directory exists; if not, create one; 2) check if the relevant files are there; if not, create an empty database; if yes, try to "recover" from those files.
• Let's assume that we do not expect more than one transaction to frequently be working on reversations for the same customer at the same time. So, assuming you merge the RESERVATIONS table with the CUSTOMERS table, it will be acceptable if, instead of locking individual reservation rows, you decide to lock the entire customer row. However, again, it is never acceptable to do table-level locking.
• The "make runserver" command attempts to start the rmiregistry at your unique port number. However, if you already have a previous instance of your rmiregistry running, you'll get a "...Port already in use..." exception. This is not a problem since the server (RM) should still work. Or, you can always use "ps -ef|grep $USER|grep rmiregistry" to find your old rmiregistry and kill it. For Part 2, this is no longer an issue because the registry is started explicitly with "make runregistry".