System requirements

Functional:

Stakeholder: user

• User is able to insert a new node at front, back, or a specific possition
• User is able to remove an element from the front, back, or a specific position based on value or index
• User is able to Retrieve elements from the list in sequential order.
• User is able to Find the position or existence of a specific element in the list.
• User is able to Modify the value of an existing element in the list.

Non-Functional:

• Fault tolerance: When a node fails, the system should still support operations correctly. The system should be able to recover from a failure.
• Consistency: All nodes should see the same data at the same time.
• Scalability: the system should scale as increased traffic
• Latency: the system should react to the operations within 100 ms
• Maintainability: The state of the system should be monitored, any abnormal value should be alerted, it should support debugging the system well.

Capacity estimation

• Assume each element is as large as 100 bytes.
• Assume the size of the linked list is 10k nodes
• The overall storage requirement is 1MB.

API design

• Add node
  • Request
    • bytes value
    • int position
  • Response
    • Status
    • int id

• Delete node
  • Request
    • int id
    • int position
  • Response
    • Status

• Search node
  • Request
    • bytes value
    • int id
  • Response
    • Status
    • int id

• Retrieve node
  • Response
    • int id
• Next
  • Request
    • int id
  • Response
    • Status
    • int id

Database design

The nodes are stored distributedly. Considering that the size of the entire list is small, so to achieve low latency, we can store them in memory as the following structure.

• int id
• bytes value
• int next_id

For the persistence requirement, we can record log events at the request handler, so that we can restore the system from the event log. The write ahead log is also very performant for heavy writes, so it won't affect the latency.

• timestamp
• int id
• byte value
• operation

High-level design

• API gateway: Does authentication, rate limiting, load balancing
• Request handler: handles the requests. Since request handlers are stateless, it is easy to scale these instances up by bringing up more instances. We can have a cost reporting algorithm from request handler back to API gateway, so that API gateway can decide which node the request is routed to.
• MQ: We can have a MQ between request handler and the log storage, to asynchronously write to log storage.
• log storage: We can write ahead log to store the operation logs. The write to the log are async to achieve low latency of answering requests.
• Storage node: keeps the storage in memory. The nodes should be distributed to achieve high concurrency. Thus, replication is required. There are high write and read QPS at the same time, so we should use a qorum based algorithm to balance the latency with the consistency.
• Coordination service: We can use zookeeper as the coordination service. It maintains which storage node is online and the qorum algorithm and configuration. It also has the ability to discover the service.
• Monitoring service: Keeps several metrics for different components: QPS, CPU usage, MQ size, storage size, storage freshness, log storage size, log storage freshness.

Request flows

Receive Operation:

• User sends a request to API gateway
• API gateway calculates with the cost reporting to decide which node this should be routed to, and forwards the request to the correct request handler node
• Request handler receives the request and looks up the online storage nodes from coordination service.
• Request handler sends the operations to the corresponding storage nodes, wait for write/read acknowledgement to meet.
• storage node processes the operation, send back the acknowledgement.
• After receiving the acknowledgement, Requqest handler sends the event to the messagequeue
• persistent storage fetches the log events from MQ.

Detailed component design

• Storage node qorum: i.e. if we have 5 nodes, and user sets write ACK to 3 and read ACK to 3, then both read and write need to get at least 3 nodes to return to confirm that this operation is done. The rest of the nodes will still operate on the operations and may sync periodically with a checksum operation.
• When nodes failure happens, nodes can read from the persistent storage to replay the events to restore.

Trade offs/Tech choices

• The quorum algorithm trades latency for consistency. The consistency is not strong consistency, but it keeps consistency among the nodes, and it kept latency well.

Failure scenarios/bottlenecks

• When nodes fail and we want to bring new node, we can use the persistent log storage to make sure the new node keeps update quickly
• If MQ fails, the event won't be written to log storage correctly.

Future improvements

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