I/O モデル基礎

3 つの主張、それぞれに数字と、手で動かせる図がついている。ブロックしたスレッドはカーネルメモリ 25.5 KiB と 1.3 µs のスイッチ 2 回を要求する。準備通知は O(n) を O(ready) に変える —— すべてが準備完了になった瞬間から助けにならない。完了モデルは操作ごとの syscall を消す。バッチ 1 では無価値、32 で 2.6 倍だ。

待ち時間と、その請求書

あらゆる I/O 呼び出しは、答えを待つか、待つことを拒むかのどちらか。このページのリングも準備通知も複写も、すべてこの分岐から生えている。

ソケットの read は 2 つの仕事をする。バイトが受信キューに入るまで待ち、コピーして出す。コピーは数マイクロ秒の正直な仕事だ。待ちには上限がなく、それが設計問題そのものだ。

だからまず待ちそのものを見る。スライダを動かして最初のバイトが着く時刻をずらし、走っていないスレッドがそこまで伸びるのを見てほしい：

read() 406 µs · CPU の外 397 µs · 退避 + 復帰 2 × 1.3 µs

注目してほしいのは、退避している区間でカーネルが何かをしているわけではないことだ。初期設定での 406 µs のうち、6 µs がコピーで、400 µs は何もない。しかもスレッドはそこで眠るためにコンテキストスイッチを 2 回、2.6 µs 払っている。

ノンブロッキングは、同じ呼び出しから待ちを削ったものだ。モードを切り替えると syscall はただちに EAGAIN で戻り、スレッドの手元に残る時間は、さっきまで退避していた区間とぴったり同じになる：

ブロッキング · read() 406 µs · CPU の外 397 µs · 退避 + 復帰 2 × 1.3 µs

モードの切り替えが実際に変えたものを見てほしい。データも、ソケットも変わらない。変わったのはその空白を誰が持つかだけだ。ブロッキングはそれをカーネルに渡して単純さを受け取る。ノンブロッキングは抱える。そしてカーネルが答えていた問い —— このディスクリプタはいつまた尋ねる価値があるのか —— を背負う。

書きやすいからといってブロッキングが無料になるわけではない。待っている接続はそれぞれ自分のスレッドを要り、1 本につきカーネルスタック 16 KiB と task_struct がつく。接続数を上げて、この固定費を見てほしい：

1,000 スレッド · カーネル 25 MiB · アドレス空間 7.8 GiB · 1 本あたり 34 KiB

なら、1 バイトも動かないうちにカーネルメモリ 249 MiB、さらに glibc 既定の 8 MiB スタックが予約するアドレス空間 78 GiB ——実体があるのはハンドラが触れたページだけだ。まで押し上げるとスレッド群はスワップできないカーネルメモリを 2.4 GiB、ユーザページ込みで 3.2 GiB —— 16 GiB の機械の 5 分の 1 を要求する。この 25.5 KiB は見積もりではなく数えた値だ。16 KiB は x86-64 の THREAD_SIZE、カーネルスタック 4 ページ分。9.5 KiB は 6.x カーネルの /proc/slabinfo が task_struct スラブについて報告する値だ。

メモリは見える請求書だ。隠れているほうはスイッチで、スケジューラと冷えたキャッシュで 1.3 µs、イベントごとに 2 回かかる。イベント率を上げて、曲線が「まるごと 1 コア」の線を横切るところを見てほしい：

21K/s イベント

スイッチ 42K/s · コアの 5.4%

スイッチ 2 回が 2.6 µs なので、交点は —— ベンチマークなら 1 接続でも届く量だ。そこを超えると 1 コアがレジスタの入れ替えに消え、アプリ側のどんな調整もそこには届かない。

ノンブロッキングだけでは解けない。待つ先のないループは尋ね直すしかないからだ。尋ね直す間隔を詰めて、2 本の棒が互いを押し合うのを見てほしい：

EAGAIN 954K/s · コアの 24% · 平均遅延 52 µs

このスライダの両端はどちらもサーバではない。ではループがコアの 125% を燃やして EAGAIN を返し、では平均 2.5 ms の遅れで答える。足りないのは「教えてもらう」経路であり、次の節はその 1 つの発想の 25 年史だ。

1 スレッド、たくさんのソケット

準備通知とは、1 スレッドが数千のディスクリプタについて 1 つの問いをカーネルに一度で投げることだ。3 世代がそれに答えてきた。

select は 1983 年に 3 枚のビットマップで答えた。気にするディスクリプタごとにビットを立て、カーネルが準備できたビットを立てて返し、こちらが走査する。ビットマップは固定長の構造体で、面倒はそこから始まる：

ディスクリプタ 900

ディスクリプタ 900 · 113 B × 3 集合 × 往復 2 回 · 1 回あたり 678 B

マーカーをドラッグしても、何も文句を言わない。FD_SET は境界検査のない配列マクロなので、末尾を越えたディスクリプタは呼び出し側がスタックに次に置いたものへ書き込む。呼び出し時にエラーも異常終了もなく、ただ壊れたローカル変数が後で別の場所で牙をむく。

poll は呼び出し側が大きさを決める配列で上限を外し、本当のコストはそのまま残した。監視集合とそのうち準備できている数を突き合わせ、カーネルが取り得た 2 通りの歩き方を読んでほしい：

select 1,000 個 · 準備完了 10 個 · 無駄 990 個 · epoll 10 個

1,000 個を監視して 10 個が準備完了なら、カーネルの 1,000 回の点検のうち 990 回は何も言うことのないディスクリプタに費やされる。そのあとユーザ空間が同じ配列をもう一度歩いて、どの 10 個かを探す。どちらも O(n) —— n は集合の大きさであって、答えの大きさではない。

epoll（Linux 2.5.44）が変えたのは 1 点だけだ。集合がカーネルに残る。再生ボタンで 3 つの syscall を進め、それぞれで何が返るかを見てほしい：

4 ステップ中 1 —— epoll_create

関心リストが登録されたままなので、起床は集合を描き直す必要がない。報告するのは実際に発火したディスクリプタだけだ。これで買える不変条件は正確に書く価値がある。ループの各周回の先頭で、すべてのディスクリプタはカーネルの関心リストにあるか、ループが今読み切っている準備集合にあるかのどちらかだ。どちらにもないものは、見えない。

集合をカーネルに残すことは、epoll がディスクリプタ番号どおりに振る舞わなくなる場所でもある。関心リストが鍵にするのは整数ではなくオープンファイル記述だ。dup と、登録した番号の close を 1 歩ずつ進めてほしい：

エントリ 1 · 記述に紐づく

エントリがディスクリプタより長生きすることに注目してほしい。閉じたはずのソケットにイベントが届き続け、閉じた番号への EPOLL_CTL_DEL は EBADF を返す ——登録したものを名指す手段がもう無い。fork は同じ罠の裏側で、子が epoll fd を継ぐので同じソケットで両方のプロセスが起こされる。閉じる前に必ず削除すること。

集合の大きさではなく答えの大きさで数えるのは、定数の改善ではなく別の曲線だ。監視集合を大きくして、2 本の線が離れていくのを見てほしい：

1,000 個を監視

監視 1,000 · 準備完了 10 · 25 µs 対 500 ns · 51×

で 1% が準備完了なら、1 起床は 250 µs 対 2.8 µs —— 91 倍だ。ところが 2 本目のスライダを上げると差は詰まる。50% が準備完了なら epoll もほぼ同じ距離を歩く。すべてが準備完了なら O(ready) と O(n) は同じものだからだ。

共有された 1 本のディスクリプタも同じ壊れ方をする。リッスンソケットを n 個のワーカプロセスに登録し、ワーカ数を上げながら、届いた接続 1 本の下で EPOLLEXCLUSIVE を切り替えてほしい：

ワーカ 8 · 起床 8 · 無駄 7 · 18 µs を消費

フラグが無ければ待っている全員が起こされる。accept を取れるのは 1 つだけで、残りは EAGAIN を受け取って眠り直す —— どれもコンテキストスイッチを 2 回、無駄に払っている。これが accept のサンダリングハードで、EPOLLEXCLUSIVE（Linux 4.5）は 1 つだけを起こす。レベルトリガ専用で、万能でもない。実際にスケールするのは SO_REUSEPORT —— ワーカごとに自分の accept キューを持たせるほうだ。

