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

(1)

DB分野におけるデータ処理の

『今』と『これから』

早稲田大学

IT研究機構上田高徳

2012/12/19

(2)

はじめに

上田高徳（うえだたかのり）

• 所属

–

早稲田大学

IT研究機構研究助手

–

早稲田大学大学院基幹理工学研究科山名研究室

• 研究分野

–

データストリームの並列分散処理，

Webデータ解析，関係データベース

本日の内容

1. 関係データベースと

DB分野

のデータストリーム処理

2. 早大山名研でのストリーム的

Web解析の取り組み

3. DB分野の今後の研究課題

三大国際会議

SIGMOD, VLDB, ICDE

(3)

• OLTP (OnLine Transaction Processing)

–

データを検索・更新して要求に応える

–

例）

A社のレーザポインタを１つ買う．

• OLAP (OnLine Analytical Processing)

–

データを解析して知識を抽出する

–

例）レーザーポインタの売上を製造会社ごとに合算し，

売上高が多い順に社名と売上高を表示

関係データベースについて

• 関係データベース

(RDBMS)

–

関係モデルに基づいたデータ処理

–

トランザクションのサポート

–

SQLによる宣言的な処理

• SQL実行最適化の基本的な目標

–

限られたメモリ資源の中での

ディスク

I/Oコストの最小化

uid 氏名性別 1 Yamana M 2 Alice F 3 Ueda M 30 Bob M Relation

RDBMS 利用方法の大分類

SELECT * FROM User WHERE 性別 = ‘F’ SQL Result Read が支配的 Read/Write Mix 2 Alice F User

(4)

関係代数モデルと演算の基本

• データはディスク上にあるのが前提（だった）

–

ある

SQLの処理方法は通常複数考えられ最適化の機会がある

–

伝統的なモデルは，

限られたメモリ資源の中で

，

ディスク

I/Oを最小化するよう最適化する

SELECT 氏名, 商品名, 価格, 購入数 FROM ユーザ, 売上, 商品

WHERE ユーザ.性別 = ‘F’ AND ユーザ.uid = 売上.uid AND 売上.pid = 商品.pid

σ

氏名，商品名，価格，購入数

⋈

ユーザ.uid = 売上.uid

⋈

売上.pid = 商品.pid 性別 = F

tid uid pid 購入数

1 2 5 3 売上テーブル uid 氏名性別 1 上田高徳 M ユーザテーブル pid 商品名価格 1 電子辞書 39800 商品テーブル実行プラン木の例

メモリの大容量化，

CPUコア数の増加

リアルタイムデータの増加

インメモリ処理の

研究が盛んに

(5)

過去

10年のDB分野での重要なアイデア (VLDB 2011)

• 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

5

VLDB 2011 のパネル中にグループディスカッションし，各グループが

1つずつキーワードを提案した後に投票．下線付きは票が集まったもの

VLDB 2011 のパネル中にグループディスカッションし，各グループが

1つずつキーワードを提案した後に投票．下線付きは票が集まったもの

Ed Lazowska David DeWitt Juliana Freire

パネラー

(6)

データストリーム処理

(DATA STREAM MANAGEMENT SYSTEM)

(7)

データストリーム処理の背景

DSMS: Data Stream Management System

多数のデータストリームを管理し，

ストレージへの蓄積なしにリタルタイムに処理するシステム

7

多メディアデータ解析

スマートシティー

アルゴリズム取引

Webグラフ処理 TV情報朝日新聞 2月26日朝刊 (1, 2面) 著作権保護のため画像は加工済みですいまは1千分の1秒の情報遅れで，数百万ドル損することもある．

TED Kevin Slavin:_{How algorithms shape our world}

If you’re a Wall Street algorithm and you’re

five microseconds behind, you’re a loser.

http://www.ted.com/talks/lang/en/kevin_sla vin_how_algorithms_shape_our_world.html 監視カメラ電力監視交通ヘルスケア Web データ Twitter TV実況解析

(8)

DSMS (Data Stream Management Systems)

DBMS (Database Management Systems)

DBMSとDSMS の違い

Storage DBMS 結果クエリ 2 アジアで一番売上が高い代理店は？ 1 データ結果データ 2 オンメモリ処理 DSMS クエリアジアで一番売上が高い代理店は？クエリ 1

処理レイテンシを短くし，リアルタイム処理を実現

(9)

関係代数モデルでのデータストリーム処理

• 従来の関係代数モデルにウィンドウを導入

–

時間ウィンドウ

or タプル数ウィンドウ

–

オペレータは異なる入力を待ち合わせしない

• オンメモリでリアルタイム処理

• 研究ポイント：計算負荷は外部からの入力で決まる

σ

S1.A, S2.B, S3.C, S4.D

⋈

S1.ID = S2.ID

⋈

S2.ID = S3.ID S1 S1.A > 100 S2.B > 200

