System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• Users can set key value pairs, with TTL configurable (max 1 day), max 1000 KV pairs allowed per day.
• Support set, get, delete, update operations.
• On GET operation, if key exists then return value. Else NA.
• Persistence is expected.

Non-Functional:

List non-functional requirements for the system...

• In memory database.
• Since the scale is expected to be big, it has to be horizontally scalable.
• Key access has to be < 2ms for eventual consistency.
• Support flexibility between strong and eventual consistency for reads.
• Data replication and persistence is expected.

Capacity estimation

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

• 30m users per month. Approximately 1m users per day.
• on average approximately 500KV pairs per user daily.
• Each KV pair (key : 32B, val: 128B, TTL: 4B (int)) = 164B
• Storage Needed :
  • In Memory : since TTL max is 1 day, lets calculate for Bytes needed per day, assuming all keys per day have 1 day TTL.
    • 1m * 500 * 164B = 80GB/day max.
  • Persistent Storage for 3 years : 80GB/day * 30 days * 36 =86,400 GB.

API design

Define what APIs are expected from the system...

POST /putKV

Request Body : { Key, Value, TTL }

Response 200 if succeeded. 503 if unable to succeed.

UPDATE /updateKV

Request Body : { Key, Value, TTL, condition }

Response 200 if succeeded. 503 if unable to succeed.

GET /getKV

Request Body : { Key }

Response 200 if succeeded. 404 if no key is present. 503 if unable to succeed.

DELETE /deleteKV

Request Body : { Key }

Response 200 if succeeded. 404 if no key is present. 503 if unable to succeed.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

.there is a load balancer that sits on front, accepting client requests. It is a L7 LB handling api requests. Based on the user id for the request and the key, which is unique, consistent hashing is used to find N (N replicas) backend master servers where this key can always be found.master server will always deal with writes. there are slave servers to it and master, based on configuration settings if strong consistency or eventual consistency is preferred, master service would either wait for write acknowledgements from slaves before sending a ack or immediately send it and asynchronously sync with replicas.number of master server depends on the number of volume of data to be handled at any given time. updates follow the same path as putKV, but does it only when condition meets. same with /deleteKVgetKV gets redirected to replicas where the hash range fall under and it queries any one of the replica based on load. Masters also commit to a WAL for every write/object storage as dump every few minutes. 

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

.there is a load balancer that sits on front, accepting client requests. It is a L7 LB handling api requests. Based on the user id for the request and the key, which is unique, consistent hashing is used to find a backend master server where this key can always be found.master server will always deal with writes. there are slave servers to it and master, based on configuration settings if strong consistency or eventual consistency is preferred, master service would either wait for write acknowledgements from slaves before sending a ack or immediately send it and asynchronously sync with replicas.number of master server depends on the number of volume of data to be handled at any given time. updates follow the same path as putKV, but does it only when condition meets. same with /deleteKVgetKV gets redirected to replicas where the hash range fall under and it queries any one of the replica based on load.

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...

The master and replicas.

• On any master failure, one of the replica elect within themselves and becomes the leader. During this time, writes can either be stopped completely or make them queue at the LB level locally and get them processed when the master is healthy and up.
• incase of a network partition between master and slave, slaves with unhealthy partition can redirect the read to healthy slaves that are still in sync with master and heal later when partition heals.
• Scaling the masters horizontally are easy since LB uses consistent hashing to map keys to master nodes. Rearrangement of keys would be limited as well, to the node nearby it.

Persistence:

For persistence, based on accuracy of persistence, they can choose either a WAL to which each master service would log before committing a write, would be useful to exactly roll out events and get back to the previous state as it was. But this would take a longer 

Master service:

• since master service is designed only to consume data from socket and write, it can be configured as a single threaded application where all writes are serialised and there is no scope for contention.
• doing multithreaded writes would potentially increase latency for each writes because of waiting for lock to unlock etc.

Trade offs/Tech choices

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

For persistence, based on accuracy of persistence, they can choose either a WAL to which each master service would log before committing a write, would be useful to exactly roll out events and get back to the previous state as it was. But this would take a longer 

based on configuration settings if strong consistency or eventual consistency is preferred, master service would either wait for write acknowledgements from slaves before sending a ack or immediately send it and asynchronously sync with replicas.number

I have chosen In mem to store kv values because in memory data access is around 100ns latency and also hash map would be a good choice for storing values since they operate in O(1) time.

Failure scenarios/bottlenecks

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

in case of strong consistency, latency would take hit since it has to replicate across all replicas.

if there is a master failure, writes would have to get suspended until a new master comes up.

Future improvements

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

there is async configuration to tradeoff consistency for lower latency.

LB can enqueue pending requests to a queue until a new master is elected and then process them.