Skip to main content Link Menu Expand (external link) Document Search Copy Copied
CS 162 HW: Raft

Part 1: Key-Value Server

In this part, you will implement a single-server key-value store and a client that communicates with it via RPC. The server stores keys with associated values and version numbers, supporting optimistic concurrency control through version checking on puts.

KV server semantics

The server maintains a map of keys to (value, version) pairs. It supports two operations:

  1. Get(key): Returns the current value and version for the key. If the key does not exist, returns Err(KVError::NoKey).
  2. Put(key, value, version): Installs or replaces the value for the key, but only if the provided version matches the server’s current version for that key. On success, the server increments the version and returns Ok(()). On version mismatch, returns Err(KVError::Version).

For a key that does not yet exist, the server’s version is 0. So to create a new key, the client must put with version = 0. If a put request is made for a key that doesn’t exist, but the version is not 0, then you should return Err(KVError::NoKey).

Subsequent puts must provide the current version. For further reading, this is how optimistic concurrency control works, by reading the current version and writing back with the version it read. If another client modifies the key in between the read/write, the version will mismatch and fail.

KV server

Implement the KV server in src/kv_single/server.rs. We outline a few tasks for you, though you are not required to follow them step by step.

  1. Define RPCs. We provide empty RPCs GetArgs, GetReply, PutArgs, and PutReply for you. You’ll need to add the fields that you need.
  2. Add state to KVServer. You will need a data structure to store key/value/version triples. Note that you will not need an Arc here as the KVServer is wrapped in the Arc.
  3. Implement get and put. You’ll need to consider synchronisation here.

Client

Implement the client in src/kv_single/client.rs.

The client wraps an RpcClient endpoint and implements the KvClient trait. For now, implement get and put assuming a reliable network (no drops):

You should use self.endpoint.call("get", &args).await to send an RPC. On a reliable network, call always returns Some.

Testing

Run the reliable-network tests:

cargo test --test kvsrv_test test_reliable -- --test-threads=1

You should pass all tests whose names start with test_reliable.

Reliability

Now make your client handle an unreliable network. When call returns None, the RPC was lost, which means the request either never reached the server, or the reply was dropped. We must distinguish between these two cases.

  1. if the request was dropped, the put didn’t happen, so retrying is safe.
  2. if the reply was dropped, the put did happen, and retrying would fail with Err(KVError::Version) (since the version was already incremented).

When the call returns None, we should retry the RPC. You may use tokio::time::sleep(Duration::from_millis(10)) to sleep between retries. Then, when a retry returns Err(KVError::Version), you should return Err(KVError::Maybe) which tells the caller the request may have been executed. Keep in mind that if your initial put RPC call return Err(KVError::Version), your client should still return Err(KVError::Version), since you know the RPC was definitely not executed by the server.

Testing

Run all single-server KV tests:

cargo test --test kvsrv_test test_reliable -- --test-threads=1
cargo test --test kvsrv_test test_unreliable -- --test-threads=1
cargo test --test kvsrv_test test_concurrent -- --test-threads=1