CS 475, Spring 2018, Homework 4, Due April 6, 2pm
Start by downloading the handout:
Please post questions on Piazza
Updates:
- 3/28: Added hint about how to implement mutual exclusion between writeFile and registerReplica
The purpose of this assignment is to introduce the concepts of replication and transactions. For this project, you’ll be enhancing your file server so that files are replicated to client-side caches. We’ll still have a single server, which will be in charge of maintaining locks and ensuring that new writes are replicated to all replicas. Our architecture will now look something like this:
Adding all of these replicas can increase the performance of our system when reading many large files, since each client will always have every file cached. When clients read files, they will not need to read them from the server: they can directly read them from their local cache. We will not be using the open-to-close semantics of NFS, and will instead be maintaining the traditional notion of consistency: each client will always read the most recent version of each file. This means that the master will need to have some protocol to ensure that a write deemed “successful” at the server level has indeed succeeded on every active client.
To simplify things, we’ve dropped the notion of tags — for this assignment, you’ll just have to worry about reading/writing/locking files (and not maintaining a mapping from files to tags).
Your primary interface for debugging your VCFS will be the same shell driver that we provided for HW3. The main difference will be that when you start the shell, you will specify a hostname and port number of a VCFS server. We have provided stubs for all of the various commands you will need to implement, with a wrapper so that you can interact with VCFS interactively. When you run the compiled jar file, you’ll get a command prompt, like this (again, note that there are fewer commands than previously):
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
cs475sh help
AVAILABLE COMMANDS
Built-In Commands
clear: Clear the shell screen.
exit, quit: Exit the shell.
help: Display help about available commands.
script: Read and execute commands from a file.
stacktrace: Display the full stacktrace of the last error.
Command
cat: Cat a file
cat-all: Cat all files
echo: Echo text into a file
echo-all: Echo text into all files
list-all-files: List all file names
|
As you implement the various functionality in the parts below, the commands above will begin to work.
We have also provided a baseline suite of unit tests, which you can execute by calling mvn test
General requirements:
We have provided you a baseline implementation of VCFS that handles all user interaction and connects to the server, but does not do anything (that is, you will not need to implement any UI or command processors; you will not need to add much RMI boilerplate). You may not include any additional libraries (e.g. download and and require additional JARs), although feel free to use any of the various libraries included with Java 8 or already included by the starter project.
You must use exclusively reentrant locks (e.g. synchronized or ReentrantReadWriteLock), with the single exception of lockFile and unlockFile, which must use StampedLocks.
Your VCFS will be compiled and tested using apache maven, which automatically downloads the various dependencies for VCFS and executes the provided JUnit tests. Please install Maven on your computer. Unfortunately, Maven is not installed on Zeus, however you can download the most recent version (e.g. apache-maven-3.5.2-bin.zip) and unzip it in your home directory. Then, to run maven, type ~/apache-maven-3.5.2/bin/mvn in the snippets below (instead of just mvn). Note that you can easily import maven projects into eclipse and IntelliJ.
To compile and run your shell, run mvn package in the top level directory and then, in the server directory run java -jar target/filemanager-server-0.0.4-SNAPSHOT.jar portnumber to start the server, and to start the client, in the client directory run java -jar target/filemanager-client-0.0.4-SNAPSHOT.jar portnumber. Your can specify any free port number on your computer over 1024; we have hardcoded the client to assume that the client runs on the same computer as the server. You’ll notice that the text-mode interface we’ve provided for you has a handy help command. To build the jar file without running the tests, run mvn -DskipTests package.
Your shell will be automatically graded for correctness (note that there will be a manual grading phase to check hard-to-automatically-catch and concurrency issues). Included with your handout is the test script that we will use to grade your assignment. Upon submitting your assignment, our server will automatically compile and test your assignment and provide you with test results. You can resubmit an unlimited number of times until the deadline. To run these tests, simply execute mvn test (of course, if you do this first off, you’ll see that they all fail!)
Note: Your code must compile and run on the autograder, under Java 8. It is unlikely that you will have any difficulties developing on a Mac, Linux or Windows, but please keep in mind the possibility of portability problems. When you feel satisfied with implementing one phase of the assignment, submit to AutoLab and verify that AutoLab agrees.
General coding/grading requirements:
- You must use exclusively reentrant locks (e.g. synchronized or ReentrantReadWriteLock), with the single exception of lockFile and unlockFile, which must use StampedLocks.
- You should feel free to add whatever additional classes you wish, or any additional methods to the existing edu.gmu.cs475.FileManagerServer and edu.gmu.cs475.FileTagManagerClient. You must not modify the edu.gmu.cs475.IFileManager interface, the edu.gmu.cs475.IFileManager interface, the edu.gmu.cs475.AbstractFileManagerClient, any of the tests, or any of the internal classes.
- Your code should be thread-safe: concurrent calls to any of these methods (or any other method in IFileTagManager) should not have any races. It should now be clearer how this can occur — you will potentially have multiple clients attempting to interact with the server simultaneously.
- You must not store any state in static fields
- All concurrency-related grading (aside from the provided tests) will account for a total 0f 10% of your grade (see Part 4).
Part 1: Client-side cache (35%)
For the very first part, you’ll configure the client and server code so that when they connect, the clients register themselves with the server, and the server provides the clients with a set of all of the files and the contents of each file. This will form the initial cache on the client. Then, whenever the server receives a write request, it will forward that request to all registered clients, who will in turn update their caches. When a client is done, it will notify the server that it’s disconnecting, which will allow the server to stop sending writes to it.
Implement your server in the server project, by implementing the empty methods in edu.gmu.cs475.FileManagerServer, and your client in the client project, by implementing the empty methods in edu.gmu.cs475.FileManagerClient. You should feel free to reuse the code you had from HW3, or write something different (you’ll notice that the API changed slightly).
Here are the methods you should be implementing in the client:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/**
* Initialzes this read-only replica with the current set of files
* @param files A map from filename to file contents
*/
protected abstract void initReplica(HashMap files);
/**
* Lists all of the paths to all of the files that are known to the client
*
* @return the file paths
*/
public abstract Iterable listAllFiles();
/**
* Return a file as a byte array.
*
* @param file Path to file requested
* @return String representing the file
* @throws IOException if any IOException occurs in the underlying read
*/
public String readFile(String file) throws RemoteException, IOException;
/**
* Write (or overwrite) a file
*
* @param file Path to file to write out
* @param content String representing the content desired
* @param xid Transaction ID, if this write is associated with any transaction, or 0 if it is not associated with a transaction
* If it is associated with a transaction, then this write must not be visible until the replicant receives a commit message for the associated transaction ID; if it is aborted, then it is discarded.
* @return true if the write was successful and we are voting to commit
* @throws IOException if any IOException occurs in the underlying write
*/
public boolean innerWriteFile(String file, String content, long xid) throws RemoteException, IOException;
|
And in the server, you’ll implement:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
/**
* Initializes the server with the state of the files it cares about
*
* @param files list of the files
*/
public abstract void init(List files);
/**
* Registers a cache with the server, returning all of the files that currently exist.
*
* @param hostname The hostname that should be used to contact this cache (sent again on disconnect)
* @param portNumber The port number to use to contact the cache (sent again on disconnect)
* @param replica The RMI object to use to signal to the replica
* @return A HashMap of all of the files that currently exist, mapping from filepath/name to its contents
* @throws RemoteException
*/
public HashMap<String, String> registerReplica(String hostname, int portNumber, IFileReplica replica) throws IOException {
/**
* Notifies the server that a cache client is shutting down (and hence no longer will be involved in writes)
*
* @param hostname The hostname of the client that is disconnecting (same hostname specified when it registered)
* @param portNumber The port number of the client that is disconnecting (same port number specified when it registered)
* @throws RemoteException
*/
public void cacheDisconnect(String hostname, int portNumber) throws RemoteException;
/**
* Write (or overwrite) a file.
* You must not allow a client to register or depart during a write.
*
* @param file Path to file to write out
* @param content String representing the content desired
* @throws IOException if any IOException occurs in the underlying write, OR if the write is not succesfully replicated
*/
public void writeFile(String file, String content) throws RemoteException, IOException;
/**
* Acquires a read or write lock for a given file.
*
* @param name File to lock
* @param forWrite True if a write lock is requested, else false
* @return A stamp representing the lock owner (e.g. from a StampedLock)
* @throws NoSuchFileException If the file doesn't exist
*/
public long lockFile(String name, boolean forWrite) throws RemoteException, NoSuchFileException;
/**
* Releases a read or write lock for a given file.
*
* @param name File to lock
* @param stamp the Stamp representing the lock owner (returned from lockFile)
* @param forWrite True if a write lock is requested, else false
* @throws NoSuchFileException If the file doesn't exist
* @throws IllegalMonitorStateException if the stamp specified is not (or is no longer) valid
*/
public void unLockFile(String name, long stamp, boolean forWrite) throws RemoteException, NoSuchFileException, IllegalMonitorStateException;
|
For part 1, writeFile should: (1) take out a write-lock on the file, (2) call innerWriteFile on each cache client, passing transaction ID 0, and (3) then update the file locally. There is no need to implement heartbeats like in HW3 – lock and unlock can just use straightforward StampedLocks.
Hint (3/28): To prevent replicas from joining or departing during a write (but still allowing concurrent writes to different files), consider using a ReentrantReadWriteLock to guard your list of replicas. Code that is reading the list of replicas (e.g. the write method, and in part 3, writeFileInTransaction) would need to acquire a read lock, while code that is changing the list of replicas (e.g. when registering or departing) would require a write lock.
When you are ready to check your work, you should run just the tests in the test class edu.gmu.cs475.P1Tests. To do so from maven, you should run mvn -Dtest=P1Tests test.
Precise grading breakdown:
- Automated functional tests (
edu.gmu.cs475.P1Tests): 32 points
- 8 JUnit tests, 4 points each
- Manual feedback: 3 points
Part 2: Server-initiated transactions on write (35%)
Next, you will implement a simple two-phase-commit protocol. The motivation for this is that our implementation so far does not guarantee that each client will always see the most recent file. In particular: consider the case where clients C1, C2 and C3 are connected to the server. Client C1 updates a file Foo by telling the server. The server sends the update to C1 (OK) and C2 (OK). When it tries to update C3, it is unable to contact C3 (perhaps the network is being really slow temporarily). At this point: what should we do? If C3 is crashed, then this is probably OK: but if C3 might show up again later, then for the period of time that C3 is out of communication, it has the wrong version of file foo!
We’re going to play it safe: the server will first try to reach all of the clients and tell them that they should get ready to do the update. Then, after all clients says “Yes, I’m ready to update that file”, the server will send a commit message, telling each client that it should perform the commit. If any one client is not able to do the update (by voting no), then the server will abort the update, canceling the change and returning an error to the original client that wanted to perform the update.
To implement this portion, you’ll need to (1) update writeFile on the server to generate a new transaction ID for each time that writeFile is called (any number is fine as long as it doesn’t repeat) and pass that ID to each client’s innerWriteFile, (2) adapt innerWriteFile so that it stores transaction writes into a separate cache, and (3) implement commit and abort on the client to apply or abort that transaction. If every innerWriteFile successfully returns (no exception and returns true), your server should call commit on each client; if not, it should call abort on each client.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/**
* Commit a transaction, making any pending writes immediately visible
*
* @param id transaction id
* @throws RemoteException
* @throws IOException if any IOException occurs in the underlying write
*/
public void commitTransaction(long id) throws RemoteException, IOException;
/**
* Abort a transaction, discarding any pending writes that are associated with it
*
* @param id transaction id
* @throws RemoteException
*/
public void abortTransaction(long id) throws RemoteException;
|
We will grade your client and server side implementation separately. We have provided a set of tests, edu.gmu.cs475.P2Tests, which automatically mock a correctly functioning server — running your client against this fake server. To run this from maven, you should run mvn -Dtest=P2Tests test.
Precise grading breakdown:
- Automated functional tests (
edu.gmu.cs475.P2Tests): 24 points
- 4 JUnit tests, 8 points each
- Manual feedback: 3 points
Part 3: Client-initiated transactions on echoToAll (20%)
Finally, you’ll extend the notion of transactions, allowing clients to define themselves when a transaction will start. In particular, you’ll configure the client so that before an echoToAll starts, it creates a transaction. This way, even if writing to a single file on a single cache replica fails, the entire echoToAll can be aborted, and the invariant that echoToAll is atomic is preserved.
EchoToAllFiles should, in this order:- Lock all files for write
- Start a transaction ( startNewTransaction)
- Write the content to each file, passing that transaction ID ( writeFileInTransaction)
- If all writes succeeded, then commit the transaction ( issueCommitTransaction), else, abort it ( issueAbortTransaction)
- Unlock all files
The spec for all of the remaining server methods:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
* Request a new transaction ID to represent a new, client-managed transaction
*
* @return Transaction organizer-provided ID that will be used in the future to commit or abort this transaction
*/
public long startNewTransaction() throws RemoteException;
/**
* Write (or overwrite) a file. Broadcasts the write to all replicas and locally on the server. Does not acquire any locks.
* You must not allow a client to register or depart during a write.
* @param file Path to file to write out
* @param content String representing the content desired
* @param xid Transaction ID to use for any replications of this write
* @return True if all replicas replied "OK" to this write
* @throws IOException if any IOException occurs in the underlying write, OR if the write is not succesfully replicated
*/
public boolean writeFileInTransaction(String file, String content, long xid) throws RemoteException, IOException;
/**
* Broadcast to all replicas (and make updates locally as necessary on the server) that a transaction should be committed
* You must not allow a client to register or depart during a commit.
* @param xid transaction ID to be committed (from startNewTransaction)
* @throws IOException in case of any underlying IOException upon commit
*/
public void issueCommitTransaction(long xid) throws RemoteException, IOException;
/**
* Broadcast to all replicas (and make updates locally as necessary on the server) that a transaction should be aborted
* You must not allow a client to register or depart during an abort.
* @param xid transaction ID to be committed (from startNewTransaction)
*/
public void issueAbortTransaction(long xid) throws RemoteException;
|
And, the spec for all of the remaining client methods (note that catAllFiles is not involved in transactions but still does locks):
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
/**
* Prints out all files. Must internally synchronize
* to guarantee that the list of files does not change
* during its call, and that each file printed does not change during its
* execution (using a read/write lock). You should acquire all of the locks,
* then read all of the files and release the locks. Your code should not
* deadlock while waiting to acquire locks.
*
* @return The concatenation of all of the files
* @throws IOException
* if any IOException occurs in the underlying read, or if the
* read was unsuccessful (e.g. if it times out, or gets
* otherwise disconnected during the execution
*
*/
public abstract String catAllFiles() throws IOException;
/**
* Echos some content into all files. Must internally
* synchronize to guarantee that the list of files does
* not change during its call, and that each file being printed to does not
* change during its execution (using a read/write lock)
*
* Given two concurrent calls to echoToAllFiles, it will be indeterminate
* which call happens first and which happens last. But what you can (and
* must) guarantee is that all files will have the *same* value (and not
* some the result of the first, qnd some the result of the second). Your
* code should not deadlock while waiting to acquire locks.
*
* Must use a transaction to guarantee that all writes succeed to all replicas (or none).
*
* @param content
* The content to write out to each file
* @throws IOException
* if any IOException occurs in the underlying write, or if the
* write was unsuccessful (e.g. if it times out, or gets
* otherwise disconnected during the execution)
*
*/
public abstract void echoToAllFiles(String content) throws IOException;
|
Again, we will grade your client and server side implementation separately. We have provided a set of tests, edu.gmu.cs475.P3Tests, which automatically mock a correctly functioning client — running your server against this fake client and simulating error conditions. To run this from maven, you should run mvn -Dtest=P3Tests test.
Precise grading breakdown:
- Automated functional tests (
edu.gmu.cs475.P3Tests): 18 points
- 6 JUnit tests, 3 points each
- Manual feedback: 2 points
Part 4: Concurrency (10%)
To receive a top score on this assignment, you will also need to be sure that your code has no races. For this assignment, we will be using the tool, RV-Predict to detect races that may occur while running your tests. RV-Predict will give you precise feedback on the races that it detects, for instance:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
Data race on field account.Account.Bank_Total: {{{
Concurrent write in thread T12 (locks held: {})
---- at account.Account.Service(Account.java:98)
at account.BankAccount.Action(BankAccount.java:41)
at account.BankAccount.run(BankAccount.java:56)
T12 is created by T1
at account.Account.go(Account.java:46)
Concurrent read in thread T13 (locks held: {})
---- at account.Account.Service(Account.java:98)
at account.BankAccount.Action(BankAccount.java:41)
at account.BankAccount.run(BankAccount.java:56)
T13 is created by T1
at account.Account.go(Account.java:46)
}}}
|
AutoLab will automatically run RV-Predict on all of your submissions. You can run it on your own computer by downloading and installing it (it’s free for non-commercial use). When you run your tests with maven, use the command mvn -Drvpredict=/path/to/rv-predict.jar test (on Mac this would be mvn -Drvpredict=/Applications/RV-Predict/Java/lib/rv-predict.jar test).
We will not give you a direct equation to correlate from # of reports from RV-Predict -> a grade on this section. We will manually award up to 10 points for concurrency correctness based on no apparent races and no over-synchronization (again, one way to avoid races could be to force every operation to be serial; this would not be ideal or correct). Moreover, note that RV-Predict will find many races, but will not find all races, which we might by hand! Note also that if you make wide use of stamped locks (instead of reentrant locks or synchronized blocks), RV-Predict will report that races are possible because it can not analyze stamped locks.
Grading
Your assignment will be graded on a series of functional tests, making sure that it implements the specification above.
Hand In Instructions
You must turn in your assignment using Autolab (You MUST be on the campus network, or connected to the GMU VPN to connect to Autolab). If you did not receive a confirmation email from Autolab to set a password, enter your @gmu.edu (NOT @masonlive) email, and click “forgot password” to get a new password.
Create a zip file of the root directory in your assignment (please: .zip, not .tgz or .7z etc) — this is the root directory that includes the client, shared, server directories. When you upload your assignment, Autolab will automatically compile and test it. You should verify that the result that Autolab generates is what you expect. Your code is built and tested in a Linux VM. Assignments that do not compile using our build script will receive a maximum of 50%. Note that we have provided ample resources for you to verify that our view of your assignment is the same as your own: you will see the result of the compilation and test execution for your assignment when you submit it.
You can resubmit your assignment an unlimited number of times before the deadline. Note the course late-submission policy: assignments will be accepted up until 24 hours past the deadline at a penalty of 10%; after 24 hours, no late assignments will be accepted, no exceptions.
Note – You MUST be on the campus network, or connected to GMU VPN to connect to Autolab.
Decoding the output:
Note, AutoLab will run your code on the tests twice: once without RV-Predict (these are the scores used for parts 1-3), and once with RV-Predict (this is informational only). The outcomes should be the same with or without RV-Predict, but we wanted to make 100% sure that adding the tool doesn’t break your otherwise seemingly functioning code.
AutoLab scoreboard:
For this assignment we’ve enabled the scoreboard. It will show everyone’s scores across all of the parts of the assignment, anonymized based on either (1) the nickname that you set in AutoLab, or (2) a “random” name (drawn from the testdir random names; if your nickname was previously your name or email we changed it to a random name to make sure you understand that it will now be shown to all). Feel free to change your nickname to anything (be it your real name or a fake name), especially if it’s funny to you or others, but again, know that it will be visible to all of your classmates.
Questions
Please post questions on Piazza