Bird
Raised Fist0

Faceted Search and Filtering at Scale

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Faceted Search and Filtering at Scale
Design a scalable faceted search system supporting billions of users with low latency filtering
mediumSearch and IndexingFreq: common
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Support faceted search on multiple attributes (e.g., category, price range, brand) with AND/OR filters
  • Return search results with low latency (P99 < 100ms) for 99.99% of requests
  • Support real-time or near-real-time indexing of new/updated items (index latency < 1 minute)
  • Provide pagination and sorting (e.g., by relevance, price, popularity)
  • Support multi-tenant indexing for different product catalogs or domains
  • Allow dynamic addition/removal of facets without full reindexing
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating 40 search queries per user per day
  • System availability SLA of 99.99% uptime
  • P99 search query latency under 100ms globally
  • Indexing throughput to support 925K writes/sec peak (derived from user activity)
  • Data retention of at least 30 days for analytics and reindexing
❓
Clarifying Questions to Ask
  • What is the expected query complexity and number of facets per query on average?
  • Are the facets static or do they change frequently? How often are new facets added?
  • What is the expected update frequency and latency requirement for indexing new data?
  • Is the search global or partitioned by geography or tenant?
  • What is the expected size and cardinality of each facet attribute?
  • Are there any SLAs for consistency between indexing and search results?
Out of Scope
✗ Ranking algorithm design and machine learning relevance tuning
✗ User personalization and recommendation systems
✗ Full-text search relevance scoring beyond faceted filtering
✗ UI/UX design for search interface
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user performs 40 search queries per day on average
  • Average search query payload size is 500 bytes
  • Average document size for indexing is 1 KB
⚡
QPS Calculation
write qps2B users × 40 queries/day ÷ 86400 sec/day ≈ 925,926 queries/sec
peak write qpsAssuming 2× peak factor: 925,926 × 2 ≈ 1.85M queries/sec
read qpsAssuming 1:1 read to write ratio for search queries: 925,926 queries/sec
💾
Storage Estimate
daily indexed docs2B users × 40 queries/day = 80B docs/day (assuming each query indexes a doc)
daily storage80B docs × 1 KB = 80 TB/day
retention days30
total storage80 TB/day × 30 days = 2.4 PB raw data
with replication2.4 PB × 2 (replication factor) = 4.8 PB total storage
🖥️
Server Estimate
indexing nodesAssuming each Elasticsearch node handles 10K writes/sec, need 185 nodes for peak write QPS
search nodesAssuming each node handles 20K queries/sec with caching, need ~46 nodes for read QPS
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client Search |
          +-------+--------+
                  |
                  v
          +-------+--------+
          |  API Gateway   |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Query Router   |
          +-------+--------+
           /              \
          v                v
 +--------+--------+  +---+------------+
 | Elasticsearch   |  | Metadata Store |
 | Cluster (ES)    |  | (Cassandra)    |
 +--------+--------+  +---+------------+
          |                 |
          v                 v
 +--------+--------+  +----+-----------+
 | Indexing Pipeline|  | Facet Config  |
 | (Kafka + LogProc)|  | Service       |
 +------------------+  +----------------+
🧩
Components
API Gateway
Receives client search requests, performs authentication, rate limiting, and routes to Query Router
Why thisNGINX with Lua scripting supports high throughput, low latency, and flexible routing
Why notAWS API Gateway adds latency and cost at 925K QPS scale; self-managed NGINX is more performant
Query Router
Parses search queries, applies routing logic to appropriate Elasticsearch shards/clusters
Why thisCustom stateless service enables dynamic routing based on tenant, geography, and facet metadata
Why notDirect client queries to ES cause hot shards and uneven load; router balances load
Elasticsearch Cluster
Stores inverted index and executes faceted search queries with low latency
Why thisElasticsearch supports inverted indices, faceted aggregations, and horizontal scaling with shards
Why notSolr lacks native cloud scaling and has slower aggregation performance at 1M+ QPS
Indexing Pipeline (Kafka + Log Processor)
Ingests raw data changes, processes and transforms them into ES index updates asynchronously
Why thisKafka provides durable, scalable message queue with partitioning for parallel processing
Why notRabbitMQ lacks partitioning and throughput at 1.85M writes/sec; direct ES indexing causes overload
Metadata Store (Cassandra)
Stores facet configuration, schema metadata, and tenant info for dynamic facet management
Why thisCassandra offers linear scalability and high availability for metadata with low latency reads
Why notPostgreSQL requires manual sharding and does not scale linearly at this scale
Facet Config Service
Manages dynamic facet definitions and propagates changes to Query Router and Indexing Pipeline
Why thisMicroservice architecture enables independent updates and fast propagation of facet config changes
Why notHardcoding facets in ES index templates requires full reindexing on every change
🔄
Data Flow
1
Client Search → API Gateway
Client sends faceted search query with filters and pagination
API Gateway authenticates and rate limits requests
2
API Gateway → Query Router
Routes query based on tenant and geography metadata
Ensures load balancing and shard awareness
3
Query Router → Elasticsearch Cluster
Executes faceted search query using ES aggregations and filters
ES returns filtered results with facet counts
4
Elasticsearch Cluster → Query Router
Returns search results and facet aggregations
Query Router formats response

