情報システム特別講義D #GB37301

GB37301.md

情報システム特別講義D

• 1時限目 イントロ - 川島先生(筑波大学)

• 2時限目 Inside PostgreSQL Kernel - 永安 悟史さん(アップタイム・テクノロジーズ)

• 3時限目 データストレージの諸々 - 星野 喬さん(サイボウズ・ラボ)

• 4時限目 並列データベースシステムの概念と原理 - 油井 誠さん(産総研)

• 5時限目 Googleクラウドが実現する大規模並列クエリサービス - 佐藤 一憲さん(Google)

• 6時限目 分散処理基板Hadoop/MapReduce - 小沢 健史さん(NTT研)

• 7時限目 Treasure Data Technologies - 中川 真宏さん(Treasure Data)

• 8時限目 Retrospection/Prospection / Norikra in Action - 田籠 聡さん(LINE株式会社)

• 9時限目 データベースのはなし - 上西 康太さん(Basho Japan)

• 10時限目 大規模グラフデータ分析に向けた取り組み - 塩川 浩昭さん(NTT研)

GB37301_1.md

1限目 イントロ - 川島先生(筑波大学)

BigDataとか

講師の方の紹介

課題：面白かった講義トップ３の感想・質問

• ただし川島先生の講義は除く。
• 講義ごとに1ページ程度、合計で3ページ程度。

概要

• NoSQLはSQLとは別の使い方をしていた。
• GoogleはOracleDBを使っていたが、データが載りきらなかったのでBigTableを作った。
• Relational DBMS

• Query processing
• Transaction processing

DBMS

• 問い合わせ言語SQLは標準化されているから、どのようなDBMSシステムでも同じようにデータを扱うことができる。

• SELECT * FROM xxxx;
• SELECT COUNT(*) FROM xxxx WHERE yyyy='zzzz';

SQLは機械にどう解釈される？

• 最適化することができる。

• Query Parser
• Query Optimizer
• Query Plan Evaluator

Transaction

• Transactionの性質 ACID

• Atomicity
• Consistency
• Isolation
• Durability

• Transactionが無いと、不具合が出た時に整合性を保てない。

Keeping Isolation

• 2 Phase Lock(成長相と縮退相)

• 2PLよりもStrict 2PLのほうが遅い→なぜ？

• ロックを持っているため、パフォーマンスが若干劣ってしまう。

NoSQL

• Not only SQL
• NoSQLは、SQLほど高機能ではないが、パフォーマンスが良い。
• なぜNoSQL？

• データがでかすぎて、SQLで処理しきれない。

• Riak, DynamoDB, PNUTSなど

New SQL

• VoltDB

• ロックを掛けないとパフォーマンス上がるんじゃね？

• Dremel @Google

• F1 @Google

テーブルの格納情報

• テーブルの情報は2次元→1次元に変換して格納
• 横？縦？

• NSM N-ary Storage Model

• PostgreSQLなど

• DSM Decomposed Storage Model

• 総和などに強い

まとめ

• Transaction
• ACID
• NoSQL

GB37301_2.md

http://www.uptime.jp/test/snaga/Tsukuba_Jan_30_2014/InsidePostgreSQLKernel.pdf

2限目 Inside PostgreSQL Kernel - 永安 悟史さん(アップタイム・テクノロジーズ)

アジェンダ

• RDBMSとはどのようなテクノロジーなのか
• その中で使われている理論について知る
• PostgreSQLの実装
• 今後のPostgreSQL

基本的なアーキテクチャ

• 共有バッファを中心として、複数のプロセス間で連携しながら処理を行うマルチプロセス構造。

SQL文の処理される流れ

• クエリ受信
• 構文解析
• 書き換え
• 実行計画作成・最適化
• 実行
• 結果送信

トランザクションにおけるACID特性

• PostgreSQLのテーブルファイルの中には、複数バージョンのタプルが存在する

• 複数のトランザクションに上手くデータを「見せる」ため

• Atomicity

• 各タプル事の可視性情報
• コミットログによるトランザクションの状態情報

• Consistency

• いずれにせよコミット完了時には制約に整合していることを保証

• Isolation

• 実装はXIDとCommandIDによるトランザクションの世代管理

• スナップショットをトランザクションごとに生成

• なにが見えて、なにが見えないのかという可視性の管理情報

• Durability

• チェックポイントによるデータファイルへの更新

• チェックポイント

• 共有メモリ上のデータをディスクに一括して反映する処理

メタデータ管理

PostgreSQLの内部でメタデータをどのように扱っているのか

