System requirements

Functional:

• CRUD key value pairs

Non-Functional:

• high availability
• eventual consistency
• tolerant network parition

Capacity estimation

• each key value pair is less than 10kb

API design

• Add(key, value) -> error | none
• Get(key) -> error | value
• Update(key, value) - > error | none
• Delete(key) -> error | none

The error can be when

• key isn't fond for Get/Update/Delete
• all client side errors like authn/authz failures
• server side errrors, network failure, server error

Database design

Each node is responsible to maintain a sstable underlying to store the key-value pairs

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

• the load balancer and API Gateway can help doing load balancing(round robin), API rate limiting, authn/authz
• We have a group of nodes which implements the consistent hashing for replicas and fault tolenrance
• inside each node, the data is read/written into a ss table

Read / Write -> Coordinator Node -> certain node -> mem cache -> sstable on disk

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

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

• Consisten hashing for auto scaling | data parition | data replica:
  • Algo: we use a has ring, let's 0 -> 2 ^ 64 and split it evenly into multiple rangee, each of which is assigned to a virtual node. Multiple virtual nodes are mapped to a physical node.
    • When a node is added, some of the existing virtual nodes can be assigned to it. When it is removed, its owned virtual nodes can be redisturted to other physical nodes
    • For key lookup, it will be handled for the virtual node hit when going clockwise on the hashnode
  • By doing, we can scale up and down the instance numbers by need
  • Also, we can keep muliple replicas for each data on different physical nodes
• Eventual consistency
  • By CAP theorem, we can only support 2 of consistency, availability and network parition tolenrance. We know network parition tolenrance is a must for distributed system and we choose availability over consistency(of course in some case like banking system, consistency is more critical). W + R < Q according to quorum theorem
  • We can uses version lock to detect inconsistency concllit by [ServerNumber, DataVersion] to get the final value by determining the preceding / succeeding relationship of the two data.
• Failure detection:
  • decentralized failure detection(gossip protocol)
  • takeover
    • if one node is failed, another node can take over for its requests temporialy until it is recovered
    • when it is done, sync all the updates back
• Read path:
  • client hit coordinator node
  • coordinator node forward the corresponding node by its key hashing
  • the node look up in memory, return if found. otherwise look up in SSTable(bloom filter can be a used for another cache)
• write path:
  • client hit cooridnator node
  • write the corresponding physical nodes, write to cache and sstable

Trade offs/Tech choices

We over-weight availablity over consistency but we still provide eventual consistency.

Failure scenarios/bottlenecks

Future improvements