Practice

(1/5)
1. A social media platform needs to handle 1 million vote updates per second with low latency and durability. Which component is best suited to buffer and reliably process these vote events before updating the main datastore?
easy
A. Use a batch processing system that aggregates votes every hour
B. Use a relational database with immediate synchronous writes for each vote
C. Use an in-memory cache like Redis without persistence to handle votes
D. Use a distributed log system like Kafka to buffer and order vote events

Solution

  1. Step 1: Identify the need for durability and ordering

    Relational DB synchronous writes (Use a relational database with immediate synchronous writes for each vote) cause high latency and don't scale to 1M writes/sec. Redis without persistence (Use an in-memory cache like Redis without persistence to handle votes) risks data loss on failure. Batch processing (Use a batch processing system that aggregates votes every hour) introduces unacceptable latency.

  2. Step 2: Recognize Kafka's role

    Kafka provides durable, ordered, high-throughput buffering of vote events, decoupling ingestion from processing.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka buffers high-write streams with durability and ordering [check]
Hint: Kafka buffers high-write streams with durability and ordering [check]
Common Mistakes:
2. For a large-scale code repository system supporting millions of users, which branching strategy best balances performance and user flexibility?
medium
A. Use a centralized locking mechanism to serialize all branch creation and merges
B. Use lightweight branch pointers referencing immutable commits with eventual consistency
C. Use full branch copies stored separately for each user to avoid conflicts
D. Use synchronous replication of branch metadata across all servers before allowing merges

Solution

  1. Step 1: Analyze branching strategies for scale

    Lightweight branch pointers referencing immutable commits allow fast branch creation and merges without locking, supporting high concurrency.

  2. Step 2: Evaluate other options

    Centralized locking serializes operations, hurting performance; full branch copies waste storage and complicate merges; synchronous replication adds latency and reduces availability.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Immutable commits + lightweight pointers -> scalable branching [check]
Hint: Immutable commits enable lightweight, scalable branches [check]
Common Mistakes:
3. If the Metadata Server crashes before acknowledging a file rename operation, what is the most likely failure observed by the client?
medium
A. Client's write operations to the file silently fail without notification
B. Client receives an error and the file remains under the old name with no partial rename
C. Client sees the file renamed but data blocks lost
D. Client sees the file under both old and new names due to partial metadata update

Solution

  1. Step 1: Understand rename operation atomicity

    Rename involves updating metadata entries; if crash occurs mid-update, partial state may persist.

  2. Step 2: Trace failure effect

    Partial metadata update can cause both old and new filenames to appear, confusing clients.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Partial metadata updates cause duplicate filenames visible to client [check]
Hint: Partial metadata update causes duplicate filenames visible [check]
Common Mistakes:
4. You must implement a distributed lock for a system with high contention and strict latency requirements. Which approach is best and why?
medium
A. Use Redis SETNX with a fixed TTL to minimize latency
B. Use a consensus-based lock service like etcd to ensure correctness despite latency
C. Use a database row lock with retries to handle contention
D. Use a local in-memory lock combined with periodic heartbeat checks

Solution

  1. Step 1: Evaluate Redis SETNX under high contention

    Redis SETNX with TTL (A) is fast but can cause split-brain and stale locks under network partitions, violating correctness.

  2. Step 2: Consider consensus-based lock service

    Consensus-based services like etcd (B) provide strong consistency and fault tolerance, ensuring correctness even if latency is higher.

  3. Step 3: Assess database row locks and local locks

    Database locks (C) have high latency and risk deadlocks; local locks (D) do not coordinate across nodes, failing correctness.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Consensus ensures correctness under contention despite latency [check]
Hint: Consensus beats speed for correctness under contention [check]
Common Mistakes:
5. At 10x scale, which component in a synchronous quorum replication system is most likely to become the bottleneck and why?
hard
A. Quorum coordinator because it must wait for majority acknowledgments synchronously
B. Storage nodes because disk I/O saturates under high write volume
C. Network links because replication traffic grows linearly with replicas
D. Client-side libraries because they block waiting for acknowledgments

Solution

  1. Step 1: Identify synchronous quorum coordinator role

    Coordinator waits synchronously for majority acks, causing latency and throughput limits.

  2. Step 2: Compare other components' scaling challenges

    Storage nodes and network scale better; client-side blocking is per client, less centralized.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Coordinator sync wait limits throughput at scale [check]
Hint: Coordinator sync wait blocks throughput first at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard