AWS SDKのエクスポネンシャルバックオフを確認してみた

AWS SDKで「エクスポネンシャルバックオフ」アルゴリズムがどのように実装されているか確認します
2020.11.09

AWSのドキュメントに登場する「エクスポネンシャルバックオフ」という見慣れない単語の詳細が気になったので、実際にAWS SDKを用いて確認してみました。

エクスポネンシャルバックオフとジッター

Wikipediaの日本語翻訳記事から引用します。

https://en.wikipedia.org/wiki/Exponential_backoff

さまざまなコンピュータネットワークで、バイナリ指数バックオフまたは切り捨てられたバイナリ指数バックオフは、多くの場合ネットワークの輻輳を回避するために、同じデータブロックの繰り返しの再送信の間隔を空けるために使用されるアルゴリズムを指します。

通信分野で使用される再試行(リトライ)処理のアルゴリズムのようです。

AWSでは以下のページに解説があります。

エクスポネンシャルバックオフの背後にある考え方は、連続したエラー応答の再試行間の待機時間を徐々に長く使用することです。

リトライ処理の間隔が固定値では一定間隔でリクエストが続くため、リクエストの成功率が上がらない恐れがあります。 例えば、5秒間のネットワーク障害が発生したとして、1秒間隔で3回リトライしても全て失敗してしまいます。

一方、エクスポネンシャルバックオフは1秒、2秒、4秒、8秒…とリトライ処理の間隔を指数関数的に徐々に長くしてリクエストの成功率を上げることが狙いです。 上記の障害例に適用すると、3回目のリトライ処理で成功するため、固定値よりも成功する可能性が高いことがわかります(あくまでこの単純な例の場合においては)。

ただし、1秒、2秒、4秒、8秒…と単なる指数関数では、同時に多数のリクエストが発生する場合は固定間隔でのリトライ処理と変わらないため、 ジッターと呼ばれるランダム値を乗じてリトライ処理によるアクセスを分散させます。

ジッターについてはAWSの解説ページにも記載があります(日本語に翻訳された文章がわかりづらいため英文を引用しています)。 「必要だったらジッターを導入してね」というニュアンスですが、多く場合はジッターを取り入れた方が良いのだと思います。

Most exponential backoff algorithms use jitter (randomized delay) to prevent successive collisions. Because you aren't trying to avoid such collisions in these cases, you don't need to use this random number. However, if you use concurrent clients, jitter can help your requests succeed faster.

ちなみに、上記ページには疑似コードが記載されていますが、ジッターは適用されていません。

AWS SDKで確認してみる

各 AWS SDK には、自動再試行ロジックが実装されています。 (中略) AWS SDKを使用していない場合は、サーバー (5xx) またはスロットリングエラーを受け取った元のリクエストを再試行する必要があります。

AWS SDKにはエクスポネンシャルバックオフが実装されているはずなので、実際にaws-sdk-jsのコードで確認してみます。 以下のリポジトリのlib/utils.js内にリトライ処理間隔を算出する関数が定義されています。

※ 本記事執筆時点のコードを参照しています。

ハイライトしているコードがリトライ処理間隔を算出している箇所です。

ランダムな値 * (2のn乗(初期値は0,最大2) * base(初期値は100ms)) と、AWSのページに書かれている通りエクスポネンシャルバックオフとジッターが実装されています。

lib/utils.js

  calculateRetryDelay: function calculateRetryDelay(retryCount, retryDelayOptions, err) {
    if (!retryDelayOptions) retryDelayOptions = {};
    var customBackoff = retryDelayOptions.customBackoff || null;
    if (typeof customBackoff === 'function') {
      return customBackoff(retryCount, err);
    }
    var base = typeof retryDelayOptions.base === 'number' ? retryDelayOptions.base : 100;
    var delay = Math.random() * (Math.pow(2, retryCount) * base);
    return delay;
  },

リトライを発生させて値を確認してみる

aws-sdk-jsのサンプルリポジトリをクローンしてaws-sdk-jsをインストールし、node_modules内にダウンロードされたsdkコードに直接console.logを仕込んでdelayがどんな数字になるか確認してみます。

git clone https://github.com/awslabs/aws-nodejs-sample.git
cd aws-nodejs-sample
npm install

node_modules/aws-sdk/lib/util.js

  calculateRetryDelay: function calculateRetryDelay(retryCount, retryDelayOptions, err) {
    if (!retryDelayOptions) retryDelayOptions = {};
    var customBackoff = retryDelayOptions.customBackoff || null;
    if (typeof customBackoff === 'function') {
      return customBackoff(retryCount, err);
    }
    var base = typeof retryDelayOptions.base === 'number' ? retryDelayOptions.base : 100;
    var jitter = Math.random();
    var delay = jitter * (Math.pow(2, retryCount) * base);
    console.log("base:", base, "\t", "jitter:", jitter, "\t", "retryCount:", retryCount, "\t", "delay:", delay);
    return delay;
  },

使用しているPCのインターネット接続を切ってsample.jsを実行するとAWSへのリクエストに失敗するため、リトライ処理の間隔を確認することができます。 sample.jsは自身のアカウントにS3のバケットを作成し適当なファイルをアップロードする、という内容です。

$ node sample.js
Create Bucket
base: 100        jitter: 0.9140613236915529      retryCount: 0   delay: 91.40613236915529
base: 100        jitter: 0.37410710386929624     retryCount: 1   delay: 74.82142077385924
base: 100        jitter: 0.794440804680022       retryCount: 2   delay: 317.7763218720088
Put Object
base: 100        jitter: 0.5885816821974228      retryCount: 0   delay: 58.85816821974228
base: 100        jitter: 0.7727058642141247      retryCount: 1   delay: 154.54117284282495
base: 100        jitter: 0.6923229555859327      retryCount: 2   delay: 276.92918223437306

一番右のdelayが実際のリトライ処理間隔の値です。徐々に長くなる、かつランダムな値になっています。 ジッターの値によっては前回のリトライ処理よりも間隔が短い場合があります。

まとめ

ドキュメントを読んでいて意味がよくわからない単語や概念が登場した際は、実際のコードを確認する・動かしてみるとより理解が深まるかと思います。 ぜひ他の言語のエクスポネンシャルバックオフがどのように実装されているか確認してみてください。