Bird
Raised Fist0

Design a Web Crawler - Scheduler, Politeness Policy, Duplicate Detection

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design a Web Crawler - Scheduler, Politeness Policy, Duplicate Detection
45 min · senior
senior

You are building a web crawler for a startup with 50 million daily active users. The crawler must efficiently schedule URL fetches, respect politeness policies to avoid overloading websites, and detect duplicate URLs to avoid redundant crawling. The system should scale to billions of URLs, handle bursty traffic, and maintain low latency for scheduling decisions.

Constraints
  • Scheduler must handle 10 million URLs per minute with P99 scheduling latency < 200ms
  • Politeness policy requires per-domain rate limiting and crawl-delay adherence
  • Duplicate detection must scale to billions of URLs with minimal false positives
  • All data in transit and at rest must be encrypted (TLS + AES-256)
  • System must tolerate partial failures without losing scheduling state
📋
Guided Steps
1/5
Step 1
Designing the Scheduler Architecture
How would you design the scheduler to handle 10 million URLs per minute with P99 latency under 200ms?
💡 Hint
Consider distributed message queues with partitioning keyed by domain to enforce politeness and scale.
Key Decision
Use Apache Kafka with domain as the partition key - ensures all URLs for a domain go to the same partition, enabling per-domain rate limiting and ordered scheduling.
Interviewer Expectation
Mid-level: Names Kafka for queueing. Senior: Explains domain-based partitioning to enforce politeness and avoid cross-domain race conditions.
⚠️Common Wrong Answer
Using a centralized database queue like MySQL - leads to bottlenecks and high latency at 10M URLs/min.
Step 2
Implementing Politeness Policy
How would you enforce per-domain crawl-delay and rate limits in a distributed crawler?
💡 Hint
Think about token buckets or leaky bucket algorithms stored in a fast in-memory store keyed by domain.
Key Decision
Use Redis with domain keys and Lua scripts to implement atomic token bucket rate limiting per domain, ensuring crawl-delay adherence.
Interviewer Expectation
Mid-level: Suggests Redis for fast access. Senior: Details atomic Lua scripts for concurrency control and explains why Redis TTL alone is insufficient.
⚠️Common Wrong Answer
Relying on client-side delays without centralized enforcement - causes politeness violations under concurrency.
Step 3
Duplicate URL Detection at Scale
How would you detect duplicate URLs efficiently at the scale of billions of URLs?
💡 Hint
Consider probabilistic data structures that trade off false positives for memory efficiency.
Key Decision
Use a distributed Bloom filter implemented with RedisBloom module to detect duplicates with low memory footprint and acceptable false positive rate.
Interviewer Expectation
Mid-level: Mentions Bloom filters. Senior: Explains trade-offs of false positives, how to shard Bloom filters by URL hash ranges, and why a relational DB is infeasible.
⚠️Common Wrong Answer
Using relational DB for exact duplicate detection - does not scale to billions and causes high latency.
Step 4
Handling Failures and Ensuring Data Integrity
How would you design the system to tolerate partial failures without losing scheduling state or violating politeness?
💡 Hint
Think about durable queues, checkpointing, and idempotent processing.
Key Decision
Use Kafka with replication factor ≥3 for durability, combined with consumer offset commits and Redis persistence for politeness state to recover gracefully after failures.
Interviewer Expectation
Mid-level: Mentions replication and retries. Senior: Explains exactly how Kafka offset commits prevent duplicate scheduling and how Redis persistence avoids politeness state loss.
⚠️Common Wrong Answer
No replication or checkpointing - leads to lost URLs or politeness violations after crashes.
Step 5
API Design for Scheduler and Crawler Interaction
Sketch 3 core API endpoints for scheduling URLs, reporting crawl results, and querying crawl status.
💡 Hint
Consider RESTful endpoints with clear request/response semantics and authentication.
Key Decision
POST /schedule-url to enqueue URLs, POST /crawl-result to report success/failure and update politeness, GET /crawl-status to query URL or domain crawl state, all secured with TLS and OAuth tokens.
Interviewer Expectation
Mid-level: Defines basic endpoints. Senior: Details request payloads, error handling, idempotency, and security considerations.
⚠️Common Wrong Answer
No authentication or using polling endpoints that cause excessive load and latency.
🔌
API Design Challenge
Sketch 3 core API endpoints for the web crawler system: scheduling URLs, reporting crawl results, and querying crawl status.
Hints
  • How does the scheduler accept new URLs and prioritize them?
  • How does the crawler report success/failure and update politeness state?
  • How can clients query the status of a URL or domain crawl?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use Kafka with domain partitioning to scale scheduling and enforce politeness
  • Implement per-domain rate limiting with Redis and atomic Lua scripts
  • Use Bloom filters for scalable duplicate URL detection
  • Design fault-tolerant state management with Kafka replication and Redis persistence
