Distributed Storage Systems

Introduction

This is the first in a sequence of labs in which you'll build a multi-server file system in the spirit of Frangipani. In this lab you'll supply the logic for a lock server that you'll use in subsequent labs to keep multiple file servers consistent.

At the end of all the labs, your file server architecture will look like this:

----------------     -------------
|              |     |           |
|   App   FS---|-----| block srvr|----- FS on other hosts
|    |    |    |  |  |           |  |
|--------------|  |  -------------  |
|    |    |    |  |  -------------  |
|    Kernel    |  |  |           |  |
|  NFS Client  |  ---| lock srvr |---
|              |     |           |
----------------     -------------

This architecture is appealing because (in principle) it shouldn't slow down very much as you add client hosts. Most of the complexity is in the per-client FS server, so new clients make use of their own CPUs rather than competing with existing clients for the server's CPU. The block server is shared, but hopefully it's simple and fast enough to handle a large number of clients. In contrast, a conventional NFS server is pretty complex (it has a complete file system implementation) so it's more likely to be a bottleneck when shared by many NFS clients. The only fly in the ointment is that the FS servers need a locking protocol to avoid inconsistent updates. In this lab you'll implement the core logic of a lock server.

Getting Started

heart% cp /home/jinyang/lab1.tgz .
heart% tar xzvf lab1.tgz
heart% cd lab1
heart% make

heart% ./server1 3772 

hand% cd ~/lab1
hand% ./lock_demo heart 3772
Asking for the lock...
Got the lock. Sleeping...
Releasing the lock.
hand% 

The lock server we've given you always grants lock requests immediately, and ignores release RPCs. As a result it will give the same lock to multiple clients, which makes for a pretty poor locking system. You can see this for yourself by starting two lock_demo programs in two different windows at the same time -- you will see that they both say "Got the lock" at the same time, rather than one waiting for the other to release.

We have supplied you with a program lock_tester that tests whether the server grants each lock just once at any given time. You run lock_tester with the same arguments as lock_demo. A successful run of lock_tester (with a correct lock server) will look like this:

hand% ./lock_tester heart 3772
Acquire a, release a, acquire a, release a:
Acquire a, acquire b, release b, release a:
Acquire a, acquire a, release a, release a:
Acquire a and b from two clients:
lock_tester: passed tests

Requirements

Your lock server must pass the lock_tester tests. We will test your lock_server with the standard client code, not your copies of the client code. Thus you should not make any significant changes to files other than lock_server.C and lock_server.h.

About the Lock Server

The lock server can manage many distinct locks. Each lock has a name; a name is a string of bytes. Names might not be printable ASCII, which is why the lock software prints lock names in hex rather than ASCII. The set of locks is open-ended: if a client asks for a lock that the server has never seen before, the server should create the lock and grant it to the client.

lock_client.C and lock_client.h implement a client-side interface to the lock server. The interface provides acquire() and release() functions, and takes care of sending and receiving RPCs. See lock_demo.C for an example of how an application uses the interface.

Different modules in a single application might ask for the same lock at roughly the same time. lock_client.C handles this by sending two separate acquire RPCs to the server. When one of the modules is done with the lock, lock_client.C releases the lock back to the server and waits for a second grant.

Tips

Coding plan

You'll need to modify class LS in lock_server.h to keep track of which locks are currently granted and which clients are waiting for locks. There is just one instance of class LS in the lock server.

You'll need to modify the LS::acquire() function in lock_server.C to check the status of a lock when an acquire RPC arrives, and only send a grant if the lock isn't currently held. acquire() should also update your record of which locks are held and what clients are waiting.

You'll need to modify LS::release() in lock_server.C in order to update the lock's status, and to potentially send a grant RPC to a waiting client.

To give you a feel for how much work should be involved, our solution adds about 40 lines of code to lock_server.C.

libasync

Both lock_client.C and lock_server.C are written in an event-driven style using the SFS libasync libraries. You can learn about event-driven programming in Section 4.4 of the NFS toolkit paper, or in Using Libasync (you can skip Section 2.2), or by reading the Libasync Tutorial. You can find the source for the libraries in /home/dss/sfs-0.8pre or at the SFS project page.

You may want to use the ihash template class to store state about the set of active locks, and the list template class to store the list of clients waiting for a lock. You can see examples of their use in lock_client.h and lock_client.C.

You can declare an ihash hash table as follows:

struct entry {
  ihash_entry<entry> hlink; // ihash uses this
  str name;    // the hash key of this entry
  int a_field; // data you want to store in the entry
  int another_field;
};
ihash<const str, entry, &entry::name, &entry::hlink> table;

An ihash hash table has three operations defined on it. table[key] yields a pointer to the entry with the indicated key, or 0 if there's no such entry. table.remove(entry *) removes an entry, given a pointer to the entry. table.insert(entry *) inserts a new entry, given a pointer to the new entry. You'll need to allocate the entry with the C++ new operator, like so:

entry *e = new entry();
// initialize e, particularly e->name
table.insert(e);

Here's an example of a definition of a list, called lst:

struct element {
  list_entry<element> llink;
  // things you want to put in each list element...
};
list<element, &element::llink> lst;

element *i;
for(i = lst.first; i; i = lst.next(i)){
  ...;
}

An alternative to the list class is the vec class which is another way to manage a dynamic list of elements. Compared to list, vec does not require a structure with an internal llink object. Thus, a vec is parameterized with only one argument: the class to be stored in the vec. vecs allow random access much like an array, elements can be added to the end of the vec, and then can be removed from either the front or the back. The vec class interface is specified in /home/dss/include/vec.h.

The str class implements constant, garbage-collected (reference counted) variable-length strings. The constructor str("xxxx") creates a new str object initialized from the C string "xxxx". The str method cstr() returns a null-terminated C string pointing to the contents of the str object. Equality with == is defined on str objects, and returns true iff the two strings contain the same bytes. str objects have an explicit length, so they can contain nulls.

Don't modify a str. Don't modify the result of str.cstr(), since cstr() returns a pointer to the str's internal storage.

Debugging

You may be able to find memory allocation errors with dmalloc by typing this before running server1:

heart% dmalloc low -l dmalloc.log -i 10

You can see a trace of all RPC requests that your server receives, and its responses, by setting the ASRV_TRACE environment variable. There is a corresponding ACLNT_TRACE variable that displays RPCs made by a process and their responses. Since the lock server must both receive and make RPCs, you may want to run with both:

heart% env ASRV_TRACE=10 ACLNT_TRACE=10 ./server1 ...

Smaller numeric values will display information less verbosely.

Collaboration Policy

Handin procedure