Requirements

Functional Requirements:

• Efficiently crawl and index billions of webpages, extracting relevant content for future searches.
• Sophisticated query processing handles complex user queries with precision.
• Search results ranked based on a robust algorithm that prioritizes alignment with user intent.
• Update the search index in near real-time to reflect latest web content changes.

Non-Functional Requirements:

• low latency - the autocomplete search responses should take less than 100 ms so the users wont see delays
• scalability - the system should be able to scale out on high demand by adding more servers and using sharding for db
• security users' search data should be protected and private (GDPR compliance and any other users compliances)
• reliability: up time 99.99% for users, they should always be able to see autocomplete searches

API Design

GET /autocomplete/search/{search}?limit=10 - this is used for autocompleting the search, we check the search term and return the list of suggested results, also we can add a constant so we only return 5 or 10 results for example, also we can constrain the search term to 50 chars

it returns a list with the search term results ordered by their rank which is incremented each time a user searches for that specific term. response is in JSON format and it is the core functionality of the api

POST /autocomplete/selected/{selected} - used for saving the selected term so we can increment the number of searches for that specific term

GET /analytics?search_term={search_term} - used by admins to get all analytics for search terms (eg how many people searched for it, what rank it has, etc)

GET /search?q={query}&page=1&limit=20&filters={JSON} &sort=relevance|date|popularity&date_range=past_day|past_week|past_month|past_year&site={domain}&type=web|image|video|news - full search endpoint that accepts filters like date range, content type (web/image/video), specific site/domain, and sorting options (relevance, date, popularity). It should return paginated results with total count, spelling suggestions ("did you mean X?"), related searches, and facets for filtering.

High-Level Design

flow search autocomplete:

1. user makes api call
2. reaches api gateway which uses rate limiter and if the user abuses the api then his call is declined
3. then call reaches Load Balancer which distributes it evenly over search services
4. search services apply some filtering, like striping special chars or doing spell checks and fetches trie cache
5. trie cache is a tree-like component which has the root an empty string, and node letters from a-z and each node has again letters a-z. we can limit it to 50 depth and at each node level we also store top 10 searches ordered by their rank and relevance
6. we should use CDN for storing trie caches, this way each region will have its own trie based on local searches and their popularity
7. when cache is missing we check the trie db directly and then cache the result and return it to the users

if we want content based on locations preferences, then we can store in cdn in different regions the tries and each region will have its own trie built with search suggestions

flow for updating the trie:

1. user selects one of the search autocomplete options, then makes a call
2. call goes to api gateway, rate limiter, load balancer and search services;
3. it increments the rank points of the term inside trie cache and in db;
4. asynchronously the aggregation worker calls trie builder which keeps updating the trie db during time intervals, with the new trending search results

for analytics, admins can check the rank points of a search term, it can also check the analytics service and its db to see different analytics

results for a search term will be cached at user lavel for 3600 seconds, just like google does by setting x-cache header to 3600s

we should also have a crawling system which takes some seed urls and starts downloading their content, fetching links from content and then if not already crawled, add them to the queue and start the crawl process, this way we will match the search terms to page contents. when changes are detected, we should update the trie results too.

each user query is checking the trie, searching for the string, and when finding the node it will return the data stored at its level: top k most searched terms for the string. when the user then selects the element from the returned list, we will increment by one the number of searches for it. whenever the number of searches is increased enough to reorder the ranking, then we update the data stored for that node

The crawling system starts with seed URLs and downloads page content. For each page, the Content Extractor parses HTML and removes boilerplate elements like navigation, ads, and footers. It extracts the title, body text, meta description, and outbound links.

The Document Processor then tokenizes the text into individual words, removes stop words (the, is, and), and applies stemming to normalize variations (running, runs, ran all become run).

The Index Builder creates an inverted index mapping each term to the documents containing it.

Incremental updates detect changed pages via Last-Modified headers and ETags, updating only those documents.

when db is down, user receives data from cache, if the cache is down, it receives data from db, if both are down, results are also cached for one hour in browser for each user so it will get data from there. for popular queries, we cache them in different shards so they can be faster accessed

Detailed Component Design

The URL Frontier maintains priority queues ordered by domain authority and freshness requirements. High-priority queues contain news sites and popular domains, medium priority contains blogs and forums, low priority contains deep pages and archives.

For politeness, we maintain separate per-domain queues. Before crawling, we fetch and parse robots.txt for each domain and obey its rules. We enforce a minimum 1-second delay between requests to the same domain and respect Crawl-Delay directives when specified. If a domain returns 429 (rate limited) or 503 (overloaded), we back off exponentially.

Documents go through a processing pipeline: first we extract raw text from HTML, then tokenize into words, convert to lowercase, remove stop words, and apply stemming. For keyword extraction, we calculate TF-IDF scores to identify important terms per document.

The index builder maintains a write buffer in memory. When the buffer reaches a threshold (e.g., 10,000 documents), it flushes to disk as an immutable segment

Before crawling, we check a Bloom filter containing all previously seen URLs. This catches most duplicates with minimal memory.

On cache miss for autocomplete: Query falls through to Trie DB, result is fetched, cached in Trie Cache with TTL, then returned to user. Latency increases from ~5ms to ~50ms.

Multiple crawlers coordinate through a centralized URL Frontier service backed by Redis. Before fetching, a crawler claims a URL by setting a lock with TTL (e.g., 5 minutes). If the crawler dies, the lock expires and another crawler can claim it.

when