全力で怠けたい

怠けるために全力を尽くしたいブログ。

いまさら指数関数的バックオフを確認と最小限の実装をしてみたメモ。

指数関数的バックオフ (Exponential backoff) を確認と最小限の実装をしてみたメモ。

指数関数的バックオフ

指数関数的バックオフとは

指数関数的バックオフとは、プログラムやネットワーク機器がデータの送信処理に失敗したときに失敗回数に応じて再送信処理を実行するまでの待ち時間を指数関数的に増やす仕組みのことをいうらしい。 wikipediaExponential backoff ページを見ると CSMA/CA とか CSMA/CD は送信したデータの衝突を検出するとしばらく待ってからデータを再送信するけど、しばらく待つ時間は指数関数的に増やしていくみたいなのが書かれてる。そういえばそうだったなーみたいな感想だけどあらためて考えてみるとかなり古くから実装されているアルゴリズムなのだなと再認識した。

CSMA/CA とか CSMA/CD とかはデータの衝突を検出したらデータを再送信するのだけど、このときは再送信するときはできるだけデータが衝突するのを避けるために指数関数的バックオフのアルゴリズムを使っているようだ。

指数関数的バックオフを使うとき

プログラムとくにアプリケーションプログラムやツールとしてのプログラムはどんなときに指数関数的バックオフのアルゴリズムを使うとよさそうか。

プログラムとくにアプリケーションプログラムやツールとしてのプログラムはどんなときに指数関数的バックオフのアルゴリズムを使うのかを考えてみたけど、パッとイメージできるのは外部や内部のサービスの API を呼び出すときに指数関数的バックオフのアルゴリズムを使うとよさそう。プログラムが API サービスのクライアントとして API サービスにリクエストを送るとき、サーバーからのレスポンスのステータスコードは以下のいずれかに分類できる。

このうち 200 は送信したリクエストが成功しているのでリトライの必要はなくて 4xx はサーバーが「エラーになってるのはクライアントが原因」といってるので通常はリトライの必要はないというかリトライしてはいけないのだけど、サーバーが 429 を返してくるときはサーバーが「API のレートリミットに引っかかってるよ」といってるのでクライアントはリクエストの送信をリトライしたら成功する可能性がある。 あとサーバー5xx を返してくるときだけど、サーバーが 5xx を返してくるときはリクエストの送信をリトライするとリクエストが成功する可能性がある。 たとえばサーバーが 504 Gateway Timeout を返してくるときはサーバーのバックエンドタスクが過負荷に陥っていてリクエストがタイムアウトしているのを示しているので、クライアントはリクエストの送信をリトライしたら成功する可能性がある。

クライアントはサーバーが 429 とか 504 を返してくるときはリクエストの送信をリトライしたら成功する可能性があるけど、もし API のレートリミットに引っかかってサーバーが 429 を返してくるときはクライアントがすぐにリクエストを再送信してもまたレートリミットに引っかかる可能性が高い。 また、サーバーのバックエンドタスクが過負荷に陥っていてリクエストがタイムアウトしてサーバーが 504 を返してくるときは、クライアントがすぐにリクエストを再送信するとバックエンドタスクはまだ過負荷状態である可能性が高くて再送信したリクエストがまたタイムアウトになる可能性が高いし、バックエンドタスクが過負荷状態にあるときにすぐにリクエストを再送信するとさらにバックエンドタスクの負荷が高まってしまってバックエンドタスクがなかなか過負荷状態から抜け出せないかもしれない。 どちらのケースも単純に実装するなら「クライアントは十分な時間を待ってからリクエストを再送信する」でいいけど、十分な時間を待つというのはそれだけ待たされるということなので、できればそんなには待ちないのが望ましい……というときは指数関数的バックオフがいい感じにハマりそう。

クライアントはリクエストを送信 (再送信) してサーバーから 429 とか 504 が返されたら、すぐもしくは 少しだけ 待ってから1回目のリトライでリクエストを再送信する。たとえばもともとのリクエストに対して 429 が返ってきてたときは、1回目のリトライまでに API 呼び出しがレートリミットのしきい値を下回っててリクエストは1回目のリトライで成功するかもしれない。 指数関数的バックオフは、もし1回目のリトライが失敗したら 少しだけ x 少しだけ 待ってから2回目のリトライでリクエストを再送信するけど、もし2回目のリトライも失敗したら今度は 少しだけ x 少しだけ x 少しだけ 待ってから3回目のリトライをして、もし3回目のリトライも失敗したら今度は 少しだけ x 少しだけ x 少しだけ x 少しだけ 待ってから4回目のリトライをして……という感じにやっていく。

指数関数的バックオフの最小限の実装

Go で指数関数的バックオフの最小限の実装をしてみた。

実装コードを少しずつ見ていく。実装コードの全文は最後に記載しておく。

リトライをする処理はこんな感じのインタフェースを実装していく。

type Retryer interface {
    Process()
    ShouldRetry() bool
    MaxRetries() int
}

リトライはこんな感じに実装した。 backoff() 関数は Retryer インタフェースを実装した構造体を受け取ってリトライ回数に応じた待ち時間後に実際の処理 Retryer.Process() を呼び出して Retryer.ShouldRetry() == true ならまたリトライ回数に応じた待ち時間後に実際の処理 Retryer.Process() を呼び出して……という感じにやっていく。 あとリトライは Retryer.MaxRetries() 以下までやるようにループ処理している (最初の処理は0回目のリトライと解釈)

