Distributed Multi-Consistency Key-Value Store

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 .

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.