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

　データストリーム処理のアプリケーションでは、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日までのグラフ。バーストが何回か起きていることが見てとれる。