func backoff(r Retryer) {
    for i := 0; i <= r.MaxRetries(); i++ {
        waitTime := getWaitTimeExp(i, 100)
        fmt.Printf("waitTime: %d\n", waitTime)
        // wait ...

        r.Process()
        if r.ShouldRetry() == false {
            return
        }
    }
}

func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) {
    if retryCount == 0 {
        return 0
    }

    return int(math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds))
}

リトライをする処理はこんな感じで実装していく。 今回の関心事は指数関数的バックオフの実装なので実際にやる処理を実装する Process() は何もしないでおく。

type MyRetryer struct {
    maxRetry int
}

func (m *MyRetryer) Process() {
    // 関心事はリトライの実行間隔なので特に処理することはない
}

func (m *MyRetryer) ShouldRetry() bool {
    // いまの関心事はリトライの実行間隔なので必ずリトライするように
    return true
}

func (m *MyRetryer) MaxRetries() int {
    return m.maxRetry
}

実装するとこんな感じで待ち時間が指数関数的に増えていくのが確認できた。

waitTime: 0
waitTime: 200
waitTime: 400
waitTime: 800
waitTime: 1600
waitTime: 3200

実装コード全文

package main

import (
    "fmt"
    "math"
)

type Retryer interface {
    Process()
    ShouldRetry() bool
    MaxRetries() int
}

type MyRetryer struct {
    maxRetry int
}

func (m *MyRetryer) Process() {
    // いまの関心事はリトライの実行間隔なので特に処理することはない
}

func (m *MyRetryer) ShouldRetry() bool {
    // いまの関心事はリトライの実行間隔なので必ずリトライするように
    return true
}

func (m *MyRetryer) MaxRetries() int {
    return m.maxRetry
}

func main() {
    r := &MyRetryer{maxRetry: 5}
    backoff(r)
}

func backoff(r Retryer) {
    for i := 0; i <= r.MaxRetries(); i++ {
        waitTime := getWaitTimeExp(i, 100)
        fmt.Printf("waitTime: %d\n", waitTime)
        // wait ...

        r.Process()
        if r.ShouldRetry() == false {
            return
        }
    }
}

func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) {
    if retryCount == 0 {
        return 0
    }

    return int(math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds))
}

ジッター (ランダムな遅延時間)

指数関数的バックオフはだいたいジッターと呼ばれるランダムな遅延時間をサポートするようにしている。

ジッターはたとえば複数のクライアントが送信したリクエストに対してサーバーのバックエンドタスクが過負荷状態になっててサーバーが 504 を返しているとき、複数のクライアントすべてが同時にリクエストを再送信するとまたバックエンドタスクが過負荷状態に陥ってリクエストが失敗する可能性を低くするやり方のことらしい。

さっきのコードがジッターを実装するとこんな感じ。

 import (
        "fmt"
        "math"
+       "math/rand"
+       "time"
 )
        backoff(r)
 }

+func init() {
+     rand.Seed(time.Now().UnixNano())
+}
func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) {
    if retryCount == 0 {
        return 0
    }

+   jitter := rand.Float64()
+   return int(jitter * math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds))
}

ジッターを実装するとこんな感じで待ち時間がバラけるのが確認できた。

waitTime: 0
waitTime: 163
waitTime: 216
waitTime: 702
waitTime: 1242
waitTime: 1799

AWS のエラー試行と指数関数的バックオフ

自分は仕事で AWS を使ってて CLI とか SDK から AWSAPI を利用してるるけど、AWSSDK は指数関数的バックオフを実装してるので SDK を利用するユーザーは特に意識することなく指数関数的バックオフとリトライできるようになっている。

簡単な再試行に加えて、各 AWS SDK はエクスポネンシャルバックオフアルゴリズムを実装し、フロー制御を改善します

github.com

AWS SDK for Go の指数関数的バックオフの実装はこのへん。 自分で指数関数的バックオフの最小限の実装をしたあとに SDK for Go のソースコードを見てインタフェースの名前とかメソッドの名前は参考にさせてもらった。

// AfterRetryHandler performs final checks to determine if the request should
// be retried and how long to delay.
var AfterRetryHandler = request.NamedHandler{
    Name: "core.AfterRetryHandler",
    Fn: func(r *request.Request) {
        // If one of the other handlers already set the retry state
        // we don't want to override it based on the service's state
        if r.Retryable == nil || aws.BoolValue(r.Config.EnforceShouldRetryCheck) {
            r.Retryable = aws.Bool(r.ShouldRetry(r))
        }

        if r.WillRetry() {
            r.RetryDelay = r.RetryRules(r)

            if sleepFn := r.Config.SleepDelay; sleepFn != nil {
                // Support SleepDelay for backwards compatibility and testing
                sleepFn(r.RetryDelay)
            } else if err := aws.SleepWithContext(r.Context(), r.RetryDelay); err != nil {
                r.Error = awserr.New(request.CanceledErrorCode,
                    "request context canceled", err)
                r.Retryable = aws.Bool(false)
                return
            }

            // when the expired token exception occurs the credentials
            // need to be expired locally so that the next request to
            // get credentials will trigger a credentials refresh.
            if r.IsErrorExpired() {
                r.Config.Credentials.Expire()
            }

            r.RetryCount++
            r.Error = nil
        }
    }}

参考サイト