Distributed Systems

ECE419, Winter 2025
University of Toronto
Instructor: Ashvin Goel

Lab Machines Lab Setup Lab Submission Lab 1 Lab 2 Lab 3 Lab 4

Lab 2: Key/Value Server

Due date: Feb 9

In this lab you will build a key/value server that runs on a single machine and ensures that each operation is executed exactly once despite network failures and that the operations are linearizable. Later labs will replicate a server like this one to handle server crashes.

Starter Code

Make sure that you have followed the the git instructions for initializing your git repository, including the git options for your repository. Then, get the latest starter code for this lab from the student repository by running:

cd ece419
git pull upstream main

This command will merge our code into your repository. It will pop up a window for you to add a merge commit message. Your merge should proceed without any conflicts. If you have conflicts and are not familiar with merging code in Git, make sure to read chapters 3.1 and 3.2 in the Pro Git Book.

The starter code for this lab is available in the kvsrv directory. You need to modify the kvsrv/client.go, kvsrv/common.go, and kvsrv/server.go files. Do not modify other files.

Update: You may modify any other files for testing but please run your final tests with the original versions of these files before submission. Also, do not add any new or remove existing files.

After you have completed your implementation, you can test your code as follows:

cd kvsrv
go test

Overview

Clients can send three different RPCs to the key/value server: Put(key, value), Append(key, arg), and Get(key). The server maintains an in-memory map of key/value pairs. Both keys and values are strings. Put(key, value) installs or replaces the value of a particular key in the map, Append(key, arg) appends arg to key's value and returns the old value, and Get(key) fetches the current value of the key. A Put should always return an empty string. An Append to a non-existent key should act as if the existing value were a zero-length string. A Get for a non-existent key should return an empty string.

Each client talks to the server via a Clerk that manages all RPC interactions with the server. The client calls the Clerk's Get/Put/Append methods.

Linearizability

Your server must ensure that the client's calls to Clerk's Get/Put/Append methods are linearizable. If client requests aren't concurrent, each Get/Put/Append call should observe the modifications to the state implied by the preceding sequence of calls. For concurrent calls, the return values and final state must be the same as if the operations had executed one at a time in some order. Calls are concurrent if they overlap in time. For example, if Client X calls Clerk.Put() and then Client Y calls Clerk.Append() before Client X's call returns, then the two calls are concurrent. For linearizability, a call must observe the effects of all calls that have completed before the call starts.

Linearizability is convenient for applications because it's the behavior you'd see from a single server that processes requests one at a time. For example, if one client gets a successful response from the server for an update request, subsequently launched reads from other clients are guaranteed to see the effects of that update. Providing linearizability is relatively easy for a single server.

Please see more details on linearizability.

Key/value server with no network failures

Your first task is to implement a solution that works when there are no dropped messages.

You'll need to add RPC-sending code to the Clerk Get/Put/Append methods in client.go, and implement Put(), Append() and Get() RPC handlers in server.go.

You have completed this task when you pass the first two tests, TestBasic2 and TestConcurrent2, in the test suite.

Key/value server with dropped messages

Now you should modify your solution to continue in the face of dropped messages (e.g., RPC requests and RPC replies).

If a message was lost, then the client's ck.server.Call() will return false (more precisely, Call() waits for a reply message for a timeout interval, and returns false if no reply arrives within that time).

One problem you'll face is that a Clerk may have to send an RPC multiple times until it succeeds. Each call to Clerk.Put() or Clerk.Append() should result in just a single execution of the RPC handlers, so you will have to ensure that the re-send doesn't result in the server executing the request twice.

Add code to Clerk to retry if it doesn't receive a reply, and to server.go to filter duplicates if the operation requires it.

You will need to uniquely identify client operations to ensure that the key/value server executes each one just once.

You will have to think carefully about what state the server must maintain for handling duplicate Get(), Put(), and Append() requests, if any at all.

Your scheme for duplicate detection should free server memory quickly, for example by having each RPC imply that the client has seen the reply for its previous RPC. It's OK to assume that a client will only make one Clerk call at a time. Your code should now pass all tests, like this:

$ go test
Test: one client ...
  ... Passed -- t  3.7 nrpc 19311 ops 19311
Test: many clients ...
  ... Passed -- t  4.5 nrpc 71341 ops 71341
Test: unreliable net, many clients ...
  ... Passed -- t  3.3 nrpc  1098 ops  871
Test: concurrent append to same key, unreliable ...
  ... Passed -- t  0.3 nrpc    67 ops   52
Test: memory use get ...
  ... Passed -- t  0.7 nrpc     6 ops    0
Test: memory use put ...
  ... Passed -- t  0.4 nrpc     2 ops    0
Test: memory use append ...
  ... Passed -- t  0.7 nrpc     2 ops    0
Test: memory use many put clients ...
  ... Passed -- t 47.5 nrpc 100000 ops    0
Test: memory use many get client ...
  ... Passed -- t 47.6 nrpc 100001 ops    0
Test: memory use many appends ...
  ... Passed -- t  3.2 nrpc  1000 ops    0
PASS
ok      ece419/kvsrv    113.544s

The numbers on each Passed line are the real time the test took in seconds, the number of RPCs sent during the test (including client RPCs), and the number of key/value operations executed (Clerk Get/Put/Append calls).

Advice

Read the Linearizability FAQ.
Check that your code is race-free using go test -race.
Compile and run your code on the UG machines.

Testing

If you wish to run individual tests, look for function names starting with Test, e.g., TestBasic2 in test_test.go. Then run the individual test as follows:

go test -run TestBasic2

For this lab, we have provided you a tool that allows you to estimate your lab grade. After setting your path variable, you can run the tool in the kvsrv directory as follows:

ece419-lab2-check

Submission

We will use the following files from your code repository for grading: kvsrv/client.go, kvsrv/common.go, and kvsrv/server.go.

Please see lab submission.

Acknowledgements

Prof. Robert Morris, Prof. Frans Kaashoek, and Prof. Nickolai Zeldovich at MIT developed these labs. We have their permission to use them for this course.