HTTP2 のフロー制御

この記事は HTTP2 Advent Calendar の 1 日目の記事です。

初回は、執筆時点での最新ドラフトである HTTP2-draft16 のフロー制御(Flow Control) について解説します。

余談ですが, 現在の仕様では "HTTP2.0" ではなく "HTTP/2" もしくは "HTTP2" が正しい名称です.

更新

@kazu_yamamoto さんに指摘頂いた点を反映しました。
@kiri__n さんに指摘頂いた点を反映しました。

詳細については更新履歴をご覧下さい。

フロー制御

HTTP2 では、同じホストへの複数のリクエストを、同一の TCP コネクション上にストリームという単位で多重化することができるようになりました。
フロー制御とは、例えばひとつのストリームがリソースを占有してしまうことで、他のストリームがブロックしてしまうことを防ぐ、といった目的で行われます。

具体的な状況はいくつか考えられます。

大きなファイルの通信が帯域を食いつぶし、他の通信を妨害する。
あるリクエストの処理にサーバがかかりっきりになり、他のリクエストをサーバが処理してくれなくなる。
高速なアップロードを行うクライアントと、低速な書き込みをしているサーバとの間に挟まったプロキシが、調整のためにデータを貯めているバッファが溢れる。

こうした状況を防ぐために、 HTTP2 ではコネクション(実態は TCP 接続)と、その上に多重化されたストリーム(これが HTTP/1.1 のリクエスト・レスポンス相当) 両者について、フロー制御を実施する仕組みを備えています。

実際には Window Size というしきい値を設定し、この値の範囲内であればデータを送ることができ、その値を使い切った場合、送信者はデータの送信を停止します。
受信者は、リソースが回復したことを WINDOW_UPDATE というフレームで通知し、そこに設定された分の値だけ Window Size を回復されることで、送信者はデータの送信を再会できるというものです。

先ほどのプロキシのようなケースに対応するため、フロー制御はホップ間で行われ、フロー制御をオフにすることはできません。
また、 Window Size を消費するのは DATA Frame だけであり、他のフレームが受信されないことによりコントロールを失うことを防ぎます。

なによりも、フローコントロールは「仕組み」だけが仕様にあり、実際どのようなアルゴリズムを適用するかは、実装者にゆだねられている点が特徴です。
そのため、時代や用途や制限に合わせて適切なストラテジを自分で考える必要があります。

ここでは、「仕組み」の方だけ解説します。

フロー制御の方法

実際の、フロー制御には SETTINGS FRAME と WINDOW_UPDATE FRAME の二つを使用します。
まずは、二つのそれぞれの意味を簡単に解説しますが、正しい使い方は以降で解説します。

SETTINGS FRAME (Initial Window Size)

SETTINGS FRAME にはストリームレベルの Window Size の初期値である SETTINGS_INITIAL_WINDOW_SIZE を含めることができます。
含めない場合は、デフォルト値として 2^16-1 (64KB-1) byte になり、最大値は 2^31-1 (2G-1) です。

SETTINGS FRAME によって、「初期値を後から変更」することもできます。ここがややこしいところです。

ちょっと面倒なので以下では Initial Window Size のデフォルト値は +1 した 64KB (65,536) として表記します。

WINDOW_UPDATE FRAME

WINDOW_UPDATE FRAME には、指定した ID のストリーム、もしくはコネクション自体で、消費された Window Size の回復を通知します。
自分は Initial Window Size を超える WINDOW_UPDATE を送ってはいけないと勘違いしていましたが、上限は Initial Window Size ではないので、 Window Size の最大値 2G まで送ることが可能です。

フロー制御の概念

まず HTTP2 の正確な挙動はおいておいて、概念的な部分を解説します。

たとえば、二つのマシンが接続しており、 Alice が Bob にファイルを転送するというシチュエーションで、 Bob の処理能力をもとにフロー制御を考えてみます。

接続時に Bob は Alice に SETTINGS FRAME で「Window Size の初期値は 100K で頼む」と送っていたとします。
ファイルを送信するために、両者のあいだに確立されたストリームにおいて、 Bob の Initial Window Size は 100K ということになります。

Alice が 10K のファイルを Bob に送る場合は、 Window Size より小さいため一気に送って問題ありません。

Alice ---------------- 10K --------------> Bob(90K)

ただし、 Alice が 300K のファイルを Bob に送る場合は注意が必要です。
Window Size は 100K に決まっているので、 Alice はファイルのうち 100/300K を送った時点で、送信を一旦止める必要があります。

Alice --------------- 100K --------------> Bob(0K)
//////////////////// block ///////////////////

止めたのは良いですが、再開はいつでしょう？

Bob がすでに受け取ったデータを処理して、さらに追加のデータの受信ができるようになったら、 WINDOW_UPDATE で、 Window Size の回復を Alice に通知します。
Bob が WINDOW_UPDATE で更新した Window サイズに収まる範囲で、 Alice はデータを送り続けます。

Alice --------------- 100K --------------> Bob(0K)
//////////////////// block ///////////////////

Alice <-------- WINDOW_UPDATE 80K -------- Bob(80K)
Alice ---------------- 80K --------------> Bob(0K)
//////////////////// block ///////////////////

Alice <-------- WINDOW_UPDATE 100K ------- Bob(100K)
Alice ---------------- 100K -------------> Bob(0K)
//////////////////// block ///////////////////

Alice <-------- WINDOW_UPDATE 50K -------- Bob(50K)
Alice ---------------- 20K --------------> Bob(30K)

こうして Bob は Alice からの膨大なサイズのデータに押しつぶされること無く、きちんとデータが処理できる訳です。

ここでは、 Bob の処理能力に注目したフローで解説しましたが、実際にはプロキシのバッファや帯域など、多くの要因をもとに制御する必要があるため、この解説はあくまでも一例だと考えてください。

コネクションレベルとストリームレベル

フロー制御はコネクションレベルのものと、ストリームレベルのものがあります。
なぜなら HTTP2 では、ひとつのコネクション(これは TCP レベルのコネクションと同義)の上に、論理的なストリームが多重化されているためです。

先ほどの例はストリームレベルのものでした。
ここでは実際の HTTP2 により近づけるため、 Alice と Bob の例にコネクションの概念を入れて解説します。

Alice は Bob に同じコネクション上で、二つのファイルを送信することを考えます。

file1 (50K)
file2 (40K)

ストリームには ID がつきます。クライアント(Alice) から開始したストリーム ID は奇数であり、コネクションは ID が 0 のストリームのように扱われます。コネクション自体の Initial Window Size 64K 固定です。

                connection
Alice ---------------------------->  Bob(64K)

コネクションが確立したら最初に SETTINGS Frame を交換します、ここで Initial Window Size を 80K で合意したとします。その値は、その後生成される二つのストリームの Window Size の初期値として使われます。

                connection
Alice ---------------------------->  Bob(64K)
      <- SETTINGS Frame (ini=80K)--
      <---------- ACK -------------

  file1 ------------------------> stream1(80K)
  file2 ------------------------> stream2(80K)

ストリームでデータが送信されると、ストリームの Window Size とともに、コネクションの Window Size も消費されます。

では、初期状態で Stream1 が一気に 50K のファイルを送ったとしましょう。
送り終わった時点で、以下の状態になります。

Alice                               Bob(14K)
  file1 --------- 50K ----------> stream1(30K)
  file2                           stream2(80K)

ストリーム上をデータが流れた場合、ストリーム(id=1) 上の Window が消費されるとともに、同じ分だけコネクションの Window も消費されます。

では、stream2 で file2 を送ってみましょう。

Alice                               Bob(0K)
  file1                           stream1(30K)
  file2 --------- 14K ----------> stream1(66K)

ストリームレベルでの Window Size は十分ありますが、コネクションレベルの Window Size は 14K しか残っていなかったため、ファイル全体を送ることはできませんでした。

この場合は、 Bob からコネクションレベル (id=0) の WINDOW_UPDATE を受け取るまでブロックします。

Alice                                   Bob(0K)
  ////////////// block //////////////////////

Alice                                   Bob(50K)
  <-------- WINDOW_UPDATE(id=0) 50K ---------

Alice                                   Bob(34K)
  file2 --------- 16K ----------> stream1(50K)

無事全て送信できました。

id=0 の WINDOW_UPDATE はコネクションレベルの Window Size を回復します。
実際のデータは、ストリームレベル、コネクションレベル両方の Window Size の範囲内で送られるということです。

