Exponential Backoff And Jitter

こんにちは。ソリューションアーキテクトの今井です。今日はAWSのPrincipal Software EngineerであるMarc BrookerのExponential Backoff And Jitterというブログポストを翻訳しました。リクエスト密度の高いシステムのクライアントを設計するうえでExponential Backoffは非常に重要な概念です。とても参考になる内容なので、ぜひお読み下さい！

 

OCC(Optimistic concurrency control)の導入

 

Optimistic concurrency control(楽観的並行性制御、以下OCC)は複数のリクエスターによる単一オブジェクトに対しての書き込みを安全に行うための時間ベースの手法です。OCCには3つの利点があります。

1. ストレージレイヤが問題なく動いている限りにおいて、必ず正しく動作する
2. 理解の容易さ
3. 実装の容易さ 

DynamoDBMapperに実装されているconditional writeはDynamoDBユーザーにとってOCCを非常に身近なものにしてくれています。

 

しかし、OCCは解決されるべき課題も持っています。それは、リクエストの多重度が高くなってくるとパフォーマンス劣化です。例えばとてもたくさんのクライアントが、データベースのある特定の行に対して同時に更新リクエストを送り始めるようなケースではそれが顕著になります。それぞれのクライアントのリクエストをひとつずつ処理していくことになりますので、処理の所要時間は多重度に比例して増大していきます。

 

ここから紹介していくグラフは、ばらつきのある遅延をもったネットワーク上で動作するOCCの挙動をモデル化した簡単なシミュレータを使って、リモートホストにあるデータベースへのリクエストの一連のテスト結果から生成されています。なお今回は平均遅延を10ms、ばらつき4msというネットワーク設定をしています。

 

最初のグラフは多重度と処理の所要時間が比例していることを表しています。これは一度のひとつのリクエストしか処理がされないので、N個のリクエストを処理するにはN回の処理が必要だからです。

また、クライアントからのリクエスト数(Work)はクライアントの個数であるNの二乗に比例します。

 

Backoff(リトライ遅延)を導入してみる

 

これでは「1回めの試行ではN個のクライアントが競合状態を起こす（そしてのそのうち1つだけが成功する）、次の試行ではN-1個のクライアントが競合状態を起こす、更に次の試行ではN-2個の・・・」という状態になってしまっており、毎回の試行で多くのクライアントのリソースが無駄に利用されています。この状態を改善する方法として個々のクライアントのリトライ速度を落としてやるというアイデアがあり、古くから知られているアルゴリズムとして制限付きExponential Backkoffというものがあります。最初のリトライ時にt、次のリトライ時に2t、更にその次のリトライ時に3t、といった形で、リトライ回数と何らかの相関を持った値の遅延を挟んでやります。制限付きというのは、最大値としてTを予め定めておくことによる、ある一定回数以上のリトライ時は毎回遅延Tを挟むということになります。擬似コードにすると以下のようになるでしょう。

 

sleep = min(cap, base * 2 ** attempt)

 

この手法を取り込んで先ほどと同じテストを走らせてみると、若干の改善は見られますが、依然としてクライアントの仕事量には問題が残ります。

問題をより明確にするにはどのようなタイミングでリトライが発生しているのかを可視化してみるのがよいでしょう。

確かに制限付きexponential backoffは働いていて、リトライの頻度が減っていることが見て取れます。しかしここで新たに「リトライのタイミングが塊になってしまっている」という問題が浮上してきました。試行時の競合するクライアント数を減らすかわりに、リクエストが全く無い時間帯というものを発生させてしまうことになりました。ネットワークの遅延のばらつきによって若干の分散は発生していますが、これではまだ競合問題の解決には程遠いと言えるでしょう。

 

Jitter（ばらつき）を導入してみる

 

解決方法はBackoffをやめることではありません。Jitterの導入です。これまでのテストはJitterが非常にうまく問題を解決してくれるいい例となるでしょう。ランダム性を導入することによって、スパイクが目立つ上のグラフを、できるだけなだらかなものに変えていきたいと思います。Jitterの導入は簡単です。

 

sleep = random_between(0 min(cap, base * 2 ** attempt))

 

いかがでしょうか。だいぶいいグラフになってきたと思います。初期のスパイク以外はだいたい一定のレートでリトライが行われるようになりました。もちろん総リトライ回数にもおおきく改善が見られます。

多重度100という条件下においては、リトライ回数を半分以下にすることに成功しています。また、処理の総所要時間にも改善が見られます。

時間ベースのBackoffにはいくかのよく知られた実装方法があります。これまで紹介してきたアルゴリズムをFull Jitterと呼ぶことにして、ここから更に2つの方法を紹介していきます。1つ目はEqual Jitterと呼ばれるアルゴリズムで、backoffとjitterをできるだけ小さくたもつように動作します。

 

temp = min(cap, base * 2 ** attempt)

sleep = temp / 2 + random_between(0, temp / 2)

 

この方式では、非常に短いsleepを避けつつ、常にbackoffをある一定の範囲にたもつように働きます。そして最後に紹介するのはDecorrlated(無相関) Jitterと呼ばれるもので、Full Jitterと考え方は近いのですが、前回計算されたsleepの値を使ってjitterの最大値を増加させるところが違います。

 

sleep = min(cap, random_between(base, sleep * 3))

 

さて、あなたはどの方法がベストだと思いますか？

 

クライアントの仕事量に注目すると、Full JitterとEqual Jitterがほぼ等しく優秀な結果を記録しています。Decorrelated Jitterは若干見劣りしますが、それでもJitter無しのアプローチと比べると非常に大きく効果をあげています。

ご覧のようにJitter無しのExponential Backoffは完全に負け組ですね。クライアントの仕事量を増やしてしまうばかりか、処理の総所要時間にも大きくマイナスの影響を及ぼします。というところで所要時間も比較してみましょう。（Jitter無しのパターンは時間がかかりすぎるので除外しています）

Jitter有りのアプローチの中ではEqual Jitterが最も悪い成績を残しています。Equal JitterはFull Jitterよりも仕事の削減量が若干劣り、所要時間への影響においては大きく劣る、ということになります。Decorelated JitterとFull Jitterの比較はもう少し難しくなります。Full Jitterのほうが仕事量の削減という意味では優秀ですが、所要時間の面では若干劣ります。しかし、どちらのアルゴリズムもクライアント、サーバーの負荷を大きく減らしてくれることには変わりがありません。

 

今回紹介してきたアルゴリズムはいずれも、並列度に相関してN^2で増加するクライアント、サーバーの負荷曲線を大きく改善してくれることには疑問の余地がないでしょう。Jitter付きbackoffの実装への投資に対するリターンは非常に大きなものが期待できることは明白であり、リモートクライアントを持つシステムにおいての導入は当然と考えてよいと思います。

 

最後に、今回の一連のOCC挙動のシミュレータはGithub上にて、aws-archi-backoff-simulatorとして公開されています。

 

- Marc Brooker