データストリーム処理におけるメモリ消費量を考慮したジョブスケジューリング

　データストリーム処理のアプリケーションでは、Aggregate(条件にマッチするまでメモリ上に蓄えられる) や Join (複数ストリームの待ち合わせ) など、オンメモリ上にデータを蓄えて処理するような処理が必要になるものがある。このとき、Split オペレータなどによってデータのある属性のハッシュ値を元にデータを並列ノードに分散させる場合、データの偏りが生じ、物理メモリを使い果たす場合がある。例えば、CDR 処理においては、ある特定のユーザーの通話履歴が極端に多い場合、そのユーザーのハッシュ値を担当する物理ホストのメモリ量では賄い切れなくなる。このような問題に対応する為、実行時にデータの偏りとメモリ使用量を定期的に監視し、負荷の均衡が保たれなくなった場合には、負荷を実行時に動的に均等にする機構が必要となる。

　実行時に動的に均衡を適正に保つ上で、いくつかの条件を満たす必要があるが、その例を次に示す。

- 溜めていたデータはロスしてはならない。すべての溜めていたデータは正しくマイグレーション先に送られる。マイグレーション先への負荷を最小限に留める。

- データは留め止めなく流れてくるため、上流のオペレータのバッファで滞留しないように、瞬間的にマイグレーションできなければならない

[StreamDS] 論文投稿完了

松浦君が COMSYS 2010 に論文投稿を完了しました。大変お疲れ様です。結果はただ待つのみですが、どちらにしてもやり残したことがいくつかあると思うので、インターンが終了したら少し整理していきましょう

[StreamCloud] 関連論文

先日フロリダで行われた国際学会 Cloud 2010 で、StreamCloud プロジェクトに関連するであろう論文一覧です。詳細はhttp://www.thecloudcomputing.org/2010/IEEE-ICWS-SCC-CLOUD-SERVICES-AdvanceProgram.pdfを見てください。

- Understanding Performance Interference of I/O Workload in Virtualized Cloud Environments (CLOUD2010-3007), Xing Pu
- Performance Measurements and Analysis of Network I/O Applications in Virtualized Cloud (CLOUD2010-3008), Yiduo Mei
- Integrating Resource Consumption and Allocation for Infrastructure Resources On-Demand (CLOUD2010-3010), Ying Zhang
- Mining Twitter in the Cloud: A Case Study (CLOUD2010-3014), Pieter Noordhuis
- Maximizing Cloud Providers' Revenues via Energy Aware Allocation Policies (CLOUD2010-3017), Michele Mazzucco
- Workload Migration into Clouds . Challenges, Experiences, Opportunities（CLOUD2010-3020), C. Ward
- Performance and Power Management for Cloud Infrastructures (CLOUD2010-3042), Hien Nguyen Van
- Optimal Resource Allocation in Clouds (CLOUD2010-3053), Fangzhe Chang
- Fault Tolerance Middleware for Cloud Computing (CLOUD2010-3009), Wenbing Zhao
- Using Cloud Technologies to Optimize Data-Intensive Service Applications (CLOUD2010-3003)
Dirk Habich

新たなデータストリーム処理系を作る動機

　今年後半から、研究室発のデータストリーム処理系を設計及び開発していこうと思いますので、そろそろ概要設計ぐらいには取り掛かりたいと思います。

　処理系の実装の動機は「System S のランタイム周りの制約から離れたい」というのが大まかな動機です。例えば、現在感じているだけでも以下のような制約があります。

(1) ランタイムの制御、特にスケジューラ周りに手を入れられなく、その周辺の研究に手を出しにくい。たとえば、今のスケジューラは CPU 使用率しか見ていませんが、メモリ使用率やリソース（データベースなど）の局所性を生かした作りになっていません. オペレータの最適配置問題を最適化問題に落として解こうと思っても、その結果をランタイムに反映できません

(2) 高信頼性（つまり必ずデータロスはない）を実現するデータストリーム処理系を実装するには、現在は、System S の外でその機構を作らないといけません。ランタイム自身にその機構を加えることができるはずです。

(3) 鈴村の SYSTOR 2010 で発表した論文では、入力データの自動分散化がスケーラビリティを出すには重要と書きましたが、System S でも強引にやればできますが、自然な形でランタイムでその機構が作れるはずです。

