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
Design a scalable web crawler with scheduling, politeness, and duplicate detection at internet scale
hardStorage and CollaborationFreq: medium
Prerequisites:BFSDNSRobots.txt
⚙️
Functional Requirements
  • Crawl billions of web pages daily with URL scheduling based on priority and freshness
  • Enforce politeness policies per domain (robots.txt compliance, rate limiting)
  • Detect and avoid duplicate URLs and content to reduce redundant crawling
  • Support incremental crawling with URL revisit scheduling based on last crawl time
  • Handle DNS resolution and HTTP fetching with retry and error handling
  • Provide real-time monitoring and metrics on crawl progress and errors
📊
Non-Functional Requirements
  • Support crawling 2 billion URLs per day (~23K URLs/sec average)
  • Ensure 99.99% availability of scheduler and duplicate detection components
  • Maintain crawl latency P99 under 100ms for scheduling decisions
  • Scale to handle peak write QPS of 100K URL insertions per second
  • Data retention for URL metadata and crawl history for at least 30 days
❓
Clarifying Questions to Ask
  • What is the expected crawl rate (URLs per second) and peak load?
  • How strict should politeness policies be (e.g., max requests per domain per second)?
  • What is the expected URL duplication rate and content duplication tolerance?
  • Should the system support prioritized crawling or domain-specific crawl budgets?
  • What is the expected crawl latency SLA for scheduling decisions?
  • Is incremental crawling with revisit scheduling required?
Out of Scope
✗ Design of the HTTP fetcher and parser components
✗ Content indexing and search engine integration
✗ User-facing APIs for search or analytics
📌
Assumptions
  • 2 billion URLs crawled per day
  • Average URL metadata size: 500 bytes (URL, headers, crawl state)
  • Peak write QPS is 5x average due to bursty crawl scheduling
  • Retention period for crawl metadata: 30 days
⚡
QPS Calculation
write qps2B URLs / 86400 seconds ≈ 23,148 writes/sec
peak write qps23,148 × 5 = 115,740 writes/sec
read qpsAssuming 2 reads per write for scheduling and duplicate checks: 23,148 × 2 = 46,296 reads/sec
💾
Storage Estimate
daily storage2B × 500 bytes = 1,000,000,000,000 bytes = 1 TB/day
retention storage1 TB/day × 30 days = 30 TB
with replication30 TB × 3 replicas = 90 TB total storage
🖥️
Server Estimate
scheduler nodesAssuming each scheduler node handles 5,000 writes/sec, need 115,740 / 5,000 ≈ 24 nodes
duplicate detection nodesUsing Cassandra with 10K writes/sec per node, need 115,740 / 10,000 ≈ 12 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  URL Frontier  |
          +--------+-------+
                   |
                   v
          +----------------+
          | Scheduler Node |
          +--------+-------+
                   |
                   v
          +----------------+
          | Politeness     |
          | Enforcer       |
          +--------+-------+
                   |
                   v
          +----------------+
          | Duplicate      |
          | Detection DB   |
          +--------+-------+
                   |
                   v
          +----------------+
          | Fetcher Pool   |
          +----------------+
🧩
Components
URL Frontier
Stores the queue of URLs to be crawled with priority and freshness metadata
Why thisApache Kafka supports high-throughput, partitioned, ordered URL queues with durable storage and consumer groups for parallelism
Why notRabbitMQ lacks the throughput and partitioning scalability needed for billions of URLs per day
Scheduler Node
Dequeues URLs from Kafka, applies scheduling logic, and enforces crawl frequency and revisit policies
Why thisStateless microservices deployed on Kubernetes allow horizontal scaling and fast scheduling decisions with low latency
Why notMonolithic schedulers cannot scale horizontally to handle 100K+ QPS scheduling decisions
Politeness Enforcer
Implements domain-level rate limiting and robots.txt compliance to avoid overloading target sites
Why thisRedis with sorted sets and TTLs enables sub-millisecond per-domain rate limiting and quick robots.txt cache expiration
Why notUsing relational DBs like PostgreSQL for rate limiting causes high latency and complex locking under scale
Duplicate Detection DB
Stores URL fingerprints and content hashes to detect duplicates and avoid redundant crawling
Why thisApache Cassandra provides linear write scalability and tunable consistency for storing billions of URL fingerprints with low latency
Why notMongoDB's single primary node per shard limits write throughput and increases latency at this scale
Fetcher Pool
Distributed fleet of HTTP fetchers that retrieve page content based on scheduled URLs
Why thisKubernetes-managed stateless pods allow elastic scaling and fault tolerance for fetchers
Why notDedicated VMs lack elasticity and increase operational overhead
🔄
Data Flow
1
URL Frontier (Kafka) → Scheduler Node
Scheduler consumes URLs from Kafka partitions
Kafka partitions enable parallel scheduling across nodes
2
Scheduler Node → Politeness Enforcer (Redis)
Scheduler checks domain rate limits and robots.txt cache
Redis sorted sets track last request timestamps per domain
3
Politeness Enforcer → Duplicate Detection DB (Cassandra)
Scheduler queries Cassandra for URL fingerprint existence
Avoids re-crawling duplicate URLs or content
4
Scheduler Node → Fetcher Pool
Scheduler dispatches approved URLs to fetchers
Fetcher pool retrieves page content asynchronously
5
Fetcher Pool → URL Frontier
Fetcher extracts new URLs and pushes them to Kafka
New URLs enter the crawl cycle

