System requirements

Functional:

• Provide key-value store to users. Support the usual KV store operations like get, set, delete, conditional update.
• Stretch
  • Support TTL
  • Support advanced data structures like sorted set

Non-Functional:

• System is highly available (99.99%)
• Eventual consistency is okay
• Minimal latency: <5ms for all operations
• Fault tolerant: no single point of failure, persistence enabled with quick recovery time
• System is scalable: new servers can be added/removed to scale out/in

Capacity estimation

• We aim to have a horizontally scalable service that can in theory scale infinitely
• The estimation may not materially affect the design but we do some estimates anyway
• Assume each server holds 500GB of data, and each KV pair is on average 100 bytes, each server can hold 1 billion KV pairs

API design

set(key, value)

get(key) -> value

delete(key)

update(key, comp, value) -> oldValue

Database design

For in-memory storage, we choose a hash table to store the KV pair.

We should shard the servers using hash of the key, and placing the servers in a consistent hash ring.

We each shard, we should create replicas.

High-level design

Gateway

• Maps client request to the correct server

Shard 0 to N

• Stores KV data

Shard 0 to N replica

• Replica servers for the shards

Request flows

• Client sends request to the Gateway node
• Based on the hash of the key, gateway locates the correct shard on the consistent hash right, and forwards the request
• The server performs the request on a single thread for all incoming requests on that server, and returns value if needed

Detailed component design

Consistency between replicas

There are several options, that can be made configurable

• Block the request until all replicas are written. This can slow down the write path
• Block the request until a quorum of servers are written to. This increases availability. At read time the differences are reconciled based on quorum.
• Keep a WAL + quorum. This improves upon the previous option. A background reconciliation process can update replicas.
• Periodically the WAL can be checkpointed and compressed.

Handling shard failures

• We can implement something like the sentinel mode for redis
• Servers in each shard monitors the primary replica. If a quorum of replicas agree that the primary is down, they elect a new primary replica.

Trade offs/Tech choices

• For consistency, we tolerate a certain level of eventual consistency in favor of availability and latency.
• A strongly consistent protocol like 2-phase commit is too slow for applications that in-memory cache aims to serve.

Failure scenarios/bottlenecks

Shard node failures

• This is addressed by replication

Network partition

• Quorum-based algorithm addresses this

Replication failures

• With WAL and reconciliation process, we alleviate the problem at the expense of consistency

Future improvements