Bird
Raised Fist0

Design Google Search - Crawling, Indexing, PageRank, Query Processing

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design Google Search: Crawling, Indexing, PageRank, Query Processing
45 min · senior
senior

Design a search engine system supporting 50 million daily active users (DAU) with a crawl rate of 10 billion pages per day, requiring fresh indexes updated every 24 hours, and query latency P99 under 200ms. The system must handle encrypted data in transit and at rest, support multi-language content, and provide high availability with 99.99% uptime.

Constraints
  • Encrypted data in transit and at rest (TLS + AES-256)
  • Index freshness: updated every 24 hours
  • Query P99 latency under 200ms at 50M DAU
  • Support multi-language content and ranking
  • High availability with 99.99% uptime
📋
Guided Steps
1/5
Step 1
Design the Web Crawler Architecture
How would you design the web crawler to efficiently crawl 10 billion pages per day with freshness and politeness constraints?
💡 Hint
Consider distributed crawling with URL frontier management and politeness policies.
Key Decision
Use Apache Nutch distributed crawler with Apache Kafka as URL frontier queue - Kafka partitions URLs by domain to enforce politeness and scale crawl workers horizontally.
Interviewer Expectation
Mid: Names Apache Nutch and Kafka for URL queue. Senior: Explains Kafka partitioning by domain to avoid overloading sites and how Nutch handles incremental crawling and politeness delays.
⚠️Common Wrong Answer
Using a single centralized queue for URLs - leads to bottlenecks and inability to enforce domain-level politeness at scale.
Step 2
Design the Indexing Pipeline
How would you design the indexing pipeline to process crawled pages and build a scalable inverted index updated every 24 hours?
💡 Hint
Think about batch processing frameworks and storage optimized for read-heavy workloads.
Key Decision
Use Apache Hadoop MapReduce for batch processing crawled data and Apache HBase as the distributed NoSQL store for inverted index - HBase supports fast random reads and writes with strong consistency.
Interviewer Expectation
Mid: Mentions Hadoop for batch and HBase for storage. Senior: Explains why HBase’s LSM-tree design suits write-heavy indexing and how MapReduce jobs handle tokenization, normalization, and index merging.
⚠️Common Wrong Answer
Using relational databases for index storage - relational DBs do not scale for billions of documents and have poor write throughput.
Step 3
Implement PageRank Computation
How would you compute PageRank scores for billions of pages efficiently and update them regularly?
💡 Hint
Consider graph processing frameworks optimized for iterative algorithms on large graphs.
Key Decision
Use Apache Giraph for distributed PageRank computation on the web graph stored in HDFS - Giraph supports iterative graph algorithms with fault tolerance and scales to billions of vertices.
Interviewer Expectation
Mid: Names Giraph or Pregel-like system. Senior: Explains iterative convergence, checkpointing for fault tolerance, and how PageRank scores are stored back in HBase for query-time retrieval.
⚠️Common Wrong Answer
Recomputing PageRank from scratch on a single machine - infeasible at web scale and causes long delays.
Step 4
Design the Query Processing System
How would you design the query processing system to serve 50M DAU with P99 latency under 200ms?
💡 Hint
Focus on distributed serving, caching, and ranking components with low-latency storage.
Key Decision
Use Elasticsearch cluster for inverted index serving with Redis caching for hot queries and a dedicated ranking service using TensorFlow Serving for ML-based ranking models.
Interviewer Expectation
Mid: Mentions Elasticsearch for search and caching. Senior: Explains query routing, shard placement, cache invalidation strategies, and how ranking models are integrated with feature extraction pipelines.
⚠️Common Wrong Answer
Querying HBase directly for every search - high latency and poor P99 performance.
Step 5
Ensure Security and High Availability
How would you ensure encrypted data handling and 99.99% uptime across the system?
💡 Hint
Consider encryption standards and multi-region deployment with failover.
Key Decision
Use TLS 1.3 for all data in transit, AES-256 encryption for data at rest in HBase and Elasticsearch, and deploy multi-region active-active clusters with automated failover using Kubernetes and Istio service mesh.
Interviewer Expectation
Mid: Names TLS and AES encryption. Senior: Details key management with HashiCorp Vault, zero-trust network policies, and disaster recovery plans with multi-region replication.
⚠️Common Wrong Answer
Ignoring encryption at rest or relying on single-region deployment - risks data breaches and downtime.
🔌
API Design Challenge
Sketch 3 core API endpoints for the search system: crawling control, indexing status, and query processing.
Hints
  • How does the crawler request and receive URLs to crawl?
  • How does the indexing system expose index freshness and health?
  • How does the query API accept user queries and return ranked results?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Distributed crawler with domain-based URL partitioning to enforce politeness and scale
  • Batch indexing pipeline using Hadoop MapReduce and HBase for inverted index storage
  • Scalable PageRank computation using a graph processing framework like Apache Giraph
  • Low-latency query serving with Elasticsearch and caching layer
  • Encryption in transit and at rest with TLS and AES-256