• pg_controlファイル

• 起動した時に最初に読み込まれるファイル

• 前回の状態のIDなどが保存されていて、クラッシュなどを検知

• OID オブジェクトID

• XID トランザクションID

• TID タプルID

• システムカタログ

• pg_catalogスキーマに保存される

MVCCとストレージ構造

• テーブルファイル

• 8kB単位のブロック単位で構成される

• 書くブロックの中に実データのレコード(タプル)を配置

• 基本的に追記のみ

• 削除したら削除マークを付加する(VACUUMで回収)

• レコード更新時は「削除＋追記」を行う

• インデックス(B-tree)ファイル

• 8kB単位のブロック単位で構成される

• VACUUM処理

• 削除マークが付いているレコードを空き領域にする

• インデックスとタプルの可視性

• PostgreSQLでは、可視性情報をレコードタプルにもつ

• インデックスエントリは、可視性情報を持たない

• インデックスとタプルの可視性

• PostgreSQLでは、可視可視性情報をレコードタレコードタプルにもつ

• インデックスエントリは、可視性情報を持可視性情報を持たない

• TOASTテーブル

• The Oversized_Attribute Storage Technique

• 長い値(2kB以上)を、通常のテーブルのブロックではなく、専用の外部テーブルに持たせる機能

• Freespace Map

• 各ページの空き領域情報を管理するためのファイル

• タプルを格納する空き領域のあるページを見つける

• 各テーブル・インデックスファイルごとに存在

• 各ページの空き領空き領域情報を管理するためのファイル

• タプルを格納する空き領域のあるペあるページを見つける

• 各テーブル・インデックスファイルごとに存在

• Visibility Map

• 各ブロックのレコードの可視状態を保持するファイル

• 削除された行があるかどうか、をビットマップで保持

• そのブロックをVACUUMする必要があるかどうかの判断

• ビットが立っていると、ブロック内の全タプルが全トランザクションに可視

メモリ管理

• 共有メモリ

• 複数のバックエンドで共有されるデータを保持する

*セッションをまたいで共有すべきデータ

• ローカルヒープ

• 個別のセッションで使用するメモリ

• ソート、演算処理などを実行するときに使用するメモリスペース

• Memory Context

• フラットなメモリ空間に構造を導入する

• メモリコンテキスト単位で確保。破棄する => メモリリーク防止

• メモリのセグメンテーションを防止する

• 共有バッファと管理アルゴリズム

• 共有バッファは、ディスク上のブロックをキャッシュする共有メモリ領域

• ディスク上のブロックの内、アクセスするものだけを読み込む

• ディスクIOを抑えて、読み書きを高速化

• 全てのブロックはバッファに載り切らないので、入れ替わりが発生する

• 「どのバッファを捨てるか、どのバッファをキープするか」が性能に影響

ロック制御

• ロック

• 並行して処理を行っているRDBMSでは、データの整合性のためにリソースに対する排他制御が必須

• ロックには、ロックレベルと粒度の概念がある

• 2-Phase Locking (2PL)

• ロックの獲得期、解放期の2フェーズに分類して管理

• ロックの獲得、解放を繰り返すとデッドロックを起こしやすくなるため

• デッドロックの検出と解消

• デッドロック

• 複数のリソースのロックを獲得しようとする複数のセッション

• Heavyweight Lock

• Lightweight Lock

• Spinlock

パース、リライト、オプティマイズ

• オプティマイザ統計情報

• 非Nullの値の最頻値とその割合

• カラムの値のヒストグラム

• 物理的な並びと論理的な並びの相関関数

• 実行コストの計算

• 実行コストは、ディスクIOコストとCPUコストで構成される

• GEQO(遺伝的問い合わせ最適化)

• 結合するテーブルが増えると、組み合わせのパt−庵が増加する

• 結合処理を行うテーブルが多くなった場合、PostgreSQLではGEQOというオプティマイザが実行

• 遺伝的アルゴリズムを用いた最適化処理

エグゼキュータ

• 結合処理

• Nested Loop Join

• Merge Join

• Hash Join

• インデックスの種類

• B-Treeインデックス

• Hashインデックス

• GiSTインデックス

• GINインデックス

• インデックスのアクセスメソッド

PostgreSQLの拡張

• 拡張する方法

• UDF(ユーザ定義関数)

• インデックス拡張

• Hook

• カスタムバックグラウンドライタ

• EXTENSION

• Hookによる拡張

• PostgreSQLは動的にモジュールをロード可能

• 内部には、関数ポインタを用いたHookが多数存在する

