多くのスクレイピング設定は、設計時にプロキシ構成を一度選び、そのまま使い続ける。このサイトにはレジデンシャルで都市ターゲティング、あのサイトにはISPプロキシ、うまくいく場所ではデータセンタープロキシといった具合だ。選択は通常、半日ほどいくつかの選択肢を試してみることで決まり、何かが壊れるまで見直されることはめったにない。
これは不確実性の下での意思決定であり、1日に何千回も繰り返され、リクエストのたびにフィードバックが得られる。これはまさに統計学者が多腕バンディットと呼ぶ問題の形であり、そのためのよく理解されたアルゴリズムが存在する。本稿では、この枠組みを説明し、短くテスト済みの実装を示し、最適な選択肢が途中で変わるシミュレーションでの挙動を示す。
要点
- ターゲットに対して使用しうる各プロキシ構成は「アーム」であり、各リクエストは「プル」であり、良い応答は「報酬」である。目標は、どんな価格でも最高の成功率を得ることではなく、良い応答1件あたりの最低コストを得ることである。
- トンプソンサンプリングは、既知の最良の選択肢を使うことと他の選択肢を試すことのトレードオフを、数行のコードで、チューニングスケジュールなしに処理する。
- ターゲットは変化するため、古い証拠は薄れさせるべきである。割引係数により、選択器はおおよそ直近1000件の結果を記憶することになる。
- 私たちのシミュレーションでは、割引ありのトンプソンサンプリングは、真の確率を事前に知っている戦略に対して2%以内に収まったのに対し、固定の「安全な」選択は良い応答1件あたりのコストが25%高く、初期の勝者にこだわり続けると57%高くなった。
- 真に良い応答のみを成功としてカウントし、センシティブなターゲットがどれだけの探索を受けるかを制限すること。
枠組み
一列に並んだスロットマシンを想像してほしい。それぞれが未知の確率で払い出しを行う。1回引くたびに1台のマシンについて何かを学べるが、出来の悪いマシンの学習に費やした1回は、出来の良いマシンに使えなかった1回でもある。知っていることを活かすこと(exploitation)と、知らないことを試すこと(exploration)の間の緊張関係、これが多腕バンディット問題である。
プロキシ選択においては、この対応関係は直接的である。
| バンディット用語 | スクレイピングにおける対応 |
|---|---|
| アーム | あるターゲットに対する1つのプロキシ構成: プロキシタイプ、ターゲティング、セッション設定 |
| プル | 1回のリクエスト |
| 報酬 | 求めていたデータを含む応答 |
| プルのコスト | 帯域幅、リトライ、そのリクエストに費やした時間 |
| 非定常性 | ターゲットが防御を変更すること、またはプールの評判が変化すること |
スクレイピング版は教科書版よりも2つの点で難しい。アームごとにコストが異なるため、最良のアームとは成功率が最も高いアームではなく、成功1件あたりのコストが最も低いアームである。そして確率は変動する。今日機能している構成が明日ブロックされることもあり、これはサブネット伝染の背後にあるパターンであり、ターゲットヘルススコアを構築すべき理由でもある。
選択器
トンプソンサンプリングは、各アームの成功率についての確率分布、すなわちその成功と失敗から構築されたベータ分布を保持する。各リクエストの前に、すべてのアームについてもっともらしい確率を1つずつ引き、その引いた値の下で成功1件あたりが最も安く見えるアームを選ぶ。証拠の少ないアームは分布が広いため、時折高い確率を引いて試される。証拠の多いアームは真の確率に近い値を引く。探索は証拠が蓄積するにつれて自然に薄れていく。
以下のバージョンでは2つの要素が加わっている。1回の試行あたりのコストと、古い証拠を事前分布に向けて減衰させる割引であり、これにより選択器は変化に気づくことができる。
import random
class ProxySelector:
"""Pick a proxy configuration per request with Thompson sampling, minimising cost per successful response.
Each configuration keeps a Beta(successes, failures) belief about its success rate. A discount below 1
lets old outcomes fade, so the selector notices when a configuration that used to work starts failing.
"""
def __init__(self, costs, discount=0.999, prior=(1.0, 1.0), rng=None):
self.costs = dict(costs) # configuration -> cost per attempt
self.discount = discount
self.prior = prior
self.wins = {arm: prior[0] for arm in self.costs}
self.losses = {arm: prior[1] for arm in self.costs}
self.rng = rng or random.Random()
def choose(self):
"""Sample a plausible success rate for each configuration and take the cheapest per expected success."""
def sampled_cost_per_success(arm):
rate = self.rng.betavariate(self.wins[arm], self.losses[arm])
return self.costs[arm] / max(rate, 1e-9)
return min(self.costs, key=sampled_cost_per_success)
def update(self, arm, success):
"""Record one outcome. Every belief decays towards the prior first, so recent results count most."""
for a in self.costs:
self.wins[a] = self.prior[0] + self.discount * (self.wins[a] - self.prior[0])
self.losses[a] = self.prior[1] + self.discount * (self.losses[a] - self.prior[1])
if success:
self.wins[arm] += 1
else:
self.losses[arm] += 1使用する際は、各リクエストの前に choose() を呼び出し、選ばれた構成を通してリクエストを送り、応答が良かったかどうかを添えて update() を呼び出す。割引係数0.999は、おおよそ1000件の結果に相当する実効記憶を与える。0.995ではおよそ200件である。
シミュレーション
答えが変化したときに選択器がどう振る舞うかを見るために、4つの構成を持つ1つのターゲットをシミュレートした。以下の成功率とコストは、トレードオフを可視化するために選んだ仮定の値であり、特定のプロバイダやネットワークの測定値ではない。
| 構成 | 想定成功率 | 想定1試行あたりコスト | 成功1件あたりコスト |
|---|---|---|---|
| データセンター | 25% | 0.5 | 2.00 |
| ISP | 80%、リクエスト5,000件後に30%へ低下 | 0.9 | 1.13、その後3.00 |
| レジデンシャル、国ターゲティング | 92% | 1.3 | 1.41 |
| レジデンシャル、都市ターゲティング | 95% | 1.6 | 1.68 |
コストは帯域幅と試行のオーバーヘッドをカバーする相対単位である。最初の5,000リクエストの間は、良い応答を得る最も安い方法はISPだが、その後ターゲットがブロックを始め、国ターゲティングのレジデンシャルが最良の選択となる。各戦略は20,000リクエストを行い、すべての戦略を異なる乱数シードで100回繰り返した。
| 戦略 | 良い応答1件あたりコスト | 完全な事後知識との差 | 良い応答数 | 変化後の適応に要したリクエスト数 |
|---|---|---|---|---|
| 完全な事後知識(真の確率を知っている) | 1.348 | 基準 | 17,806 | 0 |
| トンプソンサンプリング、割引0.999 | 1.375 | +2.0% | 16,694 | 約800 |
| トンプソンサンプリング、割引0.995 | 1.389 | +3.0% | 15,704 | 約1,075 |
| トンプソンサンプリング、割引なし | 1.428 | +5.9% | 15,933 | 約3,500 |
| イプシロングリーディ、探索10% | 1.441 | +6.9% | 15,848 | 約2,800 |
| トンプソンサンプリング、割引0.98 | 1.443 | +7.0% | 13,834 | 収束せず |
| 常にレジデンシャル、都市ターゲティング | 1.684 | +24.9% | 19,000 | 該当なし |
| 4つすべてをラウンドロビン | 1.689 | +25.3% | 12,731 | 該当なし |
| 常にISP、早期の勝者 | 2.118 | +57.1% | 8,501 | 該当なし |
数値は100回の実行の平均であり、どの戦略についても中央90%の実行は平均の2.5%以内に収まった。「適応に要したリクエスト数」とは、変化後、200リクエストの窓の90%が新しい最良構成に割り当てられるまでの中央値のリクエスト数である。
結果が示すこと
固定の選択はどちらの方向にもコストが高い。 最も信頼性の高い構成を常に使うと、良い応答数は最も多くなったが、1件あたり25%多く支払うことになった。早期に勝っていた構成を常に使い続けることは、ターゲットが変化した後では最悪の戦略であり、基準より57%高くなった。
学習だけでは不十分で、忘却が必要である。 割引なしのトンプソンサンプリングは、変化後、古い勝者について蓄積した証拠を信用しなくなるまでに約3,500リクエストを要した。割引0.999はこれを約800に短縮した。
速すぎる忘却もそれ自体が問題である。 割引0.98では、選択器はおよそ50件の結果しか記憶せず、出来の悪い選択肢を繰り返し試し続け、収束しなかった。有用な範囲はトラフィックに依存する。記憶は構成同士を区別するのに十分な数のリクエストをカバーすべきであり、それ以上であってはならない。
目的が答えを決める。 このバンディットは良い応答1件あたりのコストを最小化した。重要なのがコストにかかわらず最大のデータ量であったり、締め切りであったりする場合は、報酬にそれを反映させる必要がある。そうしなければ、選択器は誤った目標を非常に効率的に最適化してしまう。
実際のトラフィックでの使用
- 成功を厳密に定義する。 ブロックページや空の結果を伴うHTTP 200は失敗である。選択器にはサイレント失敗率に使うのと同じチェックを与えること。そうしなければ、静かに失敗する構成を好むように学習してしまう。
- ターゲットごとに1つの選択器を運用する。 成功率はサイトによって異なるため、共有の選択器は、学習させたいまさにその違いを平均化してしまう。
- センシティブなターゲットでは探索に上限を設ける。 出来の悪い構成を通じた探索的なリクエストはすべて、サイトがあなたに不利にカウントしうるリクエストである。選択器が自力で再発見するのを待つのではなく、明らかに不適切な構成は取り除くこと。
- セッションの一貫性を保つ。 ログインやカートなど状態に依存するものについては、固定セッションとローテーティングセッションが説明するとおり、リクエストごとではなくセッションごとに構成を選ぶこと。
- 実際のコストを使う。 帯域幅課金のプロキシでは、1試行あたりのコストはページの重さとリトライに依存する。クリーンレコード1件あたりコストの背後にある数値が正しい入力である。
- ロードバランシングの最低限を維持する。 バンディットはどの構成を使うかを決めるものであり、その構成内でリクエストをどう分散させるかを決めるものではない。それは依然としてローテーション、並行性、リトライのアーキテクチャの仕事である。
結論
プロキシ構成を一度選んでそのまま使い続けることは、自分のコストもターゲットも変化しないという賭けである。各リクエストを小さな実験として扱い、トンプソンサンプリングと適切な記憶を用いることで、その賭けは更新され続ける測定へと変わる。
私たちのシミュレーションでは、これは事前に答えを知っている場合との差を2%以内に収め、最良の選択肢が変化したときには約800リクエストで適応し、固定戦略の25%から57%の割増を回避した。確率とコストは仮定の値だったが、コードは自分自身のデータに対して実行できるほど短い。
出典と参考文献
- Daniel Russoら、A Tutorial on Thompson Sampling、2017年。
- 上記コードを用いてShifterが2026年10月2日に実施したシミュレーション。成功率とコストは仮定であり、特定のネットワークの測定値ではない。