1/30/2014 - 1:14 AM

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

GB37301_a.md

Rendered
Source

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を並列化

GB37301_9.md

Rendered
Source

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_8.md

Rendered
Source

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_7.md

Rendered
Source

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_6.md

Rendered
Source

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_5.md

Rendered
Source

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_4.md

Rendered
Source

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_3.md

Rendered
Source

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_2.md

Rendered
Source

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_1.md

Rendered
Source

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.md

Rendered
Source

情報システム特別講義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研)

Cacher is the code snippet organizer for pro developers

We empower you and your team to get more done, faster

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

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

目標

グラフデータ

クラスタリング

クラスタリング高速化

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

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

今日覚えてもらうこと

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

データベースの歴史

スケーリング

整合性の問題

可用性の問題

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

Retrospection / prospection and schema

Norikra in Action

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

Treasure Data

Plazma

Fluentd

Fluentd以前は

Lambda Architecture

Fluentd

Plazma

MPP Query Engine

クラウド

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

講義の狙い

処理基盤の目的

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

スケーラビリティとは

分散処理基盤の目的

代表的な分散処理基盤

RDBMS/MapReduceの事例

並列DBの特徴

Hadoopの特徴

実際の適用領域

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

MapReduce

Apache Hadoop

MapReduceの課題

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

次世代Hadoopについて

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

Google

ビジュアライゼーション

Spanner

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

趣旨

データベース

並列

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

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

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

JOIN

MapReduce

まとめ

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

自己紹介

サイボウズの紹介

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

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

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

WalBの紹介

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

アジェンダ

基本的なアーキテクチャ

SQL文の処理される流れ

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

メタデータ管理

MVCCとストレージ構造

メモリ管理

ロック制御

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

エグゼキュータ

PostgreSQLの拡張

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

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

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

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

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

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

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

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

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

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

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