Good to Have - 30%
  • Secure all data with TLS and AES-256 encryption
  • Design RESTful APIs with authentication and idempotency
  • Shard Bloom filters to reduce false positives and balance load
Bonus - 10%
  • Explain trade-offs of false positives in Bloom filters and mitigation strategies
  • Detail how to handle bursty URL submission without violating crawl-delay
Anti-patterns to Avoid
Centralized database queue for scheduling - causes bottlenecks and high latency at scale, unable to handle 10M URLs/min
Client-side politeness enforcement without centralized coordination - leads to crawl-delay violations under concurrency and distributed load
Exact duplicate detection using relational DB - does not scale to billions of URLs and causes high latency and storage overhead
No replication or checkpointing - results in lost URLs and inconsistent politeness state after failures, causing crawl errors
Unsecured APIs or plaintext data transfer - violates encryption constraints and risks data leaks and man-in-the-middle attacks
Polling-based APIs causing excessive load and latency instead of event-driven design - at 50M DAU, polling causes millions of unnecessary requests, collapsing system performance
✅
Model Answer
▼ Reveal

The system uses Apache Kafka with domain-based partitioning for scalable URL scheduling, Redis with Lua scripts for enforcing per-domain politeness policies, and RedisBloom for efficient duplicate detection. Fault tolerance is ensured via Kafka replication and Redis persistence, with all data encrypted in transit and at rest. RESTful APIs secured with OAuth enable interaction between scheduler and crawler.

Key Decisions
  • Use Apache Kafka with domain as partition key to ensure ordered scheduling and enforce politeness
  • Implement per-domain rate limiting using Redis with atomic Lua scripts for concurrency-safe token bucket algorithm
  • Detect duplicates at scale using RedisBloom distributed Bloom filters sharded by URL hash ranges
  • Ensure fault tolerance with Kafka replication factor ≥3 and consumer offset commits, plus Redis persistence for politeness state
  • Secure all data with TLS and AES-256 encryption to meet security constraints
  • Design RESTful APIs with authentication, idempotency, and error handling to support scalable crawler interaction
  • Apache Kafka with domain-based partitioning for scalable, ordered URL scheduling
  • Redis with Lua scripts implementing atomic token bucket rate limiting per domain for politeness
  • RedisBloom module for distributed Bloom filters enabling memory-efficient duplicate detection
  • Kafka replication and consumer offset commits for fault-tolerant scheduling state
  • TLS encryption for all data in transit and AES-256 for data at rest to meet security constraints
  • RESTful API endpoints secured with OAuth for scheduling, reporting, and querying crawl status
  • Sharding Bloom filters by URL hash ranges to distribute load and reduce false positives
  • Use of idempotent APIs and checkpointing to ensure exactly-once processing semantics

Practice

(1/5)
1. In a message delivery system, at Step 4 the Delivery Worker reads the message offset from Kafka and attempts to deliver it to the consumer. What happens if the consumer's acknowledgment is not received within the configured timeout?
easy
A. The Delivery Worker retries delivery without committing the offset
B. The Delivery Worker marks the message as delivered and commits the offset
C. The Delivery Worker discards the message and moves to the next offset
D. The Delivery Worker pauses all deliveries until manual intervention

