System requirements

Functional:

1. We can store a value mapped to a key.
2. We build APIs that supports the storage and retrieval of key value pairs.

Non-Functional:

1. Scalability - The system should be able to auto scale according to a larger data set.
2. Reliability - We are comfortable with eventual consistency. We prioritize availability over consistency.
3. Reliability - We can never a value associated to a key.
4. Latency - We aim for a small latency when storing or fetching a key-value pair.

Capacity Estimation

1. We estimate that each key-value pair would be 10 KB in size, which is 10^4 bytes.
2. We assume we store 1 billion key-value pairs in a year, meaning we need 10^9 * 10^4 = 10^13 = 10 TB.
3. Over 10 years, we would need 100 TB storage just for our key-value pairs alone.
4. We factor in replication and other overheads and we are looking at 500 TB of needed storage over 10 years.

API Design

We would need 4 APIs, one for creating a new key-value pair, one for fetching the value associated with a key, one for updating a key-value pair and the last one to delete a key-value pair.

1. Store key-value pair
   1. POST
   2. Takes in the key and value as parameters and stores the pair in our store
2. Get key-value pair
   1. GET
   2. Takes in a key and returns a value in case it exists, otherwise, return an error
3. Update key-value pair
   1. PUT
   2. Updates the value associated with a key if it exists, returns an error otherwise
4. Delete key-value pair
   1. DEL
   2. Takes in a key and deletes the key-value pair associated with it

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 are keys are in sorted order

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 value is not found then we hit the data store. We get the value from the data store and write the key-value pair in the cache for future reference
2. On adding a key-value, we simply write the key-value pair in the data store
3. On updating a key-value pair, we update the value in the data store and also check if the key-value pair is present in the cache, if it is, we update it
4. On deleting key-value pairs, we delete it from the data store as well as the cache if it is present. This ensures that we do not do a stale read in the future
5. All API requests go through a load balancer which employs assigns a server to a request based on average response times of servers

Detailed component design

1. To achieve remapping a large number of keys when adding or removing servers, we use the consistent hashing algorithm, where we create a ring of all the possible hash values, place our servers on the hash ring as well. We create the hash of a key and see where it falls on our ring, we travel clockwise on the ring and store the key-value pair in the first node we find
2. We also add virtual nodes to the ring to ensure uniform distribution of key-value pairs on the ring
3. To ensure that we do not lose data, instead of just copying the key-value pair on the first node we find, we copy it in the first N nodes we find while going clockwise on the ring. This ensures a high degree of data replication
4. In terms of consistency, we are going for eventual consistency, where for a short time, the value returned for a key may be inconsistent
5. To resolve conflicts, we use vector clocks.
6. To detect failed nodes, we use 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 the 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
7. We employ bloom filters to see if a key is present in our cache and data store or not

Trade Offs/Tech Choices

1. Having a cache means at times we can end up with stale reads
2. Since we are using a data store that uses a multi leader replication setup, we will deal with stale reads. We are comfortable with that since are aiming for eventual consistency

Failure Scenarios/Bottlenecks

1. In case of failure with our data nodes, when we fail a node, we promote one of its replicas as the leader
2. If in our consistent hashing scheme, the coordinator node fails, we promote a 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 value
3. If we want to ensure strong consistency, we would use a relational database like MySQL