σ

⋈

S3.ID = S4.ID S3.C > 100 S4.D > 450

σ

S2 S3 S4 処理レイテンシ = オペレータ処理時間＋通信時間到着出力データの到着時は，原則的にあるパスのみが実行される 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

(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.333-353, 2004.

• 分散処理時の高可用性の実現

– 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.779-790, 2005.

• 分散処理時の整数計画法を用いたクエリ最適化

– 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), 2011.

データストリーム処理と

CEPに関する参考文献

– 教科書：S. Chakravarthy and Q. Jiang.

“Stream Data Processing: A Quality of Service Perspective,” Springer, 2009.

– 報告書：経済産業省次世代高信頼・省エネ型ＩＴ基盤技術開発・実証事業（ソーシャルクラウド基盤技術に関する調査研究）

• http://www.meti.go.jp/policy/mono_info_service/joho/cloud/2011/index.html

• （本文）http://www.meti.go.jp/policy/mono_info_service/joho/cloud/2011/10_01.pdf • （別紙）http://www.meti.go.jp/policy/mono_info_service/joho/cloud/2011/10_03.pdf

(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をサポートするも

のも含む．

(12)

早大山名研でのストリーム的

WEB解析へ向けての取り組み

(13)

早大山名研での

Web解析

• Web解析の研究目標

–

ソーシャルメディアによってもたらされる

リアルタイム情報を活用

–

Twitter, TV, Webページなどの多メディアを

統合的に解析することで有用情報の抽出を目指す

• 必要な処理内容

–

単語フィルタ，カウント，自然言語処理，機械学習など

–

Twitterデータのリアルタイム処理

–

並列分散

Webクローラとの同時解析

–

JSON, HTML, JPEG, PDF など様々なデータ形式の処理

統合的にリアルタイム

Web解析を

行える処理基盤が必要

DBMSにデータは格納はできるが，SQLでは記述が困難な処理も多い

(14)

Web解析研究の例

日本のメーカーはわかってないな．ワンセグや高画質カメラより，いかに使える．楽しいアプリがあるかだよ．自由にアプリ使える、カスタマイズ性少なくとも、現時点でスマートフォンでキャッキャ遊んでる世代はそのくらいのリテラシー持ってるんじゃないかなぁ……そうでもないか…… アプリのイントネーションが変

• ハッシュタグが付いていない

実況ツイートの検出は難しい

• TV字幕情報と組み合わせて

解析することで抽出可能に

14 番組ごとの特徴的単語の抽出 (@jikkyo_analyzer) ハッシュタグを含まないTV実況ツイートの抽出（スマートフォン特集の番組時） TV字幕情報 Twitter この他にも様々な研究を実施 • 検索エンジンのランキング正当性検証 • Web上の画像分類 • グラフ圧縮 • Web ページ間の最短経路

(15)

計算機環境の実際

インターネット

SINET 4

Apresia13000-24GX-PSR

Dell Power Connect

6248 Cisco Catalyst 4900M

100TB

BSON

30TB

Webクローラ： 16台 Twitter 収集： 5台 TV情報収集： 2台 MySQL： 8台解析： 32台 Webデータストレージ：1台 Webクローラテスト用：5台 Cisco Nexus 5548 10Gbps 10Gbps 大学内バックボーン NII内バックボーン 10Gbps

(16)

リアルタイム並列分散処理フレームワークの開発

QueueLinker: リアルタイム並列分散処理フレームワーク

• 開発目標

–

Producer-Consumer プログラミングモデルによる自由な記述

–

自由なスレッド・計算機割り当て機構

–

タスクスケジューラ（レイテンシ重視・スループット重視）

–

Apache Zookeeper で管理

–

高可用性

–

関係代数モデルのサポート

論理タスクグラフ

物理タスクグラフ

（各計算機内でも並列化）

計算機にマップ

(17)

各モジュールの

Producer-Consumerによる基本実装方法

• データを受け取り処理を適用して返す

Producer-Consumer パターン

• モジュール間のデータ転送は

QueueLinker が行うため，

データ通信に関するコードの記述不要

Push

Module

input 0

output

input 1

public class Module extends PushModule<CrawlingData, CrawlingData> {

@Override

public CrawlingData execute(CrawlingData element, int queueId) {

if (queueId == 0)

return element.data = “Hello";

else if (queueId == 1)

return element.data = “Cloud";

return null;

} }

(18)

並列分散

Webクローラのモジュール接続図

• Producer-Consumer で実装された13種類のモジュールで構成

• 全てのモジュールは任意のスレッド数，計算機台数で動作可能

• 毎秒

6,000 ページ以上の収集能力（早大 ⇔ NII間でのテスト性能）

(i) Host Data Cache (j) Domain Name Resolver (i) Host Data Cache (a) Scheduler (c) robots.txt Downloader (k) robots.txt Processor IP記録 robots.txt 有無の記録 (i) Host Data Cache (2) IP不明 (1) robotsFlag = 1,2 (i) Host Data Cache (d) Downloader (0) robotsFlag = 0 (1) IP解決済み robotsFlag = 0, 2 (k) robots.txt Processor (e) HTML Parser (k) robots.txt Processor (0) robotsFlag = 1 (f) URL Format Filter (g) Explicit URL Filter (h) Duplicated URL Checker 3 3 2 (b) Scheduler Timer 2 robots.txt 情報の記録 DL終了通知 DL終了通知 IP検索 robots.txtの有無確認 (2) robotsFlag = 2 (1) robotsFlag = 1 (0) robotsFlag = 0 (0) robotsFlag = 0 (1) robotsFlag = 1 2 (l) Data Store (m) Seeder

(19)

図中の矩形1つは 1スレッド，1インスタンスに相当 1スレッド実行 HTML解析重複除去 (1) 並列実行 HTML解析重複除去重複除去 ℎ ≡ 0 mod 2 ℎ ≡ 1 mod 2 (2) 並列分散実行 HTML解析重複除去重複除去重複除去重複除去 ℎ ≡ 0 mod 4 ℎ ≡ 1 mod 4 ℎ ≡ 2 mod 4 ℎ ≡ 3 mod 4 (3) 計算機1台

ハッシュ分割による並列分散実行

(20)

現在の課題やクラウドへの移行可能性

• 計算機運用上の実情

–

計算機管理に興味を持つ学生が少数に

• 必要最低限の計算機のみ学内に残し，

大部分の計算機はクラウドに任せたい

クラウド

SINET4

インターネット

大体，こんな感じ？

Webクローラ Twitter 収集 MySQL 解析

(21)

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

(22)

今後

5年～10年でDB分野で重要になると思われるアイデア

• 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

22

VLDB 2011 のパネル中にグループディスカッションし，

各グループが

1つずつキーワードを提案．投票はなし．

VLDB 2011 のパネル中にグループディスカッションし，

各グループが

1つずつキーワードを提案．投票はなし．

赤線は「個人的に」クラウドや

HPCとも関係すると思われるもの

(23)

DB処理の変化：CPUインテンシブへ

伝統的な

RDBMSは

ディスク

I/Oの最適化を主眼に構築されてきた

DBはHPC分野が培ってきた技術も学ぶ時に来ている

メモリ容量増加，

CPUのメニーコア化，SSDの登場

ディスク

I/OインテンシブからCPUインテンシブへ

メモリ大容量

メニーコア

CPU

SSD

In-memory DB

ロギング方法

最適化技法の見直し

ccNUMA の考慮

CPU Cache 考慮

ロックフリー

実行時最適化

高速なランダムアクセス

インデキシング方法

故障率

(24)

これからの

DB分野におけるデータ処理の課題例

• ストレージシステムの変化への対応

–

メモリの大容量化・不揮発化によるディスクレス？

–

耐障害モデルの変化？

• アーキテクチャを考慮したクエリ実行時最適化

• クラウドとの連携

• 仮想化と

RDBMSの耐障害性

• 超大規模センサデータ処理

• 計算モデルの検索と再利用

• 様々なビッグデータを

統合的に処理できるデータモデル

• インタラクティブ解析を実現する

User Interface

(25)

おわりに

本日の話題

• 関係データベースと

DB分野のデータストリーム処理

• 早大山名研でのストリーム的

Web解析の取り組み

• DB分野の今後の研究課題

私見

• 今後，

DB界では，アーキテクチャからUIまで，

複合的な層で効率化を図る研究が増えるのでは

–

VLDB 2011 の Best Paper は VMを用いた障害対応

–

VLDB 2011 には HCI セッションができた

• 様々なコミュニティと交流することで，

新たな研究分野が生まれる期待が高まっている．

• しかし一方で，データベースコミュニティの

真の価値が問われる時期に来ている．

(26)

DB分野の日本語の情報源

• ACM SIGMOD 日本支部 (ACM SIGMOD-J) の報告会

–

SIGMOD, VLDB, ICDE の3大国際会議について，

内容報告を実施．

• 私も

VLDB 2011について報告

–

主にキーノート，ベストペーパーなど

目玉講演をカバー

• データベース勉強会

(http://qwik.jp/dbreading/FrontPage.html)

–

3大国際会議がある度に，全論文紹介を目指して開催

–

SIGMOD-Jの報告会ではカバーし切れない論文を紹介

–

不定期で

WWWとSIGIRも対象に

(27)

タグクラウド

(VLDB 2000)

http://db.csail.mit.edu/allyears2.pdf Prof. Samuel Madden (MIT) による

(28)

タグクラウド

(VLDB 2005)

(29)

タグクラウド

(VLDB 2011)

(30)

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