DB分野におけるデータ処理の『今』と『これから』

Transcription

1 DB 分野におけるデータ処理の 今 と これから 早稲田大学 IT 研究機構上田高徳 2012/12/19 グリッド協議会第 37 回ワークショップ

2 はじめに 上田高徳 ( うえだたかのり ) 所属 早稲田大学 IT 研究機構研究助手 早稲田大学大学院基幹理工学研究科山名研究室 研究分野 データストリームの並列分散処理, Web データ解析, 関係データベース 三大国際会議 SIGMOD, VLDB, ICDE 本日の内容 1. 関係データベースと DB 分野のデータストリーム処理 2. 早大山名研でのストリーム的 Web 解析の取り組み 3. DB 分野の今後の研究課題 2

3 関係データベースについて 関係データベース (RDBMS) 関係モデルに基づいたデータ処理 トランザクションのサポート SQL による宣言的な処理 SQL 実行最適化の基本的な目標 限られたメモリ資源の中でのディスク I/O コストの最小化 RDBMS 利用方法の大分類 Relation SQL Result User uid 氏名性別 1 Yamana M 2 Alice F 3 Ueda M 30 Bob M SELECT * FROM User WHERE 性別 = F 2 Alice F OLTP (OnLine Transaction Processing) データを検索 更新して要求に応える 例 )A 社のレーザポインタを1つ買う. OLAP (OnLine Analytical Processing) データを解析して知識を抽出する 例 ) レーザーポインタの売上を製造会社ごとに合算し, 売上高が多い順に社名と売上高を表示 Read/Write Mix Read が支配的 3

4 関係代数モデルと演算の基本 データはディスク上にあるのが前提 ( だった ) ある SQL の処理方法は通常複数考えられ最適化の機会がある 伝統的なモデルは, 限られたメモリ資源の中で, ディスク I/O を最小化するよう最適化する SELECT 氏名, 商品名, 価格, 購入数 FROM ユーザ, 売上, 商品 WHERE ユーザ. 性別 = F AND ユーザ.uid = 売上.uid AND 売上.pid = 商品.pid ユーザテーブル uid 氏名 性別 1 上田高徳 M 売上テーブル tid uid pid 購入数 商品テーブル σ 性別 = F ユーザ.uid = 売上.uid pid 商品名価格 1 電子辞書 売上.pid = 商品.pid 実行プラン木の例 氏名, 商品名, 価格, 購入数 メモリの大容量化,CPU コア数の増加リアルタイムデータの増加 インメモリ処理の研究が盛んに 4

5 過去 10 年の DB 分野での重要なアイデア (VLDB 2011) VLDB 2011 のパネル中にグループディスカッションし, 各グループが 1 つずつキーワードを提案した後に投票. 下線付きは票が集まったもの 本日のトピックは Stream Processing の中の Data Stream Management System Semantic Search Event Processing Busting Out of the Relational Model Column Store Stream Processing Architecture Conscious Databases OLAP / warehousing Provenance Data Exchange / Data Integration HLL (High Level Language) on top of MapReduce for analytics Green IT ecommerce with data Integration Eventual Consistency for Large Distributed Systems Self-tuning Cloud Databases (with transactions) Micro-Targeted Advertising Data Fusion Data Cleaning Tools Uncertain Data Management Scientific Databases パネラー Ed Lazowska Jennifer Widom Sam Madden David DeWitt Juliana Freire 5

6 データストリーム処理 (DATA STREAM MANAGEMENT SYSTEM) 6

7 データストリーム処理の背景 朝日新聞 2 月 26 日朝刊 (1, 2 面 ) 著作権保護のため画像は加工済みです TED アルゴリズム取引 Kevin Slavin: How algorithms shape our world vin_how_algorithms_shape_our_world.html いまは 1 千分の 1 秒の情報遅れで, 数百万ドル損することもある. If you re a Wall Street algorithm and you re five microseconds behind, you re a loser. DSMS: Data Stream Management System 多数のデータストリームを管理し, ストレージへの蓄積なしにリタルタイムに処理するシステム TV 実況解析 TV 情報 Web グラフ処理 Twitter 多メディアデータ解析 Web データ スマートシティー 監視カメラ電力監視交通ヘルスケア 7

