Project 3: Build a Single Server Key-Value Store
In Project 3, you will implement a key-value store that runs on a single node.
Figure: A single-node key-value store with three clients simultaneously trying to access it.
Summary
Multiple clients will be communicating with a single key-value server (KVServer) in a given messaging format (KVMessage) using a client library (KVClient). Communication between the
clients and the server will take place over the network through sockets (SocketServer and KVClientHandler). The server uses a threadpool (ThreadPool) to support concurrent operations across
multiple sets in a write-through set-associative cache (KVCache), which is backed by a store (KVStore).
Skeleton Code
The project skeleton you must build on top of is posted at https://bitbucket.org/bruckner/project3skeleton. You can define
additional classes and methods as you deem fit. Be aware that you may need to implement methods that are not labeled with "//implement me" comments---these comments are meant as hints only and are not comprehensive.
If you have git installed on your system, you can run git clone https://bitbucket.org/bruckner/project3skeleton.git. In case you want to fork the project on BitBucket,
make sure to make it private
so that no one else can see your code. BitBucket has an academic
licenses that give you many pro features including private repositories
with unlimited collaborators for free. Visit this link for more details. Additionally, for a quick tutorial on git, visit Eddie Kohler's tutorial on git.
Finally, you can just download it from here without ever having to learn or use git. You can continue to use the same SVN repositories that was used for projects 1 and 2.
Requirements
- Your key-value server will support 3 interfaces:
- Value GET (Key k): Retrieves the key-value pair corresponding to the provided key.
- PUT(Key k, Value v): Inserts the key-value pair into the store.
- DEL(Key k): Removes the key-value pair corresponding to the provided key from the store.
You will use the exact request/response formats defined later in the specification for communication between external and internal components.
- 'Keys' and 'values' are always strings with non-zero lengths. They cannot be nulls either.
- Each key can be of size no greater than 256 bytes and each value can be of size no greater than 256 kilobytes. If the size is breached, return an error. (Assume each character to be 1 byte in size)
- When inserting a key-value pair, if the key already exists, then the value is overwritten.
- When retrieving a value, if the key does not exist, return an error message.
- Make sure that the server can handle concurrent requests across sets.
- For all networking parts of this project, you should use only the java.net.Socket and java.net.ServerSocket classes. You should not use any wrappers around the Socket class. If in doubt, post on
Piazza if it is acceptable.
- For
this project, you cannot use any thread-safe data structures that has
been defined by the JVM. For example, you will have to use Conditional
Variables and Locks with a java.util.LinkedList rather
than depend upon Java's synchronized implementations (such as java.util.concurrent.BlockingQueue). We want you to learn how to build thread-safe data structures by using the basic synchronization building
blocks (Locks, ReadWriteLocks, Conditional Variables, etc) that you learnt in Projects 1 and 2. This means that you can use the synchronized keyword, locks (including readwrite locks), java Object's internal
locking and condition mechanisms, non thread-safe data structures like HashMap and LinkedList.
- You should ensure the following synchronization properties in your key-value service:
- Reads (GETs) and updates (PUTs and DELETEs) are atomic.
- An update consists of modifying a (key, value) entry in both the KVCache and KVStore.
- All
operations (GETs, PUTs, and DELETEs) must be parallel across different
sets in the KVCache, and they cannot be performed in parallel within
the same set.
- Each set in the cache will have a fixed number of entries, and evict entries (when required) using the SecondChance algorithm. In implementing SecondChance, a key X is marked as "accessed" only when X is in the cache and GET(X) is invoked on the cache.
- For all operations, you must use the KVCache.getSetId(key) to determine which unique set in the cache each key belongs to.
- You
should bulletproof your code, such that the key-value server does not
crash under any circumstances. For this Project you can ignore SecurityExceptions and InterruptedExceptions.
- You will run the key-value service on port 8080.
Tasks (Weights)
- (20%) Implement the message parsing library in KVMessage.
- (10%) Implement the KVClient class that you are provided with, such that it will issue requests and handle responses (generated using KVMessage) using sockets.
- (15%) Implement a ThreadPool
-- you are not allowed to use existing implementation of threadpools.
The threadpool should accept different tasks and execute them
asynchronously. The threadpool should maintain a queue of tasks
submitted to it, and should assign it to a free thread as soon as it is
available. Ensure that the addToQueue interface to the threadpool is non-blocking.
- (15%) Implement dumpToFile and restoreFromFile in KVStore. Also, implement toXML in KVCache.
- (15%) Implement a write-through set-associative KVCache
with the SecondChance eviction policy within each set. The cache should
be instantiated with parameter(s) passed to the constructor.
- (25%) Implement KVServer, SocketServer, and KVClientHandler that use the threadpool to parallelize data storage into the dummy storage system provided to you (KVStore). Use the set-associative cache you implemented to
make key lookups faster. You should follow a write-through caching policy.
Deliverables
As in projects 1 and 2, you will have to submit initial and final design documents as well as the code itself.
- Initial Design Document (Due: 4/8)
- Code (Due: 4/18)
- Final Design Document (Due: 4/19)
Additionally, you will have to submit JUnit test cases for each of the classes you will implement (KVMessage, KVClient, ThreadPool, KVStore, KVCache, and
KVServer). Following is an outline of the expected progress in terms of test cases in each of the project checkpoints.
- Initial Design Document: One sentence on each test case you plan on implementing for each class and why.
- Code: Submit the final set of test cases.
- Final Design Document: One sentence on each test case you have implemented for each class and why.
KVMessage Format
- Get Value Request:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="getreq">
<Key>key</Key>
</KVMessage>
- Put Value Request:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="putreq">
<Key>key</Key>
<Value>value</Value>
</KVMessage>
- Delete Value Request:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="delreq">
<Key>key</Key>
</KVMessage>
- Successful Get Response:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="resp">
<Key>key</Key>
<Value>value</Value>
</KVMessage>
- Successful Put Response:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="resp">
<Message>Success</Message>
</KVMessage>
- Successful Delete Response:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="resp">
<Message>Success</Message>
</KVMessage>
- Unsuccessful Get/Put/Delete Response:
<?xml version="1.0" encoding="UTF-8"?>
<KVMessage type="resp">
<Message>Error
Message</Message>
</KVMessage>
(Case-Sensitive) Error Messages
- "Success" -- There were no errors
- "Network Error: Could not send data" -- If there is an error sending data
- "Network Error: Could not receive data" -- If there is an error receiving data
- "Network Error: Could not connect" -- Could not connect to the server, port tuple
- "Network Error: Could not create socket" -- Error creating a socket
- "XML Error: Received unparseable message" -- Received a malformed message
- "Oversized key" -- In the case that the submitted key is over 256 bytes (does not apply for get or del requests)
- "Oversized value" -- In the case that the submitted value is over 256 kilobytes
- "IO Error" -- If there was an error raised by KVStore
- "Does not exist" -- For GET/DELETE requests if the corresponding key does not already exist in the store
- "Unknown Error: error-description" -- For any other error. Fill out "error-description" with your own description text.
For network errors arising on the server when it is not possible to
return the error to the client, you can drop this silently. For errors
generated on the client (KVClient), you can drop this silently as well.
KVCache.toXML() Return Format
<?xml version="1.0" encoding="UTF-8"?>
<KVCache>
<Set Id="id">
<CacheEntry isReferenced="true/false" isValid="true/false">
<Key>key</Key>
<Value>value</Value>
</CacheEntry>
</Set>
</KVCache>
There should be as many Set elements as there are sets, and within each set, there should be as many CacheEntry elements as there are entries in each set. As mentioned earlier, the number of sets
and the number of elements in each sets will be given in the constructor. Sets must have Integer ids starting from zero.
KVStore.dumpToFile(filename) Output Format
<?xml version="1.0" encoding="UTF-8"?>
<KVStore>
<KVPair>
<Key>key</Key>
<Value>value</Value>
</KVPair>
<KVPair>
<Key>key2</Key>
<Value>value2</Value>
</KVPair>
</KVStore>
On End-to-End Testing
While this project does not have an online autograder, there are
appropriate hooks to the autograder in the skeleton and a bareboned AutoGrader class has been provided to make it easier for you to write
your own test cases.
DO NOT remove AutoGrader hooks from the skeleton.