System requirements

Stakeholder: SRE, indexing system

Functional:

• The system should be able to crawl the contents from wikipedia
• The contents should be stored in a shared storage with the following pipeline
• Duplicate content should be avoided
• Updates should be crawled in delta

Non-Functional:

• High throughput: Wikipedia should be crawled with less than a few hours
• Scalability: The system should scale up if source expands
• Fault tolerance: Single instance failure should not affect the overall system performance
• Observability: The system should be easy to maintain, the system status should be monitored, alerts should be given if some piece goes wrong

Capacity estimation

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

API design

Define what APIs are expected from the system...

Database design

There are types of data need to be stored:

ContentMetadata

• String url (PrimaryKey)
• String content_storage
• datetime updated_on
• checkSum

High-level design

• MessageQueue: Stores all the urls to be fetched, since there is a content check service, we don't need worry about duplicate service, so it should be configured as at least once to allow retry.
• Scheduler: Monitors the cost and load of each worker, fetch the url from MessageQueue, check the limit number from rate limit checking service, assign the url to crawl to the worker node, also monitors the health of all the worker nodes, once found a dead node bring up a new instance.
• Worker: check the duplication and delta update from the content check service, crawls the content, store it to file storage
• File storage: Can be a distributed file system
• Metadata storage: Can be a non-relational database since there is a requirement of high write and high read
• Rate limit checking service: stores the rate limit requirement from wikipedia
• Content check service: Looks up the url to be fetched from the meatadata storage, compares the checkSum with worker node and determines if the content is duplicated. Checks the update time and decide delta update.

Request flows

• Scheduler fetches from the MessageQueue
• Scheduler checks the load of each worker
• Scheduler assigns the url to worker
• worker fetches checksum and update time from wikipedia
• worker send request to content check service to check if it should proceed
• content check service looks up the url compares checksum and update time then respond to worker
• worker decide to delta update or discard the request.

Detailed component design

• Considering the large volume of traffic for cheking sum and update, the content check service can also be distributed. Each instance can be stateless. There can be thin layer of load balancer that routes the requests to different nodes.
• To improve fault tolerance, metadata storage should be replicated. Although the size of data might not be large, replication is needed. We relie on the consistency to avoid duplicate crawl, so we need a quorom based algorithm to solve the read/write consistency. We can config the read/write ACK before starting the system. Only after a read/write request receives the success response from ACK nodes, the request is considered as successful. Otherwise, the request need to be reverted. The ACK can be configured with a coordination service, which maintains the ACK config, node status and node address.

Trade offs/Tech choices

• Checking of the duplicate page can be done at either scheduler or worker. Checking at scheduler will prevent from duplication and lower traffic to content, but there will be higher latency, which will make scheduler as a potential bottleneck.

Failure scenarios/bottlenecks

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

Future improvements

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