エクスポネンシャル・バックオフとジッターのアルゴリズムの違いと総試行回数、処理完了時間の比較

以前、このブログでAWSが推奨するエクスポネンシャル・バックオフとジッターの記事について取り上げ、JavaScriptでの実装をおこないました。

s1r-j.hatenablog.com

今回は、1度に1リクエストしか処理ができないサービスと複数の競合するクライアントをJavaScriptで用意しました。クライアント数が増えたとき、それぞれのバックオフ・アルゴリズムの処理が完了するまでの総試行回数と処理完了時間がどのように変化するかを確認します。 AWSの記事の最後にあったようなグラフに本当になるのかを試しました。

用意した実装はGitHubに置いてあります。

実装

サービス

index.jsファイルに実装しています。

用意するサービスは1度に1リクエストしか処理できないように排他制御をするので、async-lockというモジュールを利用しました。 async-lockの使い方は以前、当ブログで紹介しています。

Node.jsでasync-lockを使った排他制御をおこなう - s1r-Jの技術ブログ

このサービスは1つのリクエストを平均10ミリ秒（8～12ミリ秒の間でランダム）で処理するように作成しています。

async function request() {
  await lock.acquire('my-lock', async () => {
    const request = 10;
    const fluctuation = 4;
    await new Promise((resolve) => setTimeout(resolve, request - fluctuation / 2 + Math.random() * fluctuation));  
  });
}

バックオフとジッターのアルゴリズム

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

exponential.jsファイルに実装しています。

リトライ回数に応じて指数関数的に待機時間を伸ばしていくアルゴリズムです。

export default function exponentialBackoff({ base, attempt, cap, }) {
  return Math.min(cap && Number.MAX_VALUE, base * 2 ** attempt);
}

Full Jitter

full.jsファイルに実装しています。

エクスポネンシャル・バックオフで算出された値を最大値とし、最小をゼロとした範囲でランダムに待機時間を決定するアルゴリズムです。

export default function full({ base, attempt, cap, }) {
  return Math.random() * (Math.min(cap && Number.MAX_VALUE, base * 2 ** attempt));
}

Equal Jitter

equal.jsファイルに実装しています。

エクスポネンシャル・バックオフで算出された値の半分を最大値とし最小をゼロとした範囲でランダムに値を取り出したうえで、エクスポネンシャル・バックオフで算出された値の半分を加えた値を待機時間とするアルゴリズムです。

export default function equal({ base, attempt, cap, }) {
  const temp = Math.min(cap && Number.MAX_VALUE, base * 2 ** attempt);
  return temp / 2 + Math.random() * (temp / 2);
}

Decorrelated Jitter

decorrelated.jsファイルに実装しています。

前回の待機時間を使って待機時間を算出するアルゴリズムです。前回の値の3倍の値を最大値とし、最小を初回の待機時間とした範囲でランダムに待機時間を決定します。

export default function decorrelated({ base, cap, prevSleep, }) {
  return Math.min(cap && Number.MAX_VALUE, base + Math.random() * (prevSleep * 3 - base));
}

実行方法

実行方法はindex.jsファイルを、モード（アルゴリズム）とクライアント数を指定して呼び出します。

$ node index.js <モード> <クライアント数>

例えばFull Jitterでクライアント数10の場合には、以下のようになります。

$ node index.js full 10

測定結果

上記のコードを使って、競合するようにリクエストを発行するクライアント数（client）を増やしたとき、すべてのクライアントの処理が完了するまでにかかる時間（time）と総試行回数（work）の変化を測定しました。