Social Post Search (Keyword and Boolean Queries)

0) Problem Restatement

Design search over status posts on a social network like Facebook. A user types keywords, like pizza or pizza AND (napoli OR brooklyn), and gets matching posts, newest (or most relevant) first, with stable pagination. Posts are created, edited and deleted all the time, and new posts should be searchable within seconds. The corpus has billions of posts. Meta asked this several times, including boolean expressions with precedence and parentheses.

1) Requirements

1.1 Functional

• Keyword search, and boolean queries with AND, OR, NOT and parentheses.
• Sort by recency (or relevance), paginate stably.
• Reflect creates, edits and deletes quickly.
• Only return posts the searcher is allowed to see.

1.2 Non-Functional

• Latency under ~200 ms.
• Freshness: seconds.
• Scale: billions of posts, thousands of queries/sec.

1.3 Scale Estimates

• 5B posts, 500M new posts/day ≈ 6K writes/sec.
• 20K search queries/sec.
• The index is roughly the size of the text itself: tens of TB, sharded across many machines.

1.4 API Design

• GET /v1/search/posts?q=pizza AND (napoli OR brooklyn)&cursor=&limit=20

2) The Inverted Index

• Tokenize each post: lowercase, remove punctuation, split into words, optionally stem ("running" → "run") and drop very common words.
• Build an inverted index: for each term, a posting list of post IDs that contain it, sorted by post ID. If post IDs increase over time (e.g., Snowflake-style IDs), this order is also newest-last, which makes "newest first" easy.
• Queries:
• A AND B → intersect two sorted lists (walk both with two pointers, O(n + m); or skip ahead when one list is much shorter).
• A OR B → merge (union).
• A AND NOT B → difference.
• Parentheses and precedence: parse the query into a tree (NOT binds tightest, then AND, then OR), and evaluate bottom-up. Start with the rarest terms to keep intermediate lists small.

3) High-Level Architecture

flowchart LR
    PW["Post writes"] --> K[("Kafka - post events")]
    K --> IX["Indexers - tokenize"]
    IX --> S1[("Index shard 1 - posts by ID range or hash")]
    IX --> S2[("Index shard 2")]
    IX --> S3[("Index shard N")]
    U["Searcher"] --> Q["Query service - parse, fan out, merge"]
    Q --> S1
    Q --> S2
    Q --> S3
    Q --> PV["Privacy filter"]
    PV --> U

4) Sharding: by Document or by Term?

• Document sharding (our choice): each shard indexes a subset of posts (by hash of post ID, or by time range). A query goes to all shards. Each evaluates the full boolean query locally and returns its top results, and the query service merges them. Writes touch one shard, and complex boolean queries are easy, since all terms of a post are on the same shard.
• Term sharding: each shard owns some terms. A query only hits the shards for its terms, but AND/OR across terms means moving big posting lists between machines. Hot terms overload one shard.
• Time-based tiers: recent posts (hot, last few days) in fast in-memory shards, and older posts in larger disk-based shards. Most searches want recent posts, so we can stop early once enough results are found.

5) Key Flows

5.1 Indexing a new post

1. The post is saved. An event goes to Kafka.
2. An indexer tokenizes it and appends the post ID to each term's in-memory posting list in the right shard. It's searchable within seconds.
3. The in-memory segments are periodically flushed into immutable on-disk segments (as Lucene does) and merged in the background.

5.2 Edits and deletes

• Delete: add the post ID to a deleted set (a bitmap) checked at query time. Segment merges drop them for good.
• Edit: delete + re-index the new version.

5.3 Query

1. Parse into a boolean tree and validate it (limit query complexity).
2. Fan out to shards (or only the recent tier first). Each returns its top K by recency or score, plus a cursor.
3. Merge, remove posts the user can't see (privacy: friends-only, blocked users), and return a page with a cursor such as (last_post_id), so the next page continues exactly there.

6) Ranking and Privacy

• Recency sort is natural with time-ordered IDs. Relevance adds BM25 text scoring (how often and how rare the term is), engagement and social closeness.
• Privacy: index the post's visibility (public, friends, custom) and author. At query time, filter using the searcher's friend list (cached). For public-only search, keep a separate, simpler index of public posts.

7) Trade-offs & Alternatives

8) Wrap-Up

Tokenize posts into an inverted index with sorted posting lists, and evaluate boolean queries by parsing them into a tree and intersecting, merging and subtracting lists, rarest terms first. Shard by document with hot recent tiers, fan out and merge top results with cursor pagination, index new posts in real time via Kafka into in-memory segments, hide deletes with a bitmap, and apply privacy filters before returning results.