KVonset

In the Woonsocket project, our goals was to become familiar with network APIs such as vectored I/O and io-uring. Correspondingly, the project’s application used a synthetic workload and the project deliverables focused on comparing the performance trends between different measurement techniques and APIs.

In KVonset, we replace the synthetic workload with one closer to reality - an in-memory key-value store - and instead of comparing performance trends, our goal is simply to optimize performance as much as possible. However, as we’ve discussed in class, “optimizing performance” is not a single objective. So, in this project we will write three configurations: one that optimizes for the highest throughput possible, one that optimizes for the lowest latency possible, and one that seeks to achieve both, in a Pareto-optimality sense. In this context, implementation A is Pareto-optimal compared to implementation B if A has lower latency than B while achieving the same offered load, or alterately if A supports higher offered load than B while achieving the same latency.

Project goals

The primary requirement is simply that your in-memory key-value store, in each of three configurations (passed as a command-line argument), should optimize the following SLOs. Since the client implementation is provided in the starter code, in this project you won’t control the relationship between attempted load and offered load. Instead, we will focus on achieving the offered load (which, due to Poisson arrivals, will fluctuate over time) with a given latency target.

• Latency SLO: At an attempted load of 200,000 keys / second, achieve 99.9% of the offered load and a p95 request latency of 300 microseconds or less.
• Throughput SLO: At an attempted load of 1,000,000 keys / second, achieve 99.9% of the offered load (which should be at least 300,000 keys / second) and a p95 request latency of 1,000 microseconds or less.
• Mixed SLO: At an attempted load of 400,000 keys / second, achieve 99.9% of the offered load (which should be at least 225,000 keys / second) and a p95 request latency of 500 microseconds or less.

Reminder

The SLOs mention an attempted load (a configuration parameter for the client) and offered load (a measurement of the client’s behavior). These numbers can diverge due to TCP backpressure, as we have observed in Woonsocket.

Leaderboard

We will additionally offer an opt-in leaderboard for the three configurations, for students who exceed the minimum SLOs above. You can opt-in by modifying the leaderboard.config file provided in the starter code (opt-out by default). Feel free to can use an anonymized name, but keep the same name for future submissions. Your results will automatically be recorded on the grading server and the most recent one for each SLO will be displayed on a latency throughput graph together with other people’s results.

As usual, your project grade will be determined by your report and grading meeting; the leaderboard won’t affect grading and is just for fun.

Deliverables

This project has more implementation flexibility than previous projects in this class. However, the key-value store you implement must provide linearizability. This means that if a get returns a particular value v and there are no further puts to the value, all further gets should return the same value v.

Note

Second, the system should meet the SLOs described above in each of the three configurations on the grading server. The grading server environment will be a VM with two cores at 16GB memory. Many students’ personal computers have a larger number of cores and/or memory. Thus the SLOs may be more easily achieved on those machines, please do only report results from the grading server in your report; we want to measure your implementation and not your laptop. If you wish to test your implementation’s performance locally, you may want to use taskset or a similar mechanism to limit the number of resources available.

Report

As in previous projects, we will evaluate your report for clarity and presence of valid quantitative evidence. At minimum, your report should include:

1. Performance metrics (latency and throughput) of your server implementations for each target SLO as well as quanitative evidence that the server meets 99.9% of offered load.
2. Your written analysis for any optimizations you implemented to achieve each target SLO and their effect on the performance of the application.
3. Any other design decisions you took in your implementation.

Starter Code

The clients (client.rs)

We provide you with a partially-open-loop client workload generator. The workload generator creates new client connections in an open-loop manner based on an exponential distribution (i.e., Poisson arrivals). Each client connection is closed-loop with some probability of exiting after receiving the response to a request. This number of requests will be distributed according to a standard geometric distribution.

A new aspect of KVonset is that, unlike in Woonsocket’s synthetic work, the workload concerns operations on map keys. 12.5% (= 64 / 512) of the workload will be puts, and 88.5% will be gets. We use a Zipfian(1024, 1) distribution to determine which keys to get and put. This means that a small subset of a total of 1024 keys will be proportionally more popular than the remaining keys, with higher numbers being less popular.

The API (protocol.rs)

The concurrent in-memory key-value store should support mput and mget operations, where a client can mput many key-value records or mget the records for a variable number of corresponding keys in one request.

A client sends a Op to the server. Op has two options:

• mput: insert the specified key-value pairs into the map (or modify them if already present).
• mget: get the values of the specified keys from the map. If the key is not in the map, the associated value should be None.

The server (server/mod.rs)

As you can see, this file is quite sparse. We leave it to you to design your in-memory key value store. You should feel free to copy code you previously wrote as part of Woonsocket.

Tip

We suggest writing your three server configurations in different files for readability, but don’t mandate this in the starter code. You can use Rust’s module system to do this.