Exponential Backoff とは何か

Exponential Backoff という言葉を最近覚えたので、まとめておきます。

これはなにか

ネットワークを通してサーバーと通信失敗時にリトライ間隔をクライアント側で調節する手法です。 Exponential という名前の通り、リトライするときに失敗回数に応じて待ち時間を指数関数的に増やします。 1, 2, 4, 8秒・・・みたいな感じでどんどん次のリクエストを送るまでの時間が伸びていくわけですね。

ロードバランサを経由したリクエストを受けたけど、その先のWeb APIサーバーがダウンしてしまっている。。。みたいなときに有効です。

AWSの橋本さんの記事 にも実例が書かれています。

ジッターはリクエストの集中を防ぐ

システム内にクライアントが複数ある場合は、このまま特定のタイミングにリクエストが集中してしまう可能性があります。 そこで、ランダムに少しだけ時刻をずらすジッター（ゆらぎ）を加えることでリクエストの集中を防ぐのが定石です。

アルゴリズム例

Google Cloud Storage の Truncate Exponential backoff を参考に説明すると、

  1. リクエストを送る
  2. 失敗したら、1秒 + ジッター秒分だけずらす
  3. 失敗したら、2秒 + ジッター秒分だけずらす
  4. 失敗したら、4秒 + ジッター秒分だけずらす
  5. 待ち時間の上限を超えるまで増やし続ける
  6. リトライ上限回数を超えるまでリトライする（※ただし、待ち時間はこれ以上増やさない）

という風になります。

実装例

Go

Go も色々な実装があります。shogo82148さんのgo-retryはcontextがサポートされており、Goっぽい実装です。

package main

import (
    "context"
    "errors"
    "fmt"
    "time"

    "github.com/shogo82148/go-retry"
)

type Result int

func DoSomething(ctx context.Context) (Result, error) {
    // do something here that should to do exponential backoff https://en.wikipedia.org/wiki/Exponential_backoff
    return 0, errors.New("fails")
}

var policy = retry.Policy{
    MinDelay: 100 * time.Millisecond,
    MaxDelay: time.Second,
    MaxCount: 10,
}

func DoSomethingWithRetry(ctx context.Context) (Result, error) {
    retrier := policy.Start(ctx)
    for retrier.Continue() {
        if res, err := DoSomething(ctx); err == nil {
            return res, nil
        }
    }
    return 0, errors.New("tried very hard, but no luck")
}

func main() {
    fmt.Println(DoSomethingWithRetry(context.Background()))
}

Python

invlさんのretryはPython実装でデコレーターを使うAPIになっていて、Pythonicな実装だなーと思いました。

@retry()
def make_trouble():
    '''Retry until succeed''

参考