すべてのプログラマ必見！リトライ処理の効率的な手法、それは「Exponential Backoff」

2019年4月21日 04:11

（画像引用：https://www.brianstorti.com/rabbitmq-exponential-backoff/）

はじめまして。Artriggerのnooptrと申します。私はプログラマとして主にFOLLYの開発に携わっており、バックエンドとブロックチェーン開発を担当しております。noteではArtriggerやFOLLYに関するトピックだけでなく、テック系の記事やエンジニア向けの記事も発信していくので、ご覧いただけると幸いです。
（記事を書くのはあまり慣れていませんが、よろしくお願いします！）

さて、多くのエンジニアの方が「リトライ処理」に関するプログラムを書いた経験があると思います。エラーの発生時に、どのようにリトライすれば効率なのか。これは誰もが抱える悩みですよね。そこで私は「Exponential Backoff」という手法をご紹介したいと思います。

……と、その前にそもそもリトライ処理って何でしょうか？

リトライとは、再試行（する）という意味の英単語。操作や処理が中断、失敗、異常終了などした場合に、同じ処理の実行をもう一度試みることをリトライという。利用者の指示に従って実施される場合と、あらかじめ設定された回数や時間間隔の通りに自動的に行われる場合がある。
引用：IT用語辞典 e-Words

わかりやすく言うと"再試行の処理"ですね。
一般的なエラーリトライの例を見ていきましょう。

retries = 0

DO
    wait 1 second

    status = Get the result of response

    IF status = SUCCESS
        retry = false
    ELSE
        retry = true
    END IF

    retries = retries + 1

WHILE (retry AND (retries < MAX_RETRIES))

一見、問題ないように見えますが、実は非効率的なコードです。なぜなら、小規模のシステムの場合は「1秒ごと」など固定値で実装して良いかもしれませんが、システムの規模が大きくなると、問題が生じてしまう可能性があるからです。

では次に、具体的な方法をお話していきます。

1. Exponential Backoffの仕組み

Exponential Backoffとは、データ送信処理が失敗して再送信する際に、失敗回数が増えるに連れて再送信するまでの待ち時間を指数関数的に増やす仕組みです。

つまり、衝突の連続を防ぐために、遅延（リトライ間隔）をランダム化します。

例えば、リトライ間隔を固定値ではなく、0.5秒、1秒、2秒、4秒、8秒、16秒……というように増やしていくのです。

これによって、サーバの負荷を軽減したり、無駄なリクエストを省けたり、再試行する前に問題を修正して解決できるようになるので、結果的にリトライ後の成功率が高くなります。

引用：Bonfire API #1 APIのリトライ処理

2. Exponential Backoffを使わない時に発生する問題

先ほどの例に戻ってみましょう。これは、どのような問題があると考えられるでしょうか。

retries = 0

DO
    wait 1 second

    status = Get the result of response

    IF status = SUCCESS
        retry = false
    ELSE
        retry = true
    END IF

    retries = retries + 1

WHILE (retry AND (retries < MAX_RETRIES))

例えば、ウェブサーバが2台（1号機と2号機）あるとします。クライアントからのリクエストは、ロードバランサ経由でそれぞれのサーバに振り分けますね。

サーバ1号機が何かしらの原因でダウンしたとします。すると、クライアントからのリクエストがすべてエラーとなり、多数のリトライがサーバ 2号機に送信されることになるでしょう。

この時に、「1秒ごと」の固定値でリトライすると、当然ながら全クライアントが「1秒ごと」にリトライすることになりますよね。そうすると、サーバが「1秒ごと」に多数のリクエストを集中的に受けることになり、 DoS攻撃にも似た過剰な負荷がかかることになるのです。結果はご察しの通り、2号機も同じくダウン……。では、どのようにリトライすればいいのでしょうか？

3. Exponential Backoffアルゴリズムの実装例

答えは簡単。リトライ間隔を指数関数的に調整すれば、解決できます。

retries = 0

DO
    wait for random from 0 to (2^retries * 100) milliseconds

    status = Get the result of response

    IF status = SUCCESS
        retry = false
    ELSE
        retry = true
    END IF

    retries = retries + 1

WHILE (retry AND (retries < MAX_RETRIES))

・リクエストが失敗した場合、1 + random_number_milliseconds 秒待ってから、リクエストを再試行。

・リクエストが失敗した場合、2 + random_number_milliseconds 秒待ってから、リクエストを再試行。

・リクエストが失敗した場合、4 + random_number_milliseconds 秒待ってから、リクエストを再試行。

このようにして、最大 MAX_RETRIES 回数まで繰り返します。通常、MAX_RETRIES は 5（2^5 = 32秒）または 6（2^6 = 64秒）ですが、適切な値はユースケースによって異なります。

4. 実際の例（Google,AWSなど）

例1：Google HTTP client

retry_interval = retry_interval * multiplier ^ (N - 1)
randomized_interval := retry_interval * 
(random value in range [1 - randomization_factor, 1 + randomization_factor])

・レスポンスのステータスは5xxの場合はリトライ。

・デフォルトで、retry_interval = 0.5s, randomization_factor = 0.5, multiplier= 1.5, max_interval = 1 minute, max_elapsed_time = 15s

・retry_interval > max_elapsed_time (15s)の場合はストップ。

結果：

request retry_interval randomized_interval
01      00.50          [0.25, 0.75]
02      00.75          [0.38, 1.12]
03      01.12          [0.56, 1.69]
04      01.69          [0.84, 2.53]
05      02.53          [1.27, 3.80]
06      03.80          [1.90, 5.70]
07      05.70          [2.85, 8.54]
08      08.54          [4.27, 12.81]
09      12.81          [6.41, 19.22]
10      19.22          STOP

例2：AWS SimpleDB

currentRetry = 0
 DO
   status = execute Amazon SimpleDB request
   IF status = success OR status = client error (4xx)
     set retry to false
     process the response or client error as appropriate
   ELSE
     set retry to true
     currentRetry = currentRetry + 1
     wait for a random delay between 0 and (4^currentRetry * 100) milliseconds
   END-IF
 WHILE (retry = true AND currentRetry < MaxNumberOfRetries)

結果：

request randomized_interval
1       [0, 400)
2       [0, 1600)
3       [0, 6400)
4       [0, 25600)
5       [0, 102400)

5. まとめ

Exponential Backoffのメリットは、主に以下の2つです。

・長期的な障害が発生した時に、システムの負担を軽減できる。
・大規模分散システム内では常に部分障害が発生しているため、運用コストを削減できる。

いかがでしょうか。開発時にリトライ処理を実装する機会があれば、ぜひExponential Backoffを試してみてください。私もお勧めします。

参考資料：
Error Retries and Exponential Backoff in AWS
Exponential Backoff And Jitter
Building for Performance and Reliability with Amazon SimpleDB
切り捨て型指数バックオフ
 Bonfire API #1 APIのリトライ処理