8 DBMS と DSMS の違い DBMS (Database Management Systems) 1 データ 2 クエリ アジアで一番売上が高い代理店は? DBMS Storage 結果 DSMS (Data Stream Management Systems) アジアで一番売上が高い代理店は? 1 2 クエリ データ DSMS クエリ 結果 オンメモリ処理 処理レイテンシを短くし, リアルタイム処理を実現 8

9 関係代数モデルでのデータストリーム処理 従来の関係代数モデルにウィンドウを導入 時間ウィンドウ or タプル数ウィンドウ オペレータは異なる入力を待ち合わせしない オンメモリでリアルタイム処理 研究ポイント : 計算負荷は外部からの入力で決まる SELECT S1.A, S2.B, S3.C, S4.D FROM S1, S2, S3, S4 [Range 24 hours] WHERE S1.ID = S2.ID AND S2.ID = S3.ID AND S3.ID = S4.ID AND S1.A > 100 AND S2.B > 200 AND S3.C > 100 AND S4.D > 450 到着 S1 S2 S3 S4 σ S1.A > 100 σ S2.B > 200 σ S3.C > 100 σ S4.D > 450 S1.ID = S2.ID S3.ID = S4.ID S2.ID = S3.ID 処理レイテンシ = オペレータ処理時間 + 通信時間 データの到着時は, 原則的にあるパスのみが実行される S1.A, S2.B, S3.C, S4.D 出力 9

10 研究例のごく一部と情報源 使用メモリ量を最小化するオペレータの実行順序決定 B. Babcock, S. Babu, M. Datar, R. Motwani and D. Thomas, Operator Scheduling in Data Stream Systems, The VLDB Journal, Vol.13, Issue 4, pp , 分散処理時の高可用性の実現 J.-H. Hwang, M. Balazinska, A. Rasin, U. Çetintemel, M. Stonebraker and S. Zdonik, High-Availability Algorithms for Distributed Stream Processing, In Proc. of the 21st Int l Conf. on Data Engineering (ICDE), pp , 分散処理時の整数計画法を用いたクエリ最適化 E. Kalyvianaki, W. Wiesamann, Q. H. Vu, D. Kuhn and P. Pietzuch, SQPR: Stream Query Planning with Reuse, In Proc. of the 27th Int l Conf. on Data Engineering (ICDE), データストリーム処理と CEP に関する参考文献 教科書 :S. Chakravarthy and Q. Jiang. Stream Data Processing: A Quality of Service Perspective, Springer, 報告書 : 経済産業省次世代高信頼 省エネ型 IT 基盤技術開発 実証事業 ( ソーシャルクラウド基盤技術に関する調査研究 ) ( 本文 ) ( 別紙 ) 10

11 リアルタイム処理のオープンソース 製品 大学や研究機関によるもの Aurora (Brown, MIT, Brandeis ) Gigascope (AT&T) STREAM (Stanford) TelegraphCQ (Berkley) NiagaraCQ (Wisconsin) StreamSpinner ( 筑波大学 ) その他のオープンソースや商業製品 IBM InfoSphere Streams Microsoft Dryad Yahoo! S4 (Apache) Twitter Storm 日立 ucsdp Esper Jubatus ( 注 ) 全てが関係代数モデルによるものではなく,CEP をサポートするものも含む. 11

12 早大山名研でのストリーム的 WEB 解析へ向けての取り組み 12

13 早大山名研での Web 解析 Web 解析の研究目標 ソーシャルメディアによってもたらされるリアルタイム情報を活用 Twitter, TV, Web ページなどの多メディアを統合的に解析することで有用情報の抽出を目指す 必要な処理内容 単語フィルタ, カウント, 自然言語処理, 機械学習など Twitter データのリアルタイム処理 並列分散 Web クローラとの同時解析 JSON, HTML, JPEG, PDF など様々なデータ形式の処理 DBMS にデータは格納はできるが,SQL では記述が困難な処理も多い 統合的にリアルタイム Web 解析を行える処理基盤が必要 13

