HTTP/2 多重化

実装: network/http2/ / 実行: go test ./network/http2/

HTTP/1.1は1本の接続で一度に1つの応答しか返せない。大きな応答が詰まると、後ろに並んだ小さな応答は前が終わるまで待たされる。ヘッドオブラインブロッキングだ。HTTP/2は1本の接続に複数ストリームを作り、各応答をフレームに刻んで交互に流す。大きな応答の合間に小さな応答を差し込めるので先に完了できる。多重化とHPACKヘッダ圧縮を実装し、HoLブロッキングが解ける様子を確かめる。

この章で作るもの

HTTPサーバで 1 往復のリクエスト・レスポンスを作った。だが実際の Web ページは、1 ページを表示するのに数十から数百のリソース(HTML、CSS、JS、画像)を取りに行く。HTTP/1.1 の弱点はここで出る。1 本の TCP 接続では、一度に 1 つの要求しか処理できない。応答は要求した順に、1 つずつ返ってくる。大きな応答(重い JS ファイルなど)が 1 つ詰まると、その後ろに並んだ小さな応答は、前が終わるまで送り出されない。これがヘッドオブラインブロッキング(HoL)だ。

ブラウザはこれを、接続を 6 本ほど並べて張ることで誤魔化してきた。だが接続を増やすとサーバの負荷も、TCP の確立コストもかさむ。根本解決ではない。HTTP/2 は発想を変える。1 本の接続の上に、複数のストリーム(独立した要求・応答の流れ)を作る。各応答をフレームという小片に刻み、複数ストリームのフレームを 1 本の接続に交互に流す(多重化)。大きな応答を送っている合間に、小さな応答のフレームを差し込める。だから小さな要求が大きな要求を追い越して先に完了できる。あわせて、毎回ほぼ同じヘッダを送る無駄を HPACK で省く。

HTTP/1.1(直列)   [===== 大 =====][小][小]        小は最後まで待つ
                                    ↑11    ↑12

HTTP/2(多重化)   [大][小][小][大][大][大]...      小は最初の順番で完了
                     ↑2  ↑3                       大は少し遅れる

HTTP/1.1 は応答を順に返すので小さな応答が大きいものの後ろで待つ。HTTP/2 はフレームを交互に流すので小さな応答が先に終わる

順に見ていく。

1 接続に複数ストリーム: 独立した要求・応答の流れを、1 本の接続の上で同時に走らせる
フレームを交互に流す: 各応答を小片に刻み、順繰りに送る。小さな応答が大きな応答を追い越せる
HPACK でヘッダ圧縮: 一度送ったヘッダを索引で参照する。繰り返すヘッダの無駄を省く

① フレームと多重化: 小さな応答を先に通す

まず HoL ブロッキングそのものを、完了時刻で比べられる形にする。各応答をフレーム数で表し、HTTP/1.1 は直列送信、HTTP/2 は順繰り送信としてモデル化する:


// CompletionTicksH1 は HTTP/1.1 の完了時刻を返す。応答は要求順に直列送信され、
// 各応答は前の応答がすべて終わってから始まる(ヘッドオブラインブロッキング)。
// sizes は各応答のフレーム数。tick は 1 フレーム送信を 1 と数える論理時間。
func CompletionTicksH1(sizes []int) []int {
	done := make([]int, len(sizes))
	t := 0
	for i, s := range sizes {
		t += s
		done[i] = t
	}
	return done
}

// CompletionTicksH2 は HTTP/2 の完了時刻を返す。1 本の接続の上で全ストリームの
// フレームを順繰りに 1 つずつ流す(多重化)。大きな応答の合間に小さな応答の
// フレームが差し込まれるので、小さいものが先に完了する。
func CompletionTicksH2(sizes []int) []int {
	remaining := make([]int, len(sizes))
	copy(remaining, sizes)
	done := make([]int, len(sizes))
	tick := 0
	for {
		active := false
		for i := range remaining {
			if remaining[i] > 0 {
				active = true
				tick++
				remaining[i]--
				if remaining[i] == 0 {
					done[i] = tick
				}
			}
		}
		if !active {
			break
		}
	}
	return done
}

// Multiplex は各ストリームを順繰りにフレーム化した、接続を流れる順序を返す。
// CompletionTicksH2 と同じ順繰りで、実際のフレーム列を組み立てる。
func Multiplex(sizes []int) []Frame {
	remaining := make([]int, len(sizes))
	copy(remaining, sizes)
	var frames []Frame
	for {
		active := false
		for i := range remaining {
			if remaining[i] > 0 {
				active = true
				remaining[i]--
				frames = append(frames, Frame{
					StreamID: i + 1,
					Type:     FrameData,
					End:      remaining[i] == 0,
				})
			}
		}
		if !active {
			break
		}
	}
	return frames
}

