= Event-driven Programming for Robust Software = == 概要 == サーバソフトウェアにおけるI/Oの並列性を管理するためには、ThreadよりもEventを使う方がよい： eventは、threadによって引き起こされる、不必要なCPUの並列性によるバグを回避しやすい。 Eventベースのプログラムは、threadプログラムより、高負荷なときの性能が安定している。 ここでは、libasyncという自作のノンブロッキングI/Oライブラリを使って、 Eventベースのプログラミングをより便利にでき、このライブラリを拡張して マルチプロセッサの性能を引き出せると主張する。 私たちは、Eventは、少ない複雑さでThreadのすべての利点を実現でき、結果として堅牢なソフトウェアを作れると結論した。 == Introduction == EventかThreadかという議論は歴史がある。 議論の主題は、「並列I/Oを扱うにはeventかthreadかどっちが良いか」というものだ。 Threadが「既存の手続き型プログラミングのやり方が通用するし、MPでも性能を引き出せるから」という理由で好まれることが多いが、 MT programmingはむずかしいために、バグを産みやすいという事に気づくプログラマもいる。[[br]] 本論文ではEventを使うと便利で堅牢でMPの性能も活かせることを説明し、 並列I/Oを使うときにthreadを使う理由はないと主張する。[[br]] MTなプログラムは、1個のアドレス空間で複数のスレッドを使う[3]。 並列にI/Oするにはthreadをsuspendしてblockする必要がある。 このモデルだとプログラマはスレッドの実行を制御するための状態を保存するための変数やlockなどのデータ構造を、注意深く守る必要がある。[[br]] Eventなプログラムは、eventの処理を中心にして構成される。 プログラムが、次のeventが発生するまで処理の完了ができないとき(パケットの到来やディスクアクセスの完了などのとき)は、 callback関数を登録してそのeventが起きたときに呼ばれるようにする。 Eventベースのプログラムは、典型的には、eventをpollするループによって駆動される。 pollしたときに起きたeventの内容によって適切なcallback関数が呼び出される。 callback関数は、blockする処理にぶちあたるまでは見えない状態で実行され(ringo:おそらくuser空間で、ということかな？)、 新しいcallback関数を登録してreturnする。[[br]] このポジションペーパでは、eventモデルを使ったプログラミングが便利であり、 eventモデルを拡張することでMPに対応するためにプログラマがすべきコードへの修正が非常に少ないことを示す。 このMPのイベントモデルを用いると、システムプログラミングにおけるCPUレイヤの並列性をうまく処理できるが、 プログラマは、Lockや状態変数を追加する必要がない。 MPへの対応は、libasyncライブラリの一部になっている。 Threadを用いたプログラミングとは異なり、libasyncは、プログラマに対してthreadの同期(synchronization)を要求しない。 stackにどの程度のサイズを確保しておく必要があるかを思案する必要もなくなる。 高負荷な状態での性能も良く、隠れた性能上のコストも発生しない。 結果として、libasyncを使って書かれたプログラムは、堅牢になりやすい。 私たちの経験に基づけば、並列のI/Oを扱うためにthreadを使う理由は一つもない。 == Threadを使うと不安定なソフトウェアになりやすい == Threadの主な利点は、手続き型のプログラミングモデルの見た目を維持したまま、I/Oを多重化できることである。 Threadの主な不都合は、必要のないときにでも並列的な実行が起こってしまうことである。 この並列性により、プログラマは、スレッド間の同期という問題を解決する必要が生じる。 実際には、スレッド化されたプログラムは、見えない部分でデータの競合やデッドロックを起こしていて、その結果として、堅牢でなくなる。 私たちは、プログラマは、ソフトウェアをより堅牢にするために、複雑さという代償からは解放されなくてはならないと考える。[[br]] Threadプログラミングの問題はずっと前から認識されている。 Ousterhoutは、MPを使う場合以外は、threadの便利さより、 それによって増える間違いの害のほうが大きいと指摘している[11]。 Englerらは、同期の問題(特にデッドロックの問題)がLinuxカーネルにおいてよくあると言う[5]。 Savageらは、学生のコードにも商用のサーバにも競合が見つかったと言っている[13]。[[br]] 単一プロセッサのマシンにおいては、 同期処理を、非プリエンプティブでないスレッドに移転させることで、無くすことができるように思える。 しかし、スレッドが意図しないタイミングでCPUに処理をあけ渡してブロックしてしまう場合には問題が起きる。 複雑なシステムでは、プログラマが、他のモジュールの内部で ブロッキングが起きることを理解できない、ということは簡単におきる。 そのため、クリティカルセクション内を実行している最中に、 pre-emptionが起きるようなブロッキング関数を簡単に呼び出してしまう[1]。 pre-emptiveでないスレッドを使っているときにでも、Deadlockは起きる可能性がある。 複数回のyieldを越えてロックを保持しておきたい場合には、わかってやっていても、起きる場合がある。 Adya らは、サブモジュール内で予期しないyieldがあったときにそれを検出できるような 拡張された非プリエンプティブなスレッドを提唱し、並列I/Oの手法に関する新しい分類法を示した[2]。 彼らはEventベースのコード（彼らはこれを協調的タスクマネジメントおよび手動のスタック管理と呼んだ）と、 非プリエンプティブなThread（協調的タスクマネジメントおよび自動のスタック管理と呼んだ） を同じプログラムにおいて混在させる方法も示した。[[br]] スタックの最大サイズを予測する必要がある事も、Threadの複雑性を増加させている。 ほとんどのシステム（ＯＳ）は、スレッドごとに用意されたスタックに対して、 1ページか2ページのメモリを割り当てている。このサイズは、 callbackごとに必要な何百バイトという量よりもはるかに大きい。 Ｍachカーネルの設計者は、スタックのメモリアクセスの負荷が高いことを発見したので、 カーネルを"continuation"を使うように書き換えた。重要な事に、 彼らはイベントドリブンのスタイルをとった[4]。 スタックメモリのオーバーヘッドは、組み込みソフトウェアのようなメモリが少ない場合には、さらに重荷になる。 スタックごとにまるまるページを割り当ててしまうことは、通常はTLBやメモリキャッシュも圧迫してしまう。 特に、direct mapped cacheに対してはひどい[4]。 Cohort schedulingでは、スレッド化されたプログラムにおいて、"Stage"と呼ばれる仕組みを使って続けて実行することで、 互いに関連のある計算をするために必要なデータと命令の局所性を高めようとした[7]。[[br]] 堅牢なソフトウェアは、過負荷な状態にもうまく対応しなければならない。 Paiら[12]とWelshら[14]は、高負荷な状態でのeventドリブンなプログラミングについて探索をした。 Ｗelshは、カーネルスレッドをつかった単純なサーバのスループットは、スレッドの数が増えると急激に落ちることを示した。 Paiは伝統的なイベントドリブンの構造を拡張して、ほとんどのUNIXシステムにおいて ブロッキングしないディスクアクセスが利用できないという問題を、 ディスクアクセスをするためのヘルパー・プロセスを利用して解決しようとした。 多くの並列クライアントを含む負荷がある状態では、Paiのイベントベースのwebサーバは、 カーネルスレッドベースのサーバよりも高い性能を出した。[[br]] イベントドリブンプログラムは、上記のような問題を軽減する。データの競合は、 イベントベースのプログラムはシングルスレッドで動作させるために問題ではなくなる。 イベントドリブンプログラムは、スタック全体ではなく コールバック関数のポインタと引数だけを保持しておけば良いため、全体でのメモリ使用量が少なくなる。 さらに、これらのポインタは、極めて密に並べておくことができるため、TLBへの圧迫も減る。 イベントドリブンプログラムではイベントのキューに必要な資源以外は割り当てられないので、 高負荷時における、Threadを使ったサーバが「生きてるけど止まってるように見える(livelock)」 というような振る舞いは起きない[10]。[[br]] LauerとNeedhamは、メッセージパッシング（イベントドリブンモデルに対応する）に基づいたプログラムは、 threadのような手続き型のモデルと変わりはない(dual constructed)であると言っている[8]。(訳注： この考えに基づき、彼らはどちらのモデルも、根本的にはどっちを選択すべきであるという議論にはならないと結論した。(ringo:1978年の論文を見ると、マシンの構造によるのであって、アプリによらないという結論になっている) LauerとNeedhamによって示されたモデルは、非プリエンプティブな（thread)モデルを使う場合は、 両方を同時に使うことはそれほど難しくないという事実を見逃している。 結果として、彼らはイベントドリブンモデルによって同期処理の難しさが減るという利点を無視してしまった。[[br]] 本論文はユーザレベルのサーバに焦点を当てているが、同じ議論は、ＯＳのカーネルについても当てはまる。 この領域では、イベントドリブンの構造は、一時的な割り込みやトラップに対応して動くカーネルに対応する。 Fordらは、Flukeの文脈のもと、イベントドリブンカーネルとthreadのカーネルの比較をしている[6]。 == 非同期プログラミングを簡単にする == 最も良く言われるイベントモデルの問題点は、プログラミングが難しいという事である。 スレッドを用いたプログラムは、処理を、ブロッキングする関数をループで囲むことができる。つまり1本の流れで書ける。 それに対して、イベントモデルは、ブロッキングする処理ごとに、小さなコールバックを定義して一連の処理をさせなければならない。 スタックに積まれた情報は、コールバックが起きるごとに消えてしまう。 そのため、イベントドリブンプログラムは、動的なメモリ割り当てに大きく依存してしまい、 CやＣ＋＋のようなローレベルな言語においては、メモリ管理の間違いを引き起こしやすい。 例えば、仮に以下のような非同期の書き込み関数を考えてみる。 void awrite (int fd, char *buf, size_t size, void (*cb)(void *), void *arg); awriteは、以下のことが起きるように設定して返るだろう：ファイルディスクリプタが書き込み可能になったら、 すぐにbufの内容をディスクリプタに書き込み、cbをargを引数として呼び出す。 argはcallbackを越えて状態を保持するためのものである。 これは、threadプログラムでは、スタックに保持されている情報である。 awriteに関するいくつものバグが起きるだろう。 例えば、awriteはbufがcallbackが起きるまでに使える状態であると仮定しているが、 実際にはプログラマは、スタックに割り当てた領域を指定しているかもしれない （その場合はawriteを呼び出すときにはbuf使えない領域を指すポインタになっている）。 さらに、argをvoid のポインタにキャストして戻すことはtypesafeではない。[[br]] C++のノンブロッキングI/Oライブラリである、我々のlibasyncは、 この種のメモリの問題を回避するための機能をいくつか持っている。 汎用のリファレンスカウンタ式のガベージコレクタを持ち、 プログラマが、どのデータを解放しなければならないかを気にしなくても良いようにしている。[[br]] libasyncは、callbackを越えてtypesafeに状態をやりとりできる仕組みを提供する。 wrapという、たくさんオーバーロードされたテンプレート関数によって、 プログラマは、関数をカリー化してデータをコールバック関数間でやりとりすることができる： wrap関数は関数やメソッドのポインタとそれらへの引数を引数として受け取り、 もとの関数の型を受け入れることができる関数オブジェクトを返す。 そのため、処理の状態は、その後のcallbackにおいても引数としてひもづいたままになる。 引数は、コンパイル時に型チェックされる。[[br]] 最後に、このライブラリは、例えば、カーネルバッファが溢れてwritevが一部だけしか書き込めなかったときのような場合のような、 短いI/O処理による複雑さを扱うためのクラスを用意している。 suioクラスは、リファレンスカウントされたオブジェクトに対して、 出力用の関数呼び出しによって、"print"されたデータが完全に使われたかどうかを見守ってくれる。[[br]] libasyncを使った開発は、簡単に学べるということがわかった。 我々は、日々のネットワークアプリの開発にlibasyncを使っている。 学生たちはweb proxyや暗号化ファイルシステムを開発するといった研究室の課題をこなすためにこのライブラリを使っている。 == マルチプロセッサにおけるイベントプログラミング == 我々は、セクション3で説明した非同期プログラミング用のライブラリを、MPの性能を引き出すために修正した。 修正されたlibasync-mpは、複数のＣＰＵ上で複数のスレッドを動かしつつも スレッドプログラミングモデルの同期処理の複雑さを回避できる、単純で効果的なモデルを提供する。[[br]] libasync-mpで書かれたプログラムは、単純な並列化メカニズムを持つ： プログラマはそれぞれのコールバックに「色」をつけ、 同じ「色」のcallbackは2重に呼び出されることがないように、システムが制限をかける。 通常のcallbackにはデフォルトの「色」が設定されていて、それらは同時に実行されないため、 既存のイベントドリブンプログラムと、後方互換性がある。 このことにより、プログラマは、並列的な実行によって恩恵を受けるコールバック関数にのみ色を付けることで、 アプリケーションに対して段階的に並列性を導入できる。 それに対して、スレッドの典型的な利用方法では、すべての計算に対して並列性が要求されてしまう。 例えば、クライアントごとに1個のサーバスレッドを作ることは、 すべての、定数でなく、スレッド内に閉じていないデータに対して、同期処理が必要になってしまう。 libasync-mpによって提供される並列処理のモデルは、デッドロックを回避することができる： あるコールバック関数は、確実に1種類の色しか持つことができないので、サイクル（再帰）が発生しないからである。 さらに、もしもコールバック関数に複数の色を付けることを許したとしても、 色は前もって宣言されているので、デッドロックを前もって回避することはたやすい。[[br]] libasync-mpのモデルはThreadの同期処理のモデルよりも制限が多い。 たとえば、read-onlyの色という概念は存在しない。 しかし、我々のモデルは、Threadによるやりかたと同じ程度に、 並列性による高速化が見込めるほど、効率が良い。 （訳注：read-onlyのスレッドは、メモリキャッシュを管理する効率に関するヒントを与えるので高速化につながる） libasync-mpは、これから呼び出されるコールバック関数の列（queue）を一つ持っている。 ライブラリは、ＣＰＵのごとにスレッドを一つ確保し、コールバック関数を呼び出す。 それぞれのカーネルスレッドは、それぞれのコールバック関数に付けられた色の情報をみて、 次に実行することができるコールバック関数をキューから取り出して実行する。 さらに、プログラマが指定しなくても、ライブラリによって自動的に追加されたコールバック関数が select()関数を呼び出してイベントを入手し、それぞれのイベントに対応したコールバック関数をキューに追加していく。[[br]] MPプログラミングに対応する理想的な方法は、既存のプログラムをMP化して並列処理による性能を向上させるときに、作業が簡単でないといけない。 そのため、我々は以下の2つの基準に興味を持っている。性能とプログラミングの簡単さである。 我々は、この2つの基準を、SFS file serverの実装を通して測定した[9]。[[br]] 我々の性能測定は、P3 Xeon 4P 700MHzの上でLinux kernel 2.4.18を動作させておこなった。 プロセッサをスケールさせたときの性能は、ベンチマークのために使わない分のプロセッサを完全に停止させた状態でおこなった。[[br]] SFSサーバとクライアントの間のすべての通信は、ストリーム対称鍵を用いて暗号化され、 暗号化ハッシュ鍵を使って認証をおこなう。 暗号を使うので、SFS serverは負荷が高いときには計算処理が主になる。 そのため、libasync-mpを使って、MPによる性能向上ができると期待した。[[br]] SFS serverに対する修正は、クライアントとデータをやりとりするときの、 暗号化、復号化、認証をするためのコードに集中しておこなった。 クライアントに対してデータを送るためのコールバック関数を見れば、 我々がどのようにこのサーバを並列化させたかがわかるだろう。 我々はこのコールバック関数を、3つの小さなコールバック関数に分けた。 1個目の関数は、いままで通り同期処理をおこなった（つまり、デフォルト色のままにした） この関数は、クライアントごとに用意された送受信用のバッファにコピーする。 2個目の関数は、そのバッファ内でデータを暗号化し、他のコールバック関数と並列に動作する。 このコールバック関数は、クライアントごとに異なる色を付けておく。 この修正のために、合計12000行ほどのSFSサーバの中で、90行の変更をおこなった。[[br]] 総合的なスループットを測定するために、複数のクライアントが、 サーバのディスクキャッシュに残った状態の200MByteのファイルを読み込むときのbpsを測定した。 同じ実験を、プロセッサの数を変更しておこなった。[[br]] 図1の、libasync-mpと命名されたバーが、並列化されたSFSサーバのスループットを示している。 シングルＣＰＵにおいては、並列化されたサーバは、元のシングルプロセッサ用のサーバの0.95倍の性能を示した。 並列化されたサーバは、2プロセッサのとき1.62, 3プロセッサのときに2.18, 4プロセッサのときに2.55倍の性能を示した。 プロセッサが増えたら、その分性能が増していくだろう。（訳注：疑問。このサーバの場合は6ぐらいで頭打ちになりそう）[[br]] ハードウェアとOSによる性能限界を探索するため、 オリジナルのシングルプロセッサ用のサーバを、ＣＰＵと同数、複数を立ち上げて性能を測定した。 実際に使う場合には、このような設定は、それぞれのサーバが異なるファイルシステムを提供する場合にしか使えない。 これは例えば、SFSサーバは、ファイル属性の貸し出し状態など、プロセスを越えて同期が必要な情報を、 ファイルシステムごとに管理しているからである。 このテストは、SFSサーバというアプリケーションにおいて、libasync-mpが出せる理論上の上限値を示していると言える。[[br]] 結果は、図1において、N-copyというバーで示した。 libasync-mpライブラリを使って実装されたSFSサーバは、3CPUまでは、理論上限に近い性能を出している。 2プロセッサと3プロセッサの間の差（ringo:これは3と4の差ではないかな）は、 ファイルの貸し出し（ringo:開いているファイルの状況や権限の管理情報などを指すとおもわれる） 状況やユーザーIDのマッピングテーブルなどの共有情報によるペナルティによるものであると考えられる。 == 結論 == イベントドリブンプログラミングの伝統的な考え方は、性能は良いけどプログラミングはやりにくく、 ましてやSMPの性能を引き出すには不向きであるというものであった。 我々は、libasync-mpを使うことによって、 MPの利点を生かすイベントドリブンなアプリケーションを簡単に書けることを示した。