14 Web 解析研究の例 Twitter TV 字幕情報 ハッシュタグが付いていない実況ツイートの検出は難しい TV 字幕情報と組み合わせて解析することで抽出可能に 番組ごとの特徴的単語の抽出 ハッシュタグを含まない TV 実況ツイートの抽出 ( スマートフォン特集の番組時 ) 日本のメーカーはわかってないな. ワンセグや高画質カメラより, いかに使える. 楽しいアプリがあるかだよ. 自由にアプリ使える カスタマイズ性 この他にも様々な研究を実施 検索エンジンのランキング正当性検証 Web 上の画像分類 グラフ圧縮 Web ページ間の最短経路 少なくとも 現時点でスマートフォンでキャッキャ遊んでる世代はそのくらいのリテラシー持ってるんじゃないかなぁ そうでもないか アプリのイントネーションが変 14

15 計算機環境の実際 インターネット SINET 4 NII 内バックボーン Apresia GX-PSR 大学内バックボーン 10Gbps Cisco Nexus Gbps Dell Power Connect Gbps Cisco Catalyst 4900M Web クローラテスト用 :5 台 BSON 100TB Web データストレージ :1 台 30TB Webクローラ : Twitter 収集 : TV 情報収集 : MySQL: 解析 : 16 台 5 台 2 台 8 台 32 台 15

16 リアルタイム並列分散処理フレームワークの開発 QueueLinker: リアルタイム並列分散処理フレームワーク 開発目標 Producer-Consumer プログラミングモデルによる自由な記述 自由なスレッド 計算機割り当て機構 タスクスケジューラ ( レイテンシ重視 スループット重視 ) Apache Zookeeper で管理 高可用性 関係代数モデルのサポート 論理タスクグラフ 計算機にマップ 物理タスクグラフ ( 各計算機内でも並列化 ) 16

17 各モジュールの Producer-Consumer による基本実装方法 データを受け取り処理を適用して返す Producer-Consumer パターン モジュール間のデータ転送は QueueLinker が行うため, データ通信に関するコードの記述不要 public class Module extends PushModule<CrawlingData, CrawlingData> public CrawlingData execute(crawlingdata element, int queueid) { if (queueid == 0) return element.data = Hello"; else if (queueid == 1) return element.data = Cloud"; return null; } } input 0 input 1 Push Module output 17

18 並列分散 Web クローラのモジュール接続図 Producer-Consumer で実装された 13 種類のモジュールで構成 全てのモジュールは任意のスレッド数, 計算機台数で動作可能 毎秒 6,000 ページ以上の収集能力 ( 早大 NII 間でのテスト性能 ) (i) Host Data Cache (0) robotsflag = 1 3 (2) IP 不明 IP 検索 robots.txtの有無確認 (i) Host Data Cache robots.txt 有無の記録 (1) IP 解決済み robotsflag = 0, 2 (j) Domain Name Resolver (0) robotsflag = 0 (k) robots.txt Processor (i) Host Data Cache IP 記録 2 (1) robotsflag = 1 (k) robots.txt Processor (c) robots.txt Downloader robots.txt 情報の記録 (m) Seeder (a) Scheduler DL 終了通知 (1) robotsflag = 1,2 (2) robotsflag = 2 DL 終了通知 (1) robotsflag = 1 DL 不可 (b) Scheduler Timer 2 (0) robotsflag = 0 (i) Host Data Cache (0) robotsflag = 0 3 (k) robots.txt Processor 2 DL 可能 (d) Downloader (l) Data Store (h) Duplicated URL Checker (g) Explicit URL Filter (f) URL Format Filter (e) HTML Parser 18