Good to Have - 30%
  • ML-based ranking integrated with TensorFlow Serving
  • Multi-region deployment with automated failover for high availability
  • Detailed API design for crawler control, indexing status, and query processing
Bonus - 10%
  • Use of service mesh (Istio) for zero-trust security and observability
  • Advanced cache invalidation strategies for query cache consistency
Anti-patterns to Avoid
Single centralized URL queue causing crawl bottlenecks and politeness violations leading to crawl delays and site overload
Using relational databases for inverted index storage leading to poor scalability and slow write throughput
Recomputing PageRank on a single machine causing long delays and no fault tolerance, making updates infeasible
Querying batch storage (HBase) directly for every search causing high latency and poor P99 performance
Ignoring encryption at rest exposing sensitive data to breaches and compliance violations
Single-region deployment risking downtime and data loss during regional failures
✅
Model Answer
▼ Reveal

The system uses Apache Nutch with Kafka for distributed crawling, Hadoop MapReduce and HBase for indexing, Apache Giraph for PageRank, and Elasticsearch with Redis caching for query serving. Security is ensured with TLS and AES-256 encryption, and high availability is achieved via multi-region Kubernetes deployments.

Key Decisions
  • Use Apache Nutch with Kafka partitioned by domain to enforce crawl politeness and scale horizontally
  • Batch indexing pipeline implemented with Hadoop MapReduce jobs and HBase for fast random reads/writes
  • PageRank computed using Apache Giraph for scalable iterative graph processing with checkpointing
  • Query serving via Elasticsearch cluster with Redis caching to meet P99 latency under 200ms
  • ML-based ranking integrated using TensorFlow Serving with feature extraction pipelines
  • Encrypt all data in transit with TLS 1.3 and at rest with AES-256 encryption
  • Deploy multi-region active-active clusters managed by Kubernetes and Istio for 99.99% uptime and automated failover
  • Use HashiCorp Vault for key management and implement zero-trust network policies for security
  • Apache Nutch distributed crawler with Kafka URL frontier partitioned by domain for scalable, polite crawling
  • Apache Hadoop MapReduce batch jobs for indexing pipeline processing crawled data
  • Apache HBase as distributed NoSQL inverted index store optimized for random reads and writes
  • Apache Giraph for scalable iterative PageRank computation on web graph stored in HDFS
  • Elasticsearch cluster for low-latency query serving with Redis caching for hot queries
  • TensorFlow Serving for ML-based ranking integrated into query pipeline
  • TLS 1.3 for encrypted data in transit and AES-256 for data at rest in HBase and Elasticsearch
  • Multi-region active-active deployment with Kubernetes and Istio for 99.99% uptime and failover

Practice

(1/5)
1. In the CI/CD pipeline request flow, at Step 5 the Deployment Worker receives a build artifact reference and triggers deployment. What happens if the artifact is missing from the artifact registry at this step?
easy
A. Deployment Worker proceeds with last known artifact version silently
B. Deployment Worker retries indefinitely until artifact appears
C. Deployment Worker fails deployment and reports an error to the orchestrator
D. Deployment Worker skips deployment and triggers rollback automatically