• GiSTによるインデックスの拡張

• 汎用検索ツリー(GiST: Generalized Search Tree)

• 7つのメソッドを実装することによって新しいインデックスを実装できる

• same, consistent, union, penalty, picksplit, compress, decompress

GB37301_3.md

http://www.slideshare.net/starpos

3限目 データストレージの諸々 - 星野 喬さん(サイボウズ・ラボ)

自己紹介

サイボウズの紹介

10分で分かるデータストレージ

http://www.slideshare.net/starpos/10-30605758

• データストレージの概要

• データを記録、参照できる装置

• 電源を切ってもデータが消えない

• 基本的なストレージデバイス

• HDD

• Flash memory

• ストレージの大事なこと

0. データを失わない
1. 可用性の確保
2. 性能
3. コスト
4. その他

• ブロックデバイス：ストレージの抽象化

• ブロック単位のIO

• メインメモリに比べて低速だから (歴史的経緯)

• アドレスとサイズを指定してIOする

• ストレージ階層：性能視点

0. SRAM as cache
1. DRAM as cache
2. Cache (flash mem, DRAM)
3. SSD/Flash dirve
4. HDD
5. TAPE ...

• ストレージベンチマークの基本

• 重要なパラメータ

• シーケンシャル or ランダム

• Read or Write or Mix

• IOサイズ

• 並列度/キューサイズ

• ストレージ階層：機能視点

• アプリケーション APP

• データベースシステム DBMS

• ファイルシステム

• バッファキャッシュ層

• ブロックデバイス層

• デバイス

• ストレージ関連技術

• 目的

• データロスト回避
• 可用性向上

• 手段

• RAID
• etc..

• ストレージ進化の流れ

• 容量・スループットは徐々に向上するが、レイテンシ改善はブレイクスルーが必要

• HDD => Flash memoryなど

• ソフトウェアで様甘な機能や性能向上を実現

• エンタープライズ向け => コモディティ化 (OSS)

• その他

10分で分るブロックレイヤ

http://www.slideshare.net/starpos/10linux

• Linuxブロックレイヤ俯瞰

• IOスケジューラ

• IOリクエストを並べ替える

• 種類

• noop

• cfq

• deadline

• 生HDDに対しては効果が高い

• ブロックデバイスドライバのインターフェース

• bio interface

• 全て自分で面倒を見なければならない

• rquest-queue interface

• IOスケジューラの恩恵を受けられる

• Single-queue vs Multi-queue

• IOインタフェース(投げる側)

void generic_make_request(struct bio *bio);

• bioの中身

• データバッファ

• read or write フラグ

• その他フラグ

void make_request(struct request_queue *q, struct bio *bio);

• bio interfaceの使用時のコールバック

10分で分かるバックアップとレプリケーション

http://www.slideshare.net/starpos/10-30605788

• バックアップ

• 近過去のデータ複製を保持

• 目的：データロストの回避

• バックアップの分類

• フルバックアップ

• 差分バックアップ

• 増分バックアップ

• レプリケーション

• データを他ノードにオンライン複製

• 目的：可用性向上

• レプリケーションの種類

• Master-slave型

• 平等型

• レプリケーションの分類

• 同期

• Slaveストレージにも書いてからwriteIO完了

• 非同期

• Masterストレージに書いたらwriteIO完了

• 準動機

• いろいろな意味で使われている

|バックアップ|レプリケーション --------|--------|---------- 目的|データロストの回避|可用性の向上 復旧可能な障害の種類|オペレーションミス|機材故障 最新データを復旧可能か|No|Yes(同期)

• 指標

• ソフトウエア階層による分類

• 要素技術：増分データの作り方

• COW (Copy on write)
• ThinP (Thin Provisioning)
• WAL (Write ahead logging)

WalBの紹介

http://www.slideshare.net/starpos/walb

GB37301_4.md

http://www.slideshare.net/myui/ss-30700635

4限目 並列データベースシステムの概念と原理 - 油井 誠さん(産総研)

趣旨

• 教科書レベルより一歩進んだ話題
• 並列処理の基礎
• データベース処理の並列化
• Map Reduce

データベース

• 並列データベース

• データベースの関係処理を高速に

• 分散データベース

• 各所にデータベースを分散させる

• 並行・並列・分散

並列

• なぜデータ並列が重要か

計算環境の高性能化のアプローチ

• スケールアップ
• スケールアウト

並列計算機のアーキテクチャ

• Shared-nothing (無共有型)

• Scale-out構成が取れる

• Shared-memory (共有メモリ)

• Scale-up構成ができるが、スケーラビリティに制限がある

• Shared-disk (共有ディスク)

• ネットワーク帯域とストレージの性能依存

データベース処理の並列化

• Intra-query並列化
• Inter-query並列化

JOIN

• Nested Loop Join
• Hash Join
• Grace Hash Join
• Hybrid Hash Join
• Parallel Grace Hash Join

MapReduce

• 複雑な分散処理を単純なプログラミングモデルに包んで抽象化

• 並列ハッシュ結合のSplitと同じことをShuffleでやっている
• ユーザはMap/Reduce関数を書くだけ

まとめ

• BigDataに対処するための並列データ処理技術の紹介

• 並列データベースの構成法

• Shared-{Nothing|Disk|Memory}などのアーキテクチャ
• 並列ハッシュ結合
• データ分割

• 多重結合などの並列処理で発生する問題

• MapReduceを利用した関係演算の処理手法

GB37301_5.md

5限目 Googleクラウドが実現する大規模並列クエリサービス - 佐藤 一憲さん(Google)

Google

• Googleの中のビッグデータ

• 72時間 => Youtubeに1分間にアップロードされる動画の長さ
• ...

• DWHやMapReduceだけでは足りない

• Data Warehousソリューション

• コストが高い
• アドホックなデータ分析に対応しにくい

• 虎の子、Dremel

• 大規模並列クエリインフラ

• 検索がありえない速さ

• インデックス不要

• BigQueryはなぜ速い？

• 世界最大規模の超並列クエリインフラ

• カラム志向ストレージを採用

• 数万台で並列処理

• ディスクIOを極限まで並列化

• 階層構造による高速な集計

• MapReduceとBigQueryの得手不得手

• BigQuery

• アドホッククエリ
• QLAP/BI
• レスポンスの速さ
• 非技術者

• MapReduce

• データマイニング
• 複雑なロジック
• 非構造データ
• 大規模なデータ生成
• データの更新

ビジュアライゼーション

Spanner

• Googleの地球上で分散しているデータベース

• かつ、SQLである
• F1データベース

• 機能

• リレーショナルモデルとSQLをサポート(No NoSQL)
• Bigtableみたいにスケーラブル

LSM-Tree

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782&rep=rep1&type=pdf

• Data Organization

• TrueTime

• Multi-versioned Database

• Supports Snapshot Read

• All row has global timestamp by TrueTime

• Megastore

GB37301_6.md

6時限目 分散処理基板Hadoop/MapReduce - 小沢 健史さん(NTT研)

講義の狙い

• なぜ分散処理を選択するのか、しないのか
• いつMapReduce(Hadoop)を使うべきか

処理基盤の目的

• よくやる処理を簡単に作りたい
• 要件を満たす性能を出したい

• プログラミング言語

• Ruby, Python, Erlang, Scala, C, etc...

• ライブラリ

• Python + scikit/numpy

• フレームワーク

• MapReduce(Hadoop), MPI(OpenMPI), etc...

• RDBMS

• PostgreSQL, MySQL, Vertica, ...

なぜこんなに種類があるのか

• 要件がまちまちだから使い分ける必要がある

• 性能
• 使いやすさ
• スケーラビリティ
• 耐故障性
• etc...

• この中でも、スケーラビリティに重きをおいているのが分散処理基盤

スケーラビリティとは

• 問題の規模の拡大・増大に対して対応できるかどうかという指針
• システムにおけるスケーラビリティの指針例

分散処理基盤の目的

• 故障が起きても動き続ける
• 処理のスループットを上げる
• 分散処理をしても処理が早くなるとは限らない

• 余計な通信遅延が発生しないので、1台で十分な処理は1台でおこおなうべき。

代表的な分散処理基盤

• MPI (MessagePassingInterface)

• 主な用途：科学技術計算など
• CPUインテンシブな処理向け
• 通信の箇所をメッセージパッシングという形で隠蔽

• 並列DB

• 主な用途：クエリを低遅延で実行
• 並列IO
• インデックス、データ配置

• MapReduce

• 主な用途：大量のデータの交換を行うための基盤
• 分散ファイルシステムを前提とした処理機版で、並列IOによりスループットを稼ぐ
• 故障処理、分散処理、IOをAPIの下に隠蔽

• MapReduceのプログラムは、常に起動だけで15秒ほどかかる
• => ながーいバッチ処理のためのシステムだから、起動にそのくらいかかってもいいよね

RDBMS/MapReduceの事例

• 使い分けの例

• MapReduceは、「巨大なデータ」か、「データが増えそうな見込みの処理」に利用
• RDBMSは、低遅延のジョブでも利用されるが巨大すぎるデータでは利用できず
• 並列DBは、巨大なデータに対して高速に処理をかけたい時に利用。

並列DBの特徴

• Schema on Write

• スキーマ情報を意識して書き込んでおくことで、問い合わせを高速に処理する

• 利点

• 問い合わせ時のオーバーヘッドを最小化

• 欠点

• 設計時にスキーマや処理内容を意識する必要がある
• データロードに時間が掛かる

Hadoopの特徴

• Schema on Read

• 書くとき適当、処理時にスキーママッピング

• 利点

• スキーマやワークロードの変化に強い
• ロードを高速に行うことが可能

• 欠点

• クエリ時のオーバーヘッドが高い

実際の適用領域

• Hadoopの計算機の量は、20-1200+ ノード
• データ量は最大で4PB

実情から見るHadoopを選択する状況

• 処理しなければならないデータが巨大である場合

• 例：1日100GBずつデータが増えていく

• データベースに入れる前に、前処理を行いたい場合

• アーキテクチャ上、無茶してでも走り切る

• スキーマが頻繁に変更される場合

• アプリケーションからのログ形式の変更が多いなど

• これ以外の場合は、基本的にはRDBMSを選択するほうが無難

• かえって処理が遅くなる

MapReduce

• MapReduceが作られた経緯

• MapReduceはもともとはGoogleの内部システム

• 今年で10周年

• 検索エンジンを作るときの構成要素

• 転置インデックス
• 問い合わせに対するスコアリング
• いろいろなキーに対するソート
• クロールしてきたHTMLからデータを抽出
• 集計

• 基本、メモリからはあふれる
• 故障が起きうる

• これらの処理を簡単に作るにはどうすればよいか？

• MapReduceの考え方

• 前提

• Rawデータが相手なので事前計算はできない
• 計算機故障が頻発しうる

• 目的

• 計算機を足せば、データが増えても一定時間で処理できる
• 計算途中で計算機が故障してもジョブが動き続ける
• ソート、集計などがやりやすい

• 手段

• なるべくデータをローカルから読めるように、分散ファイルシステム上に処理系を構築
• 上記の処理を、全て簡易なAPIでラップ

• MapReduceのアーキテクチャ

• Master-Slave型のアーキテクチャ

• Masterは、ジョブの状態、FSの状態を管理して指示を出す
• Slaveは、Masterの指示に従って処理を実行

• MapReduceの動作フロー

• ユーザはMap関数とReduce関数をかく
• Map関数とReduce関数間は、KeyとValueのペアの受け渡し

Apache Hadoop

• 実装

• MapReduceのオープンソース実装
• Hadoop MapReduce、HDFS

• Hadoopのアーキテクチャ

• Master: JobTracker

• どのWorkerにどんな仕事をさせるのかの判断
• どのマシンが壊れたかを判断

• Slave: TaskTracker

• リソースをmap slot/reduce slotという形で管理
• Masterから命じられた仕事を実行
• 定期的にMasterにハートビートを送信

• HDFSのアーキテクチャ

• Master: NameNode

• データの保存要求が来た時に、どのスレーブにどのデータを配置するのかを管理
• ディレクトリ構造を管理

• Slave: DataNode

• 実際にデータが保存される
• ハートビートをMasterに送信

MapReduceの課題

• MapReduceプログラムに落とすには、分割統治できるプログラムに設計し直さないといけない
• Masterが死ぬととまっちゃう

簡単にMapReduceにするための仕組み

• Apache Pig

• Apache Hive

• MapReduceは処理遅延が大きい

• 原因

• スケーラビリティを確保するため、ハートビートベースでスケジューリング・リソース割り当てをする

• 関連技術

• スケジューリングをイベント駆動で行うようにすると高速化できる(Shark)
• Impala/Prestoのような、Dremel実行エンジンのオープンソース実装

• Masterが落ちたらどうするか

• 諦める

• 解決策
• NameNodeを冗長化する仕組みが実装された

次世代Hadoopについて

• MapReduce

• Shuffle Plugin
• JobTracker HA
• MapReduce itself is at stable phase

• HDFS

• Cache Management
• Snapshot
• Symbolic links

• HARN

• A new component for Hadoop 2.x

• What is YARN ?

• Yet Another Resource Negotiator
• JobTrackerの役割を分割し、ジェネリックに使えるように

• リソース管理をYARNに押し付けて、SparkやImpalaをYARN上で動かす

• Why YARN?

• ロングバッチはMapReduceで動かし、インタラクティブクエリはImpala、インタラクティブな機械学習はSparkがいい

• 使い分けがでてきた

• リソースの見積が難しくなってしまった、、、
• YARNにまかせちゃえ

• YARNのバックエンドはLXC

GB37301_7.md

https://dl.dropboxusercontent.com/u/374829/tkb_treasure_data_technologies.pdf

7時限目 Treasure Data Technologies - 中川 真宏さん(Treasure Data)

Treasure Data

Plazma

• Hadoopをバックエンドにしたシステム

Fluentd

• ログデータの収集

• 収集
• 保存
• 処理
• 可視化

• なるべく使いやすい

Fluentd以前は

• バッチ処理的にログを送っていた

• 1日毎などだったから、遅延がかなり大きい
• フォーマットがバラけていて大変

Lambda Architecture

http://www.drdobbs.com/database/applying-the-big-data-lambda-architectur/240162604

Fluentd

• syslogdみたいだけど、内部データ形式はJSONぽいかんじ

• Core

• Divide & Conquer
• Buffering & Retrying
• Error handling
• Message routing
• Parallelize

• Plugins

• read/receive data
• write/send data

• リトライとか再送が難しい

• Apache to Mongo

• Pluggable Architecture

• Input
• Engine
• (Buffer)
• Output

• Plugin

• in_tail
• out_webhdf
• out_copy
• out_forward

Plazma

• システムは疎結合にするべき

• Backend overview

• Used AWS products

• RDS
• S3
• EC2

• PerfectQueue/Sched

• Two storage layer

• Realtime Storage
• Archive Storage

• Query Processing flow

• Compile HiveQL

• SQL Statement

• Multi-tenancy

• FIFO
• Fair Scheduler
• Capacity Scheduler

MPP Query Engine

• Problem of MapReduce

• Low Lateny, High Throughput
• Solutions

• Direct access MPP : Presto, Impala, etc...
• Other Project: Tez, Spark, etc...
• With DWH: Netezza, Redshift, etc...

• Why Presto

• Hard to move the large to DWH

• Presto

• Open sourced Query Engine by Facebook

クラウド

• 利点

• 開発が容易
• ハードウェアの交換が簡単
• ミドルウエアも同様

• 欠点

• 既存のシステムも、分散で動くように設計し直さないといけない
• システムへガリガリとチューニングすることがむずい

まずAWSで試してから、自分のサービスの特性をわかった上でVPSのようなサーバをまるまる借りる場所に移動する人も

GB37301_8.md

http://www.slideshare.net/tagomoris/

8時限目 Norikra in Action/Retrospection - 田籠 聡さん(LINE株式会社)

Retrospection / prospection and schema

http://www.slideshare.net/tagomoris/retrospection-prospection-and-schema

• Software for Logging

• Collection
• Storage
• Processing
• Stream-Processing
• Visualization
• Appliance
• Services

• How inspect logs

• Retrospection: 一度格納された過去のデータを見る
• Prospection: まず、どのデータを見るかを決める

• Retrospection的なアプローチだと、事前の売上の予測などができない

• What logs inspected

• Schema-full data

• strict schema
• schema on read

• Schema-less data

• any fields, any types

• How/What

how/what	Schema-full	Schema-less
Retrospect	RDBMS,Hive,BigQuery	MongoDB,TD
Prospect	Esper,CEPs	Norikra,...

• Data size

• Logs (xxTB - xxPB)
• Schema

• size optimization
• access optimization on memory/disk

• Index

• access optimization on memory/disk
• hard to distribute

• Stream processing engines

• No disks => ディスクは壊れやすいお。。。

• Less memory

• Stream processing and schema

• queryを見て、やってくるデータのスキーマを決定できるのではないか？
• 自分のフィールド名と、タイプを知っているケースが多い

• 文字列関数が適用されている
• => このフィールドは文字列なんじゃない？

• GOAL

• Schema-less data stream + schema-full queries

使うか使わないかはわからないけど、とりあえず機能を入れておけ！

Norikra in Action

http://www.slideshare.net/tagomoris/norikra-in-action-ver-2014-spring

Norikra internal:
  Jump
    from schema-full world
    to schema-less world.

GB37301_9.md

https://speakerdeck.com/kuenishi/talk-on-database-ja

9時限目 データベースのはなし - 上西 康太さん(Basho Japan)

今日覚えてもらうこと

• NoSQLはバズワードであり、定義はない
• いろいろなデータストアとその分類、使い分けのコツ
• 分散システムやデータベース周辺の問題、俯瞰図
• Riakは素晴らしいデータベースである

