ネットワークプログラムのI/O戦略

図解求む。

以下「プロトコル処理」と「メッセージ処理」を分けて扱っているが、この差が顕著に出るのは全文検索エンジンや非同期ジョブサーバーなど、小さなメッセージで重い処理をするタイプ。ストリーム指向のプロトコルの場合は「プロトコル処理」を「ストリーム処理」に置き換えるといいかもしれない。

シングルスレッド・イベント駆動

コネクションN:スレッド1。epoll/kqueue/select を1つ使ってイベントループを作る。
マルチコアCPUでスケールしないので、サーバーでは今時このモデルは流行らない。
クライアントで非同期なメッセージングをやりたい場合はこのモデルを使える:

  1. サーバーにメッセージを送信
  2. イベントハンドラを登録;このときイベントハンドラのポインタを取っておく
  3. イベントハンドラ->フラグ がONになるまでイベントループを回す
  4. イベントハンドラ->結果 を返す

1コネクション1スレッド

コネクションN:スレッドN。accept(2)またはconnect(2)するごとに新しいスレッドを立て、ソケットを閉じたらスレッドも終了する。
プロトコル処理もメッセージ処理もスレッドを1本占有してコールスタックを切らずに書けるので、コードの見通しが良くなる。
コネクションが増えるとスレッドも増えるので、いわゆるC10K問題にハマる。メッセージを送るたびにコネクションを張り直すプロトコルだと、スレッドを作る遅延が無視できない。スレッドをプロセスにしても同じ。
Webサーバーには本当に向いてない、と言うか何でコレにするかワカラン*1

スレッドプール

コネクションN:スレッドM。epoll/kqueue/select を1つ使ってイベントループを作る。重いタスクはスレッドプールに投入して実行する。
サーバーで良くあるパターン。イベントハンドラプロトコルを解析してメッセージを切り出し、メッセージをスレッドプールに投入する。
イベントハンドラはシングルスレッドで動くので、プロトコル処理が重いとマルチコアCPUでスケールしない。メッセージの処理が非常に軽いプログラムの場合、スレッドプールに投入 -> コンテキストスイッチ する遅延が無視できないことがある。
スレッドプールにタスクを投入する典型的なデータ構造はBlockingQueue。

マルチスレッド・イベント駆動(scatter方式)

コネクションN:スレッドM。それぞれのスレッドで epoll/kqueue/select を作り、accept(2) または connect(2) したソケットを各スレッドに振り分ける。スレッドの数はCPUのコア数に応じて固定にするか、負荷に応じて数を変えるなど。
スレッドプール方式と違ってメッセージを処理するときにコンテキストスイッチが発生しない。
プロトコル処理もメッセージ処理もスレッドを1本占有して書ける…と思いきや、あるソケットに届いたデータを処理している間は、そのスレッドに割り振られた他のソケットに届いたデータは処理されないので、イベント駆動にしないとスケールしない・遅延が増える。
メッセージ処理だけでもコールスタックを切らずに書きたい場合は、次のスレッドプールを組み合わせる方法を使う。

マルチスレッド・イベント駆動(scatter方式)+スレッドプール

コネクションN:スレッドM。それぞれのスレッドで epoll/kqueue/select を作り、accept(2) または connect(2) したソケットを各スレッドに振り分ける。イベントハンドラプロトコルを処理してメッセージを切り出し、メッセージをスレッドプールに投入する。
メッセージ処理は書きやすいが、プロトコル処理はイベント駆動でしか書けない*2。メッセージ処理もあまりに長くブロックするとスレッドが足りなくなる可能性がなきにしもあらず。それなら1コネクション・1スレッドでもいいような。
スレッドプールにタスクを投入するときにコンテキストスイッチが発生するので、軽いメッセージが大量に届く用途だとコンテキストスイッチの遅延が無視できないことがある。
あとコード量が増える。次のwavy方式と比べるとスレッド数が無駄に増える。
※2009-07-13 追記:
nginx-0.7.x はこの方式(スレッドの代わりにプロセス)。親プロセスがaccept(2)してworkerプロセスにファイルディスクリプタを振り分けるのではなく、workerプロセスが早い者勝ちでaccept(2)する。このためファイルディスクリプタは必ずしも均等には分散されず、タイミングによって1つworkerプロセスに偏ったりする。しかしその方がaccept(2)周辺の負荷や遅延は小さいため、コネクションを細かく切ったり張ったりするケースではおそらく有効。
プロセス間でファイルディスクリプタを転送するのは移植性があまり高くない(Mac OS Xの実装が壊れ気味)という事情もあるかもしれない。
See also:prefork サーバーと thundering herd 問題, Thundering Herd のやつ