HTTP/1.1 は応答を要求順に、前が全部終わってから次を始める。大 10 フレーム・小 1・小 1 なら、小さな応答の完了は 11 tick、12 tick になる。前の大きな応答を待たされるからだ。HTTP/2 は 1 フレームずつ順繰りに流す。同じ 3 つでも、小さな応答は最初の順番で送り切れて 2 tick、3 tick で完了する。テストでこの差を固定した。大きな応答の完了はむしろ少し遅れる(10→12)。多重化は総送信量を減らすわけではない。仕事量は同じで、小さな応答を先に完了させて体感を良くする。ページの主要部分が早く見え始めるのは、この差の効果だ。

② HPACK: 繰り返すヘッダを索引にする

もう一つの無駄がヘッダだ。同じサイトへの何十ものリクエストは、Host・User-Agent・Accept・Cookie など、ほぼ同じヘッダを毎回繰り返す。1 リクエストのヘッダが数百バイト、それが何十回。HPACK は、一度送ったヘッダを動的表に覚え、次からは索引で参照する:


// Header は 1 つのヘッダ行。
type Header struct{ Name, Value string }

// HField は HPACK の符号化結果。Index>0 なら表の参照、0 なら literal(表にも追加)。
type HField struct {
	Index int // 動的表のインデックス(1 始まり)。0 は literal
	Name  string
	Value string
}

// Encoder はヘッダを動的表を使って圧縮する。一度送ったヘッダは索引で参照する。
type Encoder struct{ table []Header }

// NewEncoder は空の動的表でエンコーダを作る。
func NewEncoder() *Encoder { return &Encoder{} }

// Encode はヘッダ列を HField 列にする。表にあれば索引、なければ literal で送り表に追加。
func (e *Encoder) Encode(headers []Header) []HField {
	out := make([]HField, 0, len(headers))
	for _, h := range headers {
		if i := indexOf(e.table, h); i >= 0 {
			out = append(out, HField{Index: i + 1})
		} else {
			out = append(out, HField{Name: h.Name, Value: h.Value})
			e.table = append(e.table, h) // 次からは索引で送れる
		}
	}
	return out
}

// Decoder はエンコーダと同じ手順で動的表を育て、HField 列を復元する。
type Decoder struct{ table []Header }

// NewDecoder は空の動的表でデコーダを作る。
func NewDecoder() *Decoder { return &Decoder{} }

// Decode は HField 列をヘッダ列に戻す。literal は表に追加してエンコーダと同期する。
func (d *Decoder) Decode(fields []HField) []Header {
	out := make([]Header, 0, len(fields))
	for _, f := range fields {
		if f.Index > 0 {
			out = append(out, d.table[f.Index-1])
		} else {
			h := Header{Name: f.Name, Value: f.Value}
			d.table = append(d.table, h)
			out = append(out, h)
		}
	}
	return out
}

func indexOf(table []Header, h Header) int {
	for i, t := range table {
		if t == h {
			return i
		}
	}
	return -1
}

// EncodedSize は HField 列のおよそのバイト数。索引は 1、literal は名前と値の長さ分。
func EncodedSize(fields []HField) int {
	n := 0
	for _, f := range fields {
		if f.Index > 0 {
			n += 1 // 索引参照は 1 バイト
		} else {
			n += 1 + len(f.Name) + len(f.Value)
		}
	}
	return n
}

// RawSize は圧縮しない場合のヘッダのバイト数。
func RawSize(headers []Header) int {
	n := 0
	for _, h := range headers {
		n += len(h.Name) + len(h.Value)
	}
	return n
}

エンコーダとデコーダが同じ手順で動的表を育てるのが肝だ。初めて見るヘッダは literal(名前と値)で送り、両者が表に追加する。次に同じヘッダが来たら、エンコーダは表の索引だけを送り、デコーダは索引から復元する。テストで、二度目の同じヘッダが索引参照になってバイト数がヘッダ数ぶんにまで縮むこと、復元が元と一致することを固定した。長い User-Agent 文字列が、二度目は 1 バイトの索引になる。繰り返すほど効く圧縮だ。

③ 残る問題: TCPレベルのHoL

HTTP/2 はアプリケーション層の HoL ブロッキングを解いた。だが、もう一段下に問題が残る。多重化されたフレームは、結局 1 本の TCP 接続を流れる。TCP はパケットを順序どおりに届けることを保証するので、途中の 1 パケットが失われると、それが再送されて届くまで、後続のすべてのパケットが TCP の受信バッファで待たされる。あるストリームのパケットロスが、無関係な他のストリームのフレームまで足止めしてしまう。アプリ層では多重化したのに、TCP 層で再び HoL が起きる。