epoll は答えを 2 つの形で出し、片方は罠だ。レベルトリガはまだ読めるものをすべて報告し、エッジトリガは「到着した」ことを 1 度だけ報告する。1 回に読む量を減らし、モードを切り替えてほしい：

レベルトリガ · 起床 1 回 · 取り残し 0 B

16 KiB 読みでのエッジトリガを見てほしい。48 KiB がソケットに残り、ループは退避し、すでに届いているバイトについての起床はもう来ない。接続はぶら下がったままで、ログは何も言わない。これがこの節全体の失敗様式だ ——どちらのリストにもないディスクリプタが不変条件を破り、しかも静かに壊れる。

尋ねるのをやめて、渡してしまう

epoll はディスクリプタが準備できたと教えるだけで、仕事は自分で、1 つずつ syscall を呼んでやる。io_uring は後半を消す。

1 バッチの準備完了操作が越える境界の回数を数える。KPTI が有効なら 1 回 250 ナノ秒。準備通知のループは起床で 1 回、さらに操作ごとに 1 回払い、リングはバッチ全体で 1 回だけ払う：

32 操作 · 越境 32/33/1 回 · 1 操作 2.9 µs/339 ns/129 ns

のとき 3 つのモデルはほぼ同じ値 —— 1 操作あたり 2.9 µs、3.1 µs、2.9 µs —— になる。起床の前後にある 2 回のコンテキストスイッチが他を圧倒するからだ。効いているのは仕組みではなくバッチで、32 なら io_uring は 1 回、epoll は 33 回を払う。1 行目は 2 度読む価値がある。残り 2 行が比較される前提だからだ。接続ごとに 1 スレッドには、そもそもバッチが無い。32 の準備完了操作は 32 本のスレッドで、それぞれが起こされ、それぞれがまた退避する。だから 2 回のスイッチはバッチ単位ではなく操作単位で課金される —— 越境を 1 回多く払う epoll が 339 ns なのに、こちらが 1 操作 2.9 µs になるのはそのためだ。

その差は共有メモリで買っている。提出リングは両方のアドレス空間に同時に写像されるので、要求を書くのはストアであって呼び出しではない。tail をリングに沿ってドラッグしてほしい：

0 件を積んだ。tail をリングに沿ってドラッグする。矢印キーで 1 スロットずつ、Home で空にする

tail 0 · head 0 · 0 件が待機 · システムコール 0 回

読み出しに注目してほしい。エントリは積まれているのに、syscall はまだ 1 回も起きていない。効くのは 2 つの添字だけ —— 自分が進める tail とカーネルが進める head —— で、その差が占有量だ。まで押せばリングは満杯になり、提出はカーネル待ちになる。これがこのモデルの最悪の単発操作だ。

1 周は 4 拍で、境界を越えるのは 1 拍だけだ。再生ボタンで進めてほしい：

4 ステップ中 1 —— エントリを書く

完了も写像済みメモリに戻ってくるので、回収もまたロードで済む ——真ん中の 1 回の越境が請求書のすべてだ。これが準備から完了への転換だ。何が準備できたかを尋ねるのではなく、仕事を記述して終わったと告げられる。epoll が扱えなかった通常ファイルを io_uring が扱えるのも同じ理由による。

その 1 回すら消すモードがある。IORING_SETUP_SQPOLL を付けるとカーネルスレッドがリング上でスピンし、越境そのものが起きなくなる。ポーラを入れて、その値段を読んでほしい：

io_uring_enter 7.0K/s · コアの 0.2%

2 本の棒を同時に見てほしい。アプリの境界負担はゼロになり、まるごと 1 コアがリングの忙閑にかかわらず押さえられる。Jens Axboe の 2019 年の論文は同じデバイスでこの経路の 170 万 IOPS を、libaio の 60.8 万に対して測った —— 2.8 倍は本物で、その代金は 1 コアの賃料だ。

