DSMS のベンチマーク（続き）

ソフトウェアの世界では、類似の機能を実現するソフトウェア同士の比較のために、標準のベンチマークというものが存在する。SPEC や TPC などがある。

DSMS では、まだその歴史が浅いため、このエントリに書いたような非常に Domain Specific なベンチマークしか存在しない。我々がベンチマークを作ったとしたら、それはそれで、非常に大きな Contribution にもなるし、論文の refer 率が非常に上がるはずである。

StreamWeb の方向性(続き)

このエントリの続き

　研究の Contribution が「単に既存のアルゴリズムを System S にのっけました」的な論文になる恐れがある。これや、これなどのアイデアを核に研究を進めて行く方が、新規性も出しやすいし、かつ論文にも通りやすいはず.

ただし、産業界が即求めているのは、このエントリに書いたようなこと。研究としての新規性を出すのか、実用性を重視するのかの判断は難しいが、確実に学会では前者が評価される。

Click Fraud Detection Algorithm

WWW2005 に採択されたクリックストリームに関する論文

Duplicate Detection in Click Streams, Ahmed Metwall (UCSB), WWW 2005
http://www2005.org/cdrom/docs/p12.pdf

StreamWeb の方向性

StreamWeb プロジェクト、特に森田君が卒論で行う研究テーマに関する Main Contribution は以下の通り。

- ストリームコンピューティングの Web への（ほぼ）初の応用
- 以下の３つの応用を DSMS で実装し、有効性を示す。評価は、DSMS なしのバッチ型のバージョンと、DSMS でリアルタイムに処理する手法を比較。結果が得られるまでの時間、および必要なストレージ量が DSMS のバージョンが上回ることを示す。