(4) システム自身が様々なパッケージに依存しており、「Write once, run anywhere」 ではありません. Amazon 上で動かしたり、TSUBAME などの巨大クラスタ上でスケーラビリティテストをやりたくてもできません。

　実装言語は Javaにします. 性能は多少犠牲にしますが、プラットフォーム独立性や開発生産性およびメンテナンス性を考え, Java で実装します。特に金融のようなマイクロ秒で勝負するような処理系を作ることを目的にしていないため、レイテンシなりスループットが少し下がっても問題ないでしょう。また、GPU との親和性は当然悪くなり、JNI 経由呼び出しになります。その代わり、Python や Ruby, PHP と言ったスクリプト言語の処理系も JVM ベースのものが最近はあるため、UDOP に相当するようなユーザ定義オペレータをそれらのスクリプト言語でも記述することも当然可能になります。

ただ、最後に断っておきますが、当然、System S も併用していく予定です。ストリームマイニングやアルゴリズム周りの研究、そして GPU との統合は System S 上でも可能なはずです。

論文締め切り

　研究室メンバーのそれぞれの学会の締め切りが近づいてきました。Internet Conference 2010 と Comsys 2010、それぞれ査読つきなのでそれなりのまとまりが必要ですが、頑張っていきましょう。

「タブレットコンピューターとそれを取り巻く産業構造に係る最近の動向」

「タブレットコンピューターとそれを取り巻く産業構造に係る最近の動向」
http://www.ipa.go.jp/about/NYreport/201006.pdf

[StreamTwitter] 2010年6月の Tweet 数解析

6月1日から6月30日までの Tweet 数がすべて取れたので、再度解析しました。前回と同様に日本語の Tweet のみを抽出しています。

