Loading...
[In Non-Functional Requirements, it is a good idea to think about availability vs consistency. If we require strong consistency, you'd first think about a transactional system, e.g., using RDB. On the other hand, if we can get away with eventual consistency, we can often get other useful properties like write throughput.]
We need only one API, which is for user to search.
GET /search?search_text
This returns a JSON array of URLs. It is sorted by relevance.
[
{
rank: 0,
url: ,
snippet: ,
}, ...
]
[It is usually a good idea to keep API simple. You'd get a better score by designing one API deeply, than designing many APIs shallowly.]
[Mid-level deep dive topic]
[It is a good idea to think (and talk) about data models briefly, as it affects DB choice and design. But don't overdo. We don't think it's necessary to define data models thoroughly, unless the interviewer asks explicitly.]
Data to be stored are:
Options to store Page Metadata:
[For any tech choice, it is better to present multiple options for the job, than simply pick one that seems the best. By showing you have thought about all (at least multiple) options and made tradeoff arguments, you would demonstrate a lot of maturity. This is one of the things that separate junior and senior candidates.]
RDB would thrive in strong consistency and relational queries.
Key-Value store would provide better write throughput and horizontal scalability.
As discussed above, the data model seems rather simple. We expect simple key-value look up, rather than complex relational queries (e.g. table joins). As such, we will pick a Key-Value store.
This is a key-value pair of:
"search words" -> links to pages.
Options for storage are:
As we discussed in non-functional requirements, the response time of query (look up pages by search words) has to be fast. Therefore, let's pick an in-memory cache here.
To mitigate the problem of reliability (data would be lost when an in-memory cache server crashes), we can use fault tolerance mechanisms of Redis, e.g., replicas and persistency.
There is a clear separation of read path and write path.
Write Path: Web Crawler service which crawls the web pages on the Internet, and stores the results in Inverted Index and Metadata DB.
Read Path: Search services uses the Inverted Index and Metadata DB to respond to search requests.
Web Crawler visits 3rd party web pages and adds new data to Inverted Index and Metadata DB.
Search Service responds to search queries from client, using data in Inverted Index and Metadata DB.
[Mid-level deep dive topic. We will not go into the detailed design of Web Crawler because it is a variation of a generic Web Crawler we designed in Web Crawler section https://codemia.io/system-design/design-a-web-crawler/editorial . We should be able to modify the generic Web Crawler for our purpose.]
Starting from seed web pages, Web Crawler crawls web sites, parsing HTML documents and following links.
This Web Crawler does not have to store the raw contents (e.g. HTML documents). Instead, it creates an inverted index (a mapping from search words to web pages) and stores it in Redis Cache.
It stores metadata for a web page, including the page URL, the ranking score associated to the page, and the last time it was visited.
[Mid-level deep dive topic.]
One of the requirements is for the search result to be up-to-date. For example, if a page is updated at 10AM, ideally, we might like the new content to be indexed and searchable by, 10:30AM or so.
One approach is to go through all the visited pages (stored in Metadata DB) periodically and re-crawl them. Given there are 10B pages, this would be too time consuming and costly.
It would be better to prioritize re-crawling. Luckily, we already have assigned a ranking score (see below). Periodically, we can query Metadata DB to find some pages to re-crawl, using a heuristic with (a) the last time it was visited, and (2) its ranking score. A batch job can run periodically and push the list of web URLs into the queue Web Crawlers take URLs from.
[Mid-level deep dive topic.]
Assigning a ranking score to web pages is helpful in two ways:
Let's design a simple ranking algorithm:
a. If Page A makes a hyperlink to Page B, Page B's score increases.
b. The higher Page A's score is, the larger the increase would be.
Web Crawler can calculate this value while it crawls the web. As it parses a HTML document to extract hyperlinks (e.g. page A -> page B), it can update the score on Metadata DB.
In the real world, the algorithm to determine the score would be a lot more complex, considering things like sponsored contents, fairness, and avoiding artificially inflated scores by search engine optimizations. This would be out of the scope of this design.
Explain any trade offs you have made and why you made certain tech choices...
See discussions in Database design and Revisiting Pages above.
[Junior-level deep dive topic.]
As the number of requests increase, we need to make sure the system scales.
What if the number of search requests increases drastically (10x)?
Search Service is a stateless service. We should be able to run multiple copies for horizontal scaling.
Redis Cache that holds Inverted Index should be partitioned. Options for the partition key are:
Option 2 is the better option. However, it has a challenge of uneven load distribution. Consistent Hashing can be used to mitigate it.
Metadata DB should be partitioned by Document ID.
[Mid-Level Deep Dive Topic.]
It is important to make sure Document Metadata and Inverted Index are safe guarded from faults, and the data are kept intact even if some nodes crash.
We can use read replicas for Cache. In the leader-follower configuration, writes go to the leader node. Read replicas (followers) are kept up to date. When the leader goes down or becomes offline, one of the read replicas can take over the leader role quickly.
Inverted Index, stored in Cache, should be persisted to permanent storage (e.g. disk) by Redis Persistence feature. In addition, it should be backed up in less expensive storage systems, within the same data center and in a few other data centers, for disaster recovery.
Metadata DB can have read replicas, too. Similar to the discussion on Cache, read replicas help on scalability and fault tolerance.
Data in Metadata DB should be backed up in less expensive storage systems, and in multiple data centers.
Future directions would include supporting images and videos, which would require larger storage space, and Machine Learning based labeling.
Page ranking mechanism can be enhanced, too.