In this lab you will replicate your lock server using the replicated state machine (RSM) approach (see Schneider's RSM paper for a good, but non-required, reference. We will also discuss an example replicated state machine in Lecture.) In the replicated state machine approach, one machine is the master and the others are slaves. The master is in charge of receiving requests from clients and executing them on all replicas. To ensure that all replicas have identical state, the replicas must execute all requests in the same order and all requests must produce the same result on all replicas (i.e., the handlers must be deterministic). The RSM uses the Paxos protocol implemented in the previous lab to agree on the current master and node membership to cope with failed and re-joined replicas.

To ensure all requests are executed in a unique total order, the master assigns each request a viewstamp number which dictates the total order. The viewstamp consists of two fields, the view number (obtained from Paxos) and a monotonically increasing sequence number. The viewstamps assigned to all RSM requests dictate a total order among them. In particular, viewstamps with a lower view number are ordered before those with a higher view number and within the same view number, viewstamps with lower seqnos are ordered before those with higher seqnos. How do we guarantee all viewstamps form a unique total order? This is because Paxos guarantees all view numbers form a total order. Additionally, within each view, all nodes agree on the current view's membership and thus each RSM node can use the agreed upon membership to agree on a unique master who is the only one that can assign each request an increasingly seqno to properly order requests within a view.

The primary task in the lab is building a RSM library on top of our existing RPC library so that you can plug in any RPC program you have written so far and replicate it. To ensure the appropriate behavior, however, there are certain constraints on the RPC handlers. Most importantly, the RPC handlers must run to completion without blocking, and be deterministic and idempotent. These constraints will ensure that all replicas execute all requests in the same order and with the same result. Once you have built the RSM library we will ask you to replicate the lock server you built in previous labs using RSM. In this lab it should become clear why we asked you to write the lock server in a way so that there are no blocking RPC handlers, and why we asked you to include sequence numbers.

Getting Started

Begin by updating your lab directory with the new infrastructure code for lab 8. Since you are building on the past labs, make sure your code passes all tests for previous labs before starting in on this lab.

% cd ~/lab
% git commit -am 'my solution to lab7'

Created commit ...
% git pull
remote: Generating pack...
% git checkout -b lab8 origin/lab8
Branch lab8 set up to track remote branch refs/remotes/origin/lab8.
Switched to a new branch "lab8"
% git merge lab7

We provide you with some skeleton code of the RSM library. The library has the client and server class for RSM in files rsm_client.{cc,h} and rsm.{cc,h}.

The RSM client class (rsm_client) is used by a client program to request service from the master replica in the RSM. The RSM client takes in its constructor the address of a known replica, and immediately contacts the node to learn the addresses of all replicas as well as the current master. The client program (e.g. the lock_client class) can use the call method on the RSM client object (just as if it were an RPC client). The call method on RSM client will marshall RSM request and send it via the rsm_client_protocol::invoke RPC to the master replica. (The RPC protocol between the RSM client and RSM server (replica) is defined in the rsm_client_protocol class in file rsm_protocol.h).

To turn any server program into a replica in the RSM service, your application (e.g. lock_server_cache class) creates an RSM server object (rsm) and uses it in place of the normal RPC server rpcs object. The RSM server constructor creates a config object with arguments consisting the id of the first replica ever created and the id of this server. The RSM server registers a number of RPC handlers and spawns off a recovery thread to synchronize state with the master replica when Paxos has agreed on a stable view.

Once the master is in a stable state, it can process invoke RPCs from RSM clients. For each request, the master assigns it the next viewstamp number with an increasing seqno. The master then issues an invoke RPC on all replicas in the current view. The replicas unmarshall the request, and execute the registered handler. Note that the replicas must execute requests in the same total order as dictated by the requests' viewstamps without any gaps in seqno. If the master has succeeded in executing a request on all replicas (including itself), it will reply to the client. If the master has encountered replica failures during this process, it should instruct its config object to initiate a view change. Occasionally, an RSM client might send its request to a non-master node, in which case the node should reject the client's request by replying with rsm_client_protocol::NOTPRIMARY. The client will then call the members RPC to get an updated list of replicas.

When a failed replica re-joins a running RSM, it has potentially missed many requests and must do a state transfer to bring its state in sync with the other replicas before it can process any requests. Additionally, when the master has encountered a failure during the process of invoking the client request at various replicas, some replicas might have executed the request while others not. Thus, the RSM servers must be able to synchronize its state properly from the agreed upon master node before processing any client requests. We provide some skeleton code to do this; the interface is defined in rsm_state_transfer.h.

Your Job

Your job is to turn the lock_server_cache into a RSM service. Our measure of success is surviving failed master and slaves and incorporating re-joined replicas back into a running RSM. For this lab, you'll need to pass tests 8-16 of (as well as making sure all the file system tests from previous labs work).

The tester picks random ports for the lock server replicas, and starts them up. It redirects output to log files, named as lock_server-[master_port]-[my_port].log. The log for the tester is lock_tester-[master_port].log. Here is the output of a successful run of

% ./ 8 9 10 11 12 13 14 15 16
test8: start 3-process lock service
./lock_tester: passed all tests successfully
test9: start 3-process rsm, kill first slave while tester is running
./lock_tester: passed all tests successfully
test10: start 3-process rsm, kill second slave while tester is running
./lock_tester: passed all tests successfully
test11: start 3-process rsm, kill primary while tester is running
./lock_tester: passed all tests successfully
test12: start 3-process rsm, kill first slave at break1, continue with 2, add first slave
./lock_tester: passed all tests successfully
test13: start 3-process rsm, kill slave at break1 and restart it while lock_tester is running
./lock_tester: passed all tests successfully
test14: start 5-process rsm, kill slave break1, kill slave break2
./lock_tester: passed all tests successfully
test15: start 5-process rsm, kill slave break1, kill primary break2
./lock_tester: passed all tests successfully
test16: start 3-process rsm, partition primary, heal it
./lock_tester: passed all tests successfully
tests done
When debugging, you might want to run the tests individually by just specifying a single test number. You can also specify the same random seed values across run to make choose the same set of random ports. (e.g. ./ -s 89362 8) Once your lab works, make sure it is able to pass all (including test 0-7) tests of ./ many times in a row as well as the file system tests from previous labs.

Important: As in the previous lab, if fails during the middle of a test, the remaining lock_server processes are not killed and the log files are not cleaned up (so you can debug the causes.). Make sure you do 'killall lock_server; rm -f *.log' to clean up the lingering processes before running again.

Detailed Guidance

Step One: RSM without failures

As the first step, just get the RSM working, assuming that none of the replicas will fail. The basic protocol is: This will involve filling in the various functions in mentioned above. In particular: To change your existing lock server/client to use the RSM objects:

Upon completion of step one, you should be able to pass './ 8'. This test starts three lock_servers one after another, waits for Paxos to reach an agreement, then performs tests on the lock service using lock_tester.

Step Two: Cope with Backup Failures and Implement state transfer

In this step, you will handle node failures as well as joins in a running RSM. Upon detecting failure or a new node joining, the underlying Paxos protocol is kicked into action. When Paxos has reached an agreement on the next new view, it calls the rsm object's commit_change() to indicate that a new view is formed. When a new view is first formed, the rsm::inviewchange variable is set to true, indicating that this node needs to recover its RSM state before processing any RSM requests again. Recovery is done in a separate recoverythread in the rsm::recovery() method.

After a view change, each replica should recover by transferring state from the master. Its state must be identical to the master's before processing any RSM requests in the new view. Once recovery is finished, the replica should set its rsm::inviewchange variable to false to allow the processing of RSM requests. The master should not send any requests to the backups until all the backups have recovered.

To implement state transfer, first make lock_server_cache into a subclass of rsm_state_transfer interface. Second, implement the marshal_state and unmarshal_state methods for lock_server_cache. Use the YFS RPC marshalling code to turn various internal state into strings and vice versa. For example, if state of your lock server consists of a std::map called locks that mapped lock name (std::string) to a list of clients waiting to grab the lock (std::vector), the code might look roughly as follows:

lock_server_cache::marshal_state() {

  // lock any needed mutexes
  marshall rep;
  rep << locks.size();
  std::map< std::string, std::vector >::iterator iter_lock;
  for (iter_lock = locks.begin(); iter_lock != locks.end(); iter_lock++) {
    std::string name = iter_lock->first;
    std::vector vec = locks[name];
    rep << name;
    rep << vec;
  // unlock any mutexes
  return rep.str();


lock_server_cache::unmarshal_state(std::string state) {

  // lock any needed mutexes
  unmarshall rep(state);
  unsigned int locks_size;
  rep >> locks_size;
  for (unsigned int i = 0; i < locks_size; i++) {
    std::string name;
    rep >> name;
    std::vector vec;
    rep >> vec;
    locks[name] = vec;
  // unlock any mutexes

In the lock_server_cache constructor, call the rsm's set_state_transfer method with this as the argument so that rsm can call lock_server_cache's marshal_state and unmarshal_state function later.

Now you should be able to pass './ 9 10'. These tests starts three lock servers and kills or restarts the second slave while running the lock_tester simultaneously.

Step Three: Cope with Primary Failures

The rsm_client::invoke() method handles two special cases. First, if the replica that the client sends the invoke RPC to is no longer the primary, that replica returns rsm_client_protocol::NOTPRIMARY. In this case, the client calls init_members(), which sends a members RPC to the old primary to update its list of replicas. Then the client retries its request.

The second case is where the replica isn't responding at all (so the invoke RPC fails). In this case, init_members() won't work because the members RPC will also fail. In this case, the client calls rsm_client::primary_failure(), which should make it forget about the failed replica and ask a different replica for an updated list of members. Then invoke() should retry as before.

We have given you most of the code you need. Your job is simply to write rsm_client::primary_failure() to handle the second case.

If you did not use sequence numbers when implementing your caching lock server, you will need to add them now. In lab 5, the sequence numbers in the RPC layer were sufficient to avoid duplicate requests. However, in this lab, consider what happens if a replica crashes while some replicas have executed the request and others have not. A view change will occur, and the client will re-send the request in the new view. If the new primary has already executed the request, the RPC handler in lock_server_cache will be invoked twice. Note that if the primary crashes while (or shortly after) executing an acquire or release RPC, after recovery it will be ambiguous as to whether the appropriate retry or revoke RPCs were sent in the previous view.

A simple way to address this is to have clients that are waiting to acquire locks retry automatically every 3 seconds, even in the absence of a retry RPC. The servers can use sequence numbers (see Lab 5 for details) to identify duplicate acquire requests; however, when a server gets a duplicate acquire and another client holds the lock, it should send another revoke anyway, in case the first revoke got lost due to a crash. If you designed your protocol as we suggested in Lab 5, it should already behave correctly if there are duplicate retry and revoke RPCs.

Now you should be able to pass './ 11'. This test starts three lock servers and kills the primary while running the lock_tester simultaneously.

Step Four: Complicated failures

In rsm::client_invoke, place the function breakpoint1() after the master has finished invoking RSM request on one slave and before it moves on to issue RSM request to other slaves. In the three server test scenario (test 12), this causes the master to fail after one slave has finished the latest request and the other slave has not seen the latest request yet. If you have implemented recovery correctly, the set of RSM servers in the new view resolve this case correctly and all master/slaves will start executing requests from identical state. Note that since the rsm_client has not heard back from the master in the previous view, it will retry its request in the new view (in rsm_client::invoke()). This might cause your lock server to execute duplicate requests, but that is OK as long as these requests are idempotent, meaning they can be executed multiple times in a row without affecting correctness.

Next, place the function breakpoint1() in rsm::invoke just after the slave has finished executing a request. In the three server test scenario (test 13), this causes the second slave to fail after it has finished the latest request. Again, if you have implemented recovery correctly, the set of RSM servers in the new view resolve this case correctly and all master/slaves will start executing requests from identical state.

Then, call the function breakpoint2() in rsm::commit_change just before exiting the function and only when the node is part of the new view. Test 14 starts five server, kills one slave at breakpoint1() and promptly kills another at breakpoint2().

Test 15 is exactly like test 14 except that the primary is killed at breakpoint2() instead of a slave.

Finally, add the function partition1() right after breakpoint1() in rsm::client_invoke. This function induces a partition that splits the node away from the rest of the nodes. In the three server test scenario (test 16), this causes the primary to loose communication with the two slaves and allows the slaves to form a new view. After the slaves from a new view, the partition is healed and the old primary is allowed to join the system. Your code should be able to deal with the primary being partitioned from the slaves and with an old primary joining the system which has elected a new primary.

If your RSM works correctly, you should be able to pass './ 12 13 14 15 16'.


Here are a few things you can do if you finish the lab early and feel like improving your code. These are not required, and there are no associated bonus points, but some of you may find them interesting.

Handin procedure

Prepare a tar file by executing these commands:
% cd ~/ds-class/lab
% make clean
% rm core*
% rm *log
% cd ..
% tar czvf yfs-lab8.tgz lab/
That should produce a file called yfs-lab8.tgz in your ds-class/ directory. Go to submit site to upload yfs-lab8.tgz