Distributed Multi-Consistency Key-Value Store

1 Summary

In this project, you will implement a distributed key-value store that offers many different consistency models. You should use your KV store from earlier in the course, or use any existing key-value store (such as redis, memcached, cassandra, etc.) to store the objects on individual servers. The main task is to then implement the different consistency schemes that use the underlying key-value store replicas.

The client will make set/get requests to your top-level controller, which will then in turn issue set/get requests to the underlying replicas. The set/get requests will also include a consistency level option. You can ofcourse include other options.

You should run multiple instances of the lower-level key-value store replicas (your KV store from the firs assignment). You can refer to the following paper for more ideas about the design, implementation, and evaluation of such layered kv-store systems: BespoKV: application tailored scale-out key-value stores .

2 What to implement and submit

2.1 Different consistency schemes

  • Sequential Consistency
  • Eventual Consistency
  • Linearizability
  • Causal Consistency [Must be accompanied with a clear testcase differentiating it from sequential consistency.]

2.2 Example Clients

You should have test cases for each consistency implementation. The test cases should show that the consistency model is being implemented correctly.

2.3 Experimental Performance Evaluation

There should be some performance evaluation with the different consistency models. There will be tradeoffs in your design, and this will throw a light at them.

2.4 Detailed Report

The report should describe all facets of your design.

  • How each consistency model is implemented?
  • What were the main challenges?
  • What is your client API?
  • Some performance evaluation

You can submit a zip file, or a link to a private github repository, along with the report on Canvas.

3 Design and Implementation Hints

  1. The purpose of this assignment is to think concretely about the algorithms, design, and test-cases.
  2. A consistency mode for each set and get request is not necessary. The KV store can be started with some consistency.
  3. Starting with the ``extreme'' models (eventual and linearizability) is generally easier. You can then either relax or strengthen the implementation to obtain the other models.
  4. There are many different ways of implementing each level. Pick any one. Hopefully you will be an expert in that technique once you've finished implementing and testing it.
  5. The GET/SET operations can take the replica address as an argument.
  6. Test-cases should show adequate level of consistency and operation reordering. For example, the eventually consistent store should exhibit stale reads. Showing this will not be easy, because network delays for local processes will be small. One common technique is to inject artificial delays before sending/applying messages between replicas. This essentially ``emulates'' a slow network.
  7. Most testing will require atleast 2 clients and 3 replicas.
  8. You can use global wallclock time for testing linearizability.

4 Grading

Component Points
Sequential + test cases 40%
Linearizable + test cases 20%
Eventual 20%
Report [Design, test case description, performance eval] 20%
Causal consistency + test cases 40%

Author: Prateek Sharma

Created: 2023-03-29 Wed 15:44