これを解くのが HTTP/3 だ。TCP をやめ、UDP の上に QUIC という新しいトランスポートを載せる。QUIC はストリームごとに独立して順序保証と再送を行うので、あるストリームのパケットロスが他のストリームを止めない。層を下げて HoL を根絶した形だ。この章では TCP レベルの HoL までは扱わないが、多重化がどの層の問題を解き、どの層に残すのかを押さえておくと、HTTP/3 の動機がそのまま見える。

動かす

下のデモは、大きな応答 1 つと小さな応答をいくつか混ぜて、HTTP/1.1 と HTTP/2 で各応答がいつ完了するかを並べて見る。小さな応答が HTTP/2 でどれだけ早く終わるか、その代わり大きな応答がどれだけ遅れるかを確かめてほしい。

デモHTTP/2 多重化小応答が H2 で約 4.6倍速く完了

大1 + 小2大1 + 小4均等 3本

応答HTTP/1.1(直列)HTTP/2(多重化)

S1 (10F・大)1012

S2 (1F)112

S3 (1F)123

完了 tick(短いほど早く終わる)→

HTTP/1.1 では小さな応答が大きな応答の後ろで待たされる。HTTP/2 は多重化で先に完了させ、小応答は約 4.6倍速い。ただし大きな応答は少し遅れる(仕事量は同じ、体感を最適化)

各応答をフレーム数で表し、1 フレーム送信を 1 tick と数えている。HTTP/1.1 は応答を要求順に直列で返すので、小さな応答が大きな応答の後ろで待つ(ヘッドオブラインブロッキング)。HTTP/2 は 1 本の接続でフレームを交互に流すので、小さな応答が先に完了する。総 tick 数は変わらない。小さく重要なリソースを先に届けて、ページが早く使えるようにするのが多重化の狙いだ。

設計の観点

多重化は体感を最適化する: 総転送量や全完了時刻は改善しない。小さな・重要なリソースを先に届けて、ページが早く使えるようにする。優先度(priority)で「何を先に」を制御する
接続を 1 本に集約: HTTP/1.1 の複数接続を 1 本にまとめる。TCP 確立・TLS ハンドシェイクのコストが 1 回で済み、輻輳制御も 1 本ぶんで効く
HPACK は状態を持つ: 動的表はエンコーダ・デコーダで同期が必須。順序が狂うと復元できない。だから信頼できる順序配送(TCP)の上でのみ成立する
TCP HoL は層を下げて解く: HTTP/2 でもパケットロス時に TCP バッファで詰まる。HTTP/3 は QUIC(UDP ベース)でストリームを独立させ、これを解消する
サーバプッシュは廃れた: HTTP/2 のサーバプッシュは複雑さの割に効果が薄く、実質非推奨に。多重化と優先度が本命

対照と実例

	HTTP/1.1	HTTP/2	HTTP/3
多重化	なし(1接続1応答)	あり(ストリーム)	あり(ストリーム)
アプリ層 HoL	あり	解消	解消
TCP 層 HoL	あり	残る	解消(QUIC)
ヘッダ圧縮	なし	HPACK	QPACK
トランスポート	TCP	TCP	UDP + QUIC

裏どり:

RFC 9113 (HTTP/2): フレーム・ストリーム・多重化の仕様。この章のフレームと多重化の元
RFC 7541 (HPACK): ヘッダ圧縮の仕様。静的表 + 動的表 + ハフマン符号化。ここでは動的表の索引参照だけを実装
RFC 9000 (QUIC) / RFC 9114 (HTTP/3): TCP 層の HoL を解く到達点。ストリーム独立の順序保証
SPDY (Google): HTTP/2 の原型。多重化と圧縮の実験が標準化につながった

簡略化したこと

HPACK は動的表のみ: 実物は静的表(よくあるヘッダを事前定義)+ ハフマン符号化 + サイズ上限
フロー制御・優先度なし: WINDOW_UPDATE や依存木は扱わない。順繰りの単純な多重化のみ
TCP 層の HoL は概念のみ: パケットロス時の TCP バッファ詰まりは実装せず、設計の観点で述べた
論理的な tick: 1 フレーム送信を 1 と数える。実帯域・RTT・フレームサイズは扱わない

参考資料

RFC 9113: HTTP/2 — フレームと多重化の仕様
RFC 7541: HPACK — ヘッダ圧縮の仕様
HTTP/2 explained (Daniel Stenberg) — 多重化と HPACK の平易な解説
実装: network/http2

HTTP/2 多重化 ​

この章で作るもの ​

① フレームと多重化: 小さな応答を先に通す ​

② HPACK: 繰り返すヘッダを索引にする ​

③ 残る問題: TCPレベルのHoL ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​