Facebook Post Search

Searching posts on a social network

Design keyword search over a social network's posts: new posts searchable in seconds, results that favor the searcher's friends, and never a post the searcher is not allowed to see.

Overview

Post search looks like web search with a smaller corpus, but three things make it different. Most posts are not public, so what a person may see depends on who they are. What is relevant depends on the searcher too: a post by a friend about a marathon matters more than a stranger's. And the corpus is live: posts are written, edited, deleted and have their audience changed all the time, and a privacy change must take effect at once.

Facebook described its search backend, Unicorn, in a VLDB 2013 paper: an in-memory inverted index sharded across thousands of servers, with operators to favor socially close results, and privacy checked outside the index. A 2020 Facebook paper on embedding-based retrieval says Unicorn powers most search products there. This topic uses those ideas for posts and says where a choice is ours.

Questions to ask first

What is searched? — Text of posts (and comments later); people and pages are other verticals
How much content? — 500 million new posts a day, kept for 5 years
How many searches? — 50,000 a second on average, 150,000 at peak
How fresh? — A new post is searchable within about 10 seconds
How strict is privacy? — Absolute: an unfriend or audience change applies to the next query
What order? — Relevance, closeness to the searcher, recency

What you will be able to do

Build and shard an inverted index for posts, and explain why sharding by document beats sharding by term here.
Walk a query through scatter-gather, per-shard top-k and merging.
Keep private posts out of results with an authoritative check, and size the over-fetch it needs.
Favor friends' posts without hiding good public ones, using an operator like WeakAnd.
Make new posts, edits, deletes and privacy changes visible in seconds.

Key concepts

Inverted index
Posting lists
Document sharding
Scatter-gather
WeakAnd
Privacy post-filter
Over-fetching
Mutable over immutable index
Two-stage ranking
Prefix typeahead

Functional requirements

Search posts by keywords and return a ranked page of results
Show only posts the searcher is allowed to see
Rank posts from people close to the searcher higher, other things equal
Make new, edited and deleted posts appear or disappear within seconds
Suggest completions while the user types

Non-functional requirements

Search results in under 500 ms at p99 (a target we chose)
Suggestions in under 100 ms at p99 (a target we chose)
No privacy leaks: a changed audience or friendship applies to the next query
Losing an index server thins results a little; it never fails the query
Index freshness under about 10 seconds for new posts

Interview questions

How do you make sure results never include a post the searcher cannot see?
Why shard by document rather than by term?
How do you rank friends' posts higher without hiding great public posts?
How does a new post become searchable within seconds?
How would you build suggestions as the user types?
Every query hits every shard. How do you handle 150,000 searches a second?
How would you improve recall beyond keywords?