JavaScriptで実装するエクスポネンシャル・バックオフとジッター

AWSが推奨するエクスポネンシャル・バックオフとジッターについて、その効果といくつかの実装方法について説明されている記事があります。

Exponential Backoff And Jitter | AWS Architecture Blog

この記事では内容を要約しつつ、擬似コードで書かれているコードをJavaScriptで実装してみました。

バックオフとジッター

先にそもそもの話である、バックオフとジッターについて軽く説明しておきます。

AWSのサービスをCLIやAPIを使って呼び出すときに何らかの理由で問題が発生すると、再試行をおこないます。このとき、再試行をむやみに繰り返してもサービスが復旧してリクエストが成功している可能性は低く、またクライアントからリクエストを送信しすぎることでサービスがリソースを使い果たす危険性があります。

これらを回避するため、バックオフとジッターを使って再試行の間隔を調整することがAWSで推奨されています。

バックオフとは、試行の間にある程度の時間を空けることを指します。バックオフにはいくつかパターンがあり、よくあるのはエクスポネンシャル・バックオフという試行ごとに待ち時間を指数関数的に増加させる方法です。

ジッターとはバックオフの待ち時間にゆらぎ（ランダム性）を与えるものです。バックオフがすべてのクライアントで同じになっている場合、試行タイミングが同じになってしまって高負荷状態が繰り返されてしまいます。

ここまで説明しましたが、さらに詳しい情報はAWSブログで日本語で解説されていますので、ぜひご覧ください。

ジッターを伴うタイムアウト、再試行、およびバックオフ

要約

Exponential Backoff And Jitter | AWS Architecture Blog

ここからは最初に紹介した記事の内容を要約していきます。

全体・用語

記事ではとあるサービスに対してリクエストを送るクライアントが複数存在しており（競合している）、問題が発生した場合にバックオフとジッターによる再試行がおこなわれるという状況を想定しています。この状態で、クライアント数が変化したとき、最終的にすべてのクライアントの処理が完了するまでの時間と処理が完了するまでの総試行回数の変化をグラフにしています（クライアント数が横軸、処理完了時間または総試行回数が縦軸になっています）。バックオフの実装方法やジッターの有無によって、グラフに違いがあることが示されています。

記事で想定されているサービスは、 1度に1リクエストしか同時に処理ができず、平均遅延時間が10ミリ秒でばらつきが4ミリ秒という処理をしているようです。

グラフや記事内の擬似コードに出てくる用語をまとめます。

Competing Clients：競合するクライアント数、つまり多重度を示します。
Completion Time：処理が完了するまでにかかる時間
Work：クライアントからのリクエスト総数、つまり総試行回数

バックオフが設定されていない場合

まず、バックオフが設定されておらず、リクエストに失敗したら即時リトライをおこなう場合を想定します。

N個のクライアント（多重度N）から同時にリクエストが送信されると、1度に1リクエストしか処理されないので、すべての処理が完了するにはN回の処理が必要になります。

このため、クライアント数と処理完了時間は比例の関係になります。

初回はN個のクライアントがリクエストを送信し、1つのリクエストだけが処理に入ります。残りのN-1個のクライアントは処理に失敗したため、即時リトライをおこないます。これが繰り返されるので総試行回数は(N + 1) N * 1/2となります。よって、総試行回数はクライアント数の2乗に比例することになります。

バックオフを導入した場合

制限付きエクスポネンシャル・バックオフについて紹介されています。

エクスポネンシャル・バックオフは、リトライ回数と何らかの相関（最初のリトライ時にt、次のリトライ時に2t、更にその次のリトライ時に3t、といった形）を持った値を試行の間の待機時間（遅延）として用いることです。制限付き、というのは待機時間の最大値Tを予め定義しておき、ある一定回数以上のリトライでは毎回待機時間Tを挟むようにするということです。

擬似コードでは以下のようになります。

sleep = min(cap, base * 2 ** attempt)

sleep: 試行の間の待機時間
min関数: 引数の値の最も小さいほうを値として返す
cap: 待機時間の最大値（上で言うT）
base: 待機時間の初期値（上で言うt）
attempt: リトライ回数

