Design Boolean Search over User Status Posts
MetaSoftware Engineer · Onsite
Last updated
This problem tests the design of a scalable inverted index system capable of handling boolean queries (AND/OR/NOT) over a high-throughput stream of user status updates.
Design a Boolean Search Service for Status Posts
Design a search service that allows users to query status posts using boolean logic (e.g., "(coffee OR tea) AND NOT cold"). Assume the system handles 10,000 new status posts per second and must provide sub-200ms latency for search queries.
Requirements
- Functional: Support basic AND, OR, and NOT operations. Allow for real-time indexing of new posts and soft-deletion of existing posts.
- Non-functional: High availability, eventual consistency (within a few seconds), and efficient query evaluation.
Expectations
- Data Model: Define the inverted index structure. How do you store and retrieve the posting lists for a given token?
- Query Execution: Explain how the system evaluates complex boolean expressions. How do you merge/intersect posting lists efficiently?
- Scaling: Describe how to shard the index. What are the trade-offs between document-based partitioning versus term-based partitioning?
- Freshness & Reliability: How do you handle asynchronous indexing? How do you ensure idempotent processing of updates?
- Recovery: How do you handle node failures without losing search coverage?
Hints
Hint 1
Consider storing terms in an inverted index where each token maps to a sorted list of unique document IDs.
Hint 2
For complex boolean queries, use the 'k-way merge' algorithm to intersect or union posting lists in memory efficiently.
Hint 3
Think about using a Write-Ahead Log (WAL) to provide atomicity and a mechanism for replaying events to recover corrupted shards.
Follow-up questions
- How would you modify your design to support phrase searches (e.g., "morning coffee") rather than just individual tokens?
- If the term 'the' appears in 90% of all posts, how would your query engine handle the performance bottleneck of processing its posting list?
- What specific compression techniques would you apply to the inverted index to minimize memory usage without sacrificing query speed?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.