SEDA (Staged Event Driven Architecture) (Matt et.al, SOSP 2001) 続き

このエントリの続き。

SEDA (Staged Event Driven Architecture), Matt Welsh, SOSP 2001

Epoch-making 的な論文。OS (Operating System) の分野では最高峰の国際学会 SOSP に通っているだけあって、論文の完成度も非常に高い。この筆者 Matt Welsh さんは、松岡研究室にしばらく滞在していたこともある。今はハーバード大の教員。以下、論文概要。

スケーラブルなWeb サーバーを作る手法として、従来、スレッドベースとイベントベースの手法がある。

スレッドベース

• 基本的には１リクエストにつき、１スレッドがすべての処理を担当
• スレッド数が多すぎると、 キャッシュミス, TLB ミス、スレッドのスケジューリングオーバーヘッド、ロックコンテンションなどの問題が顕著になる
• 上記の問題は、通常、スレッドプールのサイズを制限することによって、スレッド数が必要以上に増えないようにしている (Apache など)
• しかしこのモデルだと、すべてのサーバが busy 状態になってブロック状態になると、レイテンシが極端に増加しだしてしまう
• スレッド毎に割り振られるロードは、扱うファイル(HTML) サイズによって異なる。例えば、大きなファイルサイズで、キャッシュにのらないような場合は時間がかかり、ディスクキャッシュにのるような場合には負荷が小さい。 全体のレイテンシを下げるには、前者の負荷が大きくかかるスレッドを Shedding することで、負荷の小さいスレッドをより多く実行することができるが、これをやるには全体のスレッドの様子を知る仕組みが必要。OS によるスレッドのスケジューラはここまで感知してくれない（OS をいじる研究は存在する）
• ロードが上がると、スループットも維持できないし、かつレイテンシも悪くなる
• ただし、ソフトウェアの生産性という面では優れる
  

イベントベース

• Flash や Zeus, Lighttpd などの Web サーバーはイベントベース
• 単一のスレッドのみが動き、各リクエストにつき一つの FSM を作成。FSM の状態の変遷はイベントによってトリガーされる
• イベントは、ソケットのコネクション確立、ファイルシステムアクセスなど
• 単一スレッドが、イベントを受け取ると、それに相当する FSM の状態遷移を移動させる
• ファイルシステムアクセスなどは非同期のインタフェースを持っていないので、Helper Process を立ち上げることによって、擬似的に非同期を実現
• このモデルでは、イベント処理をするスレッドがブロックをしないことを仮定しているが、現実はそうはいかない。割り込み、ページフォールト、GC (Javaの場合）などが発生して、ブロックしてしまう
• ロードが上がったときにでも、スループットを維持できる利点がある。ただし、レイテンシは増加する
• イベントベースは、ソフトウェアの生産性で劣る。
• イベントのスケジューリング、オーダリングを開発者が自前でやらなければいけない。また、スケジューリングアルゴリズムは、アプリケーション依存になってしまう
• コードのモジュラリティがない。スレッドベースより遥かに難しい
  

スレッドベース、イベントベースの問題を解決する SEDA と呼ばれる フレームワークを提案

SEDA

• スケーラブルなインターネットサービスを構築するためのフレームワークを提案
• アプリケーションをステージに分割し、イベントキューによって結ぶ
• イベントモデルの性能の利点と、スレッドモデルのプログラミングの容易さ、のいいとこ取り
• 性能向上させるポイントは以下
  (1) キューの取り出し方のスケジューリングをユーザに任せることで、アプリケーションに特化した適切なスケジューリング方法を実現できるようにした(上記のスレッドモデルでは無理）
  (2) スレッド数をロードにあわせて動的に調節する仕組みを提供
  (3) ブロックを避けるために、非同期の Socket I/O , File I/O を実装。 --> JavaのNIOにつながっている
  

• 各ステージは、スレッドプールによって実行され、プールサイズはロードによって動的に変更可能にする
• 基本的にはスレッドベースだが、スレッド数をできるだけ少なくする
• 各ステージのロジックは、イベントハンドラーを実装する
• イベントキューをはさむことによって、各イベントハンドラーがロードによって、キューからフェッチするポリシーを明示的に書くことを可能にする。例えば、Load Shedding で、イベントをすることも可。
• リソースコントローラは、適切なスレッド数を制御するスレッドプールコントローラと、一つのスレッドが処理するバッチコントローラの2種類を用意。また、カスタマイズのコントローラを作ることもできる
• アプリケーション開発者は、イベントハンドラを記述するが、スレッドは自ら作成しない。すべてランタイムにまかせる
• ステージ、イベントキューの導入によって、ソフトウェアの開発生産性も向上
• コードのモジュラリティが向上する
• ステージ間で流れるイベント列をプロキシをはさむことによって眺められるなど、デバッグがしやすくなる
  

System S との比較？

• SEDA で言うところのステージは SPADE のオペレータに相当する。プログラミングモデルは非常に類似
• ただし、SPADE は DSMS システム用言語として、Aggregate など時系列データの処理に特化したオペレータをビルトインで用意している
• IPDPS の Elastic Operator の論文は SEDA の影響を受けている
  S. Schneider, H. Andrade, B. Gedik and K.-L. Wu , Elastic Scaling of Data Parallel Operators in Stream Processing