Post and web search (Twitter/FB search, Google)

01 · CONTEXT

Searching posts without an off-the-shelf engine

The exercise is searching posts on a social network: users create and like posts, search posts by keyword, and choose to see the results by recency or by number of likes. The prompt assumes an interview rule: no off-the-shelf search engine and no prebuilt full-text index, because the goal is to test data organization, indexing, and scale.

The scope leaves out fuzzy term search, privacy rules, and personalization. Dropping personalization is the decision that helps the most: two people who search the same term with the same parameters see the same result, and that makes caching far more effective.

The non-functional requirements are the heart of the problem. The median query must respond in under 500 ms, a new post must become searchable in under a minute, every post must be findable, including old or unpopular ones, and the system must be highly available. The slack for old posts already suggests hot data in memory and cold data in cheaper storage.

02 · SCALE

Writes rule

The source starts from simple assumptions: one billion users, each creating one post per day, liking ten, and running one search. Rounding the day to one hundred thousand seconds, that gives about 10 thousand posts created per second, 100 thousand likes per second, and 10 thousand searches per second. With ten years of posts and about 1 kB of metadata per post, the raw volume reaches the range of 3.6 PB.

The lesson is in the comparison: it is a common mistake to fixate on search and assume that reads weigh more. Here likes far outnumber post creation, and the system is heavier on writes than on reads. The size of the volume also warns that you will need to limit what goes into the index.

03 · INDEX

From scan to inverted index

The naive solution stores the posts in a relational database and searches the text with a LIKE over all of them. It returns the right answer, but it is extremely slow, because the database has to look at every post at query time. Splitting the database into pieces (particionamento) or replicating it helps only a little, and the search is still far too slow.

1. The user asks for the posts that contain a word; the request goes through the gateway.

2. The search service sends the database a query that looks for the word's text inside every post.

3. Without an index, the database has to look at every post at query time; splitting the database into pieces reduces the work of each node, but the scan is still too expensive.

The right path is the inverted index: a dictionary that maps each word to the posts that contain it. When a post is created, ingestion breaks the text into words (tokenization) and appends the post ID to each word's list. The source keeps these lists in memory, with durable storage as an alternative for the durability question.

1. A new post reaches the posts service, which writes the content to the posts database.

2. The posts service notifies ingestion, which breaks the text into words (tokenization).

3. For each word in the post, ingestion appends the post ID to that word's list in the inverted index.

4. On the read path, the user searches for a word and the request reaches the search service.

5. The search service takes the word's list of IDs from the index and returns the posts, without scanning the database.

There are costs. A post can have from ten to a thousand keywords, so each post becomes many writes, and the ID lists for common words become enormous.

04 · SORTING

Recency or likes

Sorting at query time is the bad option: you take the word's list of IDs, look up the date or like count of each post, and sort in memory. For a very common word, with tens of millions of results, the index's response would reach hundreds of megabytes, and sorting millions of items on the spot adds latency for no reason.

The alternative is to keep two indexes per word: one sorted by creation and one by likes. The first can be a list where you only append at the end and read from the end; the second, a set sorted by score. The tradeoff is clear: storage doubles, and each like now requires updating several scores.

05 · READING

Cache, CDN, and phrases

To absorb the read traffic, the cache is the obvious tool, because two requirements help: there is no personalization and a post can take up to a minute to appear. A results cache next to the search service, with a time to live shorter than that deadline, never serves a result that ignores a post that should already be included.

At the edge, a CDN can store /search responses if the response carries cache-control headers. A CDN hit responds in tens of milliseconds, versus hundreds of milliseconds over the full path.

For multi-word searches, the simplest option is to take each word's lists, intersect them, and then check in the content that the phrase really appears. With lists of millions of IDs, transferring and intersecting within the deadline is prohibitive. The alternative is to index pairs of neighboring words (bigrams) and go straight to the phrase's entry, at the cost of a much larger index: from about 10 million keys to more than 100 million.

06 · WRITING

Absorbing posts, likes, and petabytes

Each post generates many writes to the index, and a burst can overload ingestion. The answer is to put a queue or stream in front: it spreads post creation across several ingestion instances, partitions the load, and smooths out bursts. In addition, the indexes can be sharded by keyword, spreading the writes across many instances.

Likes are the biggest problem. An aggregator can sum each post's likes over a time window and publish a single update: about 500 writes for a viral post become just one. But most posts are not viral, so the overall gain is small.

The bigger gain comes from updating the like index only at milestones, such as powers of two or ten: a thousand likes end up costing about ten writes. The price is a stale index, but with roughly correct order. To return N posts, you fetch twice as many from the index and query the likes service to reorder by the current count.

1. A repeated search can be answered at the edge, by the CDN, with cache headers set by the response.

2. If the edge does not have the response, the search service tries the results cache, whose time to live is shorter than the deadline for a post to appear.

3. On a cache miss, the search reads the index shard for that word; rare words come from cold storage, with a small latency penalty.

4. New posts enter through a queue, which spreads the load across ingestion instances and lets them update the indexes at their own pace.

5. Likes go through an aggregator that sums each post's likes over a window and publishes a single update to the queue.

6. Sorting by likes uses the index only as an approximation: the search service asks the likes service for the current count of the candidates and reorders them.

Storage is still missing. Limiting each index to a thousand or ten thousand items cuts the space by orders of magnitude, and rarely searched words can migrate from memory to cold blob storage; if the word is not in memory, the blob lookup has only a small latency penalty.