Lesson 10.4• 10 min read

Real-time search and scatter-gather

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 Earlybird indexes while serving and scatter-gathers queries.

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 postings 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(L1+L2)O(L_1 + L_2)what its symbols mean time, where L1L_1what its symbols mean and L2L_2what its symbols mean are the lengths of the two lists, and finds 1042 and 2104. Starting with the shortest list keeps the work down.


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
  1. New post on system design for real-time search
    @lea · id 112 · engagement 140
  2. Good system design is mostly about trade-offs
    @hal · id 108 · engagement 510
  3. System design interview: design the Twitter timeline
    @dara · id 104 · engagement 300
Clients1× instanceLoad balancer2× instancesSearch service5× instancesIndex shard 15× instancesIndex shard 25× instancesIndex shard 35× instancesIndex shard 45× instancesMessage broker (newtweets)2× instancesClients1× instanceLoad balancer2× instancesSearch service5× instancesIndex shard 15× instancesIndex shard 25× instancesIndex shard 35× instancesIndex shard 45× instancesMessage broker (newtweets)2× instancesClients1× instanceLoad balancer2× instancesSearch service5× instancesIndex shard 15× instancesIndex shard 25× instancesIndex shard 35× instancesIndex shard 45× instancesMessage broker (newtweets)2× instances
Figure 4

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 kkwhat its symbols mean gives the global top kk.
  • 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.
Sources3