rkmathi/GB37301.md

## GB37301.md

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              GB37301_3.md
            
          
    http://www.slideshare.net/starpos
3限目 データストレージの諸々 - 星野 喬さん(サイボウズ・ラボ)

自己紹介

サイボウズの紹介

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

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

データストレージの概要


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


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


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


HDD


Flash memory


ストレージの大事なこと


データを失わない
可用性の確保
性能
コスト
その他


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


ブロック単位のIO


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


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


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


SRAM as cache
DRAM as cache
Cache (flash mem, DRAM)
SSD/Flash dirve
HDD
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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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

      
    Raw
  

              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が向上するまで繰り返す


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


本研究の目標


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


クラスタリング高速化


Louvain法のボトルネック分析


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


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


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

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


グラフのクラスター性


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


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


Power-Law特性


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


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


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


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


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


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


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


低次数順ノード選択


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


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


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


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


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


並列化の基本方針


複数の計算リソースに対し、グラフデータ分割は行わない
1CPU上でSIMD命令を用いて、ノード単位でModularityを並列化
how/what	Schema-full	Schema-less
Retrospect	RDBMS,Hive,BigQuery	MongoDB,TD
Prospect	Esper,CEPs	Norikra,...
xxx	ACID	BASE	xxx
xxx	xxx	整合していなくても常にデータにアクセスできる	Basically Avaiable
Atomicity	複数の操作の成功・失敗をまとめる	xxx	xxx
Consistency	冗長化されたデータや複数のリレーションが常に整合している	最終的に整合した状態になることが保証されていれば良い	Eventually Consistent
Isolation	並行管理して更新途中の状態を見せない	xxx	xxx
Durability	データを永続化して失わない	xxx	xxx
xxx	xxx	レプリカは決定論的ではなく、確率論的であったり、グローバルに一貫していなくても良い	Soft-state
xxx	CA重視	AP重視
SQL	RDBMS	xxx
カラム指向	HBase	Cassandra
ドキュメント指向	MongoDB	CouchDB
(blob)	xxx	Riak
界隈	種類	頂点数
ORなど	交通ネットワーク	全米 :> 2x10^7
Webなど	ソーシャルネットワーク	Twitter :> 2x10^8
生物情報	タンパク質間相互作用など	>10^9
国防	謎	アメリカ国土安全保障省 :> 10^15