マルチスレッド・イベント駆動(wavy方式)

コネクションN:スレッドM。それぞれのスレッドでイベントループを作るが、1つの epoll/kqueue/select を共有する。当店オススメの方式w
プロトコル処理もメッセージ処理もスレッド1本占有して書ける。ただスレッドプールと同様にあまりに長くブロックするとスレッド数が足りなくなるので、基本的にはイベント駆動にした方がスケールする。メッセージ処理のたびにコンテキストスイッチが発生することはない。
イベントループの実装が難しい。実装方法は mp::wavy::coreimpl::operator() を参照。
詳しくは マルチコア時代の高並列性IOアーキテクチャ Wavy(Fiberのくだりは使えないのでスルーで)

Fiber方式

他の方式とは一線を画するダークホース。
Cagra はシングルスレッド・イベント駆動で動作するコア部分で fiber をスケジューリングしていた。他のやり方もあるかもしれない。マルチスレッド・イベント駆動(scatter方式)で fiber をスケジューリングするなど。
実装例は mp::fiber など。たぶん5回くらい読み返さないと分からないほどに難解。複数の fiber にまたがる処理など、複雑な処理を書きたくなるとちょっとヤバい。
UNIX系のOSでは ucontext という関数を使って fiber を作る。しかし ucontext で作った fiber は、それを作ったスレッドでしか実行できないという相当に厳しい制限がある。あと Mac OS X では挙動がアヤシイ(と言うか完全にバグがある)ので、ucontext は直接使わずに Io libcoroutine のようなライブラリを使うと良い。
※2009-07-13 追記:ucontext がスレッドをまたげない件は要検証。

送信側の戦略

経験上、1つの epoll/kqueue/select でread待ちとwrite待ちの両方をサポートすると、コードが複雑になるので避けた方が良い。read待ち専用の epoll/kqueue/select とwrite待ち専用の epoll/kqueue/select を作るとシンプルに書ける。
read待ちとwrite待ちで別のスレッドにしても良いが、epoll/kqueue/eventport(selectはムリ)はネスト(epoll の中に epoll を入れる)ができるので、read待ちのイベントハンドラの1つとしてwrite待ちをする手もある。mp::wavyはその方式。mp::wavy::out がwrite待ち epoll/kqueue のイベントハンドラになっている。

イベント駆動型のプロトコルパーサ

プロトコル処理をイベント駆動で書けるとI/O戦略の選択肢が広がる。
memcachedプロトコルのストリームパーサ で少し書いたが、イベント駆動でプロトコルをパースするには「データを次々に投げ込んでいくと内部の状態が遷移していき、ゴールの状態にたどり着くとパース完了」というタイプのパーサが必要になる。バイナリプロトコルなら「ヘッダ部を受信中」と「データ部を受信中」の2つくらいしか状態がないので手で書いても良いが、テキストプロトコルだと凄まじく面倒なので Ragel を使うと書きやすい*3
ちなみにプロトコルを自作する場合は MessagePack を使っておくと、バッファリングまで含めて面倒を見てくれるストリームデシリアライザが付いているのでオススメw
:2009-06-24 追記


# 与太話:これら各種のI/O戦略をライブラリとして提供することを目的としてmpioライブラリを開発していたが、最近では mp::wavy を中心にした便利ライブラリになっており、今では ccf の中に取り込まれるに至っている。

*1:…たぶんHTTPのプロトコル処理がイベント駆動だと超書きにくい最悪のプロトコルだから。nginxとかmongrelとか次期lighttpdは、イベント駆動型のHTTPパーサを自前で作っている

*2:スレッドプールに投入するまでの処理をしている間は、そのスレッドは他のソケットを処理できないため。read可能になった段階でスレッドプールに投入すればプロトコル処理もスレッド1本占有して書けるけど…うーん、それもアリなのかなぁ。

*3:mongrelや次期lighttpdはragelを使ってHTTPのパーサを生成している。nginxはがんばってるなぁ。