Requirements

Functional Requirements:

• Support put/set a value by key, get/retrieve a value by key, and delete/remove a key-value pair.
• Replicate data across multiple nodes for fault tolerance and high availability.
• Partition data across multiple nodes in the cluster to enable horizontal scaling.
• Provide options for persisting data to disk to safeguard against data loss.
• Support conditional writes where a value is updated only if a condition is met, enabling compare-and-swap (CAS) semantics.
• Allow keys to have a time-to-live (TTL) after which they are automatically expired and removed.

Non-Functional Requirements:

• Highly available
• At least eventual consistent
• Allows strong consistency if required
• Low latency

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

GET data/key/:id -> value

POST data/key/:id

{

value: any

}

DELETE data/key/:id

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Partitioning is done via Consistent Hashing algorithm to ensure proper balanced distribution of the data for each shard.

To handle TTLs, have Lazy Read updates (e.g. expired rows are deleted when they are read) combined with a background cron job that cleans up cold stale data.

To ensure highly available system, we use a leaderless system with read and write quorum to avoid running Raft/Paxos if the leader dies.

To support CAS operations we can use Vector clocks with a version number for each row, if two swap operations happen at the same time only one of them will have the correct version, the other would fail.

Data is regularly copied to disk via background backup jobs.

We can also have configurable consistency model (strong consistency vs eventual consistency). User can set the number of nodes that need to confirm reads(R) and those that need to confirm writes (W). If W + R > N then the key-value store is strongly consistent, otherwise we would use the eventual consistency model.

If W + R < N to guarantee an eventual consistency model we can use Anti-Entropy with Merkle Trees which runs regularly and fixes replicas with stale data.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Simple in memory data

|key | value | version|

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.