The primer’s search service, inverted indexes, and Twitter’s Earlybird: hash-partitioned shards, scatter-gather and merging.
What you will learn
Follow a search query through parsing, the search cluster and the merge.
Intersect postings lists in an inverted index.
Explain how Twitter's Earlybirdindexes while serving and scatter-gathers queries.
Search in the primer
The primer's Search Service:
Parses and tokenizes the query: removes markup, breaks the text into terms, fixes typos, normalizes capitalization, and converts the query to boolean operations.
Queries the Search Cluster (such as Lucene). It scatter-gathers: it asks every server in the cluster whether it has results.
Merges, ranks, sorts and returns the results.
The primer also notes the search cluster "would likely need to keep the tweets in memory to keep latency low".
Inverted indexes
An inverted index maps each term to its postings list, the IDs of the documents that contain it:
For raft AND consensus, walk both sorted lists together and keep IDs that appear in both. That takes O(L1+L2)what its symbols mean time, where L1what its symbols mean and L2what its symbols mean are the lengths of the two lists, and finds 1042 and 2104. Starting with the shortest list keeps the work down.
Earlybird: Twitter's real-time search
Busch et al. describe Earlybird, the engine behind Twitter's real-time search (ICDE 2012). The paper reports that it served "over two billion queries a day, with an average query latency of 50 ms". "Usually, tweets are searchable within 10 seconds after creation."
Partitioning: tweets are "hash partitioned across Earlybird servers", which index them as soon as they are processed.
Scatter-gather: a front-end Blender sends each query to multiple Earlybird servers, then "merges and re-ranks the results".
Indexing while serving: each server uses "a single-writer, multiple-reader lock-free algorithm". One thread adds new tweets while many threads answer queries, coordinated by a memory barrier rather than locks.
Time first: in real-time search "the temporal signal remains dominant". Twitter's first version simply listed hits in reverse chronological order.
Ranking signals: static signals added at indexing time, and resonance signals such as retweet counts that are updated over time. Earlybird combines these with the searcher's local social graph to rank results for each user.
Because tweets are hash-partitioned, any shard can hold a match, so every query goes to every shard. Each shard returns its best kwhat its symbols mean results, its top k, and the front end merges them. Merging each shard's top k gives the same global top k as searching one big index, which the visual lets you check. The cost is that the slowest shard sets the response time: tail latency amplification, from chapter 1.
Scatter-gather search
12 sample tweets, hash-partitioned across 4 index shards. Every shard gets the query; a front end merges each shard’s top 3.
Order results by
Shard 1
3 tweets indexed
6 postings read
3 matched, sends 3
Shard 2
3 tweets indexed
2 postings read
1 matched, sends 1
Shard 3
3 tweets indexed
2 postings read
0 matched, sends 0
Shard 4
3 tweets indexed
0 postings read
0 matched, sends 0
Merged top 3 of 4 matches
New post on system design for real-time search
@lea · id 112 · engagement 140
Good system design is mostly about trade-offs
@hal · id 108 · engagement 510
System design interview: design the Twitter timeline
Search: the search service sends each query to every index shard and merges the best results each one returns.
Follow a search. The search service parses and tokenizes the query, sends it to every index shard, and merges, ranks and sorts what comes back. Tweets are hash partitioned across the shards, so a match can be on any of them, and each shard returns only its top results. New tweets reach the shards through the message broker, and each shard indexes them while it answers queries. Because every query reaches every shard, each shard needs servers for all 4,000 searches a second: five each, at about 1,000 a second per server plus one spare.
Clients: 1 × Users
Load balancer: 2 × Load balancer
Search service: 5 × App server
Index shard 1: 5 × App server
Index shard 2: 5 × App server
Index shard 3: 5 × App server
Index shard 4: 5 × App server
Message broker (new tweets): 2 × Queue
Clients sends requests to Load balancer
Load balancer sends requests to Search service
Search service sends requests to Index shard 1
Search service sends requests to Index shard 2
Search service sends requests to Index shard 3
Search service sends requests to Index shard 4
Message broker (new tweets) sends requests to Index shard 1
Message broker (new tweets) sends requests to Index shard 2
Message broker (new tweets) sends requests to Index shard 3
Message broker (new tweets) sends requests to Index shard 4
Key takeaways
An inverted index maps each term to the sorted IDs of the documents that contain it; an AND query walks the lists together, shortest first.
Tweets are hash-partitioned, so every query goes to every shard; each returns its best few, and merging each shard's top kwhat its symbols mean gives the global top k.
Earlybird adds new tweets with one writer while many threads read, without locks, and ranks with time as the dominant signal, combined with engagement and the searcher's social graph.