(1) リアルタイムログ処理および圧縮処理
(2) 売り上げ状況を店舗にリアルタイムに伝える
(3) Click Fraud Detection (既存の Fraud Detection Algorithmを作る）

- 上記アプリケーションを GPU で性能最適化

研究の方向性としては、上記作業によってパフォーマンス特性がわかるので、この後、以下の研究テーマに広がっていく。
(X) Online と Offline の処理の融合 (スケジューリングなど）
(Y) Cloud との融合 (Eucalyptus)
(Z) Load Shedding の技術の融合

ClickStream の分析ツール

ClickStream の分析ツールのオープンソースソフトウェアは、ここに
リストアップされている. いずれも、Apache などのログから、グラフ視覚ツール graphviz を用いて視覚化。
Apache2Dot
Visitors
Web Utilization Miner
Statviz
"StatViz can actually show you these reports LIVE... If you configure the logfile to "php://stdin" then StatViz will read the log lines from STDIN. It will then periodically generate reports as the log is processed, thus allowing you to watch your traffic patterns in real-time" だそうで、リアルタイムに視覚化することも可能。

クリックストリームの過去の研究は、ここ (PDF) などが参考になるので、見てみてください。

Predicting Online Task Completion with Clickstream Complexity Measures: A Graph-Based Approach
http://www.net-question.com/chairerbc/fichiers/KSN06.pdf

ここによると、Click Fraud (Wikipedia) の Real-time Detection にも System S が使えそうです。

"As pay-per-click advertising becomes the fastest growing segment of all　advertising tools, malicious click fraud is keeping pace and shows no signs of　containment.　Advertisers are demanding resolution to this problem because it can cost them millions of dollars. Successful search engines, marketing companies and e-businesses know that fighting click fraud means quickly recognizing patterns, either through statistical algorithms automated for online filtering, or manual offline analysis. These analyses require comprehensive processing of terabytes of dynamic, detailed data in near real-time to quickly detect and stop the fraud from spreading."

また、Google でも Click Fraud Detection の対策をしているようです.

Botnet （悪意のあるコンピュータプログラム）による Click Fraudによる非常に深刻らしく、Fraud の31％が Botnet によることを示したグラフ（http://www.techcrunch.com/2009/01/27/report-click-fraud-at-record-high/）

ClickStream

Web サイトでのユーザーの行動履歴 ClickStream はWikipedia によると、売買されているものらしい。しかし、このデータ自体は場合によっては個人を特定できてしまう。AOL は一時期、研究用途に限り、検索クエリのログデータを Web 上で公開していたが、個人が特定できることがわかり、裁判沙汰になったことがある。

ユーザーのクリックストリームデータは、ユーザー（顧客）の嗜好や行動パターンなどの分析に非常に意味があり、以下のようにも書かれている。StreamWeb プロジェクトでは、このクリックストリームをリアルタイムで即座に解析することによって、よりビジネスの差別化につながれる技術基盤を作れると良いだろう。

As discussed in Van den Poel & Buckinx (2005), clickstream analysis can be used to predict whether a customer is likely to purchase from an e-commerce website. Clickstream analysis can also be used to improve customer satisfaction with the website and with the company itself. Both of these uses generate a huge business advantage. It can also be used to assess the effectiveness of advertising on a web page or site

CEP 関連ニュースサイト

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

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

ハーバード大の CitySense プロジェクト

ハーバード大学の Matt Welsh が率いる CitySense プロジェクト (http://www.citysense.net/)

町中にセンサーをばら撒き、温度、風速、CO2 濃度など町の様々なデータを取得し、環境汚染などに役立てる。センサーデータとしては以下の情報が取れるらしく、ここから　RDB に格納されたデータも取得できる。現在は、RDB だが、センサーからリアルタイムに取れるようになれば、System S の良いアプリケーションとしても良いだろう。

過去のデータを利用して、リアルタイムに町の状況をトラッキングする GUI のデモを作るのも面白いのでは.

• Air Pressure
• Air Temperature
• Relative Humidity
• Wind Direction
• Wind Speed (avg., min., & max.)
• Rain Amount
• Rain Duration
• Rain Intensity
• CO2 Density (parts-per-million)
• Sound Level (decibels)

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
  

実験環境

現在の研究室の実験環境を整理。

クライアント：　
- センサーデバイスをシミュレートするマシン（StreamDNA の場合、１台のみ）
- サーバー側のCPU使用率を少なくとも１００％にするだけのノード（Load Shedding 技術検証のため）
- System S は必要なく、また、OS も何でもよい。
- Condor クラスタのノードを用いることにする。3～4台はあればよいはず。

サーバー (Web サーバー)
- Apache Web Server, PHP, OS は何でもよい
- Condor クラスタのノードを用いる

サーバー (DSMS システム)：
- GPU マシン (Tesla)１台: CentOS 上で System S を稼動させる。

• StreamDNA において reference 塩基配列がメインメモリ上にのるように, 4GB 以上の RAM が必要。

- DSMS 稼働マシン：　

• 上記 GPU マシンと比較して、若干性能が低いマシン群
• CentOS 5.2 + System S (64 bit版) が稼動。スケーラビリティを検証するために８ノードは欲しい. いずれは CPU をQuad-Core に換装

- NIS/NFS サーバー: 上記 DSMS 稼動マシンの /home を提供


クライアントマシンと　Web サーバー用には Condor クラスタを用いれば良いが、DSMS サーバー用に少なくとも8ノードは欲しい. NTTX-Storeで、時折、格安でサーバーを売り出しているようだ。今日の時点で、NEC Express 5800 が１万８００円で買える。信じられないほど安い。クライアントマシンには向くが、PCI-Express x16 がなく、将来的にGPUカードを挿すかもしれないので、断念。

HP のML115 G5というマシンが、どうも四半期の決算日に合わせて売りに出されているようだ。 こちらのマシンが売りに出されたら即購入しよう。要チェック。

DSMS のベンチマーク

Linear Road: A Stream Data Management Benchmark, VLDB 2004
http://www.cs.brandeis.edu/~linearroad/

Aurora (Brandeis 大学、ブラウン大学、MIT の共同DSMSプロジェクト）と STREAM (スタンフォードのDSMSプロジェクト）のストリーム処理システムのベンチマークシステム。

渋滞度や事故に応じた課金体系（混んでいるときに通行すれば高くなる）を採用する高速道路課金システムをシミュレート。RDBMS (System X と製品名を隠している）と Aurora とを比較し、Aurora が5倍程度、性能を発揮。(STREAMのデータはなし）

チャレンジは以下のとおり。

(1) 入力は？
ただ単にランダムではいけないこと。車などの動きをシミュレーション
--> MITSIM (MIT Traffic Simulator) という交通シミュレーターを使用
(2) 性能比較のメトリックスをどうするか？
クエリが Continuous であるため Completion time ではなく、Response Time と スループット（処理したクエリ数）を用いる
--> L-Rating というスコア（レスポンスタイムとスループット）を導入
(3) Validation をどうするか？　
ベンチマークとして、同じクエリに対して、その時々の状況（混雑度）によって出力となる料金が異なる。よって、ベンチマーク自体、
　　 ひとつのクエリに対して、複数の料金を返す
(4) 現在、Continuous Query は存在しない
--> 特定のクエリ言語を作るのではなく、フォーマルに predicate calculus を使用

各車両からは位置情報を30秒に1回、 1％の確率でクエリをシステムに発行。（その中で50％は account balance, 10% は 1日の合計料金、40%
は目的地までの時間）

DSMS はそれら常に到着するデータを受信し、以下の処理を実行
(1) あるセグメント上に車が何台存在するか、平均速度はどのくらいかを1分ごとに計測
(2) 事故も見地リアルタイムに渋滞度、事故度を判定
(3) クエリ（セグメントの統計及び事故の状況を見て料金や目的地に到着するまでの時間）を処理し、各車両に伝える

Linear Road はあくまでベンチマークの仕様。論文では、Aurora と System X (RDBMS の製品）を用いて Linear Road を実装。System X では、300行のクエリとコードからなる Stored Procedure として実装。

Telegraph CQ

UC Berkeley の Michael Franklin らの研究室のDSMS システム. System S の SPADE のように データフロー型の言語ではなく、DBMS の世界では標準の SQL を拡張した Continuous Query 用の言語を提唱。

http://telegraph.cs.berkeley.edu/にはソフトウェアのソースコードや論文が公開されている。

Load Shedding に関する既存研究

Load Shedding に関する論文をいくつか読んでいる。


Data Triage : An Adaptive Architecture for Load Shedding in TelegraphCQ, Frederic .et.al, ICDE 2005,

TelegraphCQ (UC Berkeley の DSMS システム) が対象にしているのは、Continuos Query で、SQL の拡張版のようなクエリ言語。たとえば、R, S, T というデータストリームがあるときに、以下のように JOIN クエリを記述することができる。
SELECT * FROM R, S, T WHERE R.a = S.b AND S.c = T.d
このクエリを、Load が Bursty な時に Drop するのではなく、データのサマリーを求めるように Query を書き換える規則を提案。

評価実験では、正解セットが与えられ、ロードを Bursty な状態にしたときに、提案する Data Triage (彼らの Load Shedding 技術）が、他の既存手法（単に Drop する方法、Summarize する方法）と比較して、エラー率が低いことを示している。特にどのドメインのデータか、実アプリケーションかは示していないところが少し弱い。

Utility-driven Load Shedding for XML Stream Processing, Mingzhu et.al, WWW 2008

WWWにもこの種の論文が載ったということで、非常に頼もしい。この論文は、データストリームが XML 形式の時の Load Shedding 手法を提案。RSS (Rich Site Summary) やセンサーデータのフォーマットは XML 形式が採用されていることが多いはずであり、実用性は高い。

　この論文では、XML データ全体を Random に Drop するのではなく、XML の構造上、重要な要素、重要でない要素を分類し (Utilityまたは Preferenceと呼び、ユーザが XQuery で指定する）、かつ、その要素を頂点とするサブツリーの処理にかかるクエリの処理を計算し、投資対効果 (ROI)を計算。ROI が低いものに関しては、処理をスキップするようにする。論文で取り上げられている例は、例えば、オンラインショッピングサイトの注文データ。注文データには、商品ID, 顧客ID、そして顧客のメールアドレス、顧客の詳細情報（住所、電話番号など）、コメント。これに対して、Bursty な状況では、とりあえず、顧客の詳細情報を含むような XML のサブツリーは処理せず、他の要素のみを処理する。

Load Shedding in a Data Stream Manager, Nesime Tatbul (Brown University), VLDB 2003 (PDF)

DSMS における Load Shedding を最初に提唱した論文。

Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing, Nesim Tatbul (ETH Zurich), VLDB 2007

上記論文の同一筆者。既存の Shedding 技術はシングルノードを仮定しているが、この論文では複数ノードで DSMS が分散して稼動する場合を仮定。

産総研

　本日は、産総研の秋葉原オフィスにて Ninf の１５周年記念ワークショップというものに参加してきました。Ninf はグリッドのような広域ネットワーク環境上（高遅延かつ低セキュリティ）で RPC (Remote Procedure Call) を実現するミドルウェアであり、我が国の重要なグリッド研究成果の一つとも言えます。

　久しぶりに、産総研の研究員の方々とお話しする機会があり、ストリームコンピューティングの議論もしてきました。参考のために、そのフィードバックをしておきます。

- ストリームコンピューティングにとって、汎用的なプログラミングモデルは本当に必要なのか？極端に言えば、すべてUDOP（コールバック関数とも言える）として実装することになるのでは？

- StreamDNA は、画像認識だけではなく、２次解析（Smith-Waterman 法のGPU版）のストリーム化までやって初めて研究的な価値が出るのでは？また、StreamDNA のリアルタイム性はシビアではないのでは？

- Load Shedding にこそストリームコンピューティングの本質があるのでは？世の中のアプリケーションとして、どんなタイプのアプリが Load Shedding を許容するかを分類すべき

-ストリームアルゴリズムなどOne-path のアルゴリズムのみを対象としているのか？必ずしも、One-path だけではなく、ある程度のバッファリングは許容する

- awk はストリームエディタと言える。

Ninf プロジェクトの15周年記念

中田さんによる発表

東大森下先生

東京大学の森下真一先生。元 TRL。高速シーケンサーを使った研究をしているらしい。柏キャンパスのようだが、一度お話しを伺いに行きましょう
http://mlab.cb.k.u-tokyo.ac.jp/

可視化ツール

IBM 小澤さんから教えてもらった複雑ネットワークの可視化ソフトウェア Cytoscape　http://cytoscape.seesaa.net/
- StreamDNA の可視化ツールとして使えるかもしれない

Moore's Law for Genetics

シーケンサーの性能向上を定量的に示す資料。５枚目、６枚目注目。
”Moore’s Law, Genomics and the
Future of Animal Breeding”　David MacHugh, Animal Genomics Lab., UCD, (閲覧）

Prepare for the Deluge

Prepare for the deluge (PDF) という 2008年の Nature の論文に次世代シーケンサーのデータ爆発のことが書かれている。論文の最後は以下のように締めくくられている。

If the data problem is not addressed, ABI’s SOLiD, 454’s GS FLX, Illumina’s GAII or any of the other deep sequencing platforms will be destined to sit in their air-conditioned rooms like a Stradivarius without a bow.

StreamDNA の論文を書くときには、これを reference すべき。

また、画像データの扱いだが、４５４シーケンサーの場合は、ソフトウェアの更新により生画像からの塩基変換をより高精度に行うことができるので、画像データ（圧縮してもよし）を取っておく意味もあるということが書かれている。

その他、次次世代シーケンサについて書かれた記事。
http://www.wired.com/wiredscience/2008/07/british-institu/

Smith Waterman法の CUDA 実装

Smith Waterman 法の CUDA 実装として CUDASW++ というものがあるそうです。http://www.biomedcentral.com/1756-0500/2/73　に論文があります。松浦君、読んでみてください。性能評価もしっかりとされているようです。

ソースコードは、SourceForge(http://cudasw.sourceforge.net/) にオープンソースとして公開されているので、我々も利用できますね。とりあえず、我々の研究室でも動かしてみましょう。まあ、今は、院試に集中しましょう。

ミーティング＠慶応矢上キャンパス

　今月締め切りの公募にStreamDNA のネタを出すべく、慶応の宮本先生とミーティング。初顔合わせということで、お互いの技術紹介をした。それなりにこちらのやりたいことを理解してもらえたのではないでしょうか。次のステップとしては、まずは机上で計算できる定量的な効果を示せるといいのでしょうね。黒川研の東君からの返答を楽しみに待ちましょう。

東工大発のベンチャー

こんなにも東工大発のベンチャーがあるのか。。。
http://www.sangaku.titech.ac.jp/achieve/venture.html

古井先生の会社
http://www.inferret.jp/

吉瀬先生の会社
http://mierupc.com/?D=A

内閣府

内閣府の科学技術政策
http://www8.cao.go.jp/cstp/s&tmain.html