コネクションの Initial Window Size

前述のように SETTINGS Frame に含める Initial Window Size が変更できるのは、あくまでもストリームレベルの Initial Window Size だけです。
コネクションレベルの Initial Window Size は 64K のままで、これは SETTINGS Frame では変えられません。

しかし、先のような例で、最初からコネクションの Window Size を大きくしておきたい場合もあるでしょう。その場合 WINDOW_UPDATE で大きな値を送っておけば良いです。
WINDOW_UPDATE は最大値 2G までであれば、別に Initial Window Size を超える値まで Update しても問題ありません。

例えば、コネクションが確立してすぐに WINDOW_UPDATE で 100K を送れば、コネクションの Window Size を 164K にできます。

                connection
Alice ---------------------------->  Bob(164K)
  <------- WINDOW_UPDATE(id=0) 100K ----------

途中での SETTINGS FRAME

さて、 SETTINGS FRAME はいつでも好きなタイミングで送ることができます。

では、 Initial Window Size を途中で変えるとどうなるでしょう。
例えば以下のようなシチュエーションのストリームを考えてみます。

Initial Window Size が 20K で始まったストリーム
8K のデータを送信した
3K WINDOW_UPDATE を返した
4K のデータを送信した
その後 Initial Window Size を 30K に変更

Initial Window Size を送る直前は、8K - 3K + 4K = 9K 送ったことになるため
ストリームの Window Size は 11K になっているはずです。

// initial 20K
Alice ---------------- 9K --------------> Bob(11K)

この状態で Initial Window Size を 30K に変更するということは、初期値が 30K の状態でデータの送受信が始まった「ことにする」というような挙動になります。

つまり、この場合は 30K で始まって 9K 送ったことにするので、以下の状態になります。

// initial 30K
Alice ---------------- 9K --------------> Bob(21K)

計算式は以下のようになります。

"New Window Size" = "New Initial Window Size" - ("Current Initial Window Size" - "Current Window Size")

現在の Initial Window Size から、現在の Window Size を引くことで、そこまでに消費された Window Size を出し、新しい Initial Window サイズから始まって、その分が消費されたことにするわけです。

これは、データの更新がロックを取らず、並行してデータもガンガン送ることができるため、レースコンディションでの振る舞いを規定するために「後から初期値を変更する」という方針を取る必要があるためこうなっています。
これを全てのストリームについて計算してやる必要があります。

Window Size がマイナスになるケース

これをふまえて以下のケースを考えます。

Initial Window Size が 64K で始まったストリーム
60K のデータを送信した
その後 Initial Window Size を 16K に変更

Initial Window Size を変更する直前は、 Window Size が 4K です。

// initial 64K
Alice ---------------- 60K --------------> Bob(4K)

ここで Initial Window Size 更新し、先ほどの式に当てはめてみます。

Window Size = 16 - (64 - 4) = -44

マイナスになってしまいましたね。

// initial 16K
Alice ---------------- 60K --------------> Bob(-44K)

本来データを送っているだけでは、 Window Size が枯渇した時点で送信がブロックするのですが、 Settings Frame によって途中で初期値が変更されることにより、 Window Size がマイナスになる可能性があるのです。
この場合、 44K 以上 WINDOW_UPDATE を返して、 Window Size がプラスになるまでは、送信はブロックします。

ドラフト14 での、 "6.9.2. Initial Flow Control Window Size" の後半に書かれている例は、この挙動を説明しています。

For example, if the client sends 60KB immediately on connection
establishment, and the server sets the initial window size to be
16KB, the client will recalculate the available flow control window
to be -44KB on receipt of the SETTINGS frame.

まとめ

特に Initial Window Size の扱いがよくわかってなかった頃は、 nghttp2 の -w -W オプションで挙動を試したり、 @tatsuhiro_t さんに教えてもらいながら理解できました。ありがとうございます。

本来より低レベルなプロトコルで行われるような機能に思えますが、単一のコネクションが多くのストリームを多重化する HTTP2 のモデルならではの仕様と言えます。
実装も、特にコネクションレベルの止める方がちょっと面倒だったりして、自分の実装ではストリームレベルしかまだやっていませんが、いずれはちゃんとコネクションレベルも実装したいと思います。

もし間違い等ありましたら、遠慮なくコメントください。