この擬似コードでは、待機時間の初期値にリトライ回数を指数として2の冪乗を掛けた値と待機時間の最大値のどちらか小さい方を待機時間とする、となっています。待機時間は一定回数まで2の冪乗（指数関数的=エクスポネンシャル）で伸びていき、一定回数を超えると待機時間の最大値になります。

ジッターを導入する

前述の擬似コードのように待機時間を設定すると、競合する複数のクライアントで同じ待機時間となってしまい、ある時間帯に試行が偏ってしまいます。そこで、試行タイミングの偏りを減らすため待機時間にゆらぎ（ランダム性）を与えるのがジッター（Jitter）です。

ジッターの実装方法にはいくつか代表的な実装があるようで、記事では3種類紹介されていました。

Full Jitter

エクスポネンシャル・バックオフで算出された値を最大値とし、最小をゼロとした範囲でランダムに待機時間を決定する実装方法です。待機時間全体に対してゆらぎを与えるということだと思います。

擬似コードでは以下のようになります。

sleep  = random_between(0, min(cap, base * 2 ** attempt))

random_between関数: 引数で指定された範囲からランダムに値を返す

JavaScriptで10回の待機時間を出力するコードは以下のようになります。

const cap = 100;
const base = 10;
for (let attempt = 0; attempt < 10; attempt++) {
  const sleep = Math.random() * (Math.min(cap, base * 2 ** attempt));
    console.log(`試行回数: ${attempt + 1}, 待機時間: ${sleep}ms`);
}

冪乗の計算はMath.powでも代用できますが、エクスポネンシャル演算子のほうが新しい書き方のようです。 10回分の測定結果は以下のとおりです。

試行回数: 1, 待機時間: 6.133643849465624ms 試行回数: 2, 待機時間: 4.28762815968037ms 試行回数: 3, 待機時間: 36.74522520624706ms 試行回数: 4, 待機時間: 15.264033566194648ms 試行回数: 5, 待機時間: 91.99127184913378ms 試行回数: 6, 待機時間: 87.99504315887683ms 試行回数: 7, 待機時間: 12.71020372856766ms 試行回数: 8, 待機時間: 93.22341901336881ms 試行回数: 9, 待機時間: 20.72327114336816ms 試行回数: 10, 待機時間: 99.1551893992211ms

試行回数が多くなるほど大きな値が出やすい傾向になりますが、ランダムに値を取り出す範囲が広いため、試行回数が多くなっても待機時間が短いことがあります。

Equal Jitter

エクスポネンシャル・バックオフで算出された値の半分を最大値とし最小をゼロとした範囲でランダムに値を取り出したうえで、エクスポネンシャル・バックオフで算出された値の半分を加えた値を待機時間とする実装方法です。待機時間の半分に対してゆらぎを与える方法であり、先程のFull Jitterよりも試行回数の増加によって待機時間が長くなりやすいと思います。

下手くそな文章よりも擬似コードのほうがわかりやすいと思います。

temp = min(cap, base * 2 ** attempt)
sleep = temp / 2 + random_between(0, temp/2)

const cap = 100;
const base = 10;
for (let attempt = 0; attempt < 10; attempt++) {
    const temp = Math.min(cap, base * 2 ** attempt);
  const sleep = temp / 2 + Math.random() * (temp / 2);
    console.log(`試行回数: ${attempt + 1}, 待機時間: ${sleep}ms`);
}

試行回数: 1, 待機時間: 9.997334447546013ms 試行回数: 2, 待機時間: 18.031896756421013ms 試行回数: 3, 待機時間: 31.70505441331884ms 試行回数: 4, 待機時間: 46.49791452748417ms 試行回数: 5, 待機時間: 53.21664615161724ms 試行回数: 6, 待機時間: 81.16037636979527ms 試行回数: 7, 待機時間: 60.52639321642087ms 試行回数: 8, 待機時間: 65.18536749792602ms 試行回数: 9, 待機時間: 77.74128891358863ms 試行回数: 10, 待機時間: 73.54706365669821ms

