kqueue

柔らかプログラマを受けつつ、90年代の話。OS開発や基盤ソフト開発の楽しみというか、API designの勝利、ということで大好きなkqueueの話がある。この論文を参照。これはBSDで起きた発明で、Linuxだとepollというセクシーじゃない名前になっている(ちょっと残念)んだけど、説明してみよう。

ファイルディスクリプタ

UNIX系のOSではデータの塊にアクセスする際にファイルディスクリプタという数値のシンボルを使い、ネットワークプログラミングでも利用される。ファイルディスクリプタ自体も様々なI/Oを抽象化する発明だけども、データの待ち受け方が当時は問題になっていた。

古き良きselect/poll

ファイルディスクリプタが一つでスレッドも一つならread()を出してカーネル待ちをしていればよいがファイルディスクリプタの数が増える、つまり同時に接続されるコネクションの数が増えると困ることになる。
ファイルディスクリプタの数だけスレッドを立てるような形だとCPUキャッシュ的にもスケジューラ的にも嬉しくない。
古き良きUNIXではselect/pollという関数でまとめてデータを待つ。ユーザはデータの到着を知りたいファイルディスクリプタの一覧をまとめてカーネルに伝えるとカーネルはそのうちどれかのデータがreadyになった時点でユーザに制御を返す。
自分なんかは何の疑問もなくこの関数を使っていたが以下の問題があった。

"selectではビットマップ、pollでは配列をスキャンする"

簡略化するとこんな感じになる

1. ユーザは待ち受けたいファイルディスクリプタの一覧を作る
2. カーネルに一覧を渡す
3. カーネルは一覧を元にどのスレッドが待ち受けているかデータ源に対してエントリ
4. スレッドはデータが来るまで寝る
5. 待ち受けでデータが来たらカーネルはスレッドを起こす
6. 起きたら他にデータが来ていないか一応確認し、ユーザに渡す一覧を作る
7. ユーザは一覧を受け取ったら一覧をスキャンしながらデータを処理する

データ到着前、データ到着後、データ処理前の都合3回スキャンすることになる(設定含めると4回かも？)。また、実装上、毎回カーネルとユーザ間で長めのコピーが起こる点も見逃せない。

ディスクリプタが数個の時はいいが数百個以上待ち受けるようになると、色々とサービスがスケールしない一因がselect/pollだった。クライアント一万台問題(C10Kproblem)ってやつである。

由緒正しいんだけども。

kqueue

kqueueは大体こんな感じで動く。

1. ユーザはカーネルに待ち受けたいファイルディスクリプタを教える
2.カーネルはファイルディスクリプタの示すデータ源とスレッドの持つキュを結びつける
3.データが来たらデータ源は”データが来た”ことをキューに詰める
4.カーネルはキューの先頭に積まれている情報をユーザに返す

最初に待ち受け情報を登録すると後はデータが来るたびにキューイングされてユーザに情報が伝わる。スキャンする必要はなく、readyになった順にデータが処理されていく。

マルチスレッドになってもキューから順次情報が提供される。selectで問題になっていた点が綺麗なアイデアで解決されている（論文参照）。また、登録に工夫するとこでファイルデスクリプタでシグナルや他のありとあらゆるイベントを同時に待ち受けるということも可能にした。

結果、ワンアイデアで以下を達成したことになる。

- 不要なスキャンを減らす
- コピーを減らす
- データ以外も同時に待ち受ける

伝統的APIからを根本から再設計したことがC10K問題解決への大きな一歩だった。ここまでの研究ではみんな内部実装の改善ばかり考えてたわけで。

今となっては普通に使われるのだろうけども、アイデアを見た時に衝撃を受けたのを覚えている。

こんな風にAPIを切るのがプラットフォーム屋の夢の一つだろう。滅多に起きないけども・・・

というわけで愛してやまないkqueueの昔話でした。