Project 3: Build a Single Server Key-Value Store

In project 3, you will implement a single-node key-value store.

Figure: A single-node key-value store with three clients making simultaneous requests.

Summary

Multiple clients will be communicating with a single key-value server in a given messaging format (KVMessage) using a KVClient. Communication between the clients and the server will take place over the network through sockets (SocketServer and KVClientHandler). The KVServer uses a ThreadPool to support concurrent operations across multiple sets in a set-associative KVCache, which is backed by a KVStore.

Skeleton Code

The project skeleton you must build on top of is linked below. We recommend unpacking this download and dropping the directory in the github repository you used for projects 1 and 2. If you are using an IDE, be sure to separate your IDE-related files for each project such that nachos and kvstore are two independent projects. Do not modify the package statements; the code must be nested in edu.berkeley.cs162.

http://www-inst.eecs.berkeley.edu/~cs162/fa13/kvstore/proj3-skeleton.tar.gz

You can define additional classes and methods as you deem fit, but you must not modify the defined prototypes/interfaces. Be aware that you may need to implement methods that are not labeled with //implement me -- these comments are meant only as hints and are not comprehensive. Examples of how to create client and server instances to run the project are included in Client.java and Server.java.

Tasks (Weights)

1. (20%) Implement the message parsing library in KVMessage. See specifications below.
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. (20%) Implement a set-associative KVCache with the SecondChance eviction policy within each set. The cache should be instantiated with parameter(s) passed to the constructor.
4. (15%) Implement dumpToFile and restoreFromFile in KVStore and toXML in KVCache.
5. (10%) Implement a ThreadPool -- you are not allowed to use built-in threadpool libraries. The threadpool should accept different tasks and execute them asynchronously. The threadpool should maintain a queue of tasks submitted to it, and should assign free threads to tasks as soon as possible.
6. (25%) Implement SocketServer, and KVClientHandler, and KVServer. You will need to 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. This task integrates the entire project and requires a general understanding of all other tasks.

Deliverables

1. Tue 11/12: Initial design
2. Thu 11/21: Code with JUnit tests
3. Fri 11/22: Final design and group evaluation

You will have to submit JUnit test cases for each of the classes you will implement (KVMessage, KVClient, ThreadPool, KVStore, KVCache, and KVServer). The following are the expectations regarding testing:

• Initial Design Document: One to two sentence description of each test case you plan on implementing for each class and the reason for including them (what they test). Please follow the general outline of our design doc template (not updated for project 3). 15 page maximum, but you will likely not need all 15.
• Code: Submit code along with your set of test cases.
• Final Design Document: Description on each test case you have implemented for each class. Our evaluation of your test cases will be worth 10 of the 20 points on your final design. We are looking for unit tests with good code coverage and integration tests that verify the behavior of your system. Unlike project 2, tests will not be a part of the code grade, but we will use the tests you submit with your code along with the descriptions on your final design for the evaluation. 18 page maximum (extra 3 pages for tests), but you will likely not need it.

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 (but not concurrent within the same set).
• All XML serialization and deserialization must use standard Java XML libraries (you may want to look into javax.xml). Do not use string concatenation. Also stay away from using DataOutputStream, as there are some compatibility issues with our autograder.
• 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 learned 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. In implementing SecondChance, an entry is referenced when either a get is called on the key or if the value for a particular key is overwritten via put, even if the value is identical.
• 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.

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
• "Network Error: Could not close socket" -- Error closing 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 Testing

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. There will likely be an online autograder, but we are not promising one.

DO NOT remove AutoGrader hooks from the skeleton.