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/prashmohan/project3skeleton/. You can define additional classes and methods as you deem fit.

If you have git installed on your system, you can run git clone https://bitbucket.org/prashmohan/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:
  1. Reads (GETs) and updates (PUTs and DELETEs) are atomic.
  2. An update consists of modifying a (key, value) entry in both the KVCache and KVStore.
  3. 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.
• 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)

1. (20%) Implement the message parsing library in KVMessage.
2. (10%) Implement the KVClient class that you are provided with, such that it will issue requests and handle responses (generated using KVMessage) using sockets.
3. (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.
4. (15%) Implement dumpToFile and restoreFromFile in KVStore. Also, implement toXML in KVCache.
5. (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.
6. (25%) Implement KVServer that uses 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.

1. Initial Design Document (Due: Nov 1st, 2012)
2. Code (Due: Nov 13th, 2012)
3. Final Design Document (Due: Nov 14th, 2012)

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 the test cases you plan on implementing for each class and why.
• Code: Submit the final set of test cases.
• Final Design Document: One sentence on the test cases 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.