System requirements

Functional:

1. Read and write: the system should be able to support key value pair read and write.

Non-Functional:

1. Low latency: high performance, fast access to data
2. Availability: the store should be in highly available with zero downtime
3. Durability: no data loss

Capacity estimation

Estimate the scale of the system you are going to design...

High-level design

flowchart TB

subgraph server

direction TB

p1[P1] --> s1[S1.1]

p1[P1] --> s2[S1.2]

p2[P2] --> s3[S2.1]

p2[P2] --> s4[S2.2]

p3[P3] --> s5[S3.1]

p3[P3] --> s6[S3.2]

end

client <--> server

Client: the client is imported by the caller and provide get and set API to use. It's cluster-aware so when it's initialized it will be populated with the store cluster topology, which we will cover later.

Cluster: the cluster consists of primary nodes and secondary nodes to partition data.

Data Partition by Consistent Hashing

flowchart LR

vn1((A-01)):::green --> vn2((B-01)):::red

vn2((B-01)):::red --> vn3((C-01)):::blue

vn3((C-01)) --> vn4((A-02)):::green

vn4((A-02)):::green --> vn5((B-02)):::red

vn5((B-02)):::red --> vn6((C-02)):::blue

vn6((C-02)) --> vn7((A-03)):::green

vn7((A-03)):::green --> vn8((B-03)):::red

vn8((B-03)):::red --> vn9((C-03)):::blue

vn9((C-03)) --> vn1((A-01)):::green

classDef red stroke:#f00

classDef green stroke:#0f0

classDef blue stroke:#00f

So we would like to distribute data into different nodes to improve performance and scalability. In a normal way, when to decide which node to save a key value pair, we calculate it by hash(key) % n, where n denotes the total number of nodes. This leads to a severe inflexibility in adding/deleting nodes from the whole cluster because the data migration will happen on the all data set by hash(key) % (n - 1) or hash(key) % (n + 1) causing a significant overhead.

We will introduce the consistent hashing to improve this.

• The whole hashing ring is divided by a very large number say 2^10 = 1024 equal parts.
• Also to avoid non-uniform data and load distribution, we will introduce virtual node to put on the ring equally. In the graph above, we have three primary nodes, each of them comprises three virtual nodes. But in real world, one primary node consists of hundreds of virtual nodes to make the granularity very small.
• The mod function becomes mod_result = hash(key) % 1024. After key is hashed and mod, it will fall onto one point of this hashing ring, we move clockwise until it meets the next virtual node. The primary node which this virtual node belongs to is the server to save this key value pair.

Then we could come up with a metadata form which maps the server id to the ranges. For example:

{

NodeA: range 0 to 99, 300 to 399, 600 to 699, 900 to 999

Node B, range 100 to 199, 400 to 499, 700 to 799, 1000 to 1024

Node C, range 200 to 299, 500 to 599, 800 to 899

}

Pros:

• Small overhead by node replacement or data migration: only a small set of keys move when servers are added or removed.
• Uniform data distribution

Data Replication

To meet the requirement durability and avoid single point of failure, each primary node will have at least two secondary nodes to replicate data to.

Resilience: the primary node and 1st secondary node are within the same region but different availability zone, and the 2nd secondary node is within another region. This makes the system resilient to zone failure or region down.

So when a write request comes in, the primary node will write the data to its memory first, then it writes the data to its secondary nodes. After all of them succeed, primary node returns success to the client. So there is some trade-off between availability and consistency here. User could configure their consistency level, whether they need strong consistency or eventual consistency.

For read request, all the nodes including primary and secondary will be involved to handle the requests.

Node Discovery

Request flows

Cluster Management

Security

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?