リトライの経済学:リトライが割に合わなくなる試行回数

リトライを重ねるごとに成功率は下がっていきます。自分のログと数行のPythonを使って、リトライが割に合わなくなるポイントを見極める方法。

あらゆるスクレイパーは失敗したリクエストを再試行しますが、ほとんどが同じ方法で再試行回数を選びます。3回、なんとなく妥当に感じるからです。しかし再試行は無料ではありません。ギガバイト単位で課金されるレジデンシャルプロキシでは、再試行のたびにページを再度ダウンロードします。どのシステムでも、時間とターゲットへの負荷がかかります。そして通常、再試行は前回よりも成功する可能性が低くなります。

つまり、もう一度試す価値がそのコストを下回る地点が存在します。この調査では、実例と自分のデータで実行できるコードを使って、自分のログからその地点を見つける方法を示します。

なぜ後の再試行ほど成功しにくいのか

失敗が純粋に運の悪さであれば、どの再試行も最初の試行と同じ成功確率を持つはずです。しかし実際はそうではありません。一度失敗したリクエストは、持続的な理由で失敗している可能性が高くなります。存在しないページ、そのアドレスへのブロック、ダウンしているサイト、決してマッチしないパーサーなどです。4回目の試行に到達するジョブは、ほとんどが難しいケースです。

つまり、試行ごとの成功率は下がり、それに伴い追加の成功にかかるコストは上がります。

ログから測定する

必要なデータは、各ジョブについて成功した試行回数、あるいはすべての試行が失敗したという記録だけです。ほとんどのスクレイパーはすでにこれをログに記録しています。これにより、試行kの成功率は、試行kに到達して成功したジョブの割合として求められます。

from collections import Counter


def attempt_success_rates(outcomes, max_attempts):
    """Chance that attempt k succeeds, given the job got that far.

    outcomes: per job, the attempt number that succeeded, or None if every
    attempt failed (with max_attempts tries).
    """
    succeeded_at = Counter(o for o in outcomes if o is not None)
    reached = len(outcomes)
    rates = []
    for k in range(1, max_attempts + 1):
        rates.append(succeeded_at[k] / reached if reached else 0.0)
        reached -= succeeded_at[k]
    return rates


def cost_per_success(rates, cap, attempt_cost):
    """Expected cost of one successful job if we stop after `cap` attempts."""
    p_reach, spent, success = 1.0, 0.0, 0.0
    for rate in rates[:cap]:
        spent += p_reach * attempt_cost
        success += p_reach * rate
        p_reach *= 1 - rate
    return spent / success if success else float("inf")


def best_cap(rates, attempt_cost, value_of_success):
    """The last attempt whose expected value still exceeds its cost."""
    cap = 0
    for k, rate in enumerate(rates, start=1):
        if rate * value_of_success > attempt_cost:
            cap = k
    return cap

3つの関数があります。

attempt_success_ratesは、ログを試行ごとの成功率に変換します。
cost_per_successは、指定した回数で試行を打ち切った場合の、成功したジョブ1件あたりの平均コストを示します。
best_capは、期待値がコストをまだ上回っている最後の試行を見つけます。

実例

6回まで試行を許可された10,000件のジョブの例示的なログを以下に示します。

from retry_econ import attempt_success_rates, best_cap, cost_per_success

# Illustrative outcomes for 10,000 jobs, each allowed up to six attempts:
# the attempt that succeeded, or None if all six failed.
outcomes = [1] * 8200 + [2] * 900 + [3] * 260 + [4] * 90 + [5] * 40 + [6] * 20 + [None] * 490
rates = attempt_success_rates(outcomes, max_attempts=6)
print("success rate by attempt:", [round(r, 3) for r in rates])

for cap in range(1, 7):
    print(f"cap {cap}: cost per success {cost_per_success(rates, cap, attempt_cost=1.0):.3f}")

print("best cap if a success is worth 5 attempts:", best_cap(rates, attempt_cost=1.0, value_of_success=5.0))
print("best cap if a success is worth 20 attempts:", best_cap(rates, attempt_cost=1.0, value_of_success=20.0))

success rate by attempt: [0.82, 0.5, 0.289, 0.141, 0.073, 0.039]
cap 1: cost per success 1.220
cap 2: cost per success 1.297
cap 3: cost per success 1.357
cap 4: cost per success 1.412
cap 5: cost per success 1.464
cap 6: cost per success 1.514
best cap if a success is worth 5 attempts: 3
best cap if a success is worth 20 attempts: 5

3つの点が際立ちます。

成功率は急速に下がります。 最初の試行は82%の確率で成功します。試行2に到達したジョブのうち、半分が成功します。試行5までには、成功するのは10件に1件未満です。

追加の成功1件あたりのコストは、前回より高くなります。 1回の試行コストをその成功率で割ると、その試行からの成功1件分のコストが得られます。最初の試行ではおよそ1.2回分、2回目では2回分、3回目では3.5回分、4回目では7回分、6回目では25回分を超えます。試行回数の上限を増やすほど、成功1件あたりの平均コストはゆっくりと上昇しますが、これは各追加試行がより少数のジョブに対して実行されるためです。一方、限界コストは急激に上昇します。

適切な上限は、成功の価値によって決まります。 成功した記録が試行5回分の価値を持つなら、3回で打ち切るべきです。20回分の価値がある、たとえばどうしても取得しなければならないページなら、5回まで行くべきです。唯一の正しい数字は存在せず、価値ごとの正しい数字があるだけです。

成功に価値を設定する

成功の価値は、あなた自身が決めなければならない唯一の入力です。設定方法をいくつか挙げます。

置き換え可能な記録、たとえば毎日収集される多数の価格観測のうちの1つは、それぞれの価値が小さいものです。1件欠けても問題なく、低い上限が適切です。
必須の記録、たとえば顧客が待っているデータセットを完成させるページは、はるかに価値が高くなります。より高い上限が理にかなっています。
帯域幅以外のコストも考慮に入れます。時間、ターゲットへの負荷、失敗し続けるページを叩き続けることで他のすべてに対するブロックを招くリスクなどです。

成功したレスポンスにのみ課金されるWeb Scraping APIでは、再試行の金銭的な側面はプロバイダー側に移りますが、時間とターゲットへの負荷は依然として発生します。たとえば、ShifterのWeb Scraping APIは、失敗したリクエストには課金しません。

再試行を安価にする

上限は全体の半分にすぎません。もう半分は、各再試行をより成功しやすくすることです。

再試行の前に待ち、毎回さらに長く待ちます。 多くの失敗は一時的なレート制限であり、自然に解消されます。
失敗が示唆するものに応じて何かを変えます。 あるアドレスへのブロックは、別のアドレスからなら成功するかもしれません。タイムアウトには、同じリクエストの繰り返しではなく、より長いタイムアウトが必要かもしれません。
成功しえないものは再試行しません。 404や認証エラーは、何度やっても失敗します。

Webスクレイパーの再試行とバックオフに関するガイドで、これらの手法を詳しく解説しています。