System requirements

Functional:

• User can set, get, delete and update key value pairs
• Data is distributed between multiple servers
• Data can be saved to a persistant storage

Non-Functional:

• Hight availability on read and write 99.99%
• Low latency on read (30~100ms)
• Prioritise read availability over consistency (eventual consistency )

Capacity estimation

Assumption:

•  1 KB per key-value pair
• 1 billion record

So we need 1TB of memory space. assuming we replicate the data 2 time it's 3TB of total memory.

Assuming we store all the key on memory it would maybe 64 * 50 server. Which is a very large amount of keys. Maybe we can't keep all the ley hot in memory and reduce the server cost by using cold (disk storage with SSD and apply LRU or LFU policy to decide which keys are hot)

API design

Very simple crud API in the case

GET /records/{key}

POST /records/

body fields: key, value

PUT /records/{key}

body fields: value

DELETE /records/{key}

Database design

The system itself is a distributed database so lets talk about the inner working of the database.

Each server will be assigned one or more virtual node, and each node will be task with managing a given shard.

Virtual node forms a hash ring. And load is distributed using consistent hashing.

Shards are assigned a shard key based on the ordinal number of the virtual node they are assigned. A virtual node also hosts a copy of the shard of node (n-1) and (n-2) such that the ring contains 3 copies of each shard.

Data is first written to the primary shard, then replicated to the secondary shards (nodes n+1 and n+2).

We define a flush interval at which the node writes the current shard operations to disk (operation logs), the replication process starts once the oplog is written to the disk, a process captures the operation logs and replicates them to the secondary (ensuring eventual consistency)

High-level design

Request flows

A request arrives at the load balancer, which routes the write request to the primary shard and the read request to the secondary shard, preferably.

Once a write is committed, it is replicated to the secondary shards.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade-offs/Tech choices

Failure scenarios/bottlenecks

When a node fails, the n+1 node becomes the primary (the ring is automatically re-indexed). The mode n+2 becomes the second secondary and starts back-filling the missing shards.

This ensures no downtime of the system up to three consecutive nodes

Future improvements

Implement more advanced data structures, such as sets, hash sets, and sorted sets.