Exponential Backoff And JitterのUTを実装する

はじめに

ZOZOではAPI Gatewayを内製しています。API GatewayによるAPIリクエストのリトライ時には、Exponential Backoff And Jitterによる待ち時間を経た後にリトライする仕様となっています。

Exponential Backoff And Jitterとは

Exponential Backoff And Jitterとは、リトライ回数が増えるごとに待ち時間を指数関数的に増やし、かつランダム性も加えることで輻輳を防ぐための考えです。一定間隔での待ち時間を経たリトライに比べて、リクエストが詰まりにくくなるという利点があります。

Goでのコードは以下です。引数tryCountは、何回目のリクエストかを意味しています。0の場合は初回のリクエストです。引数baseIntervalは、基本となるインターバルです。引数maxIntervalは、最大のインターバルです。ベースインターバルを使って指数関数的に計算した結果が最大インターバルを上回る場合は最大インターバルを使用します。底は2に固定しています。

func SleepExponentialBackoffAndJitter(tryCount int, baseInterval time.Duration, maxInterval time.Duration) {
	interval := baseInterval * time.Duration(math.Pow(2, float64(tryCount)))
	if interval > maxInterval {
		interval = maxInterval
	}

	interval = time.Duration(mathRand.Float64() * float64(interval))
	time.Sleep(interval)
}

UTどうしよう

関数を実装した以上、UTも実装したくなるものです。しかし、これのUTって何を実装すればよいの？、と自分は少し手が止まってしまいました。

何をチェックするかを考える

今回のテスト対象の関数（SleepExponentialBackoffAndJitter）はreturnで何かを返す関数ではありません。では、何をチェックすれば良いのでしょうか。それは、「テスト対象関数の処理時間」と「期待するスリープ時間」の比較かと考えました。

テスト対象関数の処理時間

start := time.Now()
lib.SleepExponentialBackoffAndJitter(i, baseInterval, maxInterval)
sec := time.Since(start)

このような感じで、テスト対象関数を実行する前に現在時刻を取得し、テスト対象関数の実行完了後に time.Since 関数を実行することで、経過時間を取得することができます。

期待するスリープ時間

テスト対象関数内では、 ベースインターバル * 2^試行回数 を算出し、それが最大インターバルより大きければ最大インターバルを、そうでなければ算出結果に乱数を乗算した結果をインターバル（スリープ時間）としています。テスト関数側でもそれと同じ方法で計算します。
ただし、乱数によってインターバルの値が変動してしまうため、シードを1に固定しました。1に固定すると乱数値も固定できます。

// fix random for test
mathRand.Seed(1)

expectedInterval := baseInterval * time.Duration(math.Pow(2, float64(i)))
if expectedInterval > maxInterval {
	expectedInterval = maxInterval
}
// seedが1のrand.Float64()の1回目の呼び出し結果は0.6046602879796196
expectedInterval = time.Duration(0.6046602879796196 * float64(expectedInterval))

厳密にはチェックできない

計算結果はあくまでスリープだけの時間であり、当然ながら関数全体の処理時間ではありません。ある程度の誤差は必ず発生します。今回はざっくりと誤差を50msとして定めました。

if sec < expectedInterval || sec > expectedInterval+50*time.Millisecond {
	t.Fatalf("incorrect sleep duration")
}

stack overflowで調べてみると1.05倍を誤差として考えるアイディアもあります。今回は、後述する10回実行により、1.05倍に収まらなかったため、この方法は採用しませんでした。

最終形態

最終的に実装したUTは以下です。for分で10回実行しているのは、指数関数的に待ち時間が増える過程もテストするためです。

func TestSleepExponentialBackoffAndJitter(t *testing.T) {
	t.Run("normal", func(t *testing.T) {
		baseInterval := 1 * time.Millisecond
		maxInterval := 500 * time.Millisecond

		for i := 0; i < 10; i++ {
			// fix random for test
			mathRand.Seed(1)

			expectedInterval := baseInterval * time.Duration(math.Pow(2, float64(i)))
			if expectedInterval > maxInterval {
				expectedInterval = maxInterval
			}
			// seedが1のrand.Float64()の1回目の呼び出し結果は0.6046602879796196
			expectedInterval = time.Duration(0.6046602879796196 * float64(expectedInterval))

			start := time.Now()
			lib.SleepExponentialBackoffAndJitter(i, baseInterval, maxInterval)
			sec := time.Since(start)

			// 関数呼び出しや他処理のロスを考慮して+50msは許容とする
			if sec < expectedInterval || sec > expectedInterval+50*time.Millisecond {
				t.Fatalf("incorrect sleep duration")
			}
		}
	})
}