Go でベンチマーク
Intro
Go にはベンチマークを取る仕組みが標準で備わっています。
テストを書く仕組みも標準で備わっており、
testing モジュールと go test コマンドで行いますが、
ベンチも同じような形で実行することができます。
今回は簡単なベンチ取り方を紹介します。
テストについては、そのうちちゃんと触れます。
参考ソースとして、こちらを使います。
対象のコード
例えば以下のようなコードがあって、そのベンチを取るとします。
// swrap.go type SWrap []byte func (sw *SWrap) Add(a byte) { *sw = append(*sw, a) } func (sw *SWrap) Len() int { return len(*sw) }
Slice にメソッドを生やしただけです。
ベンチマーク関数
ベンチマークは、 *_test.go ファイルに書きます。
関数名は Bench で始め、引数として *testing.B を渡す関数として定義します。
(このへんはテストと同じです。)
// swrap_test.go import ( "testing" ) func BenchmarkAdd(b *testing.B) { for i := 0; i < b.N; i++ { sw := New(Fixture()) sw.Add(0xFF) } } func BenchmarkLen(b *testing.B) { sw := New(Fixture()) b.ResetTimer() for i := 0; i < b.N; i++ { sw.Len() } }
b.N が勝手に設定されるので、それをループの条件とするだけです。
ループにかかる時間を測るので、ループに入る前の準備処理などに時間がかかる場合は、
ループの前に b.ResetTimer() を呼ぶと準備処理分を引くことができます。
実行方法
実行は go test にオプションを追加するだけです。($GOPATH を通しておいて下さい)
$ go test -bench Add # Add とつくものだけ実行 $ go test -bench . # 全て実行
全ての実行例はこんな感じです。(インデントだけ整形済み)
$ go test -bench . PASS BenchmarkNew 2000000000 0.64 ns/op BenchmarkBytes 2000000000 1.09 ns/op BenchmarkLen 2000000000 1.23 ns/op BenchmarkAdd 5000000 334 ns/op BenchmarkMerge 10000000 254 ns/op BenchmarkDelete 20000000 148 ns/op BenchmarkCompare 50000000 32.8 ns/op BenchmarkPush 5000000 354 ns/op BenchmarkPop 10000000 114 ns/op BenchmarkShift 10000000 234 ns/op BenchmarkUnShift 20000000 109 ns/op BenchmarkReplace 5000000 614 ns/op ok swrap 27.847s
実行回数が違うのは、 b.N の値が変わっているからですね。
この b.N は直接指定するのではなく、ベンチの実行時間からの逆算です。
デフォルトは 1 秒間実行しているようです。
この実行時間は -benchtime で指定できます。
十分な時間を指定し、性能自体は ns/op で見るのが良さそうです。
benchmem
"-benchmem" オプションをつけるとメモリアロケート回数がわかります。
変数をポインタに変更するなどの改善ポイントが見つけられます。
PASS BenchmarkLen 2000000000 0.95 ns/op 0 B/op 0 allocs/op BenchmarkAdd 5000000 370 ns/op 48 B/op 2 allocs/op
比較
実はこの結果を比較するツールがひっそりと同梱されています。
まったくいいサンプルが無いんだけど手元にあったもので、
例えば以下の様な超地味なチューニングに成功したとします。
PASS BenchmarkNew 2000000000 0.47 ns/op 0 B/op 0 allocs/op ok swrap 1.000s
PASS BenchmarkNew 2000000000 0.44 ns/op 0 B/op 0 allocs/op ok swrap 0.954s
それぞれ before after で保存して
これを misc 以下にある benchcmp に渡します。
$ $GOROOT/misc/benchcmp before after benchmark old ns/op new ns/op delta BenchmarkNew 0 0 +6.82%
こうした値をパッチに添えて PR とかすると話が速くていいかもしれませんね。
オプション
オプションを簡単(適当)に訳しておきます。
(まだ使ったことがないものが多いです)
http://golang.org/cmd/go/#hdr-Description_of_testing_flags
-bench regexp 対象の指定 -benchmem メモリアロケーションの表示 -benchtime ベンチ実行時間 -blockprofile goroutine のブロックプロファイルを出力 -blockprofilerate runtime.SetBlockProfileRate の値を指定 -cpu GOMAXPROCS の値を指定 -cpuprofile CPU プロファイルを出力 -memprofile メモリプロファイルを出力 -memprofilerate runtime.MemProfileRate の値を指定 -parallel 並列実行の指定(デフォルトは GOMAXPROCS) -run テストと example の実行対象指定 -short 時間を短縮して簡易実行 -timeout タイムアウト -v 詳細出力
HPACK の Integer Representation の仕組み
intro
この内容は、 HPACK draft-03 を元に書かれています。
http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-03
将来のドラフトでは変わる可能性があるためバージョンにはご注意下さい。
(以下の内容は、自分がアルゴリズムから読み解いたものなので、間違ってたら教えて下さい。)
HPACK
HPACK のフレーム表現の中に、以下のような表記が出てくる。
0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | 1 | Index (7+) | +---+---------------------------+
この Index(7+) は、ここに数値が 7 bit もしくは、それに続く数 byte を用いて、
表現されていることを示している。
この表現は、 7 bit で収まる数値は 7bit で表現し
収まらない大きな数値は、後続の byte を必要なだけ用いて表現することで
任意の大きさの数値を表現できる仕組みになっている。
この Index(N+) の部分の表現を Integer Representation という。
Encode アルゴリズム
ドラフトを見ると、 Encode 方法として以下のアルゴリズムが示されている。
If I < 2^N - 1, encode I on N bits
Else
encode 2^N - 1 on N bits
I = I - (2^N - 1)
While I >= 128
Encode (I % 128 + 128) on 8 bits
I = I / 128
encode (I) on 8 bitsこの通りやればエンコードできるのだが、最初は意図がよくわからなかった。
また、デコードの方法は記されてないので、 Decode するためには逆算するのだが、
その導出過程で仕組みを解いてみたら面白かったので紹介する。
以下 I が表現したい値、 N が Prefix (+N の部分) とする。
仕組み
ここでは、簡素化のために N＝５ で固定する。
0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | x x x | Index (5+) | +-----------+-------------------+
I=10
まず、小さい数値 I＝１０ で導出過程を見てみる。
10 を表現するには 5 bit あれば十分である。
なぜなら N<2^5-1(31) よりも小さいから。
xxx0 1010
つまり 2^N - 1 より小さい値については、普通に 2 進数にすれば良いことがわかる。
(If I < 2^N - 1, encode I on N bits の部分)
I=3,000,000
I を大きめにしてみる。
(ドラフトのサンプルでは 1337 があるが、ターン数が少ないので、より大きな数字を選んだ)
まず、 N bit は使えるので、そこで表せる最も大きい値をそこで表すことにする。
2^N-1 = 2^5-1 = 31
つまり、 以下のようにすればとりあえず 31 は表せる。
(encode 2^N - 1 on N bits の部分)
xxx1 1111 (31)
そこで、元の I から表せた分だけ引いたものを算出すると。
3,000,000 - 31 = 2,999,969
この値は、後続の byte を用いて表す必要がある。
(I = I - (2^N - 1) の部分)
そこで、現在の値を 2 進数で表してみると。
0010 1101 1100 0110 1010 0001 (2,999,969)
全てが 8 bit には収まらないので、後続のバイト列で表現せざるをえない。
それをどう表現するか。
表現不足な例
下位から 8 bit ごとに区切っていけばいいと考えると。。
xxx1 1111 1010 0001 1100 0110 0010 1101
こうなる。
これで表現できた気もするが、問題がある。
それは、この後も別のバイト列が続いた場合に、
どこまでが I を表しているのかがわからないからだ。
終端を自己表現するために
I を表すのに何byte 使ったのかを別途持つ方法もあるが、
Integer Representation は、表現自身からどこまでが
I を表しているかわかるようにしている。
8bit ではなく、 7bit ごとに区切って、後続がある場合は
必ず先頭 bit を 1 にし、最後のバイトの場合は先頭 bit が
0 になるようにしているのである。
もう一度もとのバイト列
0010 1101 1100 0110 1010 0001 (2,999,969) xxxx xxxx xxxx xxxx xooo oooo
下位 7bit を切り出して、8bit 目を 1 にして後続の 1byte とする。
現在の表現に加える。(o の部分)
xxx1 1111 1010 0001
I からはその分削る。
次は、以下になる。
0101 1011 1000 1101 (23,437) xxxx xxxx xooo oooo
xxx1 1111 1010 0001 1000 1101
同様に。
1011 0111 (183) xooo oooo
xxx1 1111 1010 0001 1000 1101 1011 0111
で、最後は 1 になるが、これは そのまま 1 としてエンコードすれば良い。
結果は以下になる。
xxx1 1111 1010 0001 1000 1101 1011 0111 0000 0001
つまり、先頭ビットを 0 にしたまま表現できるサイズまで縮めば、
それを最後の byte とすることができる。
その値は最大で 127 である。
0111 1111 (127)
アルゴリズムで言うと
While I >= 128
この部分は、先頭ビットを 0 にしたまま表現できない値を意味している。
その間は、
Encode (I % 128 + 128) on 8 bits
128 は 2^7 であるので、 128 で割るのは、 7 bit 右シフトすることと等価である。
つまり、 128 で割ったあまりは、 7bit 右シフトしたら消えてしまう部分にあたるので、
(I % 128) は下位 7 bit をさす。
128 加えるのは、 1000 0000 を加えることなので 7bit の値に対して先頭 bit に 1 を加えることを意味する。
I = I / 128
これは、単純に今処理した 7bit を消すために 7bit 右シフトしていることと等化である。
これを繰り返し、 I < 127 (7bit で表現できる値) になったら
encode (I) on 8 bits
8 bit で表現するということは先頭がかならず 0 になるので、これを終端とみなせる。
デコード
結果をもう一度見てみよう。
xxx1 1111 1010 0001 1000 1101 1011 0111 0000 0001
この値を上から見た場合。
1, I=5 で、 5bit 読んだら全て 1 なので 5bit では表せず後続 byte を使っていることがわかる。
0001 1111
2, 次の byte を見ると、先頭が 1 なので、それを除いた 7 bit が最下位になり、まだ続くことがわかる
3, 最後の 0 で始まる byte が最後になり、そこまでをシフトしながら繋いで行けば良い。
これを図持すると以下のイメージに成る。
0010 0001
0000 1101
0011 0111
0000 0001
------------------------------------
1011 0111000 1101010 0001 (2,999,969)1 と 2-3 の結果を加える。
0001 1111 (31) 10 1101 1100 0110 1010 0001 (2,999,969) --------------------------------------- 10 1101 1100 0110 1100 0000 (3,000,000)
よって、デコードは上記を行うアルゴリズムを構築すれば良い。
#BPStudy72 で SPDY / HTTP2.0 / QUIC のお話をさせて頂きました。
資料
発表資料です。
資料は以下です。今回は、とりあえず上記 3 つを全部突っ込もうということで盛りだくさんな感じになってしまいましたが、現時点での話は割りと網羅できた気がします。
盛り込んだバージョンは、 2013/8/28 時点のものなので、バージョンでは以下のような感じです。
- HTTP/2.0 draft-06
- HPAC draft-03
- SPDY/3
- QUIC (現状)
当日の朝に HPAC の仕様が新しくなったり、 devops-ML ができたりと動きがあり、行ってから直したりしました。
週末に作った資料が水曜には古くなっているという程度の動きの速さなので、今回の資料も賞味期限は早めだと思いますが、ご注意下さい。
BPStudy
BPStudy は今回でちょうど 6 年目だそうです。もうそんなにやっているんですね。
いわゆる勉強会ブームの初期か、その前くらいから開催されていて、自分も気になるトピックを見つけては、ちょくちょく参加して勉強させていただいていました。それが今回初めて登壇者として声をかけていただいたので、とても光栄です。
技術系の会社が、自分たちの技術をキチンとアップデートするために、こうした取り組みをするだけでも凄いのに、
それを定期的に続けてここまで来たというのは素晴らしいことだと思います。
それも、代表の佐藤さんが技術について真剣に向き合ってきたからなのでしょう。
今後も興味のあるテーマは是非参加させて頂きたいと思います。
これからも有益な勉強会を期待しております。
ありがとうございました。
HTTP2.0 勉強会を開催しました
Intro
HTTP2.0 は Draft-04 が出て、その実装を持ち寄っての相互接続試験を実施し、フィードバックを踏まえて Draft-05 が出るなど、割とチェックポイントな感じがあったので、一旦色々まとめたいなと思い勉強会を実施しました。
発表資料
自分の発表資料はこちら。
前座的なポジションになったので HTTP2.0 のここまでと、現時点の実装を簡単に紹介して来ました。
あと、最近作ってた HTTP2Cat も紹介してきました。
他の方の資料も順次 connpass に上がる予定です。
HTTP2Cat
HTTP2.0 や SPDY の開発をすると tatsuhiro_t 先生のモジュール軍には必ずお世話になります。
で、その中に HTTP2.0 や SPDY の接続確認に使える nghttp, spdycat という CLI ツール(wget 的な) があります。
超絶便利なのですが、ビルドがちょっと面倒なところもあるので、 Web のフロントを作って見ました。(かなり突貫ですが。。)
結果を WebSocket で返すのに、 Nginx を使いたかったので SPDY/2 でホストしてます(nginx は spdy/3 が無い)。
使い方は nghttp, spdycat のドキュメントを見てもらえれば多分わかります(雑)
HTTP2.0 の薄い本
今回発表していただいた、 @flano_yuki さんが、コミケで HTTP2.0 の薄い本を出されました。
「learning HTTP 2.0」
かわいらしい表紙とあいまって、内容は凄く良くまとまっており、初心者向きな一冊です。
500 円でこれが読めるなら安いものでね。まだ在庫があるらしいので、欲しい方は @flano_yuki さんに言えばまだ手に入るかも。
今後
HTTP2.0 今が一番面白い時期ですね。今後もチェックポイントがあるごとに、こうして情報や成果を共有する場は作りたいと思っています。
ハッカソンとかもやりたいですね。
宣伝
8/27 の BPStudy でも SPDY/HTTP2/QUIC あたりでお話しさせていただきます。
もう埋まっているようですが、よろしくお願いいたします。
なぜ QUIC や SPDY が生まれたのか ?
Intro
Google が SPDY の開発を始めたのは 2009 年で、 2012 年に HTTP2.0 のドラフトとして採用されたあたりからちょっと話題になりました。
翌 2 月には新たなプロトコル QUIC の存在が Chromium のソースからリークしたのですが、しばらくは音沙汰なく。
6 月に入ってやっと Google から公式アナウンスとドキュメント類が出ました。
去年から今年にかけて立て続けに出てくる新しいプロトコルの話。
なぜ今 Web のプロトコルが見直されるのか？
何が問題で、なぜ Google はそれらを作り変えるのか？
SPDY や QUIC は Google の独自プロトコルだけど、それは本当にただの独自プロトコルで終わらせていいのか？
20% ルールで作ってみた Play プロジェクトでしかないのか？
こうした新しい動きには、かならず「それまで」と「今」を踏まえた議論が起こります。
つまりこれらを追うと、「今何が起こっているのか？」を知ることができて非常に得るものがあります。
プロトコルの解説は何度か書いたけど、そういう話をもう少し書いてもいいかと思い
自分がわかる範囲でちょっとつらつらと書いてみようかと思います。
Web を速くするということ
単純にWeb を高速化するといっても様々なレイヤがあります。
たとえば、ぱっと浮かぶ範囲でも以下のようなものがあります。
- A, Web アプリ/システム/サービスの高速化
- B, ブラウザ、サーバプロダクト、カーネルのネットワーク周りなどの高速化
- C, ネットワーク機器などの高速化
- D, ネットワーク帯域などのインフラの強化
A は、 Web アプリがあってそれが遅いから速くしようとした場合です。
ISUCON で行われているようなチューニングなんかが浮かぶでしょう、これは一般の開発者にとって一番手を出しやすいレイヤになります。自分のアプリなので、アップデートもしやすいです。
B は、 Chrome が速くなる Nginx が速くなるとかといったレイヤです。
OSS であれば、パッチを投げることで貢献はできますが、自分のプロダクトに手を加えるのと比べれば多少敷居は上がるかもしれません。アップデートは定期的なものになり、多少時間が必要なります。
C は、 アプリの開発者からは通常意識されないレイヤで、ネットワーク上の機器とかそういうレイヤになりますかね。 PC 自体の NIC とかも入るかもです。本格的にハードがからんでくるので、アップデートはより時間がかかるし、なかなか手を入れることも難しい部分になってきます。
D は、通常一般の開発者では手が出ないレイヤです。ネットワーク事業者などがインフラに投資をすることで、改善していきます。わかりやすいのは帯域の改善などです。サイクルは、、ものによるとしか言えないかもです。
さて、これらの改善は、独立して実施できます。つまり、それぞれが別々に努力をして改善でき、それらが組み合わさって全体を「速く」することができます。
なぜ、独立で実施できるか。これはネットワークの世界にレイヤの考え方があり、各レイヤに「約束事」としての標準プロトコル/フォーマットが存在するからです。担当するレイヤの中で、プロトコル/フォーマットに従って実装をしていれば、「相互接続性」が保たれ、プロダクトなどをアップデートしても「Web が壊れる」ことを防ぐことができます。これが、プロトコル/フォーマットを「標準仕様」として定義するメリットです。
独立で実施できるということは、大げさにとらえると、あるレイヤが改善すればボトルネックは他に移ります(アプリが十分に早ければ、ネットワークがネックになるなど)。そして、各々のレイヤで改善が進むと、最終的にボトルネックは、そのレイヤをつなぐプロトコル/フォーマットに移っていく場合があります。今回一番絡んでくるのは、「どんなに帯域とアプリが早くても、 HTTP がボトルネックになる」といったパターンです。
このレイヤ、標準プロトコル/フォーマット自体の改善は、先ほどのリストに加えて E としておきましょう。
標準仕様の改善などにあたるので、 IETF や W3C などに参加することで貢献はできます。一般の技術者には敷居が高いでしょう。またステークホルダが多いので、議論も多岐にわたり、決まっても普及に時間がかかる場合が多いです。
Make the Web Faster
Google は、 Make The Web Faster というプロジェクトを実施しており、そこでは Google というポジションだからこそできる Web の改善方法の開発や、仕様の提案を行っています。(以下、長いので単にプロジェクトと言ったらこれを指すとします。)
Page Speed というプロダクトは、先の A にあたります。 Apache のモジュールなどとして提供されていて、自分のアプリに取り込めば、「ハイパフォーマンス Web サイト」にあるような改善の補助をしてくれるものです。その内容を、ベストプラクティスとしてまとめたものも公開されています。
最近すっかりシェアを伸ばした Chrome が速くなるのは、 B にあたるでしょう。まあ、 Chrome の改善は Google が普通にやっていることで、 Make the Web Faster にリストされているのは、 Chrome の Analyze 機能の改善になっています。
Google が提供する DNS や CDN もプロジェクトに含まれています。 Google の強力なインフラをベースとしたもので、 C や D に含まれると言えそうです。
では E にはどういったものが含まれるのでしょうか？
Google が取り組む Protocol / Standards の改善
E の中身として Make the Web Faster には Protocol / Standards が分けてのせてあります。
Standards
Web はネットワークを介すので、送信するファイルのサイズは小さいほど有利です。そして、サイズが大きいファイルの代表が画像と動画でしょう。
WebP は、 PNG や JPEG といった Standard な形式よりも、効率の良い圧縮形式です。 Facebook なんかも使い始めていますが、まだ対応したオーサリングツールなどがなくてちょっと問題になったりしています。
標準的なフォーマットを変えるのはまた難しいものですが、これもプロジェクトの一つです。
(ちなみに、動画版の WebM もあります。あまり詳しくないのですが、これはコーデック問題とかそっちが主眼みたいで、プロジェクトにはリストされていません。)
画像や動画に限らず圧縮率が高いことは有利です。圧縮を有効にすると、こまごましたミニファイが誤差程度になるほどには効率が良くなる場合があります。で、この圧縮の定番である gzip を改善したのが Zopfli です。 プロジェクトには上がっていませんが、圧縮に多少時間がかかる代わりにサイズが 3-8% 小さくなる、展開時間は同じ、というもの。圧縮は Web だけの問題領域ではありませんが、モチベーションは同じかなと思っています。
他には、 HTML5 まわりで W3C に貢献すること自体、プロジェクトの一環としても位置付けられているみたいです。(まあ、これもプロジェクトを超えて、 Google 自体の大きなミッションでしょうが。)
Protocol
先ほどの D の改善で、例えばネットワーク帯域が増えたとき、動画や大きなファイルのやり取りの改善は期待できますが、小さいファイルの集合である Web ページの読み込みの改善は限界があります。
実際 Web ページについて言えば、帯域よりも RTT の改善の方が効果が大きいことが、 Google の調査からもわかっています。
RTT の改善は、要するに行って返ってくるまでの時間の短縮ですが、これは物理的な距離なども関係するので改善は難しいです。
Web ページの取得には、 DNS 名前解決、 TCP 接続(3-way-handshake)、 HTTP req/res などが必要になり、増えるほど RTT の総和は長くなるので、そもそも「RTT の数を減らす」というのが現実的なアプローチです。アプリ側でファイルを統合するなどの方法がそれにあたりますが、そもそもプロトコル自体を見なおせば、もっと減らせるかもしれません。
HTTP はそもそも、論文の共有などを目的に作られたシステムなので、設計もテキストドキュメントの共有に寄せた仕組みとなっていました。
これ自体は、重要な設計思想だったと思います。扱いやすいテキストプロトコル、スケールさせやすいステートレス性。シンプルなデザインだったからこそ、 Web はここまで普及したと言えるでしょう。
問題は、 Web 自体が十分すぎるほどに普及した今、アプリ/システム/ゲームなどのプラットフォームとして使われ、単一ドキュメントの閲覧に留まらない様々な用途に使われるようになった今現在において、そのデザインは本当に最適か？ということだと思います。
通常、標準プロトコルに手を入れるのは、接続性がなくなるために簡単にはできません。しかし、 Google は多くの Web サービスとともに、クライアントとなるブラウザも持っています。両方を備えかつユーザ規模も大きい Google は、Google のサービスに Chrome で接続するユーザにだけ、オレオレプロトコルで大規模な実証試験を行うことができたのです。
SPDY とはなんだったのか
Web の根幹を成すプロトコルに手を入れる取り組みが SPDY です。現在では Chrome と Google のほぼすべてのサービスが対応し、大規模に運用されています。
独自プロトコルとはいっても、あまり標準から外れたパケットを流すと、 intermediaries (proxy や FW など中間に入るもの) をうまく通れない可能性があります。SPDY がデフォルトを SSL にしているのはそうした意味もあります。暗号化しちゃえば中で何が流れても中間ではわからないですし、変にいじられることもありません。また 443 は 80 と並んでほぼ通るポートです。 npn というアップグレードの仕組みも Google の提案したもので対応が多いのもあるし、そもそも Google 並のサービスだとセキュリティ的に全部 SSL の方がいいという判断も絡んでいると思いますが。
SPDY にはいろいろなアイデアが盛り込まれていますが、ここではTCP 接続の扱いに着目しましょう。
HTTP/1.0 では、毎回接続し、毎回切っていました。ドキュメントを取得して表示する用途であれば、まあ自然といえば自然です。
しかし、ページを構成するコンテンツ(CSS, JS, Image)が増えると、毎回切って 3-way-handshake からやり直すのはやはり無駄です。そこで、 HTTP/1.1 では Keep-Alive で確立した TCP 接続を使いまわすようになりました。
使いまわすといっても、繋ぎっぱなしは負荷が増えるので、ページのコンテンツ全部を落としたら切断したいところです。しかし、ページ単位でのライフサイクルの管理は容易ではなく、 Apache などでは「時間」「アクセス回数」などのわかりやすい指標で設定されているのが現状のようです。
あと、せっかく使いまわせても、前のレスポンスが終わらないと次のリクエストを投げられないという仕様があり、 1 本のリクエストを使いまわすと逆に遅くなる場合がありました。これを解決するのが pipelining という仕様だったのですが、対応が難しく、しかも対応していないサイトは崩れることがあったため、ブラウザもオフのものが多かったのです(Opera は有効だったけど、無効にしているユーザが多いみたい)。
また、やったところでそんなに速くならないという話もあったり。
pipelining は10 年近くたっても普及しきらず、ブラウザベンダはたくさんの TCP 接続(6 本がメジャー)を同時に確立することで並行してコンテンツを取るように実装しました。仕様では、同一サイトには 2 本位にしようね、という推奨があるのですが、守っていると他のブラウザより「遅い」というレッテルを張られかねないので、ベンダとしてはしょうがない選択だったのでしょう。(よって 1 ドメインには 6 本までの制限ですが、別ドメインだともう 6 本確立できます。静的ファイルなどはサブドメインや別ドメインのCDN に置きましょうという最適化手法はここからきます。)
SPDY は、 1 本の接続を極力使い切る設計になっています。具体的には、コネクションの上に「ストリーム」という論理的な接続を作り、それは多重化されています。たとえば 3 つのコンテンツの取得は 3 つのストリームを確立して行い、取得が終わっても終わるのはストリームでコネクションはそのままですし、ストリームの順番も自由なのでたくさん接続を作る必要もありません(理想は)。 Keep-Alive + Pipelining + α なイメージです。
あと、一本の TCP 接続を使い続けることは、 TCP の性質上も有利です。
TCP は、輻輳制御のため、最初は小さいパケットを送り、送るたびにそのサイズを増やしていく Slow Start という仕組みがあります。接続を毎回やり直すと、パケットサイズも毎回リセットしてしまいます。使いまわせば、送れば送るほどコネクションが温まって、輻輳が起きるまではパケットサイズが増えて効率がよくなります。
さて TCP を使いまわすという点では SPDY はだいぶ効率が良くなったと思います。でも、それって「接続が確立した後」の話ですよね。ただユーザにとっては「一番最初」の表示もやっぱり重要です。
Google は SPDY 以外にも、 TCP の層にまで下りた改善提案もあります。
例えば、 TCP の 3-way-handshake を Cookie を使って 1 回省略する TCP Fast Open という仕様や、送信する最初のパケットサイズを大きくする Increasing Initial Congestion Window などがそれにあたります(これもプロジェクトに入っています)。
実際は SPDY のレイヤだけでなく、 TCP のレイヤにも手を入れたいのが本音ですね。
TCP とはなんだったのか
TCP にも手を入れたいと考えた時点で、やっぱり TCP も HTTP と同様に「現在のニーズに合わないデザインなのかも」という疑問を持つのが正しい考え方なのかもしれません。
じゃあ、 TCP のデザインってなんだったでしょう？
自分のように、ネットワークをインター博士 に学んだ人なら、 TCP は「正確・確実」であると教え込まれたでしょう。
その通りで、 TCP の 3-way-handshake も輻輳制御も、ネットワークを通じて確実にデータを届けるための仕組みです。これがあったから、今ほどネットワークが良くない時代でも、データは確実にクライアントに届きました。「正確・確実」を実現するためにチェックやリトライの仕組みを持っていたのです。
SPDY はそんな TCP の上に多重化の仕組みを設けました。つまり、どんなにストリームを多重化しても、パケットレベルで落ちれば再送が走るし、輻輳が起きればパケットサイズは下がってしまいます。(HTTPでたくさん接続を作っていた頃は、一個の接続の影響は他には出なかったのに。)
3-way-handshake もなんとかならないものでしょうか、 Fast Open で速くなるのは Cookie ができた後、つまり本当に初対面のサーバとは無理なんですよね。
しかも、 TCP レイヤの改善は影響が大きいし、いじれる余地も少ない、なにより OS レベルの対応などになるので、普及にも時間がかかります(先の二つはもうカーネルには入っていますが、 Windows には無いです)。
そもそも「TCP の上に多重化レイヤ」という発想自体は、ネットワークプログラミングの視点から見ると筋の良いものではないといえます。TCP自体の性質のために、いろいろ不自由が出てしまうし、劇的な改善も見込みにくい。
そして QUIC へ
そこで、 Google は TCP ではなく UDP の上に Web を構築するという方針にも取り組み始めました。それが QUIC です。
UDP は、ご存じのとおり信頼性を担保するレイヤがありません。とにかく送りつけて、後はしらんというような仕組みです。そのため、映像の配信のような「ちょっとくらい欠けてもいいからどんどん送る」という用途なんかに使われるという説明が多いでしょう。
さすがにそのままだと、安定した Web の提供はできません。そこで QUIC は、独自に信頼性を確保するレイヤを UDP の上に構築しています。
具体的には、 TCP のようにストリーム全体に影響がないような輻輳制御や、再送を減らすための誤り訂正の仕組みです。
また、先の理由と同じく全体を暗号化するレイヤも自分で持っています。
その上に、多重化のレイヤを構築して、 SPDY を提供することによって、 TCP がボトルネックになっていた部分を改善して、 Web を提供できるのです。
(実際に QUIC を 443 ポートを通して、 HTTPS 上で提供できるようにするための実装が、Chromium では始まっているようです。)
つまり、 QUIC は SPDY over QUIC over UDPという手法をとることで、 SPDY over TCP の限界を突破するために考えられたプロトコルです。
公式にでたドキュメントからも、 QUIC が SPDY をまねた言葉遊び先行の Play Project ではなく、本気で Make the Web Faster を考えた上にたどり着いたプロトコルだと考えるのも、無理はないのではないでしょうか？
ちなみに、この改善の効果は未知数です、Google も完全に実装が終わっているわけではないようなのですが、 Google のユーザの多いサービス群と、シェアの大きい Chrome を合わせてそのうちテストが始まるでしょう。
(今は、 SPDY-Indicator も QUIC に反応できるようになっているので、もし QUIC サービスに気が付いたら教えていただけると幸いです。)
「なぜ出てきたのか」からの学び
QUIC は、それこそまだ Google のオレオレプロトコルです。 Google 自身もこれを標準にするかどうかといったところまでまだ考えてはいないでしょう。実績も効果も未知数ですし、実際にやってみないと本当に価値があるかはわからないのが本音だと思います。
同じように、他にも色々な改善案が Google 社内では動いているのかもしれません。
Make the Web Faster は Google が本気で Web を考えて取り組んだ成果が詰まっています。今すぐ取り込めるプラクティスもあれば、一般の開発者じゃ手が出しにくい Standard や Protocol にも大きなリソースを割いています。
そして、使わなくてもこうしたプロジェクトを知ることで、 Web が持つ様々な面(良さ、欠点)が見えてきます。
それがどういうデザインで、効果がどうかという点ももちろん重要です。
すぐ使えるか、対応はどうか、みんなが使っているかというのももちろん重要です。
でも、もう一つの側面として、なんでそんなものが出てくるのか？という視点を持つと、またいろいろ見えてくるなぁと。
で、今回は SPDY/QUIC 周りを見て思ったことを、連休のノリでなんとなく書いてみたところ話が伸びて、また長くなってしまったなぁという、、
Advanced Go Concurrency 3 つのパターン
intro
ちょっと時間が経ってしまいましたが、 Go研 vol.03 では、 Google I/O 2013 で行われてた Go のセッションの 1 つである下記をテーマに研究しました。
Advanced Go Concurrency Patterns
資料は以下です。
https://github.com/goken/goken/blob/master/goken03/goken03.md
また、ここから順に実装しながら解説をしますが、その完成品はこちらにあります。
(commit 履歴も、本記事にある程度沿っています。)
https://gist.github.com/Jxck/5831269
スライドにそってやったのですが、セッションの内容は結構重ためだったので、 2 時間の Go 研だとちょっと消化不良ぎみだったのが反省点です。
そこで、このセッションの要である、並行処理に関する 3 つのパターンについて紹介します。
メインテーマ
このセッションにおいて一番重要だったのは、 Select の使い方です。
セッションでは、 RSS Reader をテーマとしていますが、その内容をデフォルメして、以下のような古典的 pooling 処理を考えてみます。
1. loop を回して、定期的に外部サーバに GET を投げる
2. 取得した結果を、 channel を経由して呼び出し側に渡す
3. 呼び出し側から Close を呼ばれたら終了処理をする
Loop の部分は、ナイーブな実装は下記のようになるでしょう。
// 定期的な取得をするループ func (p *Pooling) Loop() { for { // Close() が呼ばれいるかを調べる if p.closed { close(p.result) return } // Get を呼ぶだけ body, err := Get(p.url) if err != nil { // エラーがあったら、 3 秒間停止して再開 p.err = err time.Sleep(3 * time.Second) fmt.Println("failed") continue } // 結果を channel で渡す p.result <- body time.Sleep(1 * time.Second) } }
しかし、この実装にはいくつかの問題があります。
問題点
この loop の実装では以下の問題があります。
1. p.closed, p.err が race condition (複数の Goroutine が lock なしでアクセス)
2. Close() を実行しても Sleep() が長いとすぐには loop が終わらない
3. Close() 後に result の読み出しを止められると、 loop が永遠に終わらない
4. Get() が同期処理でブロックする
これらを解決するためには、基本的な方針として Select を用いたイベント駆動を導入します。 for-loop 内で select を使用する基本的な構造は以下になります。
func (p *Pooling) Loop() { // (1) mutable な変数の定義 for { // (2) case のための channel を定義 select { case <-c1: // イベントの補足 // read/write case c2 <- x: // 書き込み // read/write case y := <-c3: // 値の受け取り // read/write } } }
この構造は、 Go の並行処理プログラミングでは基本になります。
とくに (1), (2) と書いた領域の使い分けが大事だと学びました。
request/response パターン
Close() を channel を用いた形で実装しなおします。
トリガーにするための適当な channel を作ります。
ここでは closing という bool の channelにしています。
type Pooling struct { url string result chan string closing chan bool err error }
Close() はそこに何か送ればいいです。
といっても実際に何か送りたいデータがある訳ではないので close() してしまいます。
(close() すると ゼロ値の false が送られる)
// loop を終了させる func (p *Pooling) Close() error { close(p.closing) return p.err }
loop 側は case で補足したら終了処理をします。
func (p *Pooling) Loop() { for { select { case <-p.closing: close(p.result) return
これで p.closed へのアクセスは無くなりました。
しかし、これだと error がとれません。これは loop 側からメッセージで返して欲しいですね。
channel の channel
そこで、トリガとして作った closing を、 channel の channel にします。
type Pooling struct { url string result chan string closing chan chan error }
"error を送る channel" を送ることができる channel です。
Close() は、error を受けとるための channel を作って closing に送ります。
そして、 closing 経由でエラーが返ってくるのを待ちます。読み出してブロックするので、実際に終了処理が終わるまでは Close() は終わりません。また読み出した値をそのまま返せばシグネチャはそのままです。
// loop を終了させる func (p *Pooling) Close() error { done := make(chan error) p.closing <- done return <-done }
loop の方では、 Get() でエラーが発生したらそれを保持しておき、 Close() の(p.closing から値を受け取った)タイミングでそのエラーを送信します。
p.closing から受け取っている done は error 型の channel ななので、ここに送信するだけです。
(実際これだと最後の Get() で発生したエラーしか送れない気がするけど、今回の元ネタの方もそうなっていて、説明の都合上この方が都合がいいので細かい事は気にしない方向で)
// 定期的な取得をするループ func (p *Pooling) Loop() { // Get が失敗したらこれに入れる var err error for { select { case done := <-p.closing: close(p.result) done <- err return default: // Get を呼ぶだけ body, err := Get(p.url)
err は Loop() のローカルとして宣言しており、 Goroutine をまたいでいません。
別の Goroutine への送信は channel 経由のメッセージングを使っているので race condition はありません。
(ちなみに、 Get の結果の代入で body は新しい変数ですが、 err は再宣言になっているように思いました。実際これはエラーになりません。詳細はこちら。 http://qiita.com/Jxck_/items/2616abafea89ee97c477)
こうして、 p.closed, p.err で起こっていた race condition は解消されました。
interval channel
Close を channel 経由で実行できるようにしたため、他のも channel でイベントとして定義するようにすれば、処理を多重化することができて、この問題も解決します。
ここまで time.Sleep を用いて行ってきたインターバル処理については、 time.Tick() を用いるこでイベントにできます。 time.Tick(1 * time.Second) は想像通り、一秒毎に値を送ってくる channel を返します。
for { interval := time.Tick(1 * time.Second) // インターバル select { case done := <-p.closing: // snip case <-interval: // Get を呼ぶだけ body, err := Get(p.url) // err の方は単なる代入
標準パッケージの色々な関数は、こうした仕様を想定して channel を返すものが結構あります。
特に time.After(), time.Tick は特定のタイミングになったことを channel で伝えるようになっているため、この使い方にフィットします。
バッファリング
現在の実装では、 loop の中で p.result に取得した値を書き込んでいるためここでブロックしてしまいます。
呼出側がこれを読み込まない限りは、次の GET は発生しませんし、 Close() することもできません。
そこで、 GET で取得した結果はバッファに貯めて、クライアントへの通知とは別にしてみたいと思います。ここでバッファには単純なスライスを使います。
// 定期的な取得をするループ func (p *Pooling) Loop() { var buffer []string for { // snip case <-interval: // Get を呼ぶだけ body, err := Get(p.url) // err の方は単なる代入 // buffer に結果を追加 buffer = append(buffer, body) case p.result <- buffer[0]: buffer = buffer[1:] } } }
buffer からの取り出しは channel への書き込みになっています。
こうすると、クライアントが読み出すタイミングで順番に送ることができます。
しかし、この単純な実装だとバッファが空のタイミングで読み出されると、 index out of range で panic になります。
panic を rescue することも出きると思いますが、ここでは nil channel パターンを用いて解決してみます。
nil channel パターン
nil channel とは単純に channel の変数が nil になっている状態です。
この状態で select の case で read/write すると、ブロックされます。 case に channel を置く場合は read/write できたタイミングでヒットするため、ブロックしたままヒットしないということはその case が実質無視されるようなイメージになります(panic にはならないのがポイントです)
つまり、 select の前に channel をセットアップする段階で、実行したくない case があったらそこを nil にすればよく、実行したい場合は適切な channel で初期化しておけばよいです。
今回の場合は、スライスの中身で分岐したいので以下のようになります。
for { var first string var result chan string if len(buffer) > 0 { first = buffer[0] result = p.result // ここを通らないと nil } select { case <-interval: body, err := Get(p.url) // err の方は単なる代入 // buffer に結果を追加 buffer = append(buffer, body) case result <- first: // result が nil だと実行されない buffer = buffer[1:] } }
もし buffer が空だと、 result が nil なので result <- first の部分がブロックし、panic にはなりません。
buffer 肥大対応
buffer スライスを導入したために、クライアントの読み出しが遅かった場合は buffer に値がたまりつづけてメモリを食い尽くすリスクが出ます。
そこで、 buffer の最大値を決めておき、それを越えた場合は GET しないように変更します。
これも nil channel パターンをつかうことで解決できます。
const maxBuffer = 10 for { var first string var result chan string if len(buffer) > 0 { first = buffer[0] result = p.result // ここを通らないと nil } var interval <-chan time.Time if len(buffer) < maxBuffer { interval = time.After(1 * time.Second) // インターバル } select { case <-interval: // Get を呼ぶだけ body, err := Get(p.url) // err の方は単なる代入 // snip buffer = append(buffer, body) case result <- first: // result が nil だと実行されない buffer = buffer[1:] } }
buffer のサイズが maxBuffer を越えない場合は、 interval が nil のまま設定されないため、 Get() を呼び出す部分の case が実行されません。
Get の非同期化
Get() は同期ネットワーク I/O を伴います。
取得に時間がかかるとそこでブロックしてしまうため、これを非同期にすることでブロックしないようにすることが望ましいです。
そこで、 Get を goroutine 内で実行し channel 経由で結果を返すようにします。
返した結果は別の select で受信します。受信自体は一度に 1 つにするため channel には buffer を 1 と指定し、ここまでと同様 nil channel パターンを使います。
まず Get の結果を詰め込む構造体を定義します。
type getResponse struct { body string err error }
次に、それを渡す chennel です。この channel が使われていない時だけ interval を回し、 Get を goroutine で実行します。
取得結果の処理は別の case になります。
// 定期的な取得をするループ func (p *Pooling) Loop() { var response chan getResponse for { var interval <-chan time.Time if response == nil && len(buffer) < maxBuffer { interval = time.After(1 * time.Second) // インターバル } select { case <-interval: response = make(chan getResponse, 1) go func() { body, err := Get(p.url) // err の方は単なる代入 response <- getResponse{body, err} }() case res := <-response: response = nil // 次のループのために nil に戻す // buffer に結果を追加 buffer = append(buffer, res.body) case result <- first: // result が nil だと実行されない buffer = buffer[1:] } } }
こうして、最初にあげた問題はすべて解決しました。
nil channel によってループの中での実行タイミングを制御していることがわかります。
まとめ
Google I/O 2012 の Go Concurrency Patterns by rob pike では、 goroutine や channel の強力さなどが重点的に説明されていましたが、今回の発表では Select-Loop の強力さにフォーカスしており、非常に実践的な内容でした。
今回できたようなパターンを使うと、処理を非同期にし、メッセージングによってレースコンディションを無くした並行処理が実装ができるようになります。
Select で channel を read/write するのは、結局は イベントループとイベントドリブンなプログラミングパラダイムを自分で実装しているようなイメージで、 Node.js なんかでやっているのと基本的には同じです。
今後は Node.js でのイベントドリブンのノウハウ(Stream とか)も踏まえて、 Goroutine をより上手く扱えるように研究を重ねたいと思います。
Web+DB Press vol.75 で SPDY/HTTP2.0 特集を書かせて頂きました
intro
タイトルのとおり、 Web+DB Press の vol.75 に
Web をより速くする次世代プロトコル!!［速習］SPDY & HTTP/2.0
というタイトルで特集記事を書かせていただきました。
- 作者: 栗林健太郎,柴田博志,はまちや2,常松伸哉,黒田良,川添貴生,安宅啓,松下雅和,桑野章弘,Jxck,伊藤直也,佐藤鉄平,登尾徳誠,中川勝樹,奥野幹也,近藤宇智朗,堀江幸紀,後藤秀宣,渡邊恵太,中島聡,A-Listers,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2013/06/22
- メディア: 大型本
- この商品を含むブログ (8件) を見る
SPDY 特集
本特集は、 Make the Web Faster という取り組みの一貫として、Google が開発している、新しいネットワークプロトコル SPDY について書いています。章立ては以下のようになっています。
第1章：次世代プロトコルSPDY: GoogleがしかけるWebの高速化プロジェクト
第2章：SPDYの仕様と周辺ツール: プロトコルを知り，使いこなそう
第3章：SPDYの導入方法: 自分のサイトをSPDY対応するには
第4章：そしてHTTP/2.0へ: 見直される標準仕様とSPDYの影響
内容
今回、特集を通して解説する SPDY のバージョンは SPDY/3 です。
1章
SPDY のモチベーションを知るために HTTP とその下の TCP についておさらいします。
つまり、ネットワークプログラミングの基礎的な部分の話ですね。
すると、現在の Web の状況と照らしあわせた時にボトルネックが見てきます。
それを踏まえて、 SPDY はそれらをどう改善しているのか？という切り口で解説しました。
2章
SPDY のプロトコル仕様をより詳細に解説します。
フレームの簡単な構造と、それらが実際にやり取りする様を Spdylay という SPDYer(?) 必携ライブラリに付属する Spdycat というツールを用いて可視化しながら解説します。
3章
「自分のサイトを SPDY に対応する」というテーマで、 Apache mod_spdy, Nginx, node-spdy の 3 つの導入方法を解説します。mod_spdy と node-spdy は Server Push にも対応しているため、その設定方法についても触れています。
また、 SPDY にすれば必ず早くなるとは限らないため、 SPDY に対応するにあたり考慮すべき点などのノウハウについても、現在わかっている範囲で解説しています。
4章
去年 IETF で策定が開始された、 HTTP の次世代規格 HTTP/2.0 (draft-0 から draft-1 くらいまで)の解説です。
HTTP/2.0 は最初のドラフトに SPDY/3 が採用され、また後続の仕様議論にも SPDY/3 が大きく影響を与えているため、
この二つは非常に重要な関係にあります。
そこで、 SPDY/3 には解説を踏まえた上で、なぜ SPDY が選ばれ、HTTP/2.0 はどういう方向に進んでいるのか、両者の立ち位置はどう観るべきなのか、などといった点を現時点で筆者が把握している範囲で書きました。
今後
現時点でも SPDY は SPDY/4 が、 HTTP/2.0 は draft-3 あたりが進んでいます。
IETF も interim がありましたし、その意味ではこの雑誌が出る時点で「最新」ではない話も含まれているのが正直なところです。
しかし、これは同時に SPDY, HTTP2 の発展が早く、議論が盛り上がっていることを意味しており、それは最初から想定していました。
なので、今回の特集では SPDY や HTTP2 が「何がしたいのか？」というモチベーションの部分に注目することを意識したつもりです。
この特集を読むことで、「ここまで」を把握して、興味があれば「これから」を追いかける上で、土台となるような記事になれば幸いです。
謝辞
かなりの遅筆になってしまい、担当の稲尾さんには終始迷惑をかけまくってしまいました。
最後まで根気強く付き合って頂いたおかげで、この記事はあります。感謝してもしきれません。
また、自分の追いきれていない知識について、的確なツッコミを入れて下さったレビュアーの方々にも、非常に感謝しています。
みなさま本当にありがとうございました！
まとめ
このブログを見てくださる方々は、定期的に買っている方が多いかもしれませんが、Web+DB Press は、今月も自分の以外にも面白そうな記事が多いです。
その中の 1 つとして、是非読んでみて頂けるとありがたいです。
フィードバックも歓迎します。よろしくお願いいたします。
おまけ
同日に Web+DB Press の総集編が発売されます。
vol.1 - vol.72 までが収録されており、豪華な執筆陣による書きおろし記事もあります。
(ちなみに vol.71 には、自分も共著で書かせていただいたい WebSocket 特集もあります。)
合わせてどうぞ !!
WEB+DB PRESS 総集編〔Vol.1~72〕 (WEB+DB PRESS plus)
- 作者: 伊藤直也,外村和仁,長野雅広,松信嘉範,渡辺修司,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2013/06/22
- メディア: 大型本
- この商品を含むブログ (7件) を見る