Decorrelated Jitter

前回の待機時間を使って待機時間を算出する実装方法です。 Decorrelatedとは「無相関」という意味だそうで、試行回数との相関関係がないためにこのような名称と考えています。

sleep  = min(cap, random_between(base, sleep * 3))

擬似コードでは、前回の値の3倍の値を最大値とし、最小を初回の待機時間とした範囲でランダムに値を取り出すようになっています。

const cap = 100;
const base = 10;
let prevSleep = 0;
for (let attempt = 0; attempt < 10; attempt++) {
  const sleep = Math.min(cap, base + Math.random() * (prevSleep * 3 - base));
    prevSleep = sleep;
    console.log(`試行回数: ${attempt + 1}, 待機時間: ${sleep}ms`);
}

試行回数: 1, 待機時間: 0.6973573029971529ms 試行回数: 2, 待機時間: 5.62625973695099ms 試行回数: 3, 待機時間: 15.718183102234974ms 試行回数: 4, 待機時間: 27.265785715872514ms 試行回数: 5, 待機時間: 31.77848467421067ms 試行回数: 6, 待機時間: 10.475447479192475ms 試行回数: 7, 待機時間: 23.08435446789393ms 試行回数: 8, 待機時間: 44.8740248179586ms 試行回数: 9, 待機時間: 100ms 試行回数: 10, 待機時間: 20.750009544177612ms

前回の値の何倍を最大値とするのか、によって変わると思いますが、先の2つは指数関数的に最大値が増えるため、この実装のほうが待機時間が長くなりにくいと考えられます。

実装方法による違い

記事の最後では、バックオフを利用しなかったとき、ジッターを使わない単純なエクスポネンシャル・バックオフ、3種類の異なるジッターの実装方法を導入したバックオフ・アルゴリズムごとのクライアント数の増加と総試行回数または処理完了時間をグラフにして比較していました。

総試行回数では、Full JitterとEqual Jitterがクライアント数の増加による総試行回数の増加を抑えており、優秀な結果を示していました。 Decorrelated Jitterはその2つに比べると劣るものの、ジッターを使わないエクスポネンシャル・バックオフやバックオフを利用しないときに比べれば充分優秀な結果となっていました。

画像はExponential Backoff And Jitter | AWS Architecture Blogから引用

また、処理完了時間はジッターを使わないエクスポネンシャル・バックオフは遅くなりすぎるため、グラフに表示されていません。 Equal Jitterが最も劣っており、ジッターを使った実装方法ではDecorelated Jitterが最も優秀であり、次点でFull Jitterとなっています。

画像はExponential Backoff And Jitter | AWS Architecture Blogから引用

3つのジッター導入をしたバックオフ・アルゴリズムについてまとめると、

Equal JitterはFull Jitterよりも総試行回数の抑制でわずかに劣り、処理完了時間の抑制では大きく劣る
Equal JitterはDecorrelated Jitterよりも総試行回数の抑制で若干優秀であり、処理完了時間の抑制では大きく劣る
Full JitterはDecorrelated Jitterよりも総試行回数の抑制で若干優秀であり、処理完了時間の抑制では若干劣る

総試行回数の抑制・処理完了時間の抑制という面でみると、Full JitterとDecorelated Jitterが概ね優秀ということになりました。

おわりに

AWSのブログを確認してバックオフとジッターのアルゴリズム、そのアルゴリズムの性能についてまとめました。

バックオフとジッターの実装について知ったのは初めてでしたし、複数のアルゴリズムがあることも初めて知りました。リトライをおこなう機能を作成するときなどの参考にしたいと思いました。

今回用意したJavaScriptの実装は1つのクライアントがリトライするときの待機時間が試行回数によってどのように変わるのかを確認したものです。次回は、1度に1リクエストしか処理ができないサービスと複数の競合するクライアントを用意し、処理が完了するまでの総試行回数と処理完了時間を測定し、AWSのブログの最後にあったグラフのようになるかを検証してみたいと思います。