Exponential Backoff And Jitter の話

「くらえ、エクスポネンシャルバックオフ！！」
「なにぃ、その技は！？」

よく分からない物語が展開しそうになっていますが…
お疲れ様です。
システム開発部、生ける屍こと松山です。

久しぶりにブログを更新しようと思いましたが、
何かサンプルコードを書いて動くものを作る気力が湧かなかったので、
今回はちょっとしたアルゴリズムの話を書こうと思います。

例えば

クライアント ↔︎ サーバ間の通信時にサーバからエラーが返ってきた場合、
クライアント側の振る舞いとして考えられるものは、

① エラーメッセージを表示し、処理をキャンセルする
② もう一度同じ通信を実行する（リトライ）
③ 進行不能になる

③ は唯の不具合なので論外ですが、多くは①か②になるのかなと思います。
中でも処理を中断できないフローの場合、②による回復を期待することになると思います。

リトライ

リトライについて少し考えてみます。
シンプルにレスポンスがエラーだったのでリトライする。
とした場合、リクエスト→レスポンス（エラー）→リトライ を無限に繰り返すことになります。
何らかの原因によりサーバ側で障害が発生していた場合、
全てのユーザがリトライし続けることになり、（最早、Dos 攻撃と変わらない状況）
サーバの負荷が急上昇してついにはサーバダウンしてしまう
などといった最悪の事態に発展してしまうかもしれません。
実際に発展したことがあるのは苦い思い出です…

そこでこういった高負荷を分散させるために用いられるアルゴリズムが、
冒頭に出てきた「エクスポネンシャルバックオフ（Exponential Backoff）」になります。

エクスポネンシャルバックオフ

直訳すると、
・エクスポネンシャル = 指数関数的な
・バックオフ = 後退
ということで、指数関数的にリトライする間隔を後退させる（遅らせる）アルゴリズムになります。

何らかエラーとなった場合に、リトライを
1秒後、2秒後、4秒後、8秒後・・・
と遅らせていくことで、全体のリトライ回数を抑えて効率的なリトライを実現します。

AWS でも解説されています。
AWS の解説

ジッター

ただし、単純な指数関数では同時に多くのリクエストが発生してしまう可能性があります。
（同じタイミングでアクセスしたユーザは、リトライ間隔も同じになってしまうため）
そこでエクスポネンシャルと合わせて使われるのが「ジッター（and Jitter）」です。
直訳すると
・ジッター = 時間のずれ
となるようです。
ランダム値によりリトライ間隔に幅を持たせることで、同時リトライを分散させるイメージになります。

AWS Solution Architectブログの記事
に詳細な検証結果がまとめられています。

まとめ

実際にはリトライ回数の上限や、タイムアウトなども考慮する必要がありますが、
今回はエクスポネンシャルバックオフとジッターの紹介のみに留めておきます。

一時的に発生するようなエラーや障害の場合、リトライにより解決することも多いと思います。
回復までにかかる時間が多少ある場合に、連続したリトライを行うのではなく、
今回紹介したような効率的なリトライをすることで、不要な負荷をかけずに改善できることを
覚えておいていただければ幸いです。

ちなみに冒頭のやつは、
「エクスポネンシャルバックオフってなんか必殺技っぽいですよね」
って話を聞いたことがあったので、掴みの小ネタとして採用しました。

簡単ですが、今回のお話はこれまでになります。