CS 475, Fall 2019, Homework 1, Due Sept 18, 9:00 am
Start by downloading the handout:
Please post questions on Piazza
The purpose of this assignment is to get you familiar with basic concurrency control topics in Java. For this assignment, you will build a simple key-value store (KV Store) and client in Java. KV stores are widely used as layers underneath complex distributed systems, and examples include Redis, Voldemort, Dynamo. KV stores are very interesting to study from the perspective of concurrent and distributed software because the interface that they expose to client applications is incredibly simple (appearing effectively to be just a HashMap), but their implementation can be incredibly complex. In particular, once a KV store needs to be able to store more data than can fit in main memory on a single machine, deciding how to swap data to disk can be an interesting problem. If the KV store is then distributed amongst multiple machines, then the specific mechanisms used to keep data in sync can become quite complicated as well.
For this assignment, you will implement a simple KV store that operates entirely within memory, and on a single machine. However, the KV store will be accessed by multiple client threads, and hence, must maintain thread safety.
General requirements:
We have provided you a baseline implementation of the KV store that has various methods stubbed out, which you will implement. 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 or already included by the starter project. Your project will be compiled and tested using Java 8, so please do not use any Java 9+ exclusive features (the first long-term support version of Java > 8 just came out in September; we’ll switch to Java 11 next semester, sorry).
Your KV Store will be compiled and tested using apache maven, which automatically 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.6.1-bin.zip) and unzip it in your home directory. Then, to run maven, type ~/apache-maven-3.6.1/bin/mvn in the snippets below (instead of just mvn). Note that you can easily import maven projects into eclipse and IntelliJ (we suggest IntelliJ over eclipse).
To compile your KV store, run mvn package.
Your KV store will be automatically graded for correctness (note that there will be a manual grading phase to check hard-to-automatically-catch concurrency issues). Included with your handout is a simple version of the (large) 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 20 times before the deadline without penalty. To run these tests, simply execute mvn -Ptest 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. When you feel satisfied with implementing one phase of the assignment, submit to AutoLab and verify that AutoLab agrees.
Tips and References
You might find it useful to reference the official Java tutorial on concurrency, which does a nice job outlining at a high level how you can create threads and locks. If you find any useful references, please feel free to share them on Piazza and we will update this page as well.
Part 1: The Single Threaded Key Value Store (35%)
To get started, you’ll implement the basic functionality of the key value store, and ensure that it works in a normal (single-threaded) environment. This will act as something of a baseline for Java programming without concurrency. The tricky parts will come when we make this functionality thread-safe (in Part 2). You should implement Part 1 completely before moving on to parts 2 and 3. Within Part 1, we suggest starting with the non-list functionality (get, set, remove, append), and then moving on to support lists.
Your KV store will support two different kinds of values: strings and lists. Hence, a key might be mapped to: (1) nothing, (2) a single string, and (3) a list (containing any number of strings).
You will implement this behavior in edu.gmu.cs475.KeyValueStore, specifically in the following 10 methods, noting again that to receive full credit for part 1, you can ignore all fo the concurrent specifications:
|
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
/**
* Retrieve a String value from this key value store
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. set, lPush), or one which might modify the value itself (e.g. append)
*
* @param key the key to retrieve
* @return The value mapped to this key, if one exists, otherwise null
* @throws IllegalArgumentException if the value stored at the key does not represent a string
* @throws NullPointerException if key is null
*/
public abstract String get(String key);
/**
* Sets a key to be the given string value.
* Overwrites any existing value.
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. lPush), or one which might modify the value itself (e.g. append), or with listKeys
*
* @param key key to set
* @param value value to store
* @throws NullPointerException if key or value is null
*/
public abstract void set(String key, String value);
/**
* If the given key already exists and is a string, then this function will append the given value to the existing
* value.
*
* If the given key does not already exist, then this function will behave as if SET were called instead.
*
* If the given key exists but is not a string, then this function will throw an IllegalArgumentException.
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. set, lPush), or with listKeys
*
* @param key
* @param value
* @throws NullPointerException if key or value is null
* @throws IllegalArgumentException if the value stored at the key does not represent a string
*/
public abstract void append(String key, String value) throws IllegalArgumentException;
/**
* Returns the type of element that is stored at this key
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. set, lPush), or one which might modify the value itself (e.g. append)
*
* @param key the key to inquire about
* @return A ValueType indicating the kind of value mapped to this key, if one exists, otherwise null
* @throws NullPointerException if key is null
*/
public abstract ValueType getType(String key);
/**
* Lists all of the keys that are currently known to this key-value store
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. set, lPush, remove)
* @return A set containing all currently valid keys
*/
public abstract Set listKeys();
/**
* Removes this key and any values stored at it from the map
*
* Concurrent specification: This operation must not occur concurrently with any other operation that may modify
* the set of valid keys (e.g. set, lPush), or with listKeys
*
* @param key key to remove
* @return true if the key was successfully deleted, or false if it did not exist
* @throws NullPointerException if key is null
*/
public abstract boolean remove(String key);
/**
* Appends the given item to the head of the list stored at the given key.
*
* If the key does not exist, then a new list is created and stored at this key
*
* If the key does exist, but is not a list, then this method throws an IllegalArgumentException
*
* Concurrent specification: This operation consists of two logical operations, 1) find a list in the KVStore, and
* 2) change that list. You must not allow part 1 (finding the list) to overlap with any other operations that may
* modify key mappings (e.g. set, remove, etc.). Part 2 MUST be able to occur concurrently with other KVStore
* operations acting on other keys, but must NOT be able to overlap with other operations on this same key
*
* @param key key that contains the list
* @param newItem item to append to the list at the given key
* @throws NullPointerException if key is null
* @throws IllegalArgumentException if value stored at key doesn't exist, or that value does not represent a list
*/
public abstract void lPush(String key, String newItem) throws IllegalArgumentException;
/**
* Removes and returns the first element of the list stored at the given key
*
* Concurrent specification: This operation consists of two logical operations, 1) find a list in the KVStore, and
* 2) change that list. You must not allow part 1 (finding the list) to overlap with any other operations that may
* modify key mappings (e.g. set, remove, etc.). Part 2 MUST be able to occur concurrently with other KVStore
* operations acting on other keys, but must NOT be able to overlap with other operations on this same key
*
* @param key key containing the list
* @throws IllegalArgumentException if value stored at key doesn't exist, or that value does not represent a list
* @throws NullPointerException if key is null
* @returns The value of the element removed from the list, or null if the list exists but is empty.
*/
public abstract String lPop(String key) throws IllegalArgumentException;
/**
* Returns the first element of the list stored at the given key
*
*
* Concurrent specification: This operation consists of two logical operations, 1) find a list in the KVStore, and
* 2) change that list. You must not allow part 1 (finding the list) to overlap with any other operations that may
* modify key mappings (e.g. set, remove, etc.). Part 2 MUST be able to occur concurrently with other KVStore
* operations acting on other keys, but must NOT be able to overlap with other operations on this same key
*
* @param key key containing the list
* @throws IllegalArgumentException if value stored at key doesn't exist, or that value does not represent a list
* @throws NullPointerException if key is null
* @returns The value of the first element in the list, or null if the list exists but is empty.
*/
public abstract String lPeek(String key) throws IllegalArgumentException;
/**
* Returns the length of the list stored at the given key.
*
* If the key does not exist, returns 0
*
* If the key does not represent a list, throws an IllegalArgumentException
*
* Concurrent specification: This operation consists of two logical operations, 1) find a list in the KVStore, and
* 2) change that list. You must not allow part 1 (finding the list) to overlap with any other operations that may
* modify key mappings (e.g. set, remove, etc.). Part 2 MUST be able to occur concurrently with other KVStore
* operations acting on other keys, but must NOT be able to overlap with other operations on this same key
*
* @param key
* @return length of the list
* @throws IllegalArgumentException if the key represents a value, but doesn't represent a list
* @throws NullPointerException if key is null
*/
public abstract int lLength(String key) throws IllegalArgumentException;
|
Note the following requirements:
- You should feel free to add whatever methods you would like to the KeyValueStore class, but you must not change the names or parameters of the methods listed above.
- You must not add any fields to any classes.
- You can not use your own HashMap, but instead it is almost as easy: You must call _get, _set, _remove, and _listKeys in your KeyValueStore to access the underlying data store. You must not maintain any mapping yourself between keys and values.
- All lists must be instances of KeyValueList, and when you create them, you must pass the name of the key that is storing that KeyValueList.
Precise grading breakdown:
- Automated tests: 28 points
- 7 JUnit tests, 4 points each
- 7 points from manual grading
Part 2: Managing Thread Safety (45%)
Once you are satisfied that your key-value store works correctly in a single-threaded environment, your next task will be to add locking to it. You should implement all of your concurrency control through (1) the this.bigLock object (a java.util.concurent.locks.Lock object), and (2) by using the Lock supplied by the method getLock() of each KeyValueList . Note 9/16: You MUST use the method getLock() of each KeyValueList to handle this synchronization, otherwise you will fail most of the tests.
Note the following concurrency requirements, paraphrased from the specification above:
- You must not allow concurrent calls to any of the following methods: _get, _set, _remove, or _listKeys
- For the operations lPush, lPop, lLength, and lPeek: if any of these are concurrently called for two different keys, you must allow them to execute concurrently (subject to requirement 1), but do not allow them to occur concurrently. The overlapping behavior of these two methods is shown in the graphic below.
Precise grading breakdown:
- Automated tests: 42 points
- 7 JUnit tests, 6 points each
- 3 points from manual grading
Part 3: Testing the Tests (20%)
We have included several functional tests with your handout that simply test the behavior of each of these methods. We have not provided any tests (for you to see) that test the behavior of your software under concurrency (the tests for part 2). One of your tasks is to write such tests.
Note that it is generally impossible to automatically prove that concurrent programs have no races, it is common instead to test for low-hanging fruit. For instance, it is possible to write tests that demonstrate that two events can happen concurrently, and tests that show that it’s unlikely (but not impossible) that two other events do not happen concurrently.
We are asking you to implement one of the tests that we are using to test part 2: testPushOrPopFromDifferentListsShouldBeConcurrent. The goal of this test is to demonstrate that it is possible to call lPush(key1,value1) and lPush(key2,value2) concurrently, and for both of the underlying push operations to actually occur concurrently (and, similarly for lPop). To implement this, you can create new threads (please, no more than 2 though) and use the entirety of Java’s thread API and use flags or locks as you feel appropriate.
The illustration in part 2 above shows the interleaving that we are trying to witness: that while Thread 1’s lPush is still running (that is to say, before lPush returns in Thread 1), Thread 2 successfully starts and adds an item to the same list at the same key as Thread 1. Note that in the graphic we show the two linearization points (from your call to kvStore.get and to list.add, which should both be protected with different locks). Because each list should have its own lock, you should be able to see this scenario. Hint (9/16): There are many ways to implement this using these different APIs, locks, and shared variables. Feel free to start however you like. If you are struggling to decide where to start, we will share that the reference solution uses only thread.start(), thread.join(), and thread.isAlive(). That said, there are many different ways to do this, so please feel free to proceed however you like.
In order to force this scenario to occur, you may need to insert some code to run before any call to add or remove contents from the list. You can add such code by setting the fields KeyValueList.addCalledCallback and KeyValueList.removeCalledCallback. KeyValueList.addCalledCallback is a BiFunction that is passed as parameters the KeyValueList instance that add is being called on, as well as the value being added. KeyValueList.removeCalledCallback is a Function that is passed as a parameter the KeyValueList instance that remove is being called on. You can experiment by creating a function that, for instance, prints out every time that add is called on the list, like this:
|
1
2
3
4
5
|
KeyValueList.addCalledCallback = (list, val) -> {
System.out.println("Add called on " + list + ", val: " + val);
return null;
};
kvStore.lPush("someKey", "testValue");
|
Which will result in the output:
|
1 |
Add called on [], val: testValue
|
Implement your test in Part3TestingTheTestTests. Feel free to add any non-static fields to this class.
Your test will be tested on Autolab on three different KeyValueStores: a correct KVStore (your test should pass on this implementation) and two incorrect KVStores (your test should fail on both of these implementations).
No marks will be awarded for empty tests, or tests that have no assertions (note that otherwise, these tests would all pass on our correct implementation). You will receive full marks only if your test successfully passes on the correct implementation and fails on the buggy versions.
Grading
Your assignment will be graded on a series of functional tests, making sure that it implements the specification above. Your test will be graded by running it on purposely buggy code and verifying that it throws some errors, and then manually inspecting them for completeness. We have provided a (not exhaustive) test suite which should help you judge (on your own) how well you have done with the functional requirements. We may add additional tests beyond what we are providing you with now, so please do not rely entirely on them.
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 only the src directory in your assignment (please: .zip, not .tgz or .7z etc). 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 up to 20 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.
Questions
Please post questions on Piazza