System requirements

Functional:

1. Client can store a key-value pair in the store by calling the relevant API
2. The store is distributed in nature
3. The store supports large data sets

Non-Functional:

1. Availability - Client should be able to access the key value store at any time
2. Consistency - We aim for eventual consistency here, meaning it is possible that clients get stale values for some period of time which the store is synchronized
3. Latency - The system should have reasonable latency

Capacity Estimation

1. We estimate that each key-value pair is 10 KB in size, which equals 10^4 bytes
2. We assume that we store a total of 1 billion such pairs in a year, meaning we need 10^9 * 10^4 = 10^13 bytes = 10 TB data every year
3. Over 10 years, we would need 100 TB data
4. We factor in replication and other overheads and we are looking at roughly 500 TB data

API Design

We would need 4 different APIs, all of which are described below.

1. Store key-value pair
   1. POST
   2. Takes a key value pair from the user and stores it in the database
2. Get key-value pair
   1. GET
   2. Fetches the value corresponding to a particular key
3. Update key-value pair
   1. PUT
   2. Updates the value corresponding to a key if it exists, returns an error otherwise
4. Delete key-value pair
   1. DEL
   2. Deletes a key-value pair corresponding to a key if present

Database Design

1. We will use a non-relational DB which supports key value stores like DynamoDB
2. If not using a traditional DB, we can use a string sorted table, where keys are sorted in ascending order. We employ binary search to search for a key in the table

High-Level Design

1. All components are stateless
2. All components are horizontally scaled

flowchart TD

Client["client"];

Server{"API Server"};

Database["Database"];

Balancer["Load Balancer"];

Cache["Cache"];

Client --> Balancer;

Balancer --> Server;

Server --> Database;

Server --> Cache;

Request Flows

1. On reads, we first hit the cache, if the key-value pair is present we fetch the corresponding value, otherwise we fetch it from the data store and store the key-value pair in the cache
2. On adding a key-value pair, we simply write the pair in the data store
3. On updating the key-value pair, we update the pair in the data store and write the pair in the cache as well. If the key is already present in the cache, we update the corresponding value
4. On deleting key-value pairs, we delete them from the data store and the cache if they are present in it
5. All API requests go though the load balancer which assigns a server to a request based on average response time of the servers

Detailed Component Design

1. To avoid remapping a large number of keys when adding or removing servers, we use the consistent hashing algorithm, where we create a ring with all the possible hash values, place our servers on the ring as well, choose a hash function which creates a hash of our key, see where the hash falls on the ring and go clockwise until we find a server and store the key-value pair in that server and the next N servers for replication purposes, where N is a configurable parameter
2. We also add virtual servers to our ring to ensure uniform distribution of key-value pairs across our stores
3. We understand that we are aiming for eventual consistency here, where for a short time, requests may fetch incorrect results
4. To resolve conflicts, we use vector clocks
5. To detect failed nodes, we employ the Gossip protocol where each node sends a bunch of random nodes a heartbeat. If a server notices that a certain server has not sent a heartbeat for a while, it notifies other servers that it suspects that this server is down. The other servers also check the heartbeats received from the server in question, if multiple servers agree that a heartbeat has not been heard from the server in question, it is marked as down
6. One of the nodes will serve as the coordinator of the whole process, it is elected via an election
7. We can utilize bloom filter to check if a key is not present in our data store

Trade Offs/Tech Choices

1. Having a cache means at times, we can end up with stale reads
2. We are aiming for eventual consistency, hence, even if we did not use a cache, we would have had stale reads since we would use a database that employs multi leader replication

Failure Scenarios/Bottlenecks

1. In case of a failure of a data nodes, we promote one of its replicas as the leader
2. If in our consistent hashing scheme, if our coordinator node fails, we promote a new node to be the leader

Future Improvements

1. We can add an expiry date to a key-value pair, meaning it will be invalidated after a set amount of time
2. We can have a complicated data store mapped to our key, which we can store in the form of a JSON
3. If we want strong consistency, we can opt for a relational database like MySQL