見出し画像

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

(画像引用: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のリトライ処理

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

26

Artrigger

アート・テクノロジー・教育に関する最新トピックをお届けします。

#エンジニア 系記事まとめ

noteに投稿されたエンジニア系の記事のまとめ。コーディングTIPSよりは、考察や意見などを中心に。

コメント3件

すいません。素人質問なのですが、指数関数的に待ち時間が大きくなるので、ランダム化はしていないとおもうのですが、界隈では指数増加をランダム化と表現することがあるのでしょうか。よろしくお願いします!
ご質問ありがとうございます。

Exponential Backoffアルゴリズムの実装例によると、ランダム化はしています。

下記のコードを見ると、0から2^retires * 100までの間、ランダムして、random値を取っているからですね。
wait for random from 0 to (2^retries * 100) milliseconds

例えば、
retries = 1の場合、random値 = random (0, 2^1 * 100)
retries = 2の場合、random値 = random (0, 2^2 * 100)
retries = 3の場合、random値 = random (0, 2^3 * 100)

そういう感じですね。
あ、なるほど。。完全に勘違いしてました!確かにランダムですね。詳しい解説ありがとうございました!!
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。