Problem Statement - Design Twitter Search System

Twitter is a social networking platform where users can exchange text-based messages, news, photos, and more. Design a service capable of both storing and efficiently retrieving user tweets.

Requirements

Assume this is in place(core Twitter):

• User service — profiles, auth, login. You don't design this.
• Tweet service — the canonical store of tweets; handles creating a tweet and fetching by ID. You can assume it exists.

Scope of Design :

• An ingestion pipeline that listens to tweet events and indexes them
• The search index itself
• The query/read path that serves search requests

Out of scope:

• Ranking the tweets based on user interests

Functional Requirements:

1. Search tweets — the heart of the system. Users find tweets by:
   • Keyword (e.g., "bitcoin")
     • Full-text search over tweet text — users can query arbitrary keywords (tokenized)
   • Time range (e.g., tweets from the last 24 hours)
   • Author (e.g., tweets by a specific user)
   • And combinations of these filters.
2. Baseline usage:
   • ~1.5B total users, ~800M daily active users
   • ~400M tweets written per day (≈5K tweets/sec on average)
   • Search queries run much hotter than writes: roughly 20–30K QPS at peak, with read:write ratio around 10:1 or higher
3. Handle burst TPS of 10x
4. Global customer base
5. Only the rolling 7 days need to support tokenized search
6. Search results returned to user are 20 per page

Non-Functional Requirements:

1. High throughput & scale — Twitter volume is massive: millions of tweets written per day, tens of thousands of search queries per second.
2. Low-latency — results should feel instant, roughly a few hundred milliseconds.
   1. Write: p99 < ~200ms to return success (ack), even though the tweet may not appear in search for a bit.
   2. Search: p50 < 100ms, p99 < 500ms
3. High availability (~99.9%) — the service stays up even when servers fail; no single point of failure.
4. Fault tolerance — if a machine crashes, no tweets are lost.
5. Eventual consistency for search — a tweet posted 1 second ago might not appear in search immediately, but direct reads by ID are fast. This is a reasonable trade-off.
6. Twitter Search is a "write-heavy, read-with-latency-budget" system. Every tweet must be indexed, but search results can lag slightly — that's what makes it different from, say, a bank database.
7. Availability: 99.9% (~8.7 hours downtime per year). This is the standard for consumer social apps. The interesting interview discussion is what "available" means — for a search system, a degraded-but-up state (slightly stale results, slower p99) still counts as available, so you pair 99.9% with graceful degradation during bursts.

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

High-Level Design

Write Path:

TweetService (already existing) drops a message to a Kafka queue with the message ID, content (we assume the message is immutable), author, timestamp.

From there, consumers of the queue tokenize/normalize the tweet content, and store it in the SearchIndex component. The SearchIndex is implemented with circular hashing, sharded on search term and using inverted indexing with the search token as the key, and the list of tweetIds (chronologically) as the value. Propose using something like Lucene on the nodes. Shards are replicated in case one goes down.

If indexer falls behind during a write burst, serve existing results while the system catches up. Optionally can scale consumers during bursts.

Read Path:

Queries enter via an API gateway with rate limiting and load balancing before hitting the query service -> tokenized/normalized. Retrieve the applicable tokens from the cache if applicable, fallback to SearchIndex if not. Merge the top 20 from each list. Score and rank each using weighted sum (w1·BM25(term match) + w2·recency + w3·engagement) and throw them into a priority queue of size K.

If there is a partial outage from cache/shards being down, the system may serve slightly stale or partial results during degradation.

Burst optimization - as the SearchIndex is built with incoming tokens, cache "hot" terms with a smaller recency list. If a search query has some cached terms and some not cached, utilize the cached recency list to optimize matching tweets with the secondary terms. We assume there is also some webserver side caching for hot "queries".

In the background, have regular jobs running to clean up tombstoned (deleted) or expired tweets (older than 7 days).

Globalization:

The queue will be Kafka; each region will have its own indexer, with its own SearchIndex data store

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Detailed Component Design

The query service runs a thread-per-request model with a 400ms total budget: 10ms for tokenize/normalize (cached FST lookup), 250ms for shard fan-out (bounded by per-term cache hits), 90ms for score+rank, 50ms buffer. Per-term token cache lookup first — LRU with 1M entries, each entry a compressed posting-list head (~1K tweets). On miss, the service fans out to 1–3 shards (term sharding + hot-term replicas) with a 200ms deadline — partial results acceptable. Merging is a k-way sorted walk with skip-ahead via delta-encoded gaps. Scoring = w1·BM25 + w2·recency + w3·engagement, computed inline during the walk with early termination (MaxScore) — per-term ceilings precomputed at index time. Top-20 held in a min-heap. On shard timeout, results return with a partial=true flag and degraded ranking. The service scales horizontally behind the gateway; the token cache is local per node (so a 1M-entry LRU ≈ 8GB RAM/node, cold misses during flash-crowds fall back to shard replicas). Shard API contract: getPostings(term, offset, limit) returning delta-encoded IDs + precomputed per-doc features.