Web クローラー ── URL Frontier・Politeness・コンテンツ重複検知
扱うCS概念：BFS / DFS によるグラフ探索、URL Frontier（優先度付きキュー + Politeness キュー）、SimHash / MinHash（コンテンツ重複検知）、robots.txt、分散クロール
この章で何ができるようになるか：Web クローラーの設計で考慮すべき問題（無限ループ、重複ページ、サーバーへの過負荷）とその解決策を説明できるようになる。
問題設定
10億ページの Web をクロールする検索エンジンのクローラーを設計する。
要件：
- クロール対象：10億ページ
- クロール頻度：1日で全ページを更新（秒間 ~11,500 ページ）
- robots.txt の遵守
- 同一ドメインへの過負荷を防ぐ（Politeness）
- 重複・類似コンテンツの検知
- 無限ループの回避（動的URL生成のスパイダートラップ）
技術的課題：
1. どのURLを次にクロールするか（優先度）
2. 同じページを何度もクロールしない（重複排除）
3. サーバーに迷惑をかけない（Politeness）
4. ほぼ同じ内容のページを検知する（Near-duplicate）クローラーの全体アーキテクチャ
graph TD
Seed[シード URL] --> Frontier[URL Frontier<br/>優先度 + Politeness管理]
Frontier --> Fetcher[フェッチャー<br/>HTTP GET]
Fetcher --> RobotsCheck{robots.txt<br/>チェック}
RobotsCheck -->|許可| Download[ページ取得]
RobotsCheck -->|禁止| Skip[スキップ]
Download --> Parser[HTML パーサー<br/>リンク抽出]
Download --> Dedup[コンテンツ重複検知<br/>SimHash]
Dedup -->|新規| Store[ストレージ<br/>検索インデックスへ]
Dedup -->|重複| Discard[破棄]
Parser --> URLFilter[URL フィルター<br/>正規化 + 既知URL排除]
URLFilter --> FrontierURL Frontier：何を次にクロールするか
Frontier は単なるキューではない。優先度と Politeness の2軸を同時に管理する必要がある。
優先度の考慮（何が重要か）：
- PageRank が高いページ → 高優先
- 最後のクロールから時間が経っているページ → 高優先
- 新しく発見された URL → 中優先
- 更新頻度が高いページ → 高優先（ニュースサイトなど）
Politeness の考慮（サーバーに優しく）：
- 同じドメインへの連続アクセスは間隔を空ける（最低1秒）
- robots.txt の Crawl-delay を遵守
- 1つのドメインに同時に1リクエストまでfrom collections import defaultdict
import heapq
import time
class URLFrontier:
def __init__(self):
# 優先度キュー：(priority, url, domain)
self.priority_queues: dict[int, list] = defaultdict(list)
# ドメインごとの Politeness キュー
self.domain_queues: dict[str, list] = defaultdict(list)
# ドメインごとの最終アクセス時刻
self.domain_last_access: dict[str, float] = {}
# 既知 URL セット（Bloom Filter で省メモリ化）
self.seen_urls = BloomFilter(size=100_000_000, hash_count=7)
self.min_delay = 1.0 # ドメインあたり最低1秒間隔
def add_url(self, url: str, priority: int = 5):
if self.seen_urls.might_contain(url):
return # 既知 URL はスキップ
self.seen_urls.add(url)
domain = extract_domain(url)
heapq.heappush(self.priority_queues[priority], (priority, url, domain))
def get_next_url(self) -> str | None:
"""Politeness を守りつつ、最も優先度の高い URL を返す"""
now = time.time()
# 優先度が高い順にスキャン
for priority in sorted(self.priority_queues.keys()):
queue = self.priority_queues[priority]
# Politeness を満たす URL を探す
for i, (_, url, domain) in enumerate(queue):
last_access = self.domain_last_access.get(domain, 0)
if now - last_access >= self.min_delay:
queue.pop(i)
self.domain_last_access[domain] = now
return url
return None # 全ドメインがクールダウン中robots.txt の遵守
from urllib.robotparser import RobotFileParser
from functools import lru_cache
class RobotsChecker:
@lru_cache(maxsize=100_000)
def _get_parser(self, domain: str) -> RobotFileParser:
parser = RobotFileParser()
parser.set_url(f"https://{domain}/robots.txt")
try:
parser.read()
except Exception:
pass # robots.txt がなければ全許可
return parser
def can_fetch(self, url: str, user_agent: str = "MyBot/1.0") -> bool:
domain = extract_domain(url)
parser = self._get_parser(domain)
return parser.can_fetch(user_agent, url)
def get_crawl_delay(self, domain: str) -> float:
parser = self._get_parser(domain)
delay = parser.crawl_delay("MyBot/1.0")
return delay if delay else 1.0 # デフォルト1秒# 典型的な robots.txt
User-agent: *
Disallow: /admin/
Disallow: /private/
Crawl-delay: 2
User-agent: Googlebot
Allow: /
# 注: Googlebot は Crawl-delay をサポートしない（Google Search Console で設定）
User-agent: Bingbot
Crawl-delay: 2
Sitemap: https://example.com/sitemap.xmlコンテンツ重複検知：SimHash
Web には「ほぼ同じだが微妙に異なるページ」が大量にある（テンプレートサイト、コピーサイト、ページネーション）。完全一致はハッシュで検出できるが、**類似コンテンツ（Near-duplicate）**の検出には SimHash を使う。
import hashlib
def simhash(text: str, hash_bits: int = 64) -> int:
"""
SimHash: テキストのフィンガープリントを生成。
類似テキストは類似したハッシュ値を持つ
（通常のハッシュは1bit違うだけで全く異なる値になる）
"""
tokens = text.lower().split() # 単純な空白分割（実際は n-gram を使う）
v = [0] * hash_bits
for token in tokens:
token_hash = int(hashlib.md5(token.encode()).hexdigest(), 16)
for i in range(hash_bits):
if token_hash & (1 << i):
v[i] += 1
else:
v[i] -= 1
fingerprint = 0
for i in range(hash_bits):
if v[i] > 0:
fingerprint |= (1 << i)
return fingerprint
def hamming_distance(hash1: int, hash2: int) -> int:
"""2つの SimHash のハミング距離（異なるビット数）"""
xor = hash1 ^ hash2
return bin(xor).count('1')
# 使用例
page_a = "システム設計の基礎を学ぶための入門ガイド"
page_b = "システム設計の基本を学ぶための初心者ガイド" # 類似
page_c = "猫の飼い方完全マニュアル" # 全く異なる
hash_a = simhash(page_a)
hash_b = simhash(page_b)
hash_c = simhash(page_c)
print(hamming_distance(hash_a, hash_b)) # → 小さい（類似）
print(hamming_distance(hash_a, hash_c)) # → 大きい（非類似）
# ハミング距離 <= 3 なら重複とみなす（64bit の場合）スパイダートラップの回避
動的にURLを生成するサイトは無限にURLを作れる。
トラップの例：
/calendar/2026/01/01
/calendar/2026/01/02
/calendar/2026/01/03
...（365日 × 100年 = 36,500ページ）
/search?page=1
/search?page=2
...（無限のページネーション）対策：
class SpiderTrapDetector:
MAX_DEPTH = 16 # URLのパス深さ上限
MAX_PER_DOMAIN = 10000 # ドメインごとのURL上限
MAX_URL_LENGTH = 2048
def __init__(self):
self.domain_counts: dict[str, int] = defaultdict(int)
def is_trap(self, url: str) -> bool:
# URL長すぎ
if len(url) > self.MAX_URL_LENGTH:
return True
# パス深さ
path = urlparse(url).path
if path.count('/') > self.MAX_DEPTH:
return True
# ドメインごとの上限
domain = extract_domain(url)
if self.domain_counts[domain] >= self.MAX_PER_DOMAIN:
return True
# 繰り返しパターン検出（/a/b/a/b/a/b... のようなループ）
segments = [s for s in path.split('/') if s]
if len(segments) > 4:
for cycle_len in range(1, len(segments) // 2 + 1):
pattern = segments[:cycle_len]
if all(segments[i] == pattern[i % cycle_len]
for i in range(len(segments))):
return True
self.domain_counts[domain] += 1
return False分散クロール
10億ページを1台で処理するのは不可能。複数のクローラーを協調させる。
graph LR
Frontier[(URL Frontier<br/>Redis / Kafka)] --> C1[Crawler 1<br/>domain A-G]
Frontier --> C2[Crawler 2<br/>domain H-N]
Frontier --> C3[Crawler 3<br/>domain O-Z]
C1 & C2 & C3 --> Store[(ストレージ<br/>S3 + 検索インデックス)]
C1 & C2 & C3 --> Frontierドメインベースのパーティショニング：同じドメインは同じクローラーが担当。Politeness の管理が単一ノードで完結する。
まとめ
| 課題 | 解決策 | CS概念 |
|---|---|---|
| 優先度付きクロール | URL Frontier（優先度キュー） | 多段キュー |
| サーバーへの過負荷防止 | Politeness キュー + Crawl-delay | レート制限 |
| 既知URL の重複排除 | Bloom Filter | 確率的データ構造（Ch.03） |
| 類似コンテンツ検知 | SimHash + ハミング距離 | 局所性鋭敏ハッシュ |
| 無限ループ回避 | 深さ制限 + パターン検知 | グラフ探索の終了条件 |
| スケールアウト | ドメインベースパーティショニング | 静的シャーディング |