Katkat
Back

Design Boolean Search for Status Posts

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design an inverted index system that supports complex logical queries, high-concurrency updates, and consistent pagination over a distributed dataset.

Problem: Design Boolean Search for Status Posts

Design a search system that allows users to query status posts using Boolean expressions. The system must support AND, OR, NOT operators, nested parentheses (e.g., (tech OR software) AND NOT (meeting)), and stable pagination across millions of posts.

Requirements

Functional:

  1. Index new status posts in near real-time (sub-second latency).
  2. Support Boolean search queries with standard operator precedence.
  3. Implement stable pagination (i.e., ensure that moving to the next page of results remains consistent even if new posts are indexed).

Non-Functional:

  1. High availability and horizontal scalability.
  2. Strong eventual consistency for search updates.
  3. Handling high-volume write traffic from post creators.

Expectations

Your design should cover:

  1. Index Strategy: How do you structure the inverted index to handle logical operators? Explain the trade-offs between a centralized index and a sharded approach.
  2. Query Parsing: How do you transform a raw string query into an execution plan? Describe the representation (e.g., Abstract Syntax Tree) and optimization techniques.
  3. Data Pipeline: Describe the ingestion flow from post creation to index availability.
  4. Pagination: Propose a method for pagination that handles the 'moving target' problem in a distributed search index.

Constraints

  • Assume 50k posts/second ingestion rate.
  • Assume 10k queries/second search volume.
  • The system must remain performant even when users search for broad, high-frequency terms.

Hints

Hint 1

Consider converting Boolean expressions into Disjunctive Normal Form (DNF) or using a recursive tree-traversal approach to evaluate query branches.

Hint 2

For pagination, avoid simple offset-based approaches (`LIMIT 10 OFFSET 1000`) and instead consider cursor-based pagination using the document's unique timestamp or ID.

Hint 3

To handle high-frequency terms, implement 'posting lists' that are compressed and potentially sorted to facilitate fast intersection operations using skip-lists.

Follow-up questions

  • How would you modify your design to support 'proximity search', where words must appear within N tokens of each other?
  • If the index size exceeds the memory of a single node, what strategies would you use for index sharding (e.g., term-based vs. document-based)?
  • How do you handle 'deletion freshness', ensuring that a deleted status post disappears from search results as quickly as possible?