Practice

(1/5)
1. In a consistent hashing system, at Step 4 the request router receives a key and queries the hash ring to find the responsible shard. What happens if the shard mapped by the hash ring is currently down?
easy
A. The router retries the same shard until it recovers before forwarding the request
B. The router uses the next clockwise shard on the hash ring as a fallback for the key
C. The router returns an error immediately to the client indicating shard unavailability
D. The router hashes the key again with a different hash function to find another shard

Solution

  1. Step 1: Trace request router behavior on shard failure

    Retrying the same shard (The router retries the same shard until it recovers before forwarding the request) blocks requests; returning error (The router returns an error immediately to the client indicating shard unavailability) reduces availability; next clockwise shard (The router uses the next clockwise shard on the hash ring as a fallback for the key) is correct only if the ring is intact and shard failure is handled by virtual nodes.

  2. Step 2: Understand fallback hashing

    Rehashing with a different function (The router hashes the key again with a different hash function to find another shard) is a common fallback to find an alternate shard when the primary is down, ensuring availability without blocking or errors.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Fallback hashing finds alternate shard on failure [check]
Hint: Fallback hashing finds alternate shard if primary is down [OK]
Common Mistakes:
2. A video streaming service needs to deliver personalized movie recommendations to millions of users with low latency. Which component is best suited to handle the real-time personalization computation at scale?
easy
A. A distributed in-memory cache with precomputed user profiles updated asynchronously
B. A relational database with complex SQL queries for each user request
C. A batch processing system that recomputes recommendations once per day
D. A CDN edge server that directly computes recommendations on user devices

Solution

  1. Step 1: Identify personalization latency requirements

    Real-time personalization requires low latency responses, which batch processing (A batch processing system that recomputes recommendations once per day) cannot provide.

  2. Step 2: Evaluate component suitability

    Relational DB (A relational database with complex SQL queries for each user request) is too slow for per-request complex queries at scale. CDN edge servers (A CDN edge server that directly computes recommendations on user devices) lack the data and compute power for personalization. Distributed in-memory cache (A distributed in-memory cache with precomputed user profiles updated asynchronously) supports fast lookups with asynchronously updated profiles, fitting the latency and scale needs.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    In-memory cache with async updates enables low-latency personalization [check]
Hint: Precompute profiles in cache for fast personalization [check]
Common Mistakes:
3. If the cache warming service crashes after partially warming keys but before marking completion, what is the immediate failure observed during launch?
medium
A. The cache contains stale data from previous runs causing incorrect responses
B. The cache warming service automatically retries from the start, causing duplicate warming and wasted resources
C. The system falls back to a read-through cache mode with no performance impact
D. Clients experience cache misses for keys not warmed, causing increased latency and possible DB overload

Solution

  1. Step 1: Trace failure impact of partial warming crash

    Without completion mark, warming restarts causing duplicate warming and resource waste.

  2. Step 2: Eliminate other options

    Stale data unlikely if warming overwrites; cache misses occur but duplicate warming is immediate failure; fallback read-through causes latency, not immediate failure.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Crash without completion causes duplicate warming retries [check]
Hint: Crash without completion mark causes duplicate warming retries [check]
Common Mistakes:
4. If the Kafka cluster buffering RTMP packets crashes and loses the latest messages, what exactly breaks in the live streaming pipeline?
medium
A. The CDN serves stale HLS segments but continues streaming without interruption
B. The RTMP ingest server retries sending lost packets automatically with no impact
C. The transcoder stalls waiting for missing packets, causing segment gaps and viewer buffering
D. The player switches to a backup stream seamlessly without user noticing

Solution

  1. Step 1: Understand Kafka's role

    Kafka buffers RTMP packets to ensure ordered, durable delivery to the transcoder.

  2. Step 2: Trace failure impact

    If Kafka loses messages, the transcoder stalls (A) due to missing packets, causing segment gaps. CDN (B) serves only what it has, so stale segments appear. RTMP ingest server (C) does not retry lost packets automatically; loss is permanent. Player (D) cannot switch streams without explicit failover.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Kafka loss causes permanent packet loss; RTMP ingest lacks automatic retry [check]
Hint: Kafka loss means lost packets; RTMP ingest has no auto-retry [check]
Common Mistakes:
5. At 10x scale, which component is most likely to fail first and why in Slack's real-time delivery system?
hard
A. Chat servers, because WebSocket connections are stateful and cannot be resharded easily
B. Presence service, because TTL cache invalidations overwhelm the system
C. Kafka brokers, because partition count cannot scale beyond a fixed limit
D. The database, because increased writes cause locking and slow queries

Solution

  1. Step 1: Identify stateful bottlenecks at scale

    Chat servers hold WebSocket connections in memory, which are stateful and tied to specific servers, limiting horizontal scaling.

  2. Step 2: Compare other components

    Databases can be sharded; Kafka scales with partitions; presence service caches can be distributed; chat servers' stateful connections are the hardest to shard.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful WebSocket connections -> chat servers bottleneck at 10x scale [check]
Hint: Stateful WebSocket binds chat servers -> first bottleneck [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