データベースに保存するときの要求

• データを正しく書き込むこと、データの更新が中途半端な状態で失敗しないこと
• 書き込んだデータを正しく読みだすこと
• 書き込んだデータを別形式に変換して読みだすこと
• ハードウェア性能の限界まで高速に保存・読み出すこと
• データが消える条件が正確に判明していること

データベースの歴史

• 1977年 System R (IBM)

• 関係代数の理論に基づいたデータ操作言語
• データを永続化するトランザクション処理を実装した世界初のデータベース

• RDBMSの時代

• ACID特性に基づいたトランザクション管理
• SQLという統一されたインタフェース
• スケールアップの時代

• 1995年のHDD、7.5万円/GB

• 2003年〜 Webの時代

• ITバブル崩壊後

• Web scale

• 求められることが変化：構造は簡単でも、量やトラフィック、レスポンス、可用性の要求が多様化
• データの単価が安い

• データに対するコスト

• 預金情報は大切だからコストが高い
• サイトにアクセスしたログのようなコストは低い

• 後者のような情報は安いし捨ててもおｋ
• ...だったけど、HDDが安くなってきて保存できるようになった

• Web Scale へのアプローチ

• 家庭用コンピュータと同じHW
• LAMP + Memcached
• Google GFS, BigTable
• Amazon Dynamo

スケーリング

• スケーリングの方法

• 複数台のノードにデータを分散保持して量を稼ぐ
• 「どのデータがどのサーバにはいってるの？」

• 階層型ルーティング (HBase, DNS, ...)
• ハッシュ的ルーティング (Riak, Cassie, Dynamo, ...)

• ハッシュ的

• キーとノードIDをハッシュ化して、同じ名前空間に置く

• Locality vs Load Balancing

• 先読みを効かせてバルクでシーケンシャルアクセス

• HBase, BigTable, etc...

• ハッシュで分散させて負荷分散してランダムアクセス

• Riak, Cassie, etc...

整合性の問題

• 整合性ってなに？

• 共通するのは、「誰が見ても同じようにみえること」

• 複数種類のデータ間のInvariantが守られていること

• 複数のデータのコピーが同じであること

• ReplicationのConsistencyと、ACIDのConsistencyは違うお

• Consistent Replication is Difficult

• レプリケーションは順番が入れ替わる
• CPUのアウトオブオーダー実行と同じ

• 分散合意問題

• 「複製が全て同じである」 => 全員がひとつの値に合意できている状態

• 怪しい動作をする可能性があるもの：

• ネットワーク

• 遅延

• 合意する相手

• 相手が死んでるかも

• 制限時間：無限

• 返事が遅いだけ？相手が死んでる？

• なぜ難しいのか

• 死活監視が難しい

• お互いが目隠しして糸電話使ってる状態みたいな

• 故障的困ることの分類

• 黙って死ぬ
• 故障したら死ぬ
• 故障したフリして知らんぷりする
• メッセージ欠落
• etc...

• 分散合意の種類

• アトミックブロードキャストプロトコル

• おおまかに言って分散合意するためのプロトコルを総称

• Consensus Based Replication

• レプリケーションのリーダーを多数決で選出
• or レプリケーションごとに多数決

可用性の問題

• CAP定理

• P: どんな故障に対しても
• C: データは常に整合しており
• A: システムがとまることはない

• この3つを同時に満たすシステムは存在しない

• C重視のCAP定理

• n1とn2のレプリカを常に整合しておく
• ネットワークが切れたり故障したら止める => 可用性が下がる

• A重視のCAP定理

• n1とn2のレプリカを常に使えるようにする
• ネットワーウが切れたり故障しても書ける => 整合性が下がる

• P重視のCAP定理

• n1とn2のレプリカをエスパーにする
• ネットワークが切れたら正しいほうが分かる => 可用性がちょっと下がる

• 「とりあえず書く」という考え

• ACID vs BASE

xxx	ACID	BASE	xxx
xxx	xxx	整合していなくても常にデータにアクセスできる	Basically Avaiable
Atomicity	複数の操作の成功・失敗をまとめる	xxx	xxx
Consistency	冗長化されたデータや複数のリレーションが常に整合している	最終的に整合した状態になることが保証されていれば良い	Eventually Consistent
Isolation	並行管理して更新途中の状態を見せない	xxx	xxx
Durability	データを永続化して失わない	xxx	xxx
xxx	xxx	レプリカは決定論的ではなく、確率論的であったり、グローバルに一貫していなくても良い	Soft-state

