制限付きExponential Backoff
次に、制限付きExponential Backoffを導入してみます。
このアルゴリズムでは、リクエスト失敗後、すぐにリクエストを再送するのではなく、初期待ち時間分を待ってから再送します。リクエストが失敗しますと、（初期待ち時間 × 2）の時間分を待ってから再送します。そして、次に失敗した場には、（初期待ち時間 × 22）時間分、その次は、（初期待ち時間 × 23）時間分というように待ち時間を指数関数的に増やしていきます。ただし、最大の待ち時間は決めておき、それ以上は待ち時間を増やさないようにします。これが「制限付き」の意味になっています。
疑似コードでは下記の通りとなります。capは最大待ち時間、baseは初期待ち時間、attemptは試行回数を示しています。**は、べき乗計算を示しています。また、min()関数は、第１引数、第２引数のどちらか一方の最低値ということになります（つまり、capの数値以上にはならないということですね）。
sleep = min(cap, base * 2 ** attempt)
これを導入すると、下図のように全体のリクエスト数が低減します。
どのようなタイミングでリトライが発生したかを下図の通り可視化してみます。すると、リトライの頻度自体は減っているものの、「リトライのタイミングが塊になっている」ことが分かります。また、リクエストが全くない時間帯も発生しており、少し非効率ですね。
Jitterの導入
この問題を解決するべく待ち時間をランダムにしてみましょう。制限付きExponential Backoffのアルゴリズムで得た待ち時間を最大値として、ランダムな待ち時間を作成します。疑似コードは下記の通りとなります。
sleep = random_between(0, min(cap, base * 2 ** attempt))
リトライ発生のタイミングを再度可視化して確認すると、下図の通りです。
総リクエスト数のグラフを確認すると、大きな改善がみられました。
Equal JitterとDecorrelated Jitter
さきほどのJitterアルゴリズムを、便宜的にFull Jitterと名付けます。この他、次の2つのJitterアルゴリズムについても紹介・検証してみたいと思います。
1つめは、Equal Jitterと呼ばれるアルゴリズムです。このアルゴリズムでは、まず、制限付きExponential Backoffアルゴリズムの計算結果を1/2にします（下記擬似コードの "temp/2"）。この"temp/2"を使って、Full jitterで行なったようなランダムな数値を生成し、加算します。文章で書くと少し複雑ですが、疑似コードでは下記の通りとなります。このアルゴリズムは、backoffとjitterをできるだけ小さく保つように動作します。
temp = min(cap, base * 2 ** attempt) sleep = temp / 2 + random_between(0, temp / 2)
もうひとつは、Decorrelated Jitterと呼ばれるアルゴリズムです。Decorrelatedは無相関という意味で、これまでのアルゴリズムに挿入されていた指数関数計算部分を取り除き、単なる定数に代えています。その代わり、前回の待ち時間を使い、さらにランダムな数値を生成するものです。
sleep = min(cap, random_between(base, sleep * 3))
全てのアルゴリズムを比較してみる
全てのアルゴリズムを比較してみますと、下記グラフの通りとなります。Full Jitterと、Equal Jitterが大変優秀な成績を残し、続いて、Decorrelated Jitter、制限つきExponential Backoffの順となりました。
ちなみに、全リクエストの処理が完了するまでの総所要時間を比較してみると、下記グラフの通りとなります。Jitterなしの制限付きExponential Backoffは時間がかかりすぎるため除外しています。Jitterのアルゴリズムのみで並べますと、Decorrelated Jitter、Full Jitter、Equal Jitterの順となりました。
3つのJitterつきリトライ・アルゴリズムをご紹介しましたが、ユースケースによっては選択の余地がありそうということがお分かりいただけたかと思います。いずれにしても、Jitter有りのアプローチが優秀であることは間違いありません。リクエスト総数が少なく効率的なリトライが行われ、完了までの総所用時間が短くなっています。
シンプルなリトライ処理の総所要時間が最短の理由
最後にご紹介したグラフをよく見ますと、シンプルなリトライ処理（Backoff Algorithm none）の総所要時間が最も短いことに気づきます。この結果だけを見ると、「アルゴリズムを工夫することで、リクエスト数は低減できているけれど、シンプルにリトライを続けた方が全体として早く完了するようにみえるなぁ」と疑問に思われた方もいらっしゃるかもしれません。
この検証では、各アルゴリズムの比較検証を行うために、（リクエスト間の競合が発生しないほどの）十分なネットワークリソース、CPUリソースが存在することを仮定しています。現実的にはそれらリソースは有限ですので、シンプルなリトライ処理（Backoff Algorithm none）を実際に利用した場合には、多くのリクエストが滞留もしくは破棄されるでしょう。
TCPに関して言えば、パケットが破棄された場合には、TCPの輻輳制御アルゴリズムの影響で、さらに経過時間が伸びる可能性[注]が出てきます。また、クラウドやWeb APIサービスにはスロットリングが実装されていることが一般的なので、効率的に APIをコールしていれば成功したはずのものが、全て失敗することにもなります。
したがって、この検証結果で語られているシンプルなリトライ処理（Backoff Algorithm none）の結果は、リソースが潤沢にあり、かつ、それらリソースが枯渇しなかった場合という特殊な条件下におけるシミュレーション上の最短時間を表しているのだ、とご理解いただければと思います。現実的には大変非効率な方式ですので、その他のアルゴリズムをご検討いただくことをお勧めします。
[注] TCPは、一回のパケットで送信されるセグメントのサイズを徐々に増加しながら、データ送信を行う仕様となっている。つまり、ネットワークの輻輳（「ふくそう」と読み、アクセスが集中し、回線が繋がらなくなること）を検知した場合に、サイズの小さいセグメントサイズから試行しなおすため、転送時間という観点では輻輳を検知するとリカバリーに時間がかかる傾向がある。この問題を扱っているTCPの輻輳制御（TCP congestion control）アルゴリズムは、本稿執筆時点でも活発な研究がされており、一概に定義することは難しいが、一般的にはそのような傾向があるものととらえ、本文もそのような意図で利用している。