Solution

  1. Step 1: Understand Kafka offset commit semantics

    Kafka commits offsets only after successful acknowledgment to avoid message loss.

  2. Step 2: Delivery Worker behavior on missing ack

    If no ack is received, the worker retries delivery to ensure at-least-once semantics; it does not commit offset or discard messages.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Retries without committing offset -> ensures message redelivery [check]
Hint: No ack -> retry delivery, no offset commit [OK]
Common Mistakes:
2. For delivering notifications to mobile devices at 10M+ scale, which architecture better handles intermittent connectivity and battery constraints?
medium
A. Use push notification services (APNs, FCM) with message TTL and retries managed by the platform
B. Use persistent gRPC streaming connections from server to device for real-time delivery
C. Use long polling HTTP connections from device to server to fetch notifications
D. Use SMS as the primary delivery channel for all notifications

Solution

  1. Step 1: Evaluate persistent connection approaches

    gRPC streaming (A) is unreliable on mobile due to network changes and battery constraints; long polling (C) wastes battery and bandwidth.

  2. Step 2: Consider platform push services and SMS

    Push services (B) handle retries and offline buffering efficiently; SMS (D) is costly and not suitable for all notifications.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Platform push services manage retries and offline buffering [check]
Hint: Use platform push services, not persistent streams on mobile [check]
Common Mistakes:
3. For managing user playlists with frequent updates and offline sync, which storage architecture is best suited given the need for eventual consistency and offline support?
medium
A. Conflict-free replicated data type (CRDT) based distributed store
B. Centralized NoSQL store with eventual consistency but no offline sync
C. Strongly consistent relational database with synchronous replication
D. Local device-only storage with manual sync to server

Solution

  1. Step 1: Identify requirements

    Playlists require offline edits and eventual sync with conflict resolution.

  2. Step 2: Evaluate architectures

    Relational DB (A) blocks offline edits; centralized NoSQL (C) lacks offline sync; local-only (D) risks data loss and complex merges. CRDTs (B) enable conflict-free merges and offline edits.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    CRDTs enable offline edits with automatic conflict resolution [check]
Hint: CRDTs handle offline sync and conflicts automatically [check]
Common Mistakes:
4. If the Kafka cluster is unavailable, what exactly breaks in the log aggregation pipeline?
medium
A. Logs are lost immediately as producers drop messages without retry
B. Log processors continue processing old logs but cannot enrich new logs
C. The storage layer stops accepting writes but ingestion continues
D. Log producers block on send calls, causing backpressure and delayed ingestion

Solution

  1. Step 1: Identify Kafka's role

    Kafka buffers logs between producers and processors, enabling decoupling.

  2. Step 2: Trace failure impact

    If Kafka is down, producers may retry or block, but processors cannot consume new logs, halting enrichment.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Kafka down -> processors stall on new logs, old logs processed [check]
Hint: Kafka outage stalls processors, not immediate producer loss [check]
Common Mistakes:
5. At 10x scale, which component is most likely to become the bottleneck first in a read-heavy CQRS system with read replicas, and why?
hard
A. Event queue, because increased write events overwhelm its processing capacity
B. Primary database, because write throughput scales linearly with read volume
C. Read replicas, because replication lag increases and they cannot keep up with read demand
D. Client-side caches, because cache invalidation traffic grows exponentially

Solution

  1. Step 1: Analyze scaling impact on components

    Write volume and event propagation increase 10x, stressing the event queue.

  2. Step 2: Compare bottlenecks

    Primary DB writes scale with writes, not reads; read replicas scale horizontally; client caches don't cause exponential invalidation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event queue overwhelmed first due to write event surge [check]
Hint: Event queue chokes first as write events surge 10x [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