AWSユーザーは必ず覚えておきたいExponential Backoffアルゴリズムとは何か

cloudpackエバンジェリストの吉田真吾（@yoshidashingo）です。

Exponential Backoff

直訳すると「指数関数的後退」つまり、指数関数的に処理のリトライ間隔を後退させるアルゴリズムのことです。

詳しくはWikipediaに記載があります。

• Exponential backoff - Wikipedia

日本語でブログに書かれている方もいらっしゃいます。

• exponential backoffのメモ – Siguniang's Blog

これを見ていると、どうやらこのアルゴリズムは古くから通信装置において、イーサネットフレームのデータ送信時にコリジョン（衝突）を検出したら一定時間待機して再送して、処理を完結させるためのアルゴリズムとして使われているようです。

通信機器の世界に限らず、アプリケーションの分野でも、大規模で予測不能な処理量を有限なリソースでさばく場合に、一時的にリソースを超過したリクエストが来ても特定のスロットリング機構なしでリクエストが最終的にさばけるという点で優れていると思います。

• リクエストを滞留させる必要がない：滞留しておくためのリソースが要らない
• スロットリング機構が要らない：これ自体のためのリソースが要らない

当然、ソフトウェアの設計上、上記のような仕組み自体を否定するものでもありませんので、要件に合わせ、たとえば、一定数のリクエストまではキューに滞留させ、上限を超えたらNO WAITでエラーを返し、リクエスト元からExponential backoffでリトライさせる、などの組み合わせで実装をするといいと思います。

• ちまたにいろんな実装方法が示されているようです。

実際使うかどうかは別として Retries with Exponential Backoff はこういう感じで抽象化する、という例 / “ooyala/retries · GitHub” http://t.co/H9eF9fTnpQ

— Naoya Ito (@naoya_ito) 2013年11月11日

AWSでもアプリケーションの基本的な実装として推奨されてる

AWSのソフトウェア開発エンジニアである橋本さんという方のスライドを見つけましたが、こちらにもExponential backoffについての記載がされています。

• 大規模分散システム ”Amazon Web Services”の使い方(PDF)

2. Retries with Exponential Backoff

• Exponential Backoff
  • リトライ䛾間隔を指数関数的に増加させる
    • 例：１秒後、２秒後、４秒後、８秒後、、、
  • 長期障害発生時にシステムへの不必要な負担を軽減
• 大規模分散システム内では常に部分障害（特に一時的）が発生している
  • 障害発生時にいちいちシステムを止めていては高可用性を実現できない
• リトライにより後に成功する可能性が高い

部分的で一時的な障害のためにサービスを止めたり、サービスに介入するオペレーションをせず、リソースの再配置などサービス側のオペレーションが完了したら、ユーザー側からのリクエストがほどなく再送されてきて処理が完結するという、サービスの可用性を考慮した流れですね。

AWSのGeneral Referenceという基本概要のAPI Retriesという章には、AWS上のアプリケーションのリトライ実装として以下のように推奨されています。

• Error retries and exponential backoff in AWS - AWS General Reference

AWSにおけるエラーのリトライとエクスポネンシャルバックオフについて

DNSサーバーやスイッチ、ロードバランサーやその他のさまざまなネットワークコンポーネントはリクエストを処理するいずれかにおいてエラーを生成することがありえます。ネットワーク化された環境においてこれらのエラーに対処するためのよくあるテクニックは、クライアントアプリケーション側にリトライ処理を実装することです。このテクニックによりアプリケーションの信頼性が向上し、運用コストを削減することができます。

各AWS SDKには自動リトライ処理が実装されています。AWS SDK for Javaでは、ClientConfigurationクラスを用いることで、この自動リトライの設定を行うことが可能になっています。たとえば、最小限のレイテンシとリトライなしで作成したいWebページがあるという場合には、リトライロジックをオフにすることもできます。その場合はClientConfigurationクラスを使用して、maxErrorRetry値を0にすることでリトライをオフにできます。

もしAWS SDKを使用していない場合は、サーバーエラー(5xx)やスロットリングエラーを受け取ったら同一のリクエストを再送するようにしてください。ただし、クライアントエラー(4xx)の場合はリトライする前にリクエスト内容自体を修正する必要があります。

単純なリトライに加えて、よりよいフロー制御のために、Exponential Backoffアルゴリズムを使用することをおすすめします。Exponential Backoffの考え方は、連続したエラーに対して、次第にリトライ間隔を長くするというものです。最大遅延間隔に加えて、最大リトライ回数も実装するとよいでしょう。最大遅延間隔も最大リトライ回数も固定値で設定する必要はなく、オペレーションの内容やネットワークのレイテンシなどの個別の要素を考慮したうえで設定されるべきです。

たいていのExponential Backoffアルゴリズムは、連続したコリジョン(衝突)を避けるため、乱数によってタイミングをずらす実装がされていますが、ここではコリジョンを避ける必要があるわけではないので、乱数の実装は不要です。

以下のサンプルコードは遅延を増加させて状態をポーリングする方法を示しています。

Do some asynchronous operation.

retries = 0

DO
    wait for (2^retries * 100) milliseconds

    status = Get the result of the asynchronous operation.

    IF status = SUCCESS
        retry = false
    ELSE IF status = NOT_READY
        retry = true
    ELSE IF status = THROTTLED
        retry = true
    ELSE
        Some other error occurred, so stop calling the API.
        retry = false
    END IF

    retries = retries + 1

WHILE (retry AND (retries < MAX_RETRIES))

次のコードは、Javaでこの遅延を増加させる実装をしている例です。

public enum Results {
    SUCCESS, 
    NOT_READY, 
    THROTTLED, 
    SERVER_ERROR
}

/*
 * Performs an asynchronous operation, then polls for the result of the
 * operation using an incremental delay.
 */
public static void doOperationAndWaitForResult() {

    try {
        // Do some asynchronous operation.
        long token = asyncOperation();

        int retries = 0;
        boolean retry = false;

        do {
            long waitTime = Math.min(getWaitTimeExp(retries), MAX_WAIT_INTERVAL);

            System.out.print(waitTime + "\n");

            // Wait for the result.
            Thread.sleep(waitTime);

            // Get the result of the asynchronous operation.
            Results result = getAsyncOperationResult(token);

            if (Results.SUCCESS == result) {
                retry = false;
            } else if (Results.NOT_READY == result) {
                retry = true;
            } else if (Results.THROTTLED == result) {
                retry = true;
            } else if (Results.SERVER_ERROR == result) {
                retry = true;
            }
            else {
                // Some other error occurred, so stop calling the API.
                retry = false;
            }

        } while (retry && (retries++ < MAX_RETRIES));
    }

    catch (Exception ex) {
    }
}

/*
 * Returns the next wait interval, in milliseconds, using an exponential
 * backoff algorithm.
 */
public static long getWaitTimeExp(int retryCount) {

    long waitTime = ((long) Math.pow(2, retryCount) * 100L);

    return waitTime;
}

可用性を高め、運用コストを削減するアプローチとして、覚えておきましょう。