Solution

  1. Step 1: Trace Deployment Worker behavior on missing artifact

    The Deployment Worker validates artifact presence before deployment; missing artifact causes failure.

  2. Step 2: Check fallback behaviors

    Retrying indefinitely would block pipeline; proceeding silently risks inconsistency; automatic rollback is triggered only after failed deployment, not missing artifact.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Deployment Worker fails and reports error on missing artifact [check]
Hint: Missing artifact -> deployment fails, no silent fallback [check]
Common Mistakes:
2. In the For-You feed request flow, at step 4 the Feed Ranking Service receives user watch history and video metadata. What does it do if the user has no recent watch history?
easy
A. Falls back to a global trending video list for recommendations
B. Queries the Creator Stack for personalized creator recommendations only
C. Waits for user watch history to be populated before responding
D. Returns an empty feed immediately to avoid delay

Solution

  1. Step 1: Understand Feed Ranking fallback logic

    Empty feed (A) harms UX; waiting (C) blocks response; global trending (B) is a fallback but not personalized.

  2. Step 2: Identify personalization fallback

    Creator Stack (D) provides personalized creator recommendations when watch history is missing, improving engagement.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Creator Stack fallback personalizes feed without watch history [check]
Hint: Fallback to Creator Stack for personalization without history [OK]
Common Mistakes:
3. In a system where a load balancer forwards requests to backend servers, at step 4 the backend server checks its health status before processing the request. What happens if the health check fails at this step?
easy
A. The backend server rejects the request and signals the load balancer to reroute
B. The backend server returns an error response directly to the client
C. The load balancer retries routing the request to a different healthy backend
D. The backend server processes the request anyway, risking errors

Solution

  1. Step 1: Trace backend server health check at Step 4

    If the backend server health check fails, it should not process the request (The backend server processes the request anyway, risking errors is incorrect). Returning an error directly to the client (The backend server returns an error response directly to the client) bypasses the load balancer's retry logic. The load balancer retrying without backend signaling (The load balancer retries routing the request to a different healthy backend) is incomplete.

  2. Step 2: Understand backend rejection and signaling

    The backend server rejects the request and signals the load balancer to reroute traffic to a healthy backend (The backend server rejects the request and signals the load balancer to reroute), ensuring availability.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Backend signals load balancer to reroute on health check fail [check]
Hint: Backend signals reroute on health failure [check]
Common Mistakes:
4. You must design a system that processes high-volume event streams with strict ordering per customer but can tolerate some message duplication. Which approach is best?
medium
A. Partition the topic by customer ID and use multiple consumers in a group
B. Use Kafka with exactly-once semantics and idempotent producers
C. Use multiple topics per customer to isolate streams
D. Use a single Kafka topic with one partition to guarantee ordering

Solution

  1. Step 1: Evaluate ordering and throughput needs

    Single partition guarantees ordering but limits throughput severely.

  2. Step 2: Assess partitioning by customer ID

    Partitioning by customer ID preserves ordering per customer and allows parallel consumption.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Partition key + consumer group balances order and scale [check]
Hint: Partition by customer ID for order and parallelism [OK]
Common Mistakes:
5. For a time-series IoT data ingestion system requiring high write throughput and efficient range queries by device and time, which data modeling approach is best?
medium
A. Partition by timestamp and cluster by device ID
B. Partition by device ID and cluster by timestamp within each partition
C. Use a single partition key for all devices and cluster by timestamp
D. Use a relational database with indexes on device and timestamp

Solution

  1. Step 1: Analyze query and write patterns

    Queries filter by device and time ranges; writes are high volume per device.

  2. Step 2: Evaluate partitioning strategies

    Partitioning by device ID localizes writes and queries; clustering by timestamp supports efficient range scans. Single partition key causes hotspots; partitioning by timestamp scatters device data, hurting queries; relational DBs can't handle high write scale.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Partition by device ID + cluster by timestamp -> balanced writes and efficient queries [check]
Hint: Partition by device, cluster by time for time-series data [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