19 ハッシュ分割による並列分散実行 (1) 1 スレッド実行 HTML 解析 重複除去 (2) 並列実行 HTML 解析 h 0 mod 2 重複除去 h 1 mod 2 重複除去 (3) 並列分散実行 HTML 解析 計算機 1 台 h 0 mod 4 h 1 mod 4 h 2 mod 4 h 3 mod 4 重複除去重複除去重複除去重複除去 図中の矩形 1 つは 1 スレッド,1 インスタンスに相当 19

20 現在の課題やクラウドへの移行可能性 計算機運用上の実情 計算機管理に興味を持つ学生が少数に 必要最低限の計算機のみ学内に残し, 大部分の計算機はクラウドに任せたい インターネット クラウド Web クローラ Twitter 収集 MySQL 解析 SINET4 大体, こんな感じ? 20

21 DB 分野のデータ処理のこれから 21

22 今後 5 年 ~10 年で DB 分野で重要になると思われるアイデア VLDB 2011 のパネル中にグループディスカッションし, 各グループが 1 つずつキーワードを提案. 投票はなし. Data Spaces Crowd Sourcing Advanced Reasoning in Databases Semantic Search in Specific Domains Social Networks and Collaboration In-memory Databases Cloud Databases Improved user interaction Hardware Appliances for Databases Solve the Semantic Integration Problem Collective Intelligence Scaling Scientific Data Management Synergy Between memory technologies and Databases Domain-specific Language for Eventual Consistency Bread Crumb Data Management Provenance Visual Analytics Mobile Data Elastic Licensing Models Graph Databases 赤線は 個人的に クラウドや HPC とも関係すると思われるもの 22

23 DB 処理の変化 :CPU インテンシブへ 伝統的な RDBMS はディスク I/O の最適化を主眼に構築されてきた メモリ容量増加,CPU のメニーコア化,SSD の登場 ディスク I/O インテンシブから CPU インテンシブへ メモリ大容量メニーコア CPU SSD In-memory DB ロギング方法最適化技法の見直し ccnuma の考慮 CPU Cache 考慮ロックフリー実行時最適化 高速なランダムアクセスインデキシング方法故障率 DB は HPC 分野が培ってきた技術も学ぶ時に来ている 23

24 これからの DB 分野におけるデータ処理の課題例 ストレージシステムの変化への対応 メモリの大容量化 不揮発化によるディスクレス? 耐障害モデルの変化? アーキテクチャを考慮したクエリ実行時最適化 クラウドとの連携 仮想化と RDBMS の耐障害性 超大規模センサデータ処理 計算モデルの検索と再利用 様々なビッグデータを統合的に処理できるデータモデル インタラクティブ解析を実現する User Interface 24

25 おわりに 本日の話題 関係データベースと DB 分野のデータストリーム処理 早大山名研でのストリーム的 Web 解析の取り組み DB 分野の今後の研究課題 私見 今後,DB 界では, アーキテクチャから UI まで, 複合的な層で効率化を図る研究が増えるのでは VLDB 2011 の Best Paper は VM を用いた障害対応 VLDB 2011 には HCI セッションができた 様々なコミュニティと交流することで, 新たな研究分野が生まれる期待が高まっている. しかし一方で, データベースコミュニティの真の価値が問われる時期に来ている. 25

26 DB 分野の日本語の情報源 ACM SIGMOD 日本支部 (ACM SIGMOD-J) の報告会 SIGMOD, VLDB, ICDE の 3 大国際会議について, 内容報告を実施. 私も VLDB 2011 について報告 主にキーノート, ベストペーパーなど目玉講演をカバー データベース勉強会 ( 3 大国際会議がある度に, 全論文紹介を目指して開催 SIGMOD-Jの報告会ではカバーし切れない論文を紹介 不定期でWWWとSIGIRも対象に 26

27 タグクラウド (VLDB 2000) Prof. Samuel Madden (MIT) による 27

28 タグクラウド (VLDB 2005) Prof. Samuel Madden (MIT) による 28

29 タグクラウド (VLDB 2011) Prof. Samuel Madden (MIT) による 29

30 タグクラウド (CIDR 2011) Prof. Samuel Madden (MIT) による 30