Real-time search and scatter-gather

Search in the primer

The primer's Search Service:

1. Parses and tokenizes the query: removes markup, breaks the text into terms, fixes typos, normalizes capitalization, and converts the query to boolean operations.
2. Queries the Search Cluster (such as Lucene). It scatter-gathers: it asks every server in the cluster whether it has results.
3. 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 posting list, the IDs of the documents that contain it:

"raft"      → [1042, 1089, 2104]
"consensus" → [1042, 1520, 2104]

For raft AND consensus, walk both sorted lists together and keep IDs that appear in both. That takes $O(L_1 + L_2)$ time 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 few results 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 (the tail-latency effect from chapter 1).