環境 利用 Elastic ー ー 処理
石井 惇志 鈴村 豊太郎
東京工業大学 IBM東京基礎研究所
1.
ー ー 処理 時々刻々 送 ー 対 処理 行う計算手法 あ 手法 用い ー ョン 運用 既 Web
他 ー ョン 比 応答性 重要
ー ー 処理 い ン 増大
致 的 あ 時間 変化 ー ー
局所的 増大 場合 能 限 ン 増大 避 性 維持 要求
ー ー 急激 増加 対 計算資源 物 理的 即時 追加 配置 ー 手続 問題 現実的 い 本研究 ー ー 急
激 増加 対 仮想 ン Virtual Machine：以
VM 追加 ン 発散 抑え
提案 環境 利用 経済的
伴う 具体例 Amazon EC2[2] ッ
従量課金制 あ ン 発散 抑え いえ 必要以 VM 起動 う 分 大 く
う SLA(Service Level Agreement)
ン 維持 経済的 最小限 抑え 必要 生
問題 対処 本研究 ン 経
済的 ー 最適化問題 定式化 必要
十分 VM 確保 手法 提案
2. ー ー 処理系 環境
2.1 ー ー 処理
ー ー 処理 ー 蓄積 逐次処理
いう新 い計算 応答 要求
場合や 前後 僅 ー 参照 い計算 ー 蓄積 困難 処理 適 い
処理系 IBM Research System S 在 System S ー
ー 直感的 処理 記述 SPADE[3] いう宣言
的言語 持 自動性能最適化 行うSPADE ン
SPC[4] いう実行基盤 用い ー ー 処理 実現
SPADE 組 込 ー 処理 記述 C++やJava
い 汎用言語 用い 独自 ー や関数 高度
柔軟 処理 実装 う ー ー 処
理や 研究 適 本研究 System S 利
用
2.2 環境
環境 ッ ワー 計算資源 仮想 ン 提供 環境 あ 従量課金制 課金方式
外部 計算資源 提供 ッ 社内
一定 範 内 利用 ー
分類 既 環境 例 ッ
あ Amazon EC2[2]や ー ンソー Eucalyptus[1] 在 本研究 実際 環境 有効性 示
環境 Amazon EC2 使用
3. ElasticStream 概要
本稿 提案 環境 用い 伸縮性 あ ー
ー 処理系 "ElasticStream" ぶ 本章
本研究 ElasticStream 実装 仮定 前
提 い 述 ElasticStream 論理的 構成
い 述
最 初 本 研 究 い ー ビ 質 基 準
SLA(Service Level Agreement) ン 本研究
定 義 Amazon EC2 Eucalyptus
IaaS(Infrastructure as a Service) 指 自身 保有 計算
資源 数 固定的 変化 い
計算資源 処理 追い い場合 対象 保有 計算資源 SLA 守 必
環境 使用 前提
設計方針 ー ョン 機能 ー 信
部分 計算処理部分 分割 計算処理部分 外部 抽出 分
散 並列化 並列化 計算処理 担
当 ー ョン 一部 環境 実行
動的 並列処理 実現
4. 最適 VM数 計算手法
4.1 対象 ー ョン 分類
ElasticStream 対象 ー ョン ー
並列型 ー ョン 並列型 ー ョン 種類 分類 ー 並列型 ー ョン 計算 処理 負荷 軽く 入力 ー ー 量 多い
ッ ワー ン ン ー ョン 該当 ー ー 処理 性質 多く ー ョン 型 分類 入力 ー ー 任意 割合 分散 各 ン 性能 最大限 引 出 最小限
ン数 ン 維持 具体的
ー ョン Twitter 投稿 文 列 ッ ン や株式
引 VWAP Volume Weighted Average Price：出来高加重平 均価格 計算 あ 並列型 ー ョン 主 入力 ー ー 量 少 く 独立 計算処理 複数あ 処理負荷 大 いCPU ン ン
ー ョン 該当 ー 並列型 ー ョン
分類 い 例外的 分類
複数あ 処理 各 ン 分散 入力 ー
ー 複製 全 ン 送 複製 ー
ー 合計 ッ ワー ン 幅 超え い い 分散 ン 各々 割 当 処理 結果 返 最終的 出力 統合 最終的 出力 具 体的 ー ョン 多次元要素 SST Singular
Spectrum Transformation 異常検知 あ
4.2 最適化問題 定式化
以 ン 経済的 ー 最適
化問題 定式化 い 述 本研究 問題 VM ン ン 起動数 線形計画問題 解く方 針 定 式 化 主 旨 [16] 用 い い SDAR(Sequentially Discounting AR Model) 利用 未来
ー ー 予測 ー 計算資源 処理 量
求 残 VM 委譲 いう あ
ー ョン ー 並列 場合 ー 処理 分 ー ー 計算 く 並列 場合
ー 処理 数 求 い
1 定式化 目的関数 束縛条件 あ 目的関数
起動時間 ッ ー ッ 量 最小化
あ ン ー ッ 量 ー ョン依
あ 最適化問題 考慮 い 束縛条件 ー 計算資源 処理 い ー ー 量
く VM 側 全 処理 い
あ 定式化 線形計画問題 解く実装 C++
実装 ー ンソー あ lp_solve[13] 利用
5. ElasticStream 実装
本章 ElasticStream 実装構成 い 述
2 本稿 提案 ElasticStream ーキ ャ
あ 基本 ー ー 処理系 System S
System S 無い機能 い Ruby 利用 外部的
実装 い 動作 基本的 流 入力 ー ー
StreamManager ー 計算資源 VM
分散 計算結果 再び ー 側 集約
一方 現在 ー ー ー ー
予測 必要 応 VM数 変更 実際
ン ー ッ 最適化問題 ン ー
自動的 更新
6. 性能評価
本章 実 ー ョン 実験前 行 ン ー 結果 い 述 ン ー 使用
ー ョン 擬似 ー 正規表現 ッ ン 行 い ッ ー ー 環境 結果 送信
あ 負荷 加え 単純 ー 処理 追 加 い
実験 Amazon EC2 VM ン ン 数 1
4 変え 同一 ー ー 入力 与え 行
3 VM数 1 2 時 ー ー ン
推移 示 い ー ー 内 個々 ー
あ ー 一 当 0.1KB 10KB 変
え 前測定 行 ン 影響 無
本章 1KB 設定 い ー ン ー 送 信 ー ー ッ 約0.1秒程 あ VM1 場合 途 中 ン 発散 い 2 以 並列化 場合 ン 発散 数 多いほ 低い値 保
い 確認 ー 計算資源
ン 発散 場合 環境 VM 一定数追
加 ン 発散 抑え 実際 能 あ
分 更 ン 発散 抑え 必要最小限
VM数 求 分
7. 関連研究
[15] System S ー 負荷分散機能 組 込 い 研究 単一 計算資源 中 処理 分散 い 対 本研究 処理 委譲先 環境 求
い 異 ョ ュー ン [9] 実行時 間 最小化 線形計画問題 用い ュー ン 手法 い 述 い 環境 処理 委譲 関 [11]
ッ 処理 対象 最適 ョ ュー
ン 行 い [11] 最適化問題 ュー ン 前処理 最初 行 い 本研究 ー ー 処理 いう処理 終わ い ョ 対象
都度最適解 ッ ー い いう 異 [14] ー ー 処理系 ー 分割
い 焦 当 い [8] ー 一部 間引 い 処理 行うLoad Shedding 技法 用い ー
分割 行 い [10] 複数 環境 想定 VM 配置 い 検討 い 本研究 単一 環境 想定 い Amazon EC2 いう実環境 評価 行
いう 異 最適化 対象 [12] う 消費 電力 着目 いう研究 あ
8. 後 展望
本稿 貢献 ー ー 処理 用い
ー ョン 負荷分散手法 ElasticStream ーキ ャ 提案 処理 委譲先 あ 環境
利用 ン ー 最適化問題
定式化 最適 負荷分散手法 提案 現行 ー ー 処理系 無い 実行中 動的 計算 ー
追加 外部的 実装 最後 実 環
境 実装 性能評価 行 挙
後 展望 ー ー 予測 改善
対応 ー ョン 最適化 挙
本稿 い ElasticStream あ
System S 実装 い 本来 機能
内包 機能 あ 実際 ー
ー 処理系 内部 ElasticStream 機能 適用
利用 能 後 課題 あ 参 考 文 献
[1] Daniel Nurmi, et al., The Eucalyptus Open-source Cloud-computing System, Proceedings of the 2009 9th IEEE/ASCM
[2] Amazon Elastic Compute Cloud (Amazon EC2), http://aws.amazon.com/ec2/
[3] Daniel J. Abadi, et al., The Design of the Borealis Stream Processing Engine, 2nd Biennial Conference on Innovative Data Systems Research (CIDR’05), Asilomar, CA, January 2005
[4] Bugra Gedik, et al., SPADE: The System S Declar ative Stream Processing Engine” SIGMOD 2008
[5] Lisa Amini, et al., SPC: A Distributed, Scalable Platform for Data Mining DM-SSP 2006
[6] J. L. Wolf, N. Bansal, et al, SODA : An Optimizing Scheduler for Large- Scale Stream-Based Distributed Computer Systems, Middleware 2008. [7] Bugra Gedik, A Code Generation Approach to Optimizing High-
Performance Distributed Data Stream Processing, ASCM CIKM 2009 [8] Barzan Mozafari, et al., Optimal Load Shedding with Aggregates and
Mining, ICDE 2010
[9] JOSE R. CORREA, et al., LP-Based Online Scheduling: From Single To Parallel Machines, Mathematical Programming: Series A and B Volume 119 Issue 1, February 2009
[10] Sivadon Chaisiri, et al., Optimal Virtual Machine Placement across Multiple Cloud Providers, Services Computing Conference, 2009. APSCC 2009. IEEE Asia-Pacific
[11] Ruben Van den Bossche, et al., Cost-Optimal Scheduling in Hybrid IaaS Clouds for Deadline Constrained Workloads, 2010 IEEE 3rd International Conference on Cloud Computing
[12] Gaurav Dhiman, et al., vGreen: A System for Energy Efficient Computing in Virtualized Environments, ISLPED '09
[13] Lp_solve, http://sourceforge.net/projects/lpsolve/
[14] Vincenzo Gulisano, et al., StreamCloud: A Large Scale Data Streaming System, In Proceedings of ICDCS'2010. pp.126~137
[15] Scott Schneider, et al., Elastic Scaling of Data Parallel Operators in Stream Processing, IPDPS 2009.
[16] 松浦紘也, et al., ー ー 処理系System S Hadoop 統合
実行環境, Comsys 2010
) 2 ...( ) (
) (
, ,
0 :
) 1 ...( )
( :
loca l next VMtype
type
type type
type type
VMtype
type
type type Nin type
D D x D
N x x
Wher e
x D P P Cost Min
図 最適化問題の定式化 図 ElasticStream アーキテクチャ 図 クラウド環境での並列化
