長期間稼働しているクローラーのフェッチログを見れば、ほぼどれも同じパターンが見つかる。大多数のリクエストは前回取得したコピーと同一のページを返す。それぞれのフェッチは帯域幅やクレジットを消費し、並行実行枠を占有し、相手のサーバーに負荷をかけながら、結果として何も生み出していない。
これはフェッチャーのバグではない。スケジューリングの判断であり、たいていはデフォルトのまま行われている。すべてを同じ周期で再訪問する、あるいは重要なものをより頻繁に再訪問する。どちらも一見合理的に思えるが、どちらも予算の大半を無駄にする。この記事では、その判断を意図的に行い、各訪問がもたらす見込みの価値に応じて価格付けする方法を扱う。
正しい単位を測定する
多くのチームはフェッチしたページあたりのコストを追跡している。しかし本当に重要な数字は、検出した変化1件あたりのコストである。
1日に100万ページをフェッチし、1万件の変化を検出するクローラーは、有用な観測1件につき100回のフェッチを費やしていることになる。変化を見逃さずにフェッチ数を半分にできれば、データセットのコストも半分になる。変化がまったく増えないままフェッチ数を2倍にすれば、コストだけが2倍になる。「変化が見つからなかったフェッチ」をサイトごと、ページタイプごとにダッシュボードに表示すれば、費用がどこに流れているかが一目瞭然になる。
フェッチに実際にかかるコストを把握する
1回の訪問にかかるコストは課金方式によって異なり、よく使われる2つのモデルはそれぞれ異なる最適化を促す。
| 課金モデル | 支払い対象 | 訪問を安くする要因 |
|---|---|---|
| レジデンシャルプロキシの帯域幅 | ゲートウェイを通過するバイト数 | レスポンスを小さくする(レンダリングなし、画像なし、転送の圧縮) |
| スクレイピングAPIのクレジット | 成功したレスポンス | フェッチ回数を減らすこと。各回のサイズはさほど重要ではない |
Shifterのレジデンシャルゲートウェイでは、ヘッダーを含め送受信されたすべてのバイトがカウントされ、エラー発生前にバイトが転送されていれば失敗したリクエストもカウントされる。各フェッチを小さくすることが直接コスト削減につながり、その手法はプロキシの帯域幅コストを削減する方法で解説している。一方、Web Scraping APIでは、JavaScriptレンダリングを有効にしているかどうかにかかわらず、成功したリクエストは1クレジットかかり、失敗したリクエストやターゲットのエラーは無料である。この場合、レンダリングされたページと通常のページのコストは同じであり、請求額を動かす唯一のレバーは成功したフェッチの回数である。
いずれにせよ、最大のレバーはスケジューラーである。なぜなら、最も安いフェッチとは、行わないと決めたフェッチだからだ。
各ページはどれくらいの頻度で変化するか
期待値に基づくスケジューリングには、各ページがどのくらいの頻度で変化するかの推定が必要になる。クローラー研究における標準的な作業仮定は、変化がページごとにおおよそ一定の平均レートでランダムに発生するというもので、これにより前回の訪問以降にページが変化している確率は次のようになる。
P(changed) = 1 - e^(-rate × time since last visit)
このレートは自分自身の履歴から推定する。各訪問は、前回の訪問以降にページが変化したかどうかを教えてくれる。観測期間あたりの変化数を、ページごとに割り、3回しか訪問していないページが極端な推定値にならないよう、類似ページの平均値に向けて平滑化する。
注意点は2つある。第一に、訪問は「変化した」ということしか教えてくれず、「何回変化したか」はわからないため、訪問頻度より速く変化するページは実際よりも遅く見える。第二に、「変化した」の定義は自分が気にするフィールドで決める必要がある。タイムスタンプ、広告枠、セッショントークンが読み込むたびに異なるページは常に変化しているように見えるが、それには何の意味もない。HTMLではなく、抽出したレコードをハッシュ化すること。
直感に反する結果:最も速く変化するページを追いかけてはいけない
一見自然な方針は、変化する頻度に比例してページを訪問することだ。しかしこれは誤りであり、その証明は20年以上前になされている。
Junghoo ChoとHector Garcia-Molinaによる「Effective Page Refresh Policies for Web Crawlers」(ACM Transactions on Database Systems、2003年)は、固定の訪問予算でローカルコピーの鮮度を保つための割り当て方針を比較した。彼らの発見は、原文の言葉を借りれば「uniform policyはあらゆるシナリオにおいてproportional policyよりも常に効果的である(the uniform policy is always more effective than the proportional policy under any scenario)」というものである。彼らの最適方針はさらに踏み込んでおり、直接こうまとめている。「鮮度を改善するには、変化しすぎる要素にペナルティを課すべきである(To improve freshness, we should penalize the elements that change too often)」。
この直感は一度説明されればわかりやすい。15分ごとに変化するページは、フェッチした直後にはすでに古くなっている。そのページを訪問しても、数分間の鮮度しか買えない。一方、1日に1回程度変化するページを毎日訪問すれば、訪問後のほとんどの時間、正確な状態を保てる。予算が限られている場合、後者の方がはるかに良い買い物だ。
これは数値化できる。同じ変化モデルの下で、1回の訪問が買う鮮度は、ページが現在古くなっている確率と、その後どれくらいの期間正確な状態を保つ見込みかの積になる。1日に1回程度再訪問できるクローラーの場合:
| ページの変化頻度 | 1回の訪問が買う鮮度(日) |
|---|---|
| 15分ごと程度 | 0.010 |
| 1時間ごと程度 | 0.042 |
| 6時間ごと程度 | 0.241 |
| 1日ごと程度 | 0.400 |
| 1週間ごと程度 | 0.124 |
| 1ヶ月ごと程度 | 0.032 |
| 1年ごと程度 | 0.003 |
最も良い買い物は、自分が余裕を持って訪問できるペースにおおよそ合った頻度で変化するページである。それよりはるかに速く変化するページは、どんなに予算をかけても鮮度を保つことがほぼ不可能であり、それよりはるかに遅く変化するページはほとんど常にすでに鮮度が保たれている。
重要な例外が1つある。この結果は鮮度、つまり自分のコピーが実際のページとどれくらい一致しているかについての話である。しかし中には、イベントそのものを捉えることが目的の仕事もある。すべての価格変更、すべての在庫切れ、すべての編集を捉えたい場合だ。個々の変化それぞれが重要であるなら、速く変化するページにはより多くの訪問が必要であり、減らすべきではない。そしてその場合、正しい答えはAPI、フィード、あるいはフルフェッチなしで変化を示すリスティングページなど、まったく別のソースであることが多い。チューニングする前に、自分がどちらの問題を解いているのかを決めておく必要がある。
すべての訪問をコストあたりの期待値でスコアリングする
これらの要素を組み合わせると、各候補の訪問には優先度がつく。ページがどれだけ重要か、1回の訪問が買う鮮度がどれだけか、それをその訪問のコストで割ったものだ。
import math
def freshness_gain(rate, days_since_visit, interval_days):
"""Expected fresh days bought by visiting now, under a Poisson change model."""
p_stale = 1 - math.exp(-rate * days_since_visit)
fresh_after = (1 - math.exp(-rate * interval_days)) / rate if rate > 0 else interval_days
return p_stale * fresh_after
def priority(page, today, interval_days=1.0):
gain = freshness_gain(page.change_rate, today - page.last_fetched, interval_days)
return page.value * gain / page.costスケジューラーは優先度付きキューで動作する。各サイクルで、予算をスコアの高い訪問から順に使い切り、そこで止める。3つの入力には注意が必要だ。
- 価値は技術的判断ではなく、ビジネス上の判断である。売れている商品、重要な競合、顧客がよく実行するクエリなど。粗くとらえておけばよく、3~4段階の階層で十分なことが多い。
- コストは、その訪問にかかる実際のコストであるべきだ。そのページタイプのバイト数、クレジット、レンダリングが必要かどうか。帯域幅課金プランでヘッドレスブラウザが必要なページは、通常のフェッチの何倍ものコストがかかることがある。
- 変化率は自分自身の履歴から得られ、訪問のたびに更新される。
高コストなフェッチの前に安価なシグナルを使う
多くの場合、ページが変化したかどうかは、フェッチする本来のコストよりもはるかに安く知ることができる。
- 条件付きリクエスト。 サイトが
ETagやLast-Modifiedに対応している場合、304 Not Modifiedレスポンスは通常のフェッチのごく一部のバイト数で済む。ホストごとにバリデータが信頼できるかどうかを追跡すること。バリデータを送信してきても無視するサイトもある。 - 変化検出器としてのリスティングページ。 カテゴリページや検索結果ページは、数十件の商品の価格や在庫状況をまとめて表示していることが多い。まずリスティングをフェッチして比較し、サマリーが変化した商品だけをフェッチする。ほとんどのリアルタイム価格フィードや在庫監視がこの方法で採算を保っている。
- サイトマップとフィード。 信頼できる更新日時が記載されている場合、他の何もフェッチせずに何が変化したかを教えてくれる。
- 構造化エンドポイント。 ページの背後にあるJSONレスポンスは、通常ページ自体よりも小さく、変化が少ない。
スケジューラーが見えないものに予算を確保する
既知のページだけを最適化するスケジューラーは、徐々に「見えなく」なっていく。各サイクルの予算の一部を、以下の3つのために確保しておくこと。
- 発見。 新しいURLには履歴がなく、確立されたページに優先度で勝つことは決してない。専用の割り当てを設けること。
- 再推定。 何ヶ月も「変化しない」と評価されたページも、時々は訪問すべきだ。なぜならページの変化のふるまいは変わりうるからだ。これがなければ、誤った推定は永遠に修正されない。
- 検証。 スコアに関係なくフェッチする少数のランダムサンプルによって、モデルの前提がまだ成り立っているかどうかがわかる。
コストと健全性にスケジュールを反応させる
スケジュールは計画であって保証ではない。あるサイトがスロットリングを始めたら、スケジューラーはそれを検知して再ランク付けするべきであり、フェッチ段階で実行できない訪問をキューに入れ続けるべきではない。フェッチャーからフロンティアへ戻るこのフィードバック経路については、分散クローラーにおけるバックプレッシャーとフロー制御で解説しており、サイト全体の状態についてはターゲットヘルススコアの構築で扱っている。ヘルススコアの低下は、そのサイトを訪問する実効コストを引き上げるべきでもあり、これはまさにコスト意識のあるスケジューラーが必要とするシグナルである。
結論
クロール予算を均等に、あるいは各ページの活動頻度に比例して使うと、その大半は「何も起きなかった」ことを確認するだけに終わる。各ページがどれくらいの頻度で変化するかを自分の履歴から推定し、その訪問が何を買い、何を犠牲にするかで価格付けし、最良の買い物から順に予算を割り当てること。最良の買い物になるのは、追いかけられる余裕のあるペースにおおよそ合った頻度で変化するページであって、最も速く変化するページではない。
その見返りは請求額が小さくなることだけではない。フェッチ回数を減らし、より注意深くフェッチするクローラーは、依存しているサイトへの負荷も軽くなる。
出典と参考文献
- Junghoo Cho and Hector Garcia-Molina, Effective Page Refresh Policies for Web Crawlers, ACM Transactions on Database Systems, Vol. 28, No. 4, December 2003.
- Shifter, レジデンシャルプロキシの帯域幅と課金。トラフィックとしてカウントされるものについて。
- Shifter, Web Scraping APIのエラーと制限。クレジットコスト、失敗時の挙動、リトライについて。