Spatial Skyline Query Using Boronoi Diagram

Google Video が提供するビデオには、テクニカルなトークもあり、面白いです。

以下のビデオは、位置情報サービス（Location-Based Service) における Spatial なSkyline Queryに対応するために、ボロノイ図を利用する 研究発表です。

http://video.google.com/videoplay?docid=-2755539754474649930#

ちなみに、Google Map などの地図上で現在地がわかり、ユーザーは、”まずガソリンスタンドに行き、イタリアンレストランに行き、そして映画館に行きたい”というクエリをシステムに出すとします。 Skyline Query とは, これらの複数の条件を同時に満たすような結果(この場合には最短経路) を返すクエリのことをさします。

新メンバー第1回目演習発表会

新メンバー4人（石井君、上野君、雁瀬君、西井君）の第1回目演習発表会がありました。それぞれテーマは違いますが、頑張ったと思います。お疲れ様です。

　次の発表に向けて、ひとつだけ気をつけて欲しいことがあります。　研究では、”実用性”、”新規性”、”進歩性”をディフェンスする要素を定量的なり定性的なり言う必要がありますが、何をやったかを正確に伝える技術に加えて、自分の研究の Contribution を正確に伝える技術がとても重要です。

これをやるには、参考文献や他の研究の詳細をちゃんと調べなければいけないので時間はかかりますが、大事なことなので意識して研究に勤しんでください。

ベンチマーク

過去のエントリで DSMS には今だ標準のベンチマークがなく、過去に１つLinear Road Benchmark というものが提案されていると書いたが、練習として、SPADE / System S 上で実装してみても良いだろう。

R on GPU

オープンソースの統計言語 Rを GPU を用いて高速化するプロジェクト
http://brainarray.mbni.med.umich.edu/brainarray/rgpgpu/

Google Charts API

Google が提供するグラフ作成サービス。URL に パラメータを指定すると、作成された PNG グラフが返される。System S の 最終結果を可視化するためのツールとして使えるだろう。
http://code.google.com/intl/ja/apis/chart/#chart_type

Bootchart

http://www.bootchart.org/
基本的には、サーバ起動時の負荷状況やプロセスの推移をグラフ化するためのツールだが、多分、boot 時でなくてもできるはず。割ときれいな可視化ができそうです。

CEP 関連ニュースサイト

CEP (Complex Event Processing) に関するニュースサイト
http://complexevents.com/

アルゴトレードに特化した CEP 製品の非公式ブログ
http://apama.typepad.com/my_weblog/

Control Theory (制御理論）の Shedding への応用

SEDA の論文にも語られているが、負荷への適応に制御理論を使う研究が存在する。Check this out later.

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
  

StreamIT

MIT のストリーム処理用言語

SEDA: ソフトウェアシステムのスケーラビリティ実現手法

SEDA (Staged Event Driven Architecture) ： タイムシェアリングによるスレッドベース、プロセスベースの並行処理により大量クライアントからのロードを処理するには、限界がある。スレッド方式は、スレッドハンドリングのオーバヘッドが高い。イベントドリブンの並行性を実現するには、単一スレッドが有限状態機械を自前で制御する必要がある。

　上記の論文で提案しているSEDA とは、ソフトウェアをステージに分け、各ステージはキューによって、リクエストを投入。各ステージにはスレッドプールが存在し、その中のスレッドが処理。筆者らは、SEDA ベースの Web サーバー Haboob を実装。Apache Web Server と Flash Web Server と比較し、１０％の性能向上を達成。

メモ

いくつかメモ。

EUCALYPTUS(http://www.eucalyptus.com/open/): 　Amazon EC2 と互換のクラウド環境を実現する OSS のソフトウェア。UCSB （カリフォルニア大学サンタバーバラ校）のプロジェクト。２００１年に米国テネシーでお世話になった Rich Wolski なども参画している。System S などの DSMS をクラウド環境で稼動させる実験を Eucalyptus 上で行うのも面白いのでは。（参考文献：ZDNET )

Amazon Elastic MapReduce（http://aws.amazon.com/elasticmapreduce/）: Amazon の EC2/S3 上で MapReduce を動かすサービス。

Trac (http://trac.edgewall.org/): Subversion とのインタフェース、Wiki などを包括したオープンソースのバグ追跡システム.

Google Code: http://code.google.com/hosting/
Google がプロジェクト管理システムを無償で提供。

KML : Google Earth の入力フォーマット
http://earth.google.co.jp/userguide/v4/ug_kml.html

グリッド環境における TCP

SACSIS 2009 の TCP に関するチュートリアル。非常にまとまっている良い資料だ。
http://www.hpcc.jp/sacsis/2009/SACSIS2009_TCP.pdf

サーチエンジン

Google の創始者 Sergey Brin と Lawrence Page が書いた論文。PageRank の論文と同様に、Web のサーチエンジンアーキテクチャに関する代表的な論文であり、一読に値する。

The Anatomy of the Search Engine: http://infolab.stanford.edu/~backrub/google.html

MapReduce 入門

昨今、大変注目を浴びている 大規模並列プログラミングフレームワーク MapReduce.
ここの Lecture 1 (Introduction), 2 (MapReduce), 3 (Distributed File Systems) を見てみてください。MapReduce やその根底にある分散ファイルシステムの真髄に触れることができるでしょう。