バイトを動かす

どのディスクリプタが準備できたかを知っても、中身を動かす値段は何も分からない。その請求はメモリ帯域で支払われる。

ページキャッシュのファイルをソケットへ出すのは、バッファへの read とバッファからの write だ。再生ボタンで 1 チャンクを進め、中身が実際にどこを通るか見てほしい：

5 ステップ中 1 —— read()

1 歩目でバイトはすでにカーネルにあり、4 歩目でまたカーネルに戻ることに注目してほしい。ユーザバッファはこのデータに要らなかった往復で、その片道ずつが CPU がメモリ帯域で 1 語ずつ運ぶ作業だ。

カーネルの各インタフェースは、この片道をちょうど 1 本ずつ削る。スライダをループから MSG_ZEROCOPY まで歩かせ、CPU が通らないホップが入れ替わりに現れるのを見てほしい：

read + write · CPU コピー 2 回 · システムコール 2 回 · CPU が 128 KiB

sendfile はユーザバッファを消し、ページキャッシュがソケットへ直接流し込む。コピーは 2 回から 1 回、syscall も 2 回から 1 回。スキャッタギャザ DMA を足せばカードがページキャッシュを自分で読み、CPU は中身に一切触れない。nginx が静的ファイルを配るのはこの経路だ。

そこに大きさを与える。1 コア 10 GB/s としてファイルを大きくし、3 枚の請求書を読んでほしい：

100 MiB · CPU 22 ms / 11 ms / 401 µs · システムコール 3,206 回

100 MiB のファイルは、ループなら CPU 22 ms、sendfile なら 11 ms、スキャッタギャザなら 401 µs —— 54 倍で、そのほとんどがコピーだ。3,206 回の syscall は合計 0.8 ms にすぎない。この大きさでは境界は雑音で、帯域がすべてになる。しかもこの 54 はドラッグしても動かない。中の項がどれもバイト単位だからで、変わるのは請求額のほうだけだ。

だからこそ小さなメッセージでは逆転する。メッセージを縮めて、2 本の線が交わるところまで持っていってほしい：

64 KiB

64 KiB · write 6.8 µs · MSG_ZEROCOPY 1.6 µs

MSG_ZEROCOPY はページをピン留めし、ソケットのエラーキューから完了を回収しなければならないので、小さなメッセージでは償却しきれない固定の 1,650 ns を背負う。交点は 13.7 KiB で、カーネル文書が言うおよそ 10 KiB に近い —— それ未満ではゼロコピーは省いたコピーより遅く、では 1.3 µs 遅い。

それぞれが本当に勝つ場所

3 つのモデル、3 本の軸。どれもどこでも最速ではなく、議論を決める 2 本は速さと関係がない。

1 本目の軸はメモリだ。epoll の登録は約 200 バイト、スレッドは決してスワップも縮小もしないカーネルメモリ 25.5 KiB。

接続数を増やし、1 接続 1 ディスクリプタの線が、離れて登っていく線の下で平らなままなのを見てほしい：

1,000 接続

1,000 接続 · 25 MiB 対 200 KiB 対 125 MiB · 128×

比は 128 倍で平らなまま、噛みつくのは絶対値だ。でスレッドは 249 MiB を要求し、2.0 MiB 側と並ぶ。C10K は 1999 年には名前のついた問題で、いまはそうではない。解決は速いスレッドではなく、スレッドを持たないことだった。

上限を決めるのは色のついた 2 本ではない。ここが用意しておくべき追問だ。その上を走る灰色の線がソケットバッファで、Linux の tcp_rmem の既定は 4 KiB / 128 KiB / 6 MiB。どちらのモデルも接続ごとに払う。1 万本なら受信バッファだけで 1.2 GiB ——スレッド分の 5 倍だ。スレッドを捨てて買えるのは下の軸で、この軸ではない。

2 本目は誰もが飛ばす軸だ。イベントループは 1 スレッドなので、その中でブロックするものは全員をブロックする。ブロッキング呼び出しをゼロから引き出してほしい：

後ろに 199 接続 · 停止 0 ns · p99 に +0 ns

ループは自分を横取りできないので、準備できていた残り 199 接続は呼び出しをまるごと待たされる —— の getaddrinfo は、その全員の p99 に乗る 10 ms だ。goroutine も同じ形をしている。ランタイムは知っている I/O では epoll に退避させ、知らないものではカーネルスレッドを固定する。

3 本目の軸は使えるかどうかだ。io_uring は最速で最も使えない。Docker の既定 seccomp は io_uring_setup を塞ぎ、6.6 以降には kernel.io_uring_disabled がある。まず epoll の道を書くこと。

早見表

そらで答える価値のある 3 問、実際に出荷されるバグ、そしてレビューで止めるべき 5 つ。

io_uring は速いのか？

まとめて出す場合だけだ。まとめて提出する操作数を決め、1 コアが境界の仕事だけで支えられる天井を読んでほしい：

32 件のバッチ · 351K/s / 2.9M/s / 7.7M/s · 22×

なら 3 本の棒は同じ長さ —— どれも毎秒 32 万から 35.5 万 —— になる。2 回のコンテキストスイッチが支配するからだ。32 なら完了モデルが 770 万、290 万に対して伸び、接続ごとに 1 スレッドは動かない。まとめられるものが何もないからだ。

この節が本当に扱っているバグは何か。

エッジトリガの epoll は「届いた」ことを 1 度しか報告しない。ハンドラが read を 1 回だけして戻ると、入りきらなかった分はソケットに残り、それについての起床はもう来ない。64 KiB が 16 KiB のバッファに一度に届けば、下の上の行は 48 KiB を永久に取り残し、下の行は EAGAIN まで読み切る：

/* EPOLLET, one read: 48 KiB stranded */
n = read(fd, buf, sizeof buf);

/* correct: drain until EAGAIN */
while ((n = read(fd, buf, sizeof buf)) > 0)
  handle(buf, n);

上の 1 行が出荷されるバグだ。合法な C で警告も出ず、相手がバッファ 1 つ分より少なく送るすべてのテストで正しい。オーバーヘッドは隣の仕事と並べて初めて議論になるので、1 リクエストがする仕事を決めてほしい：

20 µs の仕事 · オーバーヘッド 12% / 1.7% / 0.6% · 19×

20 µs の仕事 —— キャッシュ参照や小さな解析 —— では接続ごとに 1 スレッドがリクエストの 12% をオーバーヘッドに使い、0.64% で済む側と並ぶ。まで引き出せばどのモデルも 0.3% 未満だ。自分のチームが午前 3 時にデバッグできるほうを選べばいい。

epoll はなぜ poll より速く、どんなときに速くないのか？

poll は二重に O(n) だ。カーネルが配列全体を歩き、こちらのループも歩く。epoll は集合を登録したままにし、発火したものだけを返す。毎回の起床で集合の大半が準備完了なら、それは同じ歩みだ —— 2 つのコストを 1 本の軸で読み、軸の上限はもう一方の手に預けてほしい：

システムコール、KPTI オン · 250 ns

覚えるべき段差は 250 ns の syscall 対で 5.2 倍。どのモデルも結局は「切り替えない」戦略だ。64 KiB のコピーは 6.55 µs で、そのどれよりも大きい。

数字の出どころ。

250 ns と 60 ns は Gregg 2018、1.3 µs は lmbench 型 ping-pong、10 GB/s は DDR4-3200 の 1 コア、170 万対 60.8 万 IOPS は Axboe の論文。25 ns/fd と 40 ns/エントリは推算で、図の軸にもそう書いた。

新しいコードの select。FD_SETSIZE は 1024 で、マクロはそれを検査しない。
読み切りループのないエッジトリガ。静かなデータ喪失。測った理由がないならレベルトリガを使う。
イベントループ内のブロッキング呼び出し。DNS、ファイルの open、ロック —— 準備できた接続全員が支払う。
静的ファイルを read と write で配る。コピー 2 回、syscall も 2 倍。sendfile なら 1 行だ。
小さなメッセージへの MSG_ZEROCOPY。およそ 10 KiB 未満ではピン留めのほうがコピーより高い。