私の担当回では、AWSという巨大な分散システムを支える技術要素のうち、アーキテクチャ設計、プログラミング技術のいくつかについて見ていきたいと思います。これらは、AWSの内部を支える技術というだけでなく、皆さんのアプリケーションをダウンタイムゼロのシステムに近づけるための基礎技術、クラウド・ネイティヴなアプリケーションを構築する基礎的なテクニックとも言えると思います。
その基礎的なテクニックは大きく、下記の4つがあります。
- 非同期処理（Asynchronous process）
- リトライ（Retry with Exponential Backoff and jitter）
- 結果整合性（Eventual Consistency）
- 冪（べき）等性（Idempotency）
本記事では、リトライ（Retry with Exponential Backoff and jitter）についてご紹介します。
多数のコンポーネントから構成される大規模分散システムでは、常にどこかで部分障害が発生しています。エンドユーザー向けにダウンタイムの無い安定したサービスを提供するために、リトライのテクニックは大変重要な技術となっています。
リトライとは、文字通り、リクエストを「再試行する」テクニックなのですが、いつ、どのようにリトライを行えばいいのでしょうか。シンプルながら奥深いテーマについて見て参りましょう。
リトライ ～ 一時的な障害に強いシステムにするために
耐障害性を向上させるため、さまざまな箇所を冗長化したシステムを構築したとします。下図のようにAWSのアベイラビリティゾーン（AZ：Availability Zone）間でWeb APIサーバ群を分散配置させてみます。
例えば、1台のWeb APIサーバがダウンしてしまったとします。一方、Elastic Load Balancing（ELB）を経由したリクエストは、既にそのサーバ宛に送信されていたとします。
この場合、サーバはダウンしていますので、ELBは、バックエンドのサーバーから応答を得られず、Timeout時間分レスポンスを待った後、500番台のHTTPステータスエラーコードを付けてクライアント側にレスポンスを返すことになるでしょう。
このとき、レスポンスを受け取ったクライアント側アプリケーションは、この状況をどう処理すべきでしょうか。
ひとつのアイデアとして、クライアント側アプリケーションは、エンドユーザーに対してエラーが発生したことを通知してもよいと思います。
しかし、このシチュエーションでは、クライアントアプリケーション側でリクエストの送信をリトライしてもよいでしょう。この場合、次のリクエストはELBにより正常稼働中の別のサーバーに振り分けられ、正常に処理を完了できます。
このように、リトライによってエンドユーザーを煩わせることなく、処理を継続できる場合があります。
どのようにリトライすればよいか
このリトライのアルゴリズムについて、システムの規模が小さい場合は、シンプルに「5秒ごと」などの固定値で実装してもよいかもしれません。
しかし、システムの規模が大きくなり、万が一のAZレベル障害も考慮しなくてはいけなくなった場合を想定した場合には、取るべき最適な方法が異なります。この場合は、多くのサーバが停止していることになるので、多数のクライアントからのリクエストがエラーになり、結果的に多数のリトライが再度別のサーバに対して送信されることになるでしょう。
このとき、クライアント側で「5秒ごと」などの固定値でリトライ処理を実装していたとしますと、当然ながら、全クライアントが5秒ごとに同じタイミングでリトライ処理を実施することになります。Web APIサーバ側からみると、5秒ごとに多数のリクエストを集中的に受けることになり、DoS攻撃にも似た過剰な負荷がかかることになります。
では、どのような間隔でリトライを行えば、システム全体としてもっとも効率的なのでしょうか。
エクスポネンシャル・バックオフ・アンド・ジッター
この問題を解決する手法として、「エクスポネンシャル・バックオフ・アンド・ジッター（Exponential backoff and jitter）」というリトライのアルゴリズムがあります。これは、エクスポネンシャル・バックオフとジッターという2つのアルゴリズムを合わせたものです。
エクスポネンシャル・バックオフは、リクエスト処理が失敗した後のリトライの際、現実的に成功しそうな程度のリトライを、許容可能な範囲で徐々に減らしつつ継続するアルゴリズムです。具体的には、再試行する度に、1秒後、2秒後、4秒後と指数関数的に待ち時間を加えていきます。これにより、全体のリトライ回数を抑え効率的なリトライを実現します。
ジッターとは、random関数を用いたジッター（ゆらぎ）を導入することを指しています。これによりリクエスト間のタイミングの衝突を回避する効果があります。
AWS Solution Architectブログの記事「Exponential Backoff And Jitter」にて、詳細な検証結果がまとめられています。本稿では、さらに補足を加えつつ平易に説明を試みたいと思います。
シンプルなリトライ処理
この検証では、問題をシンプルにするために、サーバ側は「ある一時点において1リクエストしか処理を受け付けられない」という仮定でシミュレーションを行なっています。
最初のアルゴリズムはシンプルなリトライ処理（Backoff Algorithm none）です。これは、「失敗したらすぐにリクエストを送信する」というループ処理を、処理が成功するまで延々と続けるというものです。
グラフが2種類あります。横軸はクライアント数の増加を表しています。一つ目のグラフの縦軸はリクエスト完了までの時間、二つ目のグラフの縦軸はすべてのリクエスト処理が完了するまでに送信されたリクエスト数をそれぞれ表しています。
このシンプルなリトライ処理（Backoff Algorithm none）では、全てのリクエストが完了するまでの時間は線形に増加し、全体のリクエスト数は指数関数的に増加していることがお分かりいただけるかと思います。