• CAP定理からみた製品の分類

• CA重視

• RDBMS, MongoDB, HBase, etc..
• 整合性維持のための分散合意の仕組みが必要

• AP重視

• Cassandra, Riak, CouchDB, etc...
• 分散合意の仕組みが不要 => 実装も運用も簡単

• 新しいデータモデル

• カラム指向

• カラムをいくらでも増やすことができる
• Query Languageを作る
• HBase, Cassandra, etc...

• ドキュメント指向

• 個々のレコードが自由な形式を持つ
• MapReduceでクエリ
• XML, JSON, etc..

xxx	CA重視	AP重視
SQL	RDBMS	xxx
カラム指向	HBase	Cassandra
ドキュメント指向	MongoDB	CouchDB
(blob)	xxx	Riak

GB37301_a.md

10時限目 大規模グラフデータ分析に向けた取り組み - 塩川 浩昭さん(NTT研)

目標

• アルゴリズムの観点からのビッグデータへの取り組みを知ってもらう

グラフデータ

• グラフデータとは

• ノードとエッジからなるデータ構造

• 大規模グラフ処理

界隈	種類	頂点数
ORなど	交通ネットワーク	全米 :> 2x10^7
Webなど	ソーシャルネットワーク	Twitter :> 2x10^8
生物情報	タンパク質間相互作用など	>10^9
国防	謎	アメリカ国土安全保障省 :> 10^15

クラスタリングについて紹介

クラスタリング

• 互いに密に接続したノードの部分集合

• グラフクラスタ

• 互いに密に接続したノードの部分集合 => ソーシャルグラフのコミュニティ抽出や、交通シミュレーションなどで利用

• Normalized Cut法(2001)

• クラスタ間のエッジが最小、クラスタ内のエッジが最大になるようにグラフを2分割にする手法

• 計算量がO(N^3)でめちゃ大きい
• クラスタの精度がいまいち

• Modularity

• ランダムグラフモデルからの乖離具合をクラスタの質として定義

• ランダムグラフと、クラスタの差を見て比較

• Modularityによるグラフクラスタリング

• 既存技術では対象とする規模のグラフを処理できない

• Girvan-Newman法(2004) => グラフから適当にエッジを削除して、その時のModularityを評価 => Modularityが最も大きくなったものを結果として出力

• Newman法(2004) => 貪欲法によりボトムアップからModularityを向上させる手法

• CNM法(2004) => ヒープの導入やヒューリスティクスによるNewman法の高速化

Newman法/CNM法はO(N^2)-O(MlogN)

• Louvain法(2008) => 以下のパスをModularityが向上するまで繰り返す

0. ノードのローカルクラスタリング
1. クラスタに含まれるノードの一括集約

• 本研究の目標

• 既存技術と同程度の精度を保ち、もっと大きなデータを処理したい

クラスタリング高速化

• Louvain法のボトルネック分析

• 第一パスにおける処理時間の増加 => 第一パスが、処理時間の99%以上を占めていた

• 要因1: データアクセスコストの肥大化

• 全てのエッジをランダムに参照 => 隣接リスト表現なのでCPUのキャッシュヒット率が著しく低下

隣接リスト表現をメモリ上において連続した領域に配置する

• グラフのクラスター性

• グラフのクラスター性に着目

• 「友達の友達は友達」みたいなケースが多いので計算はしょれる

• Power-Law特性

• グラフ中のエッジには大きな偏りが存在する

• みんながみんな、アルファツイッタラーみたいに大多数とつながっているわけでは無い

• ノードの逐次集約による参照効率化

• グラフのクラスター性を利用
• 同一クラスタを逐次的に等価な重み付きグラフに変換

• クラスタが自明なノードの枝刈り

• グラフのPower-Law特性に着目
• クラスタが自明なノードを逐次的に枝刈り

• エッジ数が1本のノード
• 隣接ノードが1クラスタであるノード

• 低次数順ノード選択

• グラフのPower-Law特性に着目
• 低次数順に計算対象ノードを選択

グラフクラスタリングの並列化

• より高速なクラスタリングを行うためには、並列化などの高速化技術が不可欠

• グラフデータ処理の並列化は難しい

• データを分割し、分割統治法的に解く => データ並列化により高速化はされるが、Cutされたエッジの計算が実行されず、精度の低下が。。。

• 並列化の基本方針

• 複数の計算リソースに対し、グラフデータ分割は行わない
• 1CPU上でSIMD命令を用いて、ノード単位でModularityを並列化