結果として面白いのは、20214番目のデータ(1単位は1分）で通常のピーク数よりも3倍の Tweet 数が見られ、Bursty なデータが見て取れるということです。20214番目は、6月14日あたりということですが、これはワールドカップで、日本とカメルーンが対戦した日です。

解析ですが、NFS がボトルネックとなるので、st01 のみの4コアで計測し、3時間程度で解析が終了しました。st01-st08 まで8台あるので、入力データ及び出力データをうまくローカルディスクを利用しながら解析すれば30分台で解析できるはずです。



以下は、そのバースト時が起きた時刻を中心とした1時間のデータ。



以下、6月10日から6月30日までのグラフ。バーストが何回か起きていることが見てとれる。

[StreamTwitter] べき乗則に従う Twitter のリプライ回数の頻度

1ヶ月の Twitter の返信頻度を System S / SPADE で解析した結果、べき乗則に従うことが見てとれる。

X軸はリプライの回数。Y軸は頻度を対数にした数値。用いたデータは4月中のほぼ1ヶ月のデータ。最大返信数は197．平均は 3.874 回、中央値は 3 回。

Twitter ログ解析 4/1 から 4/26 の１分間単位の Tweet 数の変遷

Twitter ログ解析 4/1 から 4/26 の１分間単位の Tweet 数の変遷

最大値：811
最小値：1 (怪しい）
平均値：241.82
中央値：235
標準偏差：112.37

以下、任意の3日間を切り出したときのグラフ





以下、ヒストグラム。X軸は 1分間のTweet 数。

講演＠NEC 中央研究所

　NEC中央研究所からの依頼で、「ストリームコンピューティングの最新動向」と題して、講演してきました。研究室からは、雁瀬君、石井君、そして徳田研の Li さんも来てくれました。結構、活発に質問してくださったので、こちらも非常にしゃべりやすかったです。やはり、「質問力」は重要ですね。あういう場できっちりと質問しているできる人こそ、社内での立場が良くなります。

　

　ところで、ブログ、ほぼ1ヶ月更新していない人がいますが、更新してください。

博士課程に進学するということ

たまには、研究以外のことも書きます。

博士課程に進む、ということはちゃんとした信念を持って進めば良いことだと思います。私自身は、修士から博士課程への進学を決めなければいけないときにちょうど米国に研究留学中でした。そもそもアメリカにそのまま残ってUSのシリコンバレーでの就職を目指していた私でしたので、鼻から博士課程など考えていませんでした。しかし、USでの就職というのは、Ph.D 、つまり博士号を持っているか持っていないかで、圧倒的に博士号を持っている方が有利ですし、格段に年収の差が出てきます。それと、USで研究していた研究テーマが SuperComputing という HPC (High Performance Computing) 系では競争率の高い国際会議に採択された、というのも大きな自分への勇気付けにもなったのですが、そんなこんなで、博士課程への進学を決めました。そんな人生の選択をせまられていた時期が、皆さんとあまり大差ない歳だったかと思います。

　博士号を取るということは決して簡単なことではないと思いますが、一番のメリットは、修士で企業に就職して習得できないことが、若くて吸収力のある3年間のうちに得られるということだと思います。ほとんどの企業がトップダウンに戦略を決めていくので、修士で入ってしまうと、その中で決められたプロジェクトに上から言われるがままに遂行するだけで、自らの発想力、プレゼンテーション能力、グローバルに活躍する素養などを身に着ける余裕などありません。しかし、それがある時、必ず必要になってくるのです。私自身、企業に勤めて、修士で入ってくる人材と博士で入ってくる人材を見ますが、格段にそれらの違いがあると感じます。

　ただ、一つだけ注意しなければいけないのは、ちゃんとしたビジョン、3年間で成し遂げておきたいことをしっかり持って博士課程に進まないと、これは逆に良くありません。これらを見極めるというのが、4年生の後半から M1 の冬ぐらいまでだと思います。企業の良し悪し、アカデミックの良し悪し、を私は幸いにも十分に感じています。各自、十分に考えて周りに流されず、進路を考えていってください。

ICDE 2010 勉強会

データベース系の会議 ICDE 2010 の勉強会で、研究室の学生5人が発表しました。大変、お疲れ様でした。http://qwik.jp/icde2010readings/

[論文紹介] Operator Placement Optimization

Query-Aware Partitioning for Monitoring Massive Network Data Streams, Theodore, (AT&T Labs)

[論文紹介] High-Availability Algorithms for Distributed Stream Processing, ICDE 2005

High-Availability Algorithms for Distributed Stream Processing, Jeon-Hyon Hwang, Micheal Stonebraker, ICDE 2005

データストリーム処理システムの耐故障性 (Fault Tolerance)、高可用性 (High Availability) に関する論文。かの有名な Micheal Stonebraker 等のグループの研究。データベース周辺ではこのような FT / HA に関しては既に様々な研究、技術が存在するが、この論文ではじめて、データストリーム処理システムに関する適用が試みられている。

当然、アプリケーションが要求するノードダウン時のデータ損失の影響度合いによるのだが、一般的に、当論文では、３つのリカバリーモデルが存在すると述べている。Precise Recovery, Rollback Recovery, Gap Recovery. いずれも、プライマリーサーバー、バックアップサーバーの２つを仮定しており、プライマリが落ちたらバックアップサーバーに処理を委譲。プライマリとバックアップのステートを常に同期させることも考えられるが、ランタイムへのオーバーヘッドは多大なものになる。よって、このオーバーヘッドを少なくするために、以下の３つのモデルを列挙。

• Precise Recovery: 一時的に処理の応答時間は増えるが、Failure を完全に排除し、結果にも影響を与えない。金融、証券系では必須
• Rollback Recovery: 入力データのデータリカバリまでは保証するが、出力する計算結果が完全に一致するとは限らない。プライマリとバックサーバーノードの２つがあり、バックサーバーで再処理させた場合に結果が異なることを許す
• Gap Recovery: 最もリカバリー保証がゆるい方式で、結果に影響を与えない古いデータは破棄し、ランタイムへのオーバーヘッドやリカバリーのスピードを高速化する方式

また、上記のモデルを実現するアプローチとしては以下の方式を提案

• Amenesia: ランタイムへのオーバーヘッドを与えずに Gap Recovery を実現
• Passive-Standby: プライマリはセカンダリ（バックアップ）に定期的にステートを送信
• Active-Standby: セカンダリはすべてのタプルを並行して処理
• Upstream backup: アプリケーション上の下流のノードが落ちた際には、上流のノードが、ログに一時的に保存しているタプルを再送信

4番目の Upstream Backup がユニークであろう。詳細は論文を。

時空間データベースに関する論文

Geotagging with Local Lexicons to Build Indexes for Textually-Specified Spatial Data, Michael, D. Lieberman (University of MaryLand), ICDE 2010,

インターネット上の記事などから地名データを抽出し、周りのコンテキスト情報からその地名データをほぼ正確に緯度、軽度に変換するための手法を提案。昨今、写真共有データベースの Flickr などでは、写真に位置情報を付与するサービスを提供しているが、それよりも更に難しい問題に取り組んでいる。

C3: Concurrency Control on Continuous Queries over Moving Objects, Jian Dai, ICDE 2010

GPS や RFID など常に移動し続けている移動物体オブジェクトの位置情報を管理し、それに対するクエリを一貫性を保ちつつ正確な答えを返す lazy-update の方式を提案。空間データベースのインデックスとして良く使われている R 木 は覚えておくべし。

データストリーム処理におけるメモリ使用量を考慮したスケジューリング

データストリーム処理のスケジューリングの研究では、System S のSODA や COLA などの論文において、主にＣＰＵやネットワークの通信量を見ながら全体のスループットを向上させる論文があるが、メモリ量を最小化するようなスケジューリング方式が以下の論文に述べられている。

------

Chain: Operator Scheduling for Memory Minimization in Data Stream Systems

Babcock, Brian and Babu, Shivnath and Datar, Mayur and Motwani, Rajeev (2003) Chain: Operator Scheduling for Memory Minimization in Data Stream Systems. In: ACM International Conference on Management of Data (SIGMOD 2003), June 9-12, 2003, San Diego, California .

データ工学研究会のプログラム

来週 6月28日、松浦君と森田君がデータ工学研究会で発表を行います。場所は名古屋大学です。以下、プログラム。

http://www.ieice.org/ken/program/index.php?mode=program&tgs_regid=47f142a95586bfa10dd18d213411b033e450b0214431c01668661d79fabe984e&tgid=DE&layout=&lang=

[StreamGreen] Google Map + 渋滞情報

[全力案内ナビ] ユビークリンク社 (野村総合研究所 NRI が 100% の会社。URL)

個々の走行車両の位置データから道路の混雑を生成。ユビーリンクと契約しているタクシー１２０００台と、全力案内！会員の位置情報から独自に生成。また、カーナビ用だけではなく、徒歩などのナビ（音声あり）にも使える。

http://rik.skr.jp/archives/2009/07/iphone_42.html

[Google が提供する　Google Map 上の渋滞情報]

http://jp.techcrunch.com/archives/20090825google-maps-will-now-show-you-traffic-conditions-on-the-back-roads/

Google Maps Navigation takes a mobile turn

http://news.cnet.com/8301-30684_3-10384544-265.html

ICDE 2010 論文読み準備

今週は、研究室全体で ICDE 2010 の論文読みをしています。結構、タフですが、有名な学会の論文の精読を何回かちゃんとやると、どのような論文が採択されるのかが、わかってくると思います。頑張りましょう。

[StreamGPU] 第72回全国大会優秀賞！！

森田君の論文が、第72回全国大会優秀賞・奨励賞選定委員で審議の結果、大会優秀賞 に選ばれました。おめでとうございます！http://www.ipsj.or.jp/01kyotsu/award/taikai_yushu/index.html

なお、表彰式は、次回の第73回全国大会（東京工業大学 大岡山キャンパス、2011.3.2-4）で行う予定だそうです。
http://www.ipsj.or.jp/10jigyo/taikai/73kai/index.html

[StreamSR] GPU による高速化

古井先生の「話し言葉音声の認識精度向上のために」という以下の論文の 5.3 章に GPU による高速化の話が少し述べられている。

http://www.furui.cs.titech.ac.jp/publication/2007/AI-Challenge.pdf

Internet Conference 2010

http://www.internetconference.org/

研究室からは以下の論文を提出したいと思います。

西井君: StreamSR の話

石井君：StreamCloud の話

こちらもがんばりましょう。

COMSYS 2010

COMSYS 2010 http://www.ipsj.or.jp/sig/os/index.php?ComSys2010

研究室からは以下の論文を出したいと思います。

- 松浦君＋雁瀬君 --> StreamDS の話

- 上野君 --> StreamGPU の話

7月23日が論文アップロード締め切りです。がんばりましょう。

[StreamCloud] Eucalyptus の内部アーキテクチャ

Eucalyptus の内部アーキテクチャに関して、もう少しどのようなアーキテクチャ構成になっているかを調べていきましょう。An Assessment of Eucalyptus Version 1.4 (PDF) は1年前のものなので、1.6.2 では大幅に改善されていると思いますが、少し参考になります。

- CLC (Cloud Controller), CC (Cluster Controller), NC (Node Controller) は Web Service として実装されており、WSDL (Web Service Description Language) が存在する。CLC-CC 間、および CC-NC 間はSOAP over HTTP で通信しており、eucalyptus.conf のデフォルト設定では、WS-Security が有効になっているので、暗号化して通信が行われている

- Amazon S3 (ストレージサービス） に相当する Walrus はどのように実装されているのでしょう。これも上記のドキュメントには Web サービスとして実装されていると記述されています。

- EMI (Eucalyptus 用のイメージ）の CC から NC への転送、NC 側でのキャッシングポリシー、そして、CLC/CC 側での元の EMI イメージとの同期方法がまだよくわからないので、これも調べてください。

English, English, English !

　今日は慶応大学からのM2 の学生が来て、英語のテクニカルトークをしてもらいました。どの研究分野でもそうですが、国際舞台で自身の研究が認められてこその世界です。英語を聞く機会はいろんな情報ソースもあるので問題ないと思いますが、しゃべる機会は英会話教室などにでもいかないとなかなかないと思うので、率先して研究室で作っていきたいと思います。

[StreamCloud] System S on Eucalyptus 1.6.2

Eucalyptus 1.6.2 を tesla (Cloud Controller と Cluster Controller) と st00 (Node Controller) にインストールし、System S が Eucalyptus から立ち上げた VM インスタンス上で動くことを確認しました。これでこのプロジェクトは一歩前進したと言えるでしょう。

エンジニアリングなシステム構築は見えてきましたが、これからしっかりと、リサーチ的な新規性を考えていかないといけないでしょう。

ちなみに、rpm ではなく、ソースをダウンロードしてみました。 メインのほとんどが Java で書かれていますね。Cluster Controller / Cloud Controller のスケジューラーの部分は未成熟だと Eucalyptus に書かれているので、その部分に手を入れても面白いでしょう。

[StreamXML] XML Stream 関係の論文

特に松浦君に関係しますので、High Performance XML Stream Processing with GPU のテーマに移ったら、以下の論文を読んでいきましょう。

• Efficient Processing of XML Update Streams, ICDE 2008
• Distributed XML Stream Filtering with High Scalability, ICDE 2005,
• XML Prefiltering as a String Matching Problem, ICDE 2008

StreamGreen プロジェクト

３年生向けの StreamGreen プロジェクトのキックオフミーティングが6/7(月)に行われます。非常におおまかにいうと、昨今コモディティ化しているiPhone などの スマートフォンを利用し、それらの位置情報を取得することで、リアルタイムかつスケーラブルな環境・交通モニタリングを行う社会基盤を構築する、というのがプロジェクトの趣旨です。

プロジェクトには複数人参加するので、各自責任を持ってできるように、以下のように役割分担をしていきたいと思います。

1. システムの全体構想を固める
   - プロジェクトの成功の条件は？
   - プロジェクトの出口は？
   - 類似の研究プロジェクトとの差異は？（新規性）
2. Stakeholder とのミーティングを行い、実用性、有効性を確認する
3. システムの全体設計
4. システムのコンポーネント化と詳細設計
5. 上記のシステムのうち、技術的な課題を洗い出し、研究テーマとしてくくりだす（一番重要）

Waterfall 型のシステム開発ではなく、Agile に進めていきたいと思います。まず月曜日は、再度プロジェクトの詳細を鈴村から説明し、その後、毎週のゴールを決めていきたいと思います。

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 とは, これらの複数の条件を同時に満たすような結果(この場合には最短経路) を返すクエリのことをさします。

Must Submit !! SPSS 2011

締め切りは12月。来年は研究室から少なくとも1件はサブミッションしましょう。

International Workshop on Scalable Stream Processing System 2010

http://research.ihost.com/ssps/