Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

0. なぜサーバーは遅くなるのか — C10K 問題の再訪

1999 年、Dan Kegel が「C10K problem」を書いた頃、1 台のサーバーで 1 万 の同時接続を捌くのは不可能に見えた。当時の常識:

接続 1 つ = スレッド 1 つ。
1 万スレッド = スタックだけで 10GB (2MB x 10000)。
コンテキストスイッチの暴騰。
カーネルデータ構造の枯渇。

だが 2020 年代の今、nginx は 1 台で 100 万 の接続を捌く。何が起きたのか。本稿は 30 年にわたる Linux I/O インターフェースの進化を追う。1 行の read() の裏にある革命たちを。

1. Blocking I/O — 1970 年代の遺産

1.1 最もシンプルなモデル

char buf[1024];
int n = read(fd, buf, sizeof(buf));  // データが来るまでブロック

カーネルはそのスレッドを 待ち行列 に入れ、別のスレッドを実行。
データ到着時にスレッドを起こす。
プログラマから見れば同期式でコードが簡潔。

1.2 問題: 接続 1 つしか処理しないサーバー

while (1) {
    int client = accept(server_fd, ...);
    while (1) {
        int n = read(client, ...);
        write(client, ...);
    }
}

複数のクライアントを同時に受けられない。

1.3 スレッドプール — Apache prefork モデル

while (1) {
    int client = accept(server_fd, ...);
    spawn_worker(client);  // 接続ごとにスレッド/プロセス
}

利点: 直感的。
欠点: スレッド生成コスト、スタック (2MB x スレッド)、コンテキストスイッチ、1 万接続でシステム崩壊。

Apache の prefork MPM はこのモデルで、C10K の壁に正面衝突した。

2. Select — 最初の I/O 多重化 (1983)

2.1 「1 スレッドで複数接続を監視」

fd_set readfds;
FD_ZERO(&readfds);
FD_SET(fd1, &readfds);
FD_SET(fd2, &readfds);

int n = select(maxfd+1, &readfds, NULL, NULL, NULL);

1983 年 4.2BSD で導入。発想: 「複数の fd をまとめて監視し、どれかが準備できたら教えて」。

2.2 select の致命的な 3 つの限界

限界 1: FD_SETSIZE の上限 (1024)

fd_set は 1024 ビット固定。fd 1025 を SET するとスタックオーバーフロー。Linux でこれを上げるには glibc 再コンパイル が必要。

限界 2: O(n) スキャン

select は呼び出しごとに:

すべての fd ビットマップをカーネルへコピー。
カーネルが全 fd を走査して状態チェック。
結果ビットマップをユーザーへコピー。
ユーザーが再び全 fd を走査し準備できたものを探す。

1 万接続 x 毎回 1 万スキャン = 線形劣化。実際に活性なのが 1% でも 99% を毎回チェック。

限界 3: 呼び出しごとのビットマップ再設定

select は戻る際に fd_set を 上書き する。毎回の再設定が必要。

3. Poll — 同じ問題、違う包装 (1986)

3.1 struct pollfd の配列

struct pollfd fds[10000];
fds[0].fd = sock1; fds[0].events = POLLIN;

int n = poll(fds, 10000, timeout);

System V で導入。改善点:

fd 数の上限なし (配列サイズ次第)。
ビットマップの代わりに構造体配列 — 意味のあるエラーコード (POLLHUP, POLLERR)。
呼び出し後も events が保持 される。

しかし O(n) スキャン問題は残存。1 万接続で毎回 1 万スキャン。

4. Nonblocking I/O — ブロック回避の基礎

4.1 O_NONBLOCK フラグ

fcntl(fd, F_SETFL, O_NONBLOCK);
int n = read(fd, buf, size);
if (n == -1 && errno == EAGAIN) {
    // データなし、後で再試行
}

即座に返る。データが無ければ EAGAIN (または EWOULDBLOCK)。

4.2 select/poll + nonblocking の組み合わせ

これが Reactor パターンの原型。1 スレッドが複数 fd を監視し、nonblocking read で実際の I/O を行う。

5. Epoll — Linux の革命 (2002)

5.1 登場の背景

2000 年代初頭、C10K が現実に (ICQ, IRC, ゲームサーバー)。Linux 2.5.44 で Davide Libenzi が epoll を導入。

5.2 3 つの API

int epfd = epoll_create1(0);

struct epoll_event ev;
ev.events = EPOLLIN;
ev.data.fd = sock;
epoll_ctl(epfd, EPOLL_CTL_ADD, sock, &ev);

struct epoll_event events[64];
int n = epoll_wait(epfd, events, 64, timeout);
for (int i = 0; i < n; i++) {
    read(events[i].data.fd, ...);
}

5.3 なぜ O(1) なのか

fd 集合をカーネルが永続保持 (epoll_ctl で一度登録)。
イベント発生時にのみ カーネルが内部 red-black tree + ready list に追加。
epoll_wait は ready list だけを返す — 準備できたものだけ処理。

1 万接続のうち 100 個が活性なら 100 回だけ走査。select/poll が毎回 1 万回走査していたのと対照的。

5.4 level-triggered と edge-triggered

level-triggered (LT, 既定):

条件が真である限り通知し続ける。例: バッファにデータがある限り。
「一度に読み切らなくても次の epoll_wait で再通知」。
select/poll と互換の直感的モデル。

edge-triggered (ET):

状態変化時のみ通知。
「読めるようになった瞬間」1 度だけ。
EAGAIN が出るまで読み切る 必要あり。さもないと次の通知を取り逃す。
高性能だがコーディングが難しい。

// ET モードではこう書く
while (1) {
    int n = read(fd, buf, size);
    if (n == -1 && errno == EAGAIN) break;
    if (n <= 0) break;
    process(buf, n);
}

nginx は ET で極限の性能を引き出している。

5.5 EPOLLEXCLUSIVE — thundering herd の解決

複数スレッドが同じ listen socket を epoll に登録すると、accept 可能時に全員起きる。1 つだけ成功、残りは EAGAIN。無駄。

Linux 4.5+ の EPOLLEXCLUSIVE: 「この fd は 1 人だけに通知」。nginx, HAProxy が活用。

5.6 epoll の限界

依然としてシステムコールが多い: イベントごとに read, write。高性能域ではシステムコールのコストが支配的。
LT の余分なウェイクアップ: 処理しても再通知。
通常ファイルは常に「ready」: epoll は regular file には無意味。ディスク I/O は結局ブロック。

これらの限界が io_uring を生んだ。

6. kqueue — BSD のもう 1 つの道

同時期、FreeBSD (2000) が kqueue を導入。epoll に似るが:

ファイルシステムイベント、シグナル、タイマーなど より多くのイベント源。
統一 API で全てを扱う。

macOS も kqueue。libevent, libuv などのクロスプラットフォームライブラリは「Linux では epoll、BSD/macOS では kqueue、Windows では IOCP」を抽象化している。

7. 非同期ディスク I/O — ネットワークとは違う戦い

7.1 epoll がファイルに効かない理由

通常ファイルに epoll_ctl すると常に「ready」を返す。理由: ファイルはページキャッシュにあるか無いかで、「準備中」が無い。無ければ ブロッキング I/O でディスクから読む。

7.2 POSIX AIO — 失敗した最初の試み

Linux の glibc POSIX AIO は実はユーザー空間のスレッドプールで模擬したもの。真のカーネル非同期ではない。

7.3 Linux AIO (libaio) — 限定的成功

io_submit, io_getevents。本物のカーネル AIO だが:

O_DIRECT のみサポート (OS ページキャッシュを回避)。
多くの状況で依然ブロック。
実運用では稀。

MySQL InnoDB など一部 DB のみ使用。一般サーバーには普及せず。

8. io_uring — 2019 年の Linux I/O 革命

8.1 Jens Axboe のビジョン

2019 年、Linux 5.1、ブロック I/O メンテナの Jens Axboe が io_uring を導入。核心:

「システムコールを一切呼ばずに I/O を提出し、結果を受け取れる」。

8.2 2 つのリングバッファ

Submission Queue (SQ): ユーザーが I/O 要求を入れる。
Completion Queue (CQ): カーネルが完了結果を入れる。

どちらも mmap による ユーザー/カーネル共有メモリ:

ユーザー:
  SQ に要求を書き込む
  io_uring_enter() 呼び出し (任意)

カーネル:
  SQ から要求を読む
  I/O を実行
  CQ に結果を書く

ユーザー:
  CQ から結果を読む

8.3 なぜ革命的か

1. システムコールの削減

バッチ提出: 1 度の io_uring_enter() で複数要求。
SQ_POLL モード: カーネルスレッドが SQ を poll -> システムコール 0 回。
高 QPS 域で 10 倍以上の性能向上。

2. 統一インターフェース

ネットワーク、ファイル、タイマー、シグナル — すべて同じ API。epoll/AIO の混在が不要。

3. リンクされた要求 (linked SQE)

「これが成功したら次を自動実行」。例: openat -> read -> close を 1 度に提出。

4. Buffer Selection

何千もの接続それぞれにバッファを事前確保する代わりに、必要な時だけプールから選ぶ。

8.4 io_uring の成長速度

5.1 (2019): 基本導入。
5.5: accept サポート。
5.7: シグナル、ファイル open/close。
5.19: ネットワーク zero-copy 送信。
6.x: より多くの opcode、multishot accept。

2025 年現在、ほぼ全ての Linux システムコールが io_uring で実行可能。

8.5 io_uring の影

セキュリティ問題が多く発見。Google ChromeOS と Android は io_uring を無効化 した (2023)。理由:

攻撃面が広い (多くの opcode)。
カーネル脆弱性の新経路。
既存 seccomp では制御が難しい。

方向性: io_uring 向け seccomp 拡張、ACL、許可された opcode サブセットのみ許可するポリシー。

9. 実戦アーキテクチャ — Event Loop パターン

9.1 Reactor パターン (Node.js, nginx, Redis)

Event Loop (1 スレッド)
  while (true) {
    events = epoll_wait()
    for (e in events) handle(e)
  }

1 スレッドで全 I/O を監視。
イベント到着時に短いハンドラを実行し即次へ。
ハンドラは ブロック禁止 (全体が止まる)。
CPU 集約処理は worker thread にオフロード。

9.2 Node.js の構造

V8 JavaScript Runtime
libuv (クロスプラットフォーム)
  epoll / kqueue / IOCP
  Thread Pool
OS Kernel

I/O は libuv が epoll で非同期処理 -> JavaScript コールバック。
DNS 解決、ファイル読み込み、暗号化などの「非同期エミュレーション」は thread pool (既定 4)。
CPU 集約処理は Worker threads (v10+) へ。

9.3 nginx の master-worker モデル

Master (root 権限、設定管理)
  Worker 0 (epoll ループ、数万接続)
  Worker 1
  Worker N (通常 CPU コア数)

各 worker は独立した event loop。
listen socket を共有 (SO_REUSEPORT) — カーネルが接続を分配。
master-worker 分離で無停止設定リロード。

9.4 Redis — シングルスレッドの美学

Redis は 1 つのメインスレッド で全コマンドを処理:

epoll で数千接続を監視。
メモリだけなのでコマンド処理は µs 単位。
ロックなし -> 競合なし -> バグ少。

6.0+ から I/O threading: ネットワーク読み書きだけ複数スレッド、コマンド実行は依然シングルスレッド。I/O がボトルネックの環境で効く。

9.5 io_uring ベースの現代アーキテクチャ

ScyllaDB: 最初から io_uring 中心設計。Cassandra 互換で 10 倍速い。
QEMU/KVM: 仮想ディスク I/O を io_uring へ -> 40% の性能向上。
Ceph: バックエンドストレージに io_uring 導入。
nginx experimental: io_uring プラグイン。

10. Reactor と Proactor — 2 つの非同期哲学

10.1 Reactor (通知ベース)

「準備できたら教えて、読むのは自分」。
epoll, kqueue スタイル。
ユーザーがバッファ管理。

10.2 Proactor (完了ベース)

「ここに読み込んで、終わったら教えて」。
Windows IOCP、io_uring スタイル。
カーネルが直接バッファに書く。

10.3 なぜ Proactor が速いのか

Reactor: 「読める」-> read() システムコール -> データコピー -> 処理。 Proactor: カーネルがバックグラウンドでコピー完了 -> ユーザーは即処理。

システムコールが 1 回少ない。大量トラフィックではこの差が決定的。

Windows は 1994 年 NT 3.5 から IOCP で proactor。長く Linux は epoll で reactor のみだったが、2019 年に io_uring で proactor 陣営に合流。

11. ネットワークスタックの Zero-Copy

11.1 sendfile と read+write

ファイル -> ソケットの転送時:

通常:
  read(file)  : ディスク -> カーネル -> ユーザーバッファ (コピー 1)
  write(sock) : ユーザーバッファ -> カーネル -> NIC (コピー 2)

sendfile:
  ディスク -> カーネル -> NIC (コピー 0、DMA で直接)

nginx、Apache が静的ファイル転送に sendfile を使う理由。2 倍速 + CPU 1/10。

11.2 splice, tee, vmsplice

splice はパイプを介して fd 間でデータを移動。ユーザー空間コピーなし。

splice(fd_in, NULL, pipefd[1], NULL, size, SPLICE_F_MORE);
splice(pipefd[0], NULL, fd_out, NULL, size, SPLICE_F_MORE);

11.3 MSG_ZEROCOPY

Linux 4.14+ send(fd, buf, size, MSG_ZEROCOPY):

ユーザーバッファから直接 NIC へ DMA。
送信完了までバッファを触ってはいけない -> errqueue で完了通知。
大規模転送で 30% の性能向上。

11.4 io_uring + zero-copy

io_uring_prep_send_zc(sqe, fd, buf, size, 0, 0);

io_uring 内で MSG_ZEROCOPY と同等の効果。大きな応答を返す CDN、ビデオサーバーで決定的。

12. 観測とチューニング — 実務

12.1 接続数の上限

ulimit -n              # fd 上限 (通常 1024 または 1M)
ulimit -n 1000000
/etc/security/limits.conf

さらに:

sysctl fs.file-max
sysctl net.core.somaxconn
sysctl net.ipv4.ip_local_port_range
sysctl net.ipv4.tcp_tw_reuse

12.2 TCP バッファサイズ

sysctl net.core.rmem_max
sysctl net.core.wmem_max
sysctl net.ipv4.tcp_rmem

BDP (Bandwidth-Delay Product) が既定より大きければ調整が必要。10Gbps x 100ms = 125MB — 既定の 208KB では不足。

12.3 観測ツール

ss -antp: 現在の接続状態 (netstat 代替)。
iftop, nload: リアルタイムネットワーク。
tcpdump / wireshark: パケットダンプ。
bpftrace: カーネル内部イベントトレース。
perf trace: システムコールプロファイリング。

12.4 io_uring 導入戦略

段階的移行: 性能ホットスポットのみ io_uring、残りは epoll。
カーネル 5.15+ 推奨: 初期版はバグが多い。
セキュリティ: seccomp で許可 opcode を制限。
ライブラリ: liburing (Jens Axboe 公式)、tokio-uring (Rust)、io_uring-rs。

13. おわりに — 30 年の I/O 進化が教えてくれること

1970 年代の read() 1 行から始まった旅:

1983 select: 1 スレッドで複数 fd。
1986 poll: 制限解除、しかし依然 O(n)。
1994 Windows IOCP: 最初の proactor。
2000 FreeBSD kqueue: 統一イベント。
2002 Linux epoll: O(1) イベント。
2019 Linux io_uring: システムコール無しの I/O。

各世代は前世代の限界から生まれた。次の革命は何か。候補:

DPDK / XDP: カーネルバイパス、10Gbps+ ラインレート処理。
Userspace TCP: Kernel bypass でレイテンシ µs。
RDMA: CPU バイパスのメモリアクセス。
Smart NIC: I/O 処理を NIC にオフロード。

「決まった正解」の無い変化の連続。しかし中核原則 — 「システムコールは高価」「コピーは高価」「監視対象が増えるほど O(1) であるべき」— は 50 年前も今も同じ。

次回は ネットワークスタックそのもの — TCP 状態機械、輻輳制御 (Cubic と BBR)、nagle、delayed ack、Fast Open、そして QUIC がなぜ UDP の上に新スタックを作ったのか — を深掘りする。

参考資料

Dan Kegel — "The C10K problem" (1999-2014).
Davide Libenzi — "Improving (network) I/O performance..." epoll 提案 (2002).
Jens Axboe — "Efficient IO with io_uring" (2019).
Jens Axboe — "Ringing in a new asynchronous I/O API" (LWN.net, 2019).
Linux kernel source: fs/eventpoll.c, fs/io_uring.c, io_uring/.
liburing: https://github.com/axboe/liburing
"The Secret To 10 Million Concurrent Connections" — Robert Graham.
Felix Uherek — "The method to epoll's madness".
ScyllaDB Engineering Blog — Seastar / io_uring シリーズ。
"What Every Systems Programmer Should Know About Concurrency" (PDF) — Matt Kline.