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.

Architecture Diagram

Figure: A single-node key-value store with three clients simultaneously trying to access it.


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

If you have git installed on your system, you can run git clone 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.


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.


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.

KVMessage Format

(Case-Sensitive) Error Messages

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"?>
  <Set Id="id">
    <CacheEntry isReferenced="true/false" isValid="true/false">

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"?>

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.