【しばらく編集不可モードで運営します】 編集(管理者用) | 差分 | 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

TheC10kProblem - 「C10K問題」(クライアント1万台問題)とは、ハードウェアの性能上は問題がなくても、あまりにもクライアントの数が多くなるとサーバがパンクする問題のこと

目次

「C10K問題」(クライアント1万台問題)とは、ハードウェアの性能上は問題がなくても、あまりにもクライアントの数が多くなるとサーバがパンクする問題のこと

この文書について


C10K 問題

ウェブ・サーバが一万ものクライアントによる同時接続に耐えねばならない時代がきた, そうは思わないだろうか. 今や, ウェブは広大なのだ.

そして計算機の性能も莫大なものになった. 2ギガバイトの主記憶と ギガビット・イーサを積んだ 1000MHz のマシンをたかだか 1200 ドル程度で買うことができる. 20000 クライアントで割ると, これは 1 クライアントあたり 50KHz, 100Kbytes, 50Kbits/秒 だ. 4 キロバイトのデータをディスクから読み出し, 毎秒 1 回各 2 万のクライアントに送るのに, これ以上の馬力がいるはずはない. (ところでクライアントあたりの費用は 0.08 ドルになる. ある種の OS が課す 1 クライアント 100 ドルのライセンスは荷が重くなりだした.) 従って, もはやハードウェアはボトルネックでない.

1999 年, 最繁を極めた FTP サイトのひとつである cdrom.com は, ギガビットのイーサを通じ実に 10000 ものクライアントから同時接続をもっていた. つづく 2001 年, いくつかの ISP がこの通信速度を提供しはじめた. この速度が大きな顧客を持つ人気ビジネスに発展すると誰が考えたろうか.

その後, シン・クライアントの計算様式は復権を遂げた -- 今やサーバはインターネットにあり, 数千ものクライアントに仕えているのだ.

こうした流れを念頭に置き, 数千のクライアントをサポートするために いかに OS を構成し, コードを書くべきかについての覚書をまとめた. 議論は Unix 系の OS を中心に置く. 私が個人的に興味を持っているからだ. ただし Windows についても少しだけ触れる.

関連サイト

2003 年 10 月, Felix von Leitner が ネットワークのスケーラビリティに関する素晴しいウェブページプレゼンテーションを公開した. これは様々なネットワーク系システムコールや OS をベンチマークで比較したものだ. 彼の洞察によると, 2.6 系の Linux カーネルは本当に 2.4 系カーネルを上回っている. それにしてもこの資料には多くの優れたグラフを含んでおり, OS 開発者にとっては時間をかけて考えを深めるための材料となるだろう. (Slashdot のコメントを参照: Felix の実験結果を追試し補う者がいるかどうか眺めると面白い. (訳注: いないってことですかね.))

まず読むべき本

もしまだ読んでいないなら, 書店に出向いて故リチャード・スティーブンスによる "Unix Network Programming : Networking Apis: Sockets and Xti (Volume 1)" を 一冊入手すること. 本書は高性能サーバを書く上での 多くの I/O 戦略や落とし穴について解説している. それどころか "大集約(thundering herd)" 問題にまで言及している. そしてこれを読んだら, Jeff Darcy による高性能サーバ設計に関する忘備録へ進むとよい.

(ウェブサーバを "書く" のではなく "使う" のなら, 上記とは別に Cal Handerson による "Building Scalable Web Sites" の方が役立つかもしれない.)

I/O フレームワーク

これから説明していく技術のうちいくつかは, ライブラリのパッケージとして使うことができる. ライブラリを使えば, コードを OS から切り離して可搬性を高めることができる.

I/O 戦略

ネットワーク・ソフトウェアの設計者には多くの選択肢がある. いくつか列挙してみよう.

以下 5 種類の組合せに人気があるようだ.

1. 各スレッドが複数のクライアントを受け付ける. そしてノンブロッキング I/O と レベル・トリガ型の完了通知を利用する.

ネットワークのハンドルをノンブロッキングモードに設定し, select() や poll() を使ってハンドルにデータが届くのを待つ. 伝統的に好まれている方法はこれだ. この方式を使うと, カーネルはファイル記述子がレディ(ready: 準備ができた)かどうかを ユーザに伝える. カーネルによる前回の通知の後でユーザがファイル記述子に何をしても, この通知は行なわれる. ("レベル・トリガ" の名前は計算機ハードウェアの設計から来ている: 逆は "エッジ・トリガ(edge triggered)" という. Jonathon Lemon が BSDCON 2000 の kqueue() に関する論文でこの用語を導入した.)

注記: 大事なことなので覚えておいて欲しい: カーネルからの完了通知はあくまで "ヒント" にすぎない. ファイル記述子は読もうとしてもまだレディでない (not be ready: 準備ができていない)かもしれない. だから完了通知を使う際にはノンブロッキングにするのが重要になる.

この方式での重大なボトルネックは, ディスクからの read() や sendfile() がブロックする所にある. 呼び出し時にページが主記憶上にないと, これらの関数はブロックする. ディスクファイルハンドルをノンブロッキングモードに設定することは何の効果もない. メモリマップされたファイルも同様である. 最初にサーバがディスク I/O を要求するとき, プロセスはブロックする. 全てのクライアントは待たされる. 素のスレッドなしだと性能は無駄になる.

この問題に対処するために 非同期 I/O がある. AIO のないシステムでは, ワーカスレッドやプロセスがディスク I/O を担当することで ボトルネックを回避できる. ひとつのアプローチして メモリマップしたファイルを使う方法がある. mincore() でファイル I/O が必要かをしらべ, 必要ならワーカに I/O の作業を依頼する. あとは引き続きネットワークのデータを捌く. Jef Poskanzer によれば, Pai, Druschel, and Zwaenepoel らの Flash ウェブサーバが この技を使っているという. 彼らが行った USENIX 99 の講演による. mincore() は BSD 派生の UNIX である FreeBSD や Solaris には備わっているが, Single Unix Specificaton には含まれていない. Linux では Chuck Lever のおかげで カーネル 2.3.51 から利用できる.

しかし, 2003 年の freebsd-hackers メーリングリストで, VivekPei? らは良好な結果を示している. 彼らはシステム全体にわたるプロファイリングを用い Flash web サーバのボトルネックに挑んだ. 彼らがみつけたボトルネックのひとつは mincore にあり, (これを使うのは結局あまり良いアイデアではないのかもしれない.) もう一つは sendfile がディスクアクセスでブロックする点にあった 彼等は性能改善のために sendflile() を改造し, ページがメモリ上に無いときは EWOULDBLOCK 相当の値を返すようにした. (ページがメモリ上にあらわれたことをユーザに知らせる方法はわからない. 本当に必要なものは aio_sendfile() ではないかと私は思う.) 高速化の結果, SpecWeb99 のスコア 800 点を 1GHz/1GB の FreeBSD マシンで達成した. この結果は spec.org にあるファイルのどれよりも優れている.

単一スレッドに対し, I/O がレディになったノンブロッキング・ソケットの集合を通知する方法は 何通りかある.

伝統的な select()

残念ながら select() は FD_SETSIZE でハンドル数が制限されている. この制限は標準ライブラリやユーザのプログラムがコンパイルされる時に決まってしまう. (あるバージョンの C ライブラリは ユーザのアプリケーションをコンパイルする際にこの数を増やすことができる.)

Poller_select の例 (cc, h) には, 他の完了通知方式と相互互換のある方法で select() を使う方法が載っている.

伝統的な poll()

ハードコードされたファイル数の上限は poll() を使う分にはない. とはいえ接続が数千になると遅くなる. どの瞬間も大半のファイル記述子はアイドル状態にあるからだ. その数千のファイル記述子を走査するには時間がかる.

いくつかの OS (Solaris8 など) は, poll() などを高速化するために poll hinting のようなテクニックを導入した. Niels Provos は 1999 年に Linux 版を実装し, ベンチマークを行っている.

Poller_poll の例 (cc, h, ベンチマーク) には, 他の完了通知方式と相互互換のある方法で poll() を使う方法が載っている.

/dev/poll

Solaris では poll の代替としてこれを勧める. /dev/poll の裏にある考えとして, どうせ poll() は大抵おなじ引数を渡して呼び出すという事実がある. /dev/poll を使うなら, ユーザは /dev/poll へのハンドルを開き, OS に興味のあるファイルを知らせるべく一度だけハンドルへ書込みをすればいい. そのあとはレディなファイル記述子のセットをそのハンドルから読み出すことができる.

kqueue()

これは FreeBSD 向け(もうすぐ NetBSDにも入る)の poll の代替である. 後に述べるように, kqueue() はエッジ・トリガにもレベル・トリガにも設定できる.

2. 各スレッドが複数のクライアントを受け付ける. そしてノンブロッキング I/O と 変更型の完了通知(readiness change notification)を利用する.

変更型の完了通知(エッジ・トリガの通知)とは次のようなものだ. まずユーザがファイル記述子をカーネルに渡す. その後ファイル記述子が "レディでない" 状態から "レディ" 状態に遷移したとき, カーネルはユーザに何らかの通知を行う.それ以降はファイル記述子がレディだという前提を置き, 同じ通知をそれ以上よこすことはなくなる. ユーザが何か操作をしてファイル記述子がレディでなくなると, また通知をよこすようになる. (レディでなくなるとは, ユーザが send, recv, accept の呼び出しから EWOULDBLOCK エラーを受けとるようになったか, または要求したバイト数だけの転送を行えない状態を指す.)

もし変更型の完了通知を使うなら, 不要な(spurious)イベントへの準備が必要だ. というもの, よくある実装のひとつに, なんらかのパケットが到着すると常に完了通知を行うものがある. これはファイル記述子がレディかどうかとは無関係におこる.

これは "レベル・トリガ" とは反対の完了通知の仕組みだ. この仕組みはプログラミングの間違いに対して寛容でない. もし完了通知を一つでも取り逃したら, そのコネクションは永遠に詰まってしまう. とはいえエッジ・トリガの完了通知だと OpenSSL を使う ノンブロッキング・クライアントのプログラミングが楽になるのにも気付いた. この方式にも試してみる価値はある.

[Banga, Mogul, Drusha '99] (usenix99event.ps.gz) は 1999 年に同様の方法について述べている.

何種類かの API が アプリケーションへ 'ファイル記述子がレディになった' 通知を渡すために用意されている.

kqueue()

FreeBSD (もうすぐ NetBSDも) 向けに推奨されているエッジトリガ型の監視 API. FreeBSD 4.3 以降, および 2002 年 10 月時点での NetBSD-current は poll() の汎用代替 API として kqueue() と kevent() をサポートしている. これはエッジ・トリガ, レベル・トリガのどちらもにも利用できる. (Jonathan Lemon のページから kqueue() に関する BSDCon 2000 の論文を参照.)

/dev/poll と同様, ユーザは監視用のオブジェクトを取得する. ただ /dev/poll を開くのではなく kqueue() を呼び出す. 監視するイベントを変更したり, イベントのリストを取得するには kqueue() から取得した記述子に対して kevent() を使う. 監視できるのはソケットのレディだけでなく, 通常のファイル, シグナル, I/O の完了までもが監視できる.

注記: 2000 年 10 月の段階では, FreeBSD のスレッドライブラリは kqueue() との相性が悪いようだ. kqueue() がブロックすると, 呼び出しスレッドだけでなくプロセス全体がブロックしてしまう.

Poller_kqueue の例 (cc, h, ベンチマーク) には, 他の完了通知方式と相互互換のある方法で kqueue() を使う方法が載っている.

kqueue() を使っているライブラリの例:

epoll

Linux カーネル 2.6 向けに推奨されているエッジトリガ型の監視 API.

2001 年 7 月, Davide Libenzi がリアルタイム・シグナルの代替を提案した. そのパッチが /dev/epoll である. リアルタイム・シグナルによる完了通知と類似しているが, この方法だと冗長なイベントをひとまとめにできるし, イベントの一括取得もより効率的に行える.

epoll はインターフェイスの変更後, 2.5.46 から 2.5 カーネルにマージされた. /dev/ 以下の特殊ファイルだった古いインターフェイスから, sys_epoll() システムコールに変更が行われた. 古いバージョンの epoll は 2.4 カーネル用のパッチもある.

epol, aio, その他のイベントソースの統合に関する長い議論が 2002 年のハロウィンに起こった. その後も続いたのかもしれないが, Davide はまず epoll の安定化に注力した.

Polyakov による kevent の実装 (linux 2.6 以降) に関するニュース: 2006 年 2 月 9 日と 2006 年 7 月 9 日, Evgeniy Polyakov は epoll と aio を統合したというパッチを投稿した. 目的は ネットワークでの AIO のサポートである. 以下を参照すること:

Drepper の新ネットワーク・インターフェイスについて: OLS 2006 に, Ulrich Drepper は新しい高速非同期ネットワーク API を提案した.

リアルタイム・シグナル

Linux カーネル 2.4 向けに推奨されているエッジトリガ型の監視 API.

2.4 の linux カーネルはソケットの完了イベントを特定のリアルタイム・シグナルで通知する. 以下にそれを有効にするコードを示す:

 /* Mask off SIGIO and the signal you want to use. */
 sigemptyset(&sigset);
 sigaddset(&sigset, signum);
 sigaddset(&sigset, SIGIO);
 sigprocmask(SIG_BLOCK, &m_sigset, NULL);
 /* For each file descriptor, invoke F_SETOWN, F_SETSIG, and set O_ASYNC. */
 fcntl(fd, F_SETOWN, (int) getpid());
 fcntl(fd, F_SETSIG, signum);
 flags = fcntl(fd, F_GETFL);
 flags |= O_NONBLOCK|O_ASYNC;
 fcntl(fd, F_SETFL, flags);

この設定により, 通常の I/O 関数である read() や write() などが完了した時に シグナルが届くようになる. これを使うなら, 外側のループで poll() を使い内側では sigwaitinfo() を呼んでループする. その前に poll() から通知された fd はすべて処理しておくこと. sigwaitinfo や sigtimedwait がリアルタイム・シグナルを返したら, siginfo.si_fd と siginfo.si_band は poll() を読んだあとの pollfd.fd と pollfd.revents とほぼ同じ情報になる. 従ってユーザはその I/O を処理し, また sigwaitinfo() を呼べばいい.

sigwaitinfo が古い SIGIO を返したら, シグナルキューが溢れている. ユーザはシグナルハンドラを一旦 SIG_DFL に変更してキューをフラッシュする必要がある. その後は break して外側の poll() ループに戻る.

Poller_sigio の例 (cc, h) には, 他の完了通知方式と相互互換のある方法で リアルタイム・シグナル を使う方法が載っている.

直接この機能を使っている例は Zach Brown による phttpd を参照. (いや参照しなくてもよい. phhttpd はちょっと分かりにくい...)

[Provos, Lever, and Tweedie 2000] (citi-tr-00-7.ps.gz) は phttpd のベンチマークとして sigtimedwait の亜種であるsigtimedwait() と sigtimedwait4() を試している. この API を使うとユーザは複数のシグナルを一度の呼出しで取り出すことができる. 興味深いことに, 彼らにとっての sigtimedwait4() を使う主たる利点が アプリケーションからシステムの過負荷を推測できるところにある. (過負荷時に適切な振舞いをするためである.) なお poll() を使っても過負荷について同様の測定を行うことができる.

fd 単位のシグナル (Signal-per-fd)

Chandra と Mosberger は, リアルタイム・シグナルを "fd 単位のシグナル" アプローチに変更するよう提案している. これによって冗長なイベントをまとめ, リアルタイム・シグナルのキューあふれを 減らすか, 無くすことができる. ただしこの方法は epoll を凌駕することはできない. 彼らの論文 (http://www.hpl.hp.com/techreports/2000/HPL-2000-174.html) では select() や /dev/poll と比較をしている.

Vitaly Luban はこの方法を実装したパッチを 2001 年 5 月 18 日 に公表した. パッチは彼のサイト (http://www.luban.org/GPL/gpl.html) にある. (注記: 2001 年 9 月の時点ではまだ高負荷時の安定性に問題がある. dkftpbench を 4500 ユーザで動かすと悲鳴をあげる.)

Poller_sigfd の例 (cc, h) には, 他の完了通知方式と相互互換のある方法で リアルタイム・シグナルを使う方法が載っている.

3. 各スレッドが複数のクライアントを受けつける. そして非同期 I/O を使う.

この方法はまだ Unix での人気はない. おそらく非同期 IO をサポートしている OS が少ないのと, (ノンブロッキング I/O 同様) アプリケーション側に再考を求めるからだろう.

標準 Unix を使う場合, 非同期 I/O には aio_ インターフェイスが用意されている. (リンク先ページの "Asynchronous input and output" までスクロールすること.) この API ではシグナルと IO 操作の値を関連づける. シグナルと値はキューに入り, 効率的にユーザプロセスへ配信される. これは POSIX 1003.1b のリアルタイム拡張に由来している. また Single Unix Specificaton のバージョン 2 にも含まれている.

AIO はふつうエッジ・トリガの完了通知を行う. つまり, シグナルは操作が完了した時にキューに入る. (レベル・トリガの完了通知として使う場合は aio_suspend() を呼ぶ. ただしこれを使うケースはほとんどないようだ.)

glibc 2.1 以降は性能より標準準拠を重視した汎用的な実装を用意している.

Ben LaHaise? による Linux AIO の実装は Linux カーネル 2.5.32 にマージされた. これはカーネルスレッドを使わず, 極めて効率的な API を基盤としている. ただし (2.6.0-test2 の段階では) まだソケットをサポートしていない. (2.4 カーネル向けの AIO パッチもあるが, これは 2.5/2.6 向けのものとはいくらか異なる.) 詳細は以下を参照:

Suparna は DAFS API による AIO へのアプローチも読むよう言っている.

Red Hat AS や Suse SLES はいずれも 2.4 カーネル上で 高性能な実装を行っている. これは 2.6 カーネルの実装と関係しているが, 全く同じではない.

2006 年 2 月, ネットワークの AIO を実装しようとする動きが始まった. 先に示した Evgeniy Polyaov の kekvent による AIO のノートを参照.

1999 年, SGI は 高速 AIO を Linux 上に実装した. バージョン 1.1 はソケットとディスク I/O の双方で動作するとしている. これはカーネルスレッドを使っているようだ. Ben の AIO がソケットをサポートするまで 待てない向きには今でも有用だろう.

オライリーの書籍 "POSIX.4: Programming for the Real World" は AIO の入門に良いと言われている.

古い非標準の Solaris 向け実装を使うチュートリアルは Sunsite のオンラインにある. 眺めてみるのもいいかもしれないが, aioread を aio_read などに読み替える必要を 気にとめておくこと.

なお, AIO はブロッキングのディスク I/O なしにファイルを開く方法は用意していない. ディスク上のファイルを開くのにスリープするのが気になる人に Linus 曰く, 単に別スレッドで開けばいいから aio_read() を待ち望むことはないとのこと.

Windows では, 非同期 I/O は "オーバーラップ I/O" や IOCP, "I/O 完了ポート" などの用語が使われている. Microsoft の IOCP は, それまでの非同期 I/O (aio_write など) や 完了通知のキュー化 (aio_write と使う aio_sigevent フィールドなど) のような技術に, 単一の IOCP 定数 に関連づけられたスレッドの数を一定に保つために 複数のリクエストを保持したままにしておくという新しいアイデアを組み合わせたものである. 詳細は sysinternals.com の Mark Russinovich による "Inside I/O Completion Port", Jeffrey Richter の書籍 "Programming Server-Side Applications for Microsoft Windows 2000" (Amazon, MSPress), 米国特許 #06223207, MSDN を参照.

4. 各スレッドが一つのクライアントを受けつける

...そして read() と write() はブロックする. クライアント毎にスタックフレームを丸ごと使うのが欠点だ. メモリを浪費する. また多くの OS は数百スレッドを超えると問題がおこる. もし各スレッドが 2MB のスタックを使うとしたら (非常識でもないデフォルト値だ.) "仮想記憶が" 飽和してしまうだろう. (2^30/2^21) = 512 スレッドで, 32 ビット機の 1GB ユーザアクセス可能な仮想メモリは飽和する. (通常の x86 向け linux がこれだ.) より小さなスタックサイズをスレッドに使えば問題は回避できるが, 大半のスレッドライブラリは一旦つくったスレッドのスタックサイズを増やせない. つまりプログラムのスタック利用を最小化するよう設計をしなければいけない. 64 ビット機に移行し回避してもいい.

Linux, FreeBSD, Solaris でのスレッドのサポートは改善されている. 64ビット機は主流になろうとさえしている. そう遠くない未来, 1 スレッド 1 クライアント方式を好む人は その方法で 10000 クライアントに対応できるかもしれない. ただ今はまだ, 多数のクライアントに対応したいなら他の方法を使う方がいいだろう.

スレッド推進派による強気な視点としては von Behren, Condit, Brewer UCB の "Why Events Are A Bad Idea (for High-concurrency Servers)" を参照. HotOS IX で発表された. 反スレッド陣営に反論の記事はないだろうか? :-)

LinuxThrads?

LinuxThreads は Linux 標準のスレッドライブラリを指す. これは glibc2.0 以降の glibc に統合されている. またほぼ POSIX 互換であるが, 性能やシグナルのサポートは素晴しいとはいえない.

NGPT: Next Generation Posix Threads for Linux

NGPT は IBM の立ち上げたプロジェクトで, POSIX 互換の優れたスレッドサポートを Linux 上で行なおうというものだ. 安定版は 2.2 で, よく動く...が, NGTP のチームはそのコードをサポートのみのモードに移行すると発表した. その理由は彼らいわく "それがコミュニティを支援する最良の道だ" と感じたからとのこと. NGPT チームは今後も Linux のスレッドサポートを改善しつづけるが, 労力は NPTL の改善に向けられることになる. (NGPT チームのすばらしい成果や NPTL を評価するその姿勢を讃えたい.)

NPTL: Native Posix Thread Library for Linux

NTPLUlrich Drepper (glibc の独裁^H^Hメンテナ) と Ingo Molnar の 立ち上げたプロジェクトで, linux 上でのワールドクラスのスレッドサポートを目指している. 2003 年 10 月の時点で, NPTL は glibc の CVS ツリーにアドオンとしてマージされた. (LinuxThreads? と同じ.) glibc の次回リリースには含まれることになるだろう.

NPTL の初期スナップショットを含む最初のメジャーな配布系は Red Hat 9 である. (一部のユーザには不便かもしれないが, 誰かは最初の一歩を進まなければ...)

NTPL のリンク:

ここで NPTL の歴史をまとめてみよう. (Jerry Coopersten の記事も参照してほしい.)

2002 年 3 月, NGPT チームの Bill Abt と glibc メンテナの Ulrich Drepper らは ミーティングを持ち, LinuxThreads? に対し何をすべきかを話しあった. ミーティングで生まれたアイデアのひとつは mutex の性能を改善しようというものだった. (Rusty Russell はそれを踏まえ fast userspace mutexes (futexes) を実装した. これは NGPT と NPTL の双方から使われている.) 大半の参加者は NGPT を glibc にマージするべきだと指摘した.

しかし Ulrich Drepper は NGPT が好きではなかった. そして自分ならもっとよいものにできると主張した. (glibc にパッチを送ったことがあれば, これは大して驚きでもないだろう:-) その数ヶ月後, Ulrich Drepper, Ingo Molnar らは glibc とカーネルに変更を行った. これが Native Posix Thread Library (NPTL) と呼ばれることになる. NPTL は NGPT のためのカーネルの変更を全て利用し, 更にいくつかの利点があった Ingo Molnar はカーネルの改善について次のように述べている.

NPTL は NGPT のために導入されたカーネルの機能を三つ利用している: PID を返す getpid(), CLONE_THREAD, futexes だ. NPTL は更に広範なカーネルの機能を使って(かつ依存して)いる. それらの機能はこのプロジェクトの一環として開発したものだ. NGPT が 2.5.8 付近で持ち込んだいくつかのカーネルの機構は変更, 整理, 拡張された. スレッドグループの処理(CLONE_THREAD) などがそうだ. (CLONE_HREAD への変更のうち NGPT に影響のある部分は NGPT 開発者と足並みを揃えている. そのため NGPT がひどく被害をうけることはない.) NPTL のためのカーネルの変更は設計のホワイトペーパを参照のこと. http://people.redhat.com/drepper/nptl-design.pdf 簡単なリスト: TLS サポート, 様々な clone 拡張 (CLCONE_SETTLS, CLONE_SETTID, CLONE_CLEARTID), POSIX スレッドシグナル補足, sys_exit() 拡張 (VM の 開放時に TID futex を開放), sys_exit_group() システムコール, デタッチしたスレッドを扱える sys_execve() の拡張. PID 空間を拡張する変更もある. 例: procfs は 64K の PID を 仮定しているためクラッシュする, max_pid, pid の確保がスケールする変更, 性能のみに関する改善も完了した. まとめると, これら新機能は 1:1 スレッドへの妥協しないアプローチである. スレッドを改善できるためにカーネルでできることはなんでもやる. またスレッド処理プリミティブでのコンテクスト切り替えやカーネル呼び出しは きっちり最小化されている.

二つのスレッド実装の大きな違いは, NPTL が 1:1 スレッドモデルなのに対し NGPT が M:N スレッドモデルを採用している点だ. (下記参照.) にもかかわらず, Ulrich の初期ベンチマークでは NPTL が NGPT よりずっと高速だという 結果がでている. (NGPT チームは結果を検証するためにベンチマークのコードを見ようとしている.)

FreeBSD のスレッドサポート

FreeBSD は LinuxThreads? とユーザ空間のスレッドライブラリをサポートしている. また KSE と呼ばれる M:N 実装が FreeBSD 5.0 から導入された. 概要は http://www.unobvious.com/bsd/freebsd-threads.html を参照のこと.

2003 年 3 月 25 日, Jeff oberson の freebsd-arch への投稿:

... Julian による出資, David Xu, Mini, Dan Eischen, そのほか KSE や libthread の開発者に感謝したい. Mini と私は 1:1 スレッドの実装を行った. このコードは KSE と並列に動き, 何も破壊しない.. むしろ M:N スレッドと協調し, shared bit をテストする.

2006 年 7 月, Robert Watson は 1:1 スレッドの実装を FreeBSD 7.x のデフォルトにしようと提案:

この問題が過去に議論されたのは知っている. しかし 7.x がゆっくりと歩みをすすめる中で, 問題を再考すべき時が来たと感じている. 一般的なアプリケーションによる多くのベンチマークで, libthr は libthread より ずっと良い性能を示している. また libthr は我々のプラットホームのうちより広くで 実装されており, いくつかでは libthread として使われてもいる. MySQL など徹底してスレッド化されたアプリケーションに対し, 我々がした最初のおすすめは "libthr に変えてみろ" だった. これは示唆深い! そこで叩き台として提案をしたい: 7.x では libthr をデフォルトにしよう.

NetBSD のスレッドサポート

Noriyuki Soda の覚書より:

カーネルサポートのある M:N のスレッドライブラリがある. これは Scheduler Activation に基くもので, 2003 年 1 月 18 日に NetBSD-current へマージされた.

詳細は Wasabi Systems Inc の Nathan J.Williams による "An Implementation of Scheduler Activations on the NetBSD Operating System" を参照. FREENIX '02 で発表された.

Solaris のスレッドサポート

Solaris のスレッドサポートは進化を続けている... Solaris 2 から Solaris 8 まで デフォルトのスレッドライブラリは M:N モデルを採用していた. しかし Solaris 9 は 1:1 モデルのスレッドをデフォルトとした. Sun のマルチスレッドプログラミングガイドJava と Solaris のスレッドに関する注釈を 参照のこと.

JDK 1.3.x 以前の Java のスレッドサポート

よく知られているように, JDK1.3.x 以前の Java は 1 スレッド 1 クライアント 方式以外の方法でネットワーク接続を処理することができなかった. Volanomark による小さなベンチマークは毎秒のメッセージのスループットを 様々な同時接続数で計測している. 2003 年 3 月の時点で, 様々なベンダによる JDK1.3 実装は実際に一万の同時接続を処理することができた. 性能劣化は著しかったが. どの JVM が一万接続を処理できたか, 接続数の増加に伴いどれだけ性能が損なわれたかは Table 4 を参照.

注釈: 1:1 スレッド vs. M:N スレッド

スレッドライブラリを実装するのには選択肢がある: 全てのスレッド処理をカーネルで行う (これを 1:1 スレッドモデルという.) か, 一部をユーザ空間に持ってくるかだ. (これを M:N スレッドモデルという.) ある時点では M:N スレッドの方が高性能だと考えられていた. しかし正しく動かすにはあまりに複雑だったため, やがて人々は離れていった.

5. サーバのコードをカーネルに組込む

Novell や Microsoft はこの仕組みを作ったと何度か言っている. すくなくとも NFS 実装はこうなっている. また linux の khttpd は静的なページを処理できる. そして "TUX" (Threaded linUX webserver) は激速かつ柔軟なカーネル空間の HTTP サーバで, Ingo Molnar によって Linux 用に開発された. Ingo の 2000 年 9 月 1 日の発表は TUX のアルファ版が ftp://ftp.redhat.com/pub/redhat/tux からダウンロードできるといい, メーリングリストに入る方法を説明している. linux-kernel のメーリングリストでは, このアプローチの利点と欠点を議論してきた. そこで得られたと思われる同意点は, カーネル内にウェブサーバを持ち込むより, カーネルにウェブサーバの性能向上のためのフックを最小限追加する方がいいというものだった. その方法なら他のサーバにも有難味がある. ユーザ空間とカーネルの HTTP サーバに関する Zach Brown の注記を参照. それによれば, 2.4 カーネルは十分なパワーをユーザのプログラムにもたらしている. X15 サーバ (後述) は TUX と同じくらい高速だが, カーネルへの変更は行わない.

コメント

Richard Gooch は I/O の選択肢に関する議論を記事にまとめている.

2001 年, Tim Brecht と Michal Ostrowski select を使った簡単なサーバで様々な戦略を測定している. 彼らのデータは一見に値する.

2003 年, Tim Brecht は userver のソースコードを投稿した. これは小さなウェブサーバで, Abhishek Chandra, David Mosberger, David Pariag, Michal Ostrowski によって書かれたいくつかのサーバを一つにまとめたものだ. select(), poll(), epoll(), sigio を使うことができる.

1999 年に戻ると, Dean Gaudet の投稿がある.

なぜ Zeus のような select/event ベースの方法を使わないのかと よく訊かれる. それは明らかに最速なのに...

彼の理由はこうだ. "その方法は本当に大変で, 割にあうかはわからない." しかし数ヶ月後, その方向に進みたがっていることが明らかになる.

Mark Russinovich は 2.2 linux カーネルでの I/O 戦略についての議論で 編集後記記事を書いている. いくつか間違いはあるが一読に値する. 間違いのうち, 特に彼は linux 2.2 の非同期 I/O (上記の F_SETSIG 参照) は ユーザプロセスにデータの到着を通知せず, コネクションの到着だけを通知するとしている. これはひどい誤解だと思う. 初期のドラフトへのコメント, Ingo Molnar による 1999 年 4 月 30 日の反論, 1999 年 3 月 2 日の Russinovich のコメント, Alan Cox の反論, そのほか様々な linux-devel の投稿を参照のこと. 彼が言おうとしているのは Linux が非同期ディスク I/O を サポートしないということではないかと私は考えている. これは正しかったが, 今は SGI が KAIO を実装し, もはや正しくない.

sysinternals.comMSDN の "完了ポート" に関する記事を参照. 記事ではそれが NT 固有の仕組みだと主張している. 簡単にいうと, win32 の "オーバーラップ I/O" は低レベル過ぎて不便なため, "完了ポート" が完了イベントのキューをもつラッパとして用意されている. またスケジューリングの魔法で動作しているスレッドの数を定数に抑え, あるスレッドが(ブロッキング I/O などで)眠っている時に なるべく他のスレッドが完了イベントを取得できるようにする.

OS/400 の I/O 完了ポートのサポートについても参照.

1999 年 9 月に linux-kernel メーリングリストで面白い議論があった. 題して "> 15,000 Simultaneous Connections" (http://www.cs.helsinki.fi/linux/linux-kernel/Year-1999/1999-36/0160.html). (二週目のスレッドも参照.) ハイライト:

面白い読み物だ!

オープンしたファイルハンドルの制限

/boot/loader.conf を編集し, 以下の行を追加する

 set kern.maxfiles=XXXX

XXXX にはシステムでのファイル記述子の上限を書く. それから再起動する. 次のような書込みをくれた匿名の読者に感謝. 彼は FreeBSD4.3 で 10000 接続を実現した:

私の知る限り, sysctl を使って接続数の最大値を変える自明な方法はない. /boot/loader.conf ファイルを書く必要がある. というのも, ソケットや tcpcb 構造体をゾーンに確保する zalloci() の呼び出しは システム起動のとても早い段階で呼ばれるから. これらゾーンはどちらも stable かつスワップ可能にしたいのだ. それと mbuf の数を多めに設定する必要もある. (変更のないカーネルでは)接続毎に mbuf を一つ食い潰して keepalive を実装しているから.

別の読者はこういう:

FreeBSD 4.4 以降では, tcptempl 構造体はもう確保されない. だからもう mbuf がコネクション毎にひとつ使われるという心配はいらない.

以下も参照

OpenBSD ではプロセス毎の最大ファイルハンドル数を増やすのに追加の設定が必要だ. /etc/login.conf の openfile-cur を増やす必要がある. kern.maxfile を変更するには sysctl -w か sysctl.conf を変更すればいい. ただしこれには意味がないい. 設定には気をつける必要がある. 出荷状態では longin.confg はかなり小さな値, 非特権プロセスで 64, 特権プロセスで 128 に制限をしているからだ.

 echo 32768 > /proc/sys/fs/file-max

でシステムの上限を増やせる.

 ulimit -n 32768

で現行プロセスの上限を増やせる.

2.2.x のカーネルでは

 echo 32768 > /proc/sys/fs/file-max
 echo 65536 > /proc/sys/fs/inode-max

でシステムの上限を増やせる.

 ulimit -n 32768

で現行プロセスの上限を増やせる.

私は Red Hat 6.0 (2.2.5 とパッチ) 上のプロセスで最低 31000 個のファイル記述子が オープンできることをした. 別の同僚は 2.2.12 で 90000 個を確認している. (適当な制限にした上で.) 上限は利用できるメモリ量で決まるように見える. Stephen C. Tweedie はグローバルな ulimit の設定やユーザ毎の制限を, initscript や pam_limit を用いて起動時に行う方法を投稿している. ただし古い 2.2 カーネルではオープンできるファイル記述子の数は 1024 に制限されている. Oskar の 1998 年の投稿を参照. この記事では 2.0.36 カーネルでの プロセス単位, システム全体のファイル記述子の上限について述べている.

スレッドの制限

どのアーキテクチャを使うにせよ, 仮想記憶が飽和するのを防ぐためにスレッド毎に確保される スタックの容量を削る必要があるだろう. pthread を使うなら, この値は pthread_attr_init() で指定できる.

Java 関係

JDK 1.3 までは, Java の標準ライブラリはほぼ クライアントあたり 1 スレッドモデルだけしか使えなかった. ノンブロッキングでの読み出しはできたが, 書込みはできなかった.

2001 年 3 月, JDK 1.4java.nio パッケージを導入した. これはノンブロッキング I/O のフルサポート (そのほかあれこれ) を提供している. リリースノート参照. 試しに使って Sun にフィードバックをしよう!

HP の Java も Thread Polling API を用意している.

2000 年, Matt Welsh は Java 向けにノンブロッキング・ソケットを実装した. ベンチマークでは, ブロッキングソケットに対し (1000 以上の) 大量のソケットを扱う時の優位性が示された. 彼のクラス・ライブラリは java-nbio という. これは Sandstorm プロジェクトの一環である. 10000 接続時のベンチマークが入手可能.

Dean Gaudet による Java, ネットワーク入出力, スレッドについてのエッセイMatt Welsh の イベント対ワーカースレッドに関する論文も参照.

NIO 以前, Java のネットワーク API を改善する提案がいくつかなされていた.

その他の Tips

ゼロ・コピー

データをある場所から他の場所に動かすのに, 普通は何回ものコピーが行われる. このコピーを物理的に最小の数まで減らす技術をまとめて "ゼロ・コピー" と呼ぶ.

送信側のゼロ・コピーは NetBSD-1.6 リリースからサポートされており, "SOSEND_LOAN" カーネルオプションを使うと有効になる. このオプションは NetBSD-current ではデフォルトで有効になっている. (NetBSD-current でも "SOSEND_NO_LOAN" カーネルオプションを 指定することで無効化できる.) この機能を使うと, ゼロ・コピーは自動的に実現される. 4096 バイト以上のデータを送信する場合に有効になる.

writev (または TCP_CORK) を使って小さなフレームを避ける

Linux での新しいソケットオプション TCP_CORK は, カーネルに部分的なフレームを送らないよう指示する. これは少し効く. つまり, 何かデータをまとめられない事情があったせいで大量の小さな write() を発行する時に 効果がある. このオプションを外すとバッファがフラッシュされる. とはいえ writev() を使う方が望ましいだろう...

LWN 2001 年 1 月 25 日号には linux-kernel メーリングリストで行なわれた TCP_CORK や代替案である MSG_MORE に関する 議論がまとめられている.

過負荷時に注意深く振る舞う

[Provos, Lever, Tweedie 2000] (citi-tr-00-7.ps.gz) によると, サーバの過負荷時に受けつけた接続を捨てることで性能曲線が改善, 総エラー率も低下するという. 彼らは負荷の測定に "I/O 待ちになっているクライアント数" を丸めて用いている. このテクニックは select, poll, そのほか完了状態のイベント数を呼び出し毎に返す システムコールがあれば容易に適用することができる. (/dev/poll や sigtimedwait4() でもいいだろう.)

非POSIXなスレッドを使うといいプログラムもある

全てのスレッドが平等に作られているわけではない. Linux の clone() 関数 (あるいは他の OS での類似関数) を使うと, 自身の作業ディレクトリを持つスレッドが作られる. これは FTP サーバを作る際に便利だ. POSIX でなくネイティブのスレッドを使う例には Hoser FTPd がある.

自分のデータはキャッシュするといいかもしれない

3 月 9 日, new-httpd メーリングリストへの Vivek Sadananda Pai による投稿 "Re: fix for hybrid server problems" より:

FreeBSD と Solaris/x86 上で select べースなサーバの生性能を比較した. このマイクロベンチマークでは, ソフトウェア・アーキテクチャの違いから来る 性能差は小さなものだった. select ベースなサーバでの大きな性能向上は, アプリケーション・レベルでのキャッシュが主になっている. 複数プロセスのサーバなら同じことを高めのコストで実現できるかもしれない. ただし, 実負荷で(マイクロベンチマークと比べて)同じ効果を得るのは難しいだろう. この測定結果は次回の Usenix で発表する. postscript の論文は http://www.cs.rice.edu/~vivek/flash99/ にある.

その他の制限

カーネルの問題

Linux の場合, カーネルのボトルネックは継続的に修正されている. Linux Weekly News, Kernel Traffic, the Linux Kernel メーリングリスト, 私のMindcraft Redux ページを参照してほしい.

1999 年, Microsoft がスポンサーとなり, NT と Linux を比較して HTTP と smb で大きなファイルを扱うベンチマークが行われた. Linux は良い結果を出すことができなかった. 詳細は私が Mindcraft で 1999 年 4 月に行ったベンチマークについての記事を参照.

Linux Scalability Project を参照. 彼らは興味深いことをしている. それには Niel Provo の poll hinting のパッチも含まれている. また thundering herd 問題にも取り組んでいる.

Mike Jagdis による select() と poll() の改善を参照. Mike の投稿もある.

Mohit Aron (aron@cs.rice.edu) は, 割合(rate)ベースのクロックを使った TCP で "遅い" 接続に対する HTTP レスポンスを 80% 改善できると書いている.

サーバ性能の測定

次の二つの試験が単純で, 興味深く, 難しい.

Jef Poskanzer は多くのウェブサーバを比較したベンチマークを公開している. 結果は以下のURLを参照: http://www.acme.com/software/thttpd/benchmarks.html

私も thttpd と Apache を比べた際のメモをいくつか残している. 初心者にはいいかもしれない.

Chuck LeverBanga と Druschel によるウェブサーバのベンチマークについての論文を 思いださせてくれた. 一読に値.

IBM が Java Server benchmarks [Baylor et al, 2000] という素晴しい論文を書いている. 一読に値.

気になる select() ベースのサーバ

気になる /dev/poll ベースのサーバ

気になる kqueue() ベースのサーバ

気になるリアルタイム・シグナルベースのサーバ

気になるスレッドベースのサーバ

気になるカーネル内サーバ

そのほかのリンク

著作権情報

 Copyright 1999-2006 Dan KEGEL, dank@kegel.com

著作権情報の付記は原著者の要望につき, 消さないでおいてくださいませ. -- 訳者