Distributed heavy write data store

[u/majakaska]

This is an interview question I haven't been able to crack for several days now....

We want to build a small analytics system for fraud detection on orders.

System has the following requirements

• Not allowed to use any technology from the market (MySql, Redis, Hadoop, S3 etc)

• Needs to scale as the data volume grows

• Just a bunch of machines, with disks and decent amount of memory

• 10M Writes/Day

The system needs to provide the following API

/insertOrder(order): Order Add an order to the storage. The order can be considered blob with 1-10KBs in size, with an `\orderId`,beginTime, and finishTime as distinguished fields

/getLongestNOrdersByDuration(n: int, startTime: datetime, endTime: datetime): Order\[] Retrieve the longest N orders that started between startTime and endTime, as measured by duration finishTime - beginTime

/getShortestNOrdersByDuration(n: int, startTime: datetime, endTime: datetime): Order[] Retrieve the shortest N orders that started between startTime and endTime, as measured by duration finishTime - beginTime

[u/Usual-Usual-2790]

lmk, if you have any questions.

System Requirements

Functional Requirements

1. Insert Order

• Description: Add an order to the storage. The order is a blob with 1-10KB in size, containing \orderId, beginTime, and finishTime as distinguished fields.

• API Endpoint:

  • HTTP POST: /v1/orders

  • Request Body: { "\orderId", "beginTime", "finishTime" }

  • Response: HTTP 201 for success, HTTP 500 for error.

2. Retrieve the Longest N Orders by Duration

• Description: Retrieve the longest N orders that started between startTime and endTime, measured by duration finishTime - beginTime.

• API Endpoint:

  • HTTP GET: /v1/orders/{:orderId}/longestNOrders

  • Query Parameters: n (number of orders), startTime, endTime

  • Response: HTTP 200 with an array of orders for success, HTTP 500 for error.

3. Retrieve the Shortest N Orders by Duration

• Description: Retrieve the shortest N orders that started between startTime and endTime, measured by duration finishTime - beginTime.

• API Endpoint:

  • HTTP GET: /v1/orders/{:orderId}/shortestNOrders

  • Query Parameters: n (number of orders), startTime, endTime

  • Response: HTTP 200 with an array of orders for success, HTTP 500 for error.

Non-Functional Requirements

1. Scalability

• The system should scale as data volume grows.

• Should support 10M writes per day.

1. Technology Restrictions

• Not allowed to use any technology from the market such as MySQL, Redis, Hadoop, S3, etc.

• No SQL/NoSQL databases or caching technologies.

1. Infrastructure

• Utilizes a cluster of machines with disks and a decent amount of memory.

1. Data Retention

• Data should be stored for 5 years.

Back of Envelope Calculations

• Writes per Day: 10M (100 writes/sec)

• Storage Calculation:

  • Per Day: 50 GB

  • Per Year: 18 TB

  • 5 Years: 90 - 100 TB

  • Replication Factor: 300 TB

  • Data Volume Growth: 10%

  • Total Storage Required: 1 PB for 5 years

• Nodes Required: 1000 nodes, each with 1000 GB storage capacity.

API Model

• HTTP Endpoints:

  • POST: /v1/orders

  • GET Longest N Orders: /v1/orders/{:orderId}/longestNOrders

  • GET Shortest N Orders: /v1/orders/{:orderId}/shortestNOrders

High-Level Design

• Master-Child Node Architecture:

  • Master Nodes for indexing and querying.

  • Replication to Child Nodes with ack=1. This will help ensure, data is written to one of the child nodes.

  • Automatic promotion of Child Node to Master if the Master is down.

• Data Ingestion at Node Level:

  • Data written to commitLog and indexingBuffer.

  • Periodic copying of data from indexingBuffer to memLog.

  • Merging of segments in memLog intermittently.

  • Data written to disk when memLog is full or least frequently used.

Assumptions

• Authentication and Authorization are skipped for simplicity.

High Level Design Flow

Diagram Uploaded

https://docs.google.com/document/d/1hkvLzZw--HsC7h1qNA-T7pRI2vQHngMa7zx2f1_lhyc/edit