Web Crawler

Web Crawler (паук/бот) -- система для систематического обхода веба, загрузки и обработки веб-страниц. Используется поисковыми системами, SEO-инструментами, мониторингом цен.

Шаг 1: Требования

Функциональные требования

1. Обход веба начиная с seed URL-ов
2. Извлечение ссылок и контента со страниц
3. Соблюдение robots.txt и crawl delay
4. Дедупликация URL и контента
5. Приоритизация URL (важные страницы краулятся первыми)
6. Сохранение результатов для последующей индексации

Нефункциональные требования

1. Масштабирование до 1B страниц в месяц (~400 страниц/секунду)
2. Politeness: не перегружать сайты
3. Устойчивость к spider traps и бесконечным циклам
4. Обработка разных content types (HTML, PDF, XML)

Шаг 2: Оценка нагрузки

Шаг 3: High-Level архитектура

┌──────────────┐     ┌──────────────────┐     ┌──────────────────┐
│  Seed URLs   │────>│  URL Frontier    │────>│  URL Fetcher     │
│              │     │  (Priority Queue)│     │  (Workers Pool)  │
└──────────────┘     └────────┬─────────┘     └────────┬─────────┘
                              │                        │
                     ┌────────▼─────────┐     ┌────────▼─────────┐
                     │  URL Dedup       │     │  DNS Resolver    │
                     │  (BloomFilter +  │     │  (Local Cache)   │
                     │   Redis)         │     └──────────────────┘
                     └──────────────────┘              │
                                               ┌──────▼──────────┐
                                               │  Content Parser │
                                               │  (HTML/PDF)     │
                                               └──────┬──────────┘
                                                      │
                              ┌────────────────────────┼───────────────┐
                              │                        │               │
                     ┌────────▼────────┐    ┌──────────▼─────┐  ┌─────▼──────────┐
                     │  Link Extractor │    │  Content Dedup │  │  Content Store │
                     │                 │    │  (Simhash)     │  │  (S3/HDFS)     │
                     └────────┬────────┘    └────────────────┘  └────────────────┘
                              │
                     ┌────────▼────────┐
                     │  URL Normalizer │───> Back to URL Frontier
                     └─────────────────┘

Шаг 4: Ключевые компоненты

4.1 URL Frontier (очередь с приоритетами и politeness)

<?php

declare(strict_types=1);

final class UrlFrontier
{
    public function __construct(
        private readonly \Redis $redis,
        private readonly RobotsChecker $robots,
        private readonly UrlDeduplicator $dedup,
    ) {}

    /**
     * Add URL to the frontier with priority
     */
    public function add(string $url, int $priority = 5, int $depth = 0): bool
    {
        // 1. Normalize URL
        $normalized = $this->normalizeUrl($url);

        // 2. Check if already crawled or in queue
        if ($this->dedup->isSeen($normalized)) {
            return false;
        }

        // 3. Check robots.txt
        $host = parse_url($normalized, PHP_URL_HOST);
        if (!$this->robots->isAllowed($normalized, 'MyBot/1.0')) {
            return false;
        }

        // 4. Max depth check (prevent infinite crawling)
        if ($depth > 10) {
            return false;
        }

        // 5. Add to host-specific queue (politeness)
        $hostQueue = "frontier:host:{$host}";
        $this->redis->zAdd($hostQueue, $priority * 100 - $depth, json_encode([
            'url' => $normalized,
            'depth' => $depth,
            'added_at' => time(),
        ]));

        // 6. Register host in active hosts set
        $this->redis->sAdd('frontier:hosts', $host);

        // 7. Mark as seen
        $this->dedup->markSeen($normalized);

        return true;
    }

    /**
     * Get next URL to crawl (respects politeness per host)
     */
    public function getNext(): ?CrawlTask
    {
        // Round-robin across hosts to ensure politeness
        $hosts = $this->redis->sMembers('frontier:hosts');

        if (empty($hosts)) {
            return null;
        }

        shuffle($hosts);

        foreach ($hosts as $host) {
            // Check crawl delay for this host
            $lastCrawl = (int) $this->redis->get("frontier:last_crawl:{$host}");
            $crawlDelay = $this->robots->getCrawlDelay($host) ?? 1;

            if ((time() - $lastCrawl) < $crawlDelay) {
                continue; // Too soon, try another host
            }

            // Pop highest priority URL from host queue
            $hostQueue = "frontier:host:{$host}";
            $items = $this->redis->zRevRange($hostQueue, 0, 0);

            if (empty($items)) {
                $this->redis->sRem('frontier:hosts', $host);
                continue;
            }

            $item = json_decode($items[0], true);
            $this->redis->zRem($hostQueue, $items[0]);

            // Update last crawl time
            $this->redis->set("frontier:last_crawl:{$host}", time());

            return new CrawlTask(
                url: $item['url'],
                depth: $item['depth'],
                host: $host,
            );
        }

        return null; // All hosts in cooldown
    }

    private function normalizeUrl(string $url): string
    {
        $parsed = parse_url($url);

        // Lowercase scheme and host
        $scheme = strtolower($parsed['scheme'] ?? 'https');
        $host = strtolower($parsed['host'] ?? '');
        $path = $parsed['path'] ?? '/';
        $query = $parsed['query'] ?? '';

        // Remove default ports
        $port = $parsed['port'] ?? null;
        if (($scheme === 'http' && $port === 80) || ($scheme === 'https' && $port === 443)) {
            $port = null;
        }

        // Remove fragment
        // Remove trailing slash (except root)
        $path = $path !== '/' ? rtrim($path, '/') : $path;

        // Sort query parameters
        if ($query) {
            parse_str($query, $params);
            ksort($params);
            // Remove tracking parameters
            unset($params['utm_source'], $params['utm_medium'], $params['utm_campaign']);
            $query = http_build_query($params);
        }

        $normalized = "{$scheme}://{$host}";
        if ($port) {
            $normalized .= ":{$port}";
        }
        $normalized .= $path;
        if ($query) {
            $normalized .= "?{$query}";
        }

        return $normalized;
    }
}

final readonly class CrawlTask
{
    public function __construct(
        public string $url,
        public int $depth,
        public string $host,
    ) {}
}

4.2 URL Deduplicator (Bloom Filter)

<?php

declare(strict_types=1);

final class UrlDeduplicator
{
    private const BLOOM_SIZE = 100_000_000; // 100M bits ~ 12 MB
    private const HASH_COUNT = 7;

    public function __construct(
        private readonly \Redis $redis,
    ) {}

    public function isSeen(string $url): bool
    {
        $hashes = $this->getHashes($url);

        // Check all bits
        foreach ($hashes as $hash) {
            $bit = $this->redis->getBit('bloom:urls', $hash);
            if ($bit === 0) {
                return false;
            }
        }

        // Probably seen (false positive rate ~1%)
        return true;
    }

    public function markSeen(string $url): void
    {
        $hashes = $this->getHashes($url);

        foreach ($hashes as $hash) {
            $this->redis->setBit('bloom:urls', $hash, 1);
        }
    }

    private function getHashes(string $url): array
    {
        $hashes = [];
        $hash1 = crc32($url);
        $hash2 = crc32(strrev($url));

        for ($i = 0; $i < self::HASH_COUNT; $i++) {
            // Double hashing technique
            $combined = abs($hash1 + $i * $hash2);
            $hashes[] = $combined % self::BLOOM_SIZE;
        }

        return $hashes;
    }
}

4.3 Content Parser и Link Extractor

<?php

declare(strict_types=1);

final class ContentParser
{
    public function parse(string $url, string $html): ParsedPage
    {
        $dom = new \DOMDocument();
        @$dom->loadHTML($html, LIBXML_NOERROR);
        $xpath = new \DOMXPath($dom);

        // Extract title
        $titleNodes = $xpath->query('//title');
        $title = $titleNodes->length > 0 ? $titleNodes->item(0)->textContent : '';

        // Extract text content
        $body = $xpath->query('//body');
        $textContent = $body->length > 0 ? $this->extractText($body->item(0)) : '';

        // Extract links
        $links = $this->extractLinks($xpath, $url);

        // Extract metadata
        $metadata = $this->extractMetadata($xpath);

        return new ParsedPage(
            url: $url,
            title: trim($title),
            content: trim($textContent),
            links: $links,
            metadata: $metadata,
        );
    }

    private function extractLinks(\DOMXPath $xpath, string $baseUrl): array
    {
        $links = [];
        $anchors = $xpath->query('//a[@href]');

        foreach ($anchors as $anchor) {
            $href = $anchor->getAttribute('href');

            // Resolve relative URLs
            $absoluteUrl = $this->resolveUrl($baseUrl, $href);

            if ($absoluteUrl === null) {
                continue;
            }

            // Skip non-HTTP URLs
            $scheme = parse_url($absoluteUrl, PHP_URL_SCHEME);
            if (!in_array($scheme, ['http', 'https'], true)) {
                continue;
            }

            // Check nofollow
            $rel = $anchor->getAttribute('rel');
            $nofollow = str_contains($rel, 'nofollow');

            $links[] = new ExtractedLink(
                url: $absoluteUrl,
                anchorText: trim($anchor->textContent),
                nofollow: $nofollow,
            );
        }

        return $links;
    }

    private function extractText(\DOMNode $node): string
    {
        $text = '';

        foreach ($node->childNodes as $child) {
            if ($child instanceof \DOMText) {
                $text .= ' ' . $child->textContent;
            } elseif ($child instanceof \DOMElement) {
                // Skip script, style, nav, footer
                if (in_array($child->tagName, ['script', 'style', 'nav', 'footer', 'header'], true)) {
                    continue;
                }
                $text .= $this->extractText($child);
            }
        }

        return preg_replace('/\s+/', ' ', $text);
    }

    private function resolveUrl(string $base, string $href): ?string
    {
        if (str_starts_with($href, 'http://') || str_starts_with($href, 'https://')) {
            return $href;
        }

        if (str_starts_with($href, '//')) {
            $scheme = parse_url($base, PHP_URL_SCHEME);
            return "{$scheme}:{$href}";
        }

        if (str_starts_with($href, '/')) {
            $scheme = parse_url($base, PHP_URL_SCHEME);
            $host = parse_url($base, PHP_URL_HOST);
            return "{$scheme}://{$host}{$href}";
        }

        if (str_starts_with($href, '#') || str_starts_with($href, 'javascript:')) {
            return null;
        }

        // Relative URL
        $basePath = dirname(parse_url($base, PHP_URL_PATH) ?? '/');
        $scheme = parse_url($base, PHP_URL_SCHEME);
        $host = parse_url($base, PHP_URL_HOST);
        return "{$scheme}://{$host}{$basePath}/{$href}";
    }

    private function extractMetadata(\DOMXPath $xpath): array
    {
        $meta = [];
        $nodes = $xpath->query('//meta[@name or @property]');

        foreach ($nodes as $node) {
            $name = $node->getAttribute('name') ?: $node->getAttribute('property');
            $content = $node->getAttribute('content');
            if ($name && $content) {
                $meta[$name] = $content;
            }
        }

        return $meta;
    }
}

4.4 Content Deduplication (Simhash)

<?php

declare(strict_types=1);

final class SimhashDeduplicator
{
    private const HASH_BITS = 64;
    private const SIMILARITY_THRESHOLD = 3; // Max Hamming distance

    public function __construct(
        private readonly \Redis $redis,
    ) {}

    /**
     * Check if content is near-duplicate of existing document
     */
    public function isNearDuplicate(string $content): bool
    {
        $hash = $this->computeSimhash($content);

        // Check against existing hashes using Hamming distance
        $existingHashes = $this->redis->sMembers('simhash:all');

        foreach ($existingHashes as $existing) {
            if ($this->hammingDistance((int) $hash, (int) $existing) <= self::SIMILARITY_THRESHOLD) {
                return true;
            }
        }

        // Store hash
        $this->redis->sAdd('simhash:all', (string) $hash);

        return false;
    }

    private function computeSimhash(string $content): int
    {
        $tokens = preg_split('/\s+/', mb_strtolower($content));
        $vector = array_fill(0, self::HASH_BITS, 0);

        foreach ($tokens as $token) {
            $hash = $this->hashToken($token);

            for ($i = 0; $i < self::HASH_BITS; $i++) {
                if (($hash >> $i) & 1) {
                    $vector[$i]++;
                } else {
                    $vector[$i]--;
                }
            }
        }

        $simhash = 0;
        for ($i = 0; $i < self::HASH_BITS; $i++) {
            if ($vector[$i] > 0) {
                $simhash |= (1 << $i);
            }
        }

        return $simhash;
    }

    private function hashToken(string $token): int
    {
        return crc32($token);
    }

    private function hammingDistance(int $a, int $b): int
    {
        $xor = $a ^ $b;
        $distance = 0;

        while ($xor) {
            $distance += $xor & 1;
            $xor >>= 1;
        }

        return $distance;
    }
}

Шаг 5: Обработка Spider Traps

<?php

declare(strict_types=1);

final class SpiderTrapDetector
{
    public function isTrap(string $url, int $depth): bool
    {
        // 1. Max depth exceeded
        if ($depth > 10) {
            return true;
        }

        // 2. URL too long (often generated)
        if (strlen($url) > 500) {
            return true;
        }

        // 3. Repeating patterns in path
        $path = parse_url($url, PHP_URL_PATH) ?? '';
        if ($this->hasRepeatingPattern($path)) {
            return true;
        }

        // 4. Calendar traps (infinite future dates)
        if (preg_match('/\d{4}\/\d{2}\/\d{2}/', $path)) {
            preg_match('/(\d{4})/', $path, $matches);
            $year = (int) $matches[1];
            if ($year > (int) date('Y') + 1) {
                return true;
            }
        }

        return false;
    }

    private function hasRepeatingPattern(string $path): bool
    {
        $segments = explode('/', trim($path, '/'));

        // Check for repeating segments
        if (count($segments) > 5) {
            $unique = array_unique($segments);
            if (count($unique) < count($segments) * 0.5) {
                return true; // More than 50% duplicates
            }
        }

        return false;
    }
}

Возможные вопросы интервьюера

1. Как обеспечить politeness?

   • robots.txt compliance
   • Crawl delay per domain (1-5 sec)
   • Per-host queues с rate limiting

2. Как приоритизировать URL?

   • PageRank
   • Свежесть (когда последний раз менялась страница)
   • Глубина (closer to root = higher priority)

3. Как обрабатывать JavaScript-rendered страницы?

   • Headless browser (Puppeteer/Playwright)
   • Pre-rendering сервис
   • Гибридный подход

4. Как масштабировать до миллиардов страниц?

   • Distributed frontier (шардированный по доменам)
   • Множество fetcher workers
   • Distributed storage (HDFS/S3)

5. Какой Bloom Filter size нужен?

   • 1B URLs, 1% false positive: ~1.2 GB
   • Формула: m = -n * ln(p) / (ln(2))^2