Lab: Distributed Key–Value Store

Assigned

• February 10, 2026

Due

• February 24, 2026 11:59pm

Collaboration

You may work individually or in pairs on this lab. If you choose to work with a partner you may choose your own group. At the end of class on our first day with this lab I will collect a list of groups for this lab.

Submitting

Submit your completed implementation to Gradescope under the corresponding lab assignment. Make sure your submission includes all of your code, a working Makefile, and a README file explaining your system design.

For this lab, you will implement a distributed version of a key–value store. You can think of a key–value store as a sort of hash table, where you can read and write data items at specified keys. In our case, keys and values will both be strings. The minimum set of operations your key–value store must support is:

void set(char* key, char* value)

Store the data item value at the location key. If a value is already stored with that key, overwrite it.

char* get(char* key)

Look up a data item at the location key. If no value is present at the given key, return NULL.

So far this matches what a simple hash table or dictionary implementation would do, but you will be implementing a distributed key–value store. Your key–value store will be reachable over the network, and must support at least two storage nodes that can both handle set and get requests from client programs.

Requirements

You are free to make any design decisions you like as long as the end result is a system with the features discussed below. Your submission should include a README file that discusses your design with regard to each of the requirements below.

Distributed Storage

When a client program wants to read or write data from the key–value store, it should be able to do so by contacting any of the storage nodes that make up the key–value store. One way to achieve that is to keep a copy of every key–value pair at every storage node, so data will be available no matter which storage node a client contacts. This first approach requires you think about how you will handle consistency, a requirement discussed in more detail below.

An alternate approach is to divide keys up between nodes. You will need to consider how you will assign keys to nodes, and you may need to build a mechanism to forward client requests to the correct node if the first node they contact does not have the requested key.

Regardless of which approach you take, it should be possible to run your storage nodes on different computers within the MathLAN network, or using different ports on the same MathLAN machine. You may find it helpful to use the setsockopt option on your server socket using the option SO_REUSEADDR. This allows you to specify a port and reuse it immediately instead of generating a random port on each run. You can read about this option on the socket(7) manual page.

Your README should describe your system design at a high level, including some basic information about how key–value pairs are assigned to nodes and the lookup procedure your client will use.

Consistency

Regardless of how you arrange the storage in your system, it should not be possible for storage nodes to disagree about the stored keys and values for an extended period of time. This is particularly important if you keep copies of key–value pairs on multiple nodes, as a write to one storage node won’t immediately affect the other node. You could resolve this by communicating between nodes, or by pushing some of that work to the client program.

You are welcome to implement any kind of consistency model you like, as long as you can make a case that the system eventually reaches a consistent state. You should make this argument (informally) in the README you submit with your lab.

Client Code

You will need to implement a client library or program to access the key–value store. This can be a library with a .h file that provides the set and get functions (along with any other required functions to configure access to the system). As an alternative, you can write a client program that you run each time you want to get or set a value from the system. Regardless of which approach you choose, the client code should contain all the necessary steps to get or set a value while exposing a simple interface to an end user (e.g. the simple get and set functions). Make sure you describe this interface in your README so I can write a simple program or command to act as a client in your system.

Test Program

You will need to write a test program that performs a series of get and set operations on your key–value store to test its functionality. The test program should generate a configurable number of set and get operations. Your test program must also report some basic statistics, although you have some flexibility as to which statistics you collect. Some potential measurements of interest would be the average latency of set and get operations, or the percentage of out-of-date values returned if your system implements some type of relaxed consistency model.

Include instructions for setting up and running a complete test in your README file.

Non-Required Elements

We have read about distributed systems that are designed to scale, to tolerate failures, and to provide other guarantees or performance characteristics. These are useful properties for a complete system, but you do not need to implement them in your lab to receive credit.

You may make the following simplifying design decisions or assumptions when completing this lab:

1. Storage nodes can all be started up before there are any accesses to the key–value store.
2. Your system only needs to support two storage nodes, although if it supports more that is also fine.
3. Storage nodes will not fail for the duration of a test.
4. There will not be any network outages or partitions during a test.
5. Storage nodes can use a hard-coded list of all nodes that make up the distributed system, including any information necessary to assign keys to individual nodes.
6. Keys and values will both be strings, and you can place an upper limit on the length of those strings.
7. Clients can be required to establish a new connection for each get or set request, or you can allow a client to make multiple requests while holding a connection to a storage node; either is okay.
8. If your system relies on a hash function, you may use any hash function that is convenient; you do not need to make any security guarantees or use a strong cryptographic hash.

There are likely other simplifying design choices or assumptions you can make as you work on this lab. Check with me (the instructor) to make sure those assumptions are reasonable, and if so I will add them to this list.