大規模データシステム論

Author

gentam

Status
archived
Date
2018-06-04
Category

lecturenote

Tag

database, lecture

Updated

2018-07-24

大規模データシステム論 / Big Data System (川島英之) の授業ノート

Contents

シラバス

科目概要

デバイスや計算機の発展に伴い,人類が扱うデータの規模・多様性は増加の一途を辿って います.このようなビッグデータを管理するために,多種多様なデータシステムが研究開 発されています.一見複雑なデータシステムですが,その基本は美しく単純です.本講義 ではそれらの概念と技法を学びます.

主題と目標/授業の手法など

深層学習をはじめとするAI技術と仮想通貨の基盤を成すブロックチェーン技術が隆盛を極 めている.これらの技術はいずれも大規模データに基づくため,それを管理する基盤技術 が必要である.この基盤技術はデータベースシステムと呼ばれる.データベースシステム には伝統的なリレーショナルデータベースから,特定用途に合わせられたグラフ・時系列 データベースなど,様々なものがあり,多数のプロダクトが乱立している. そのように 多様なデータベースシステムではあるが,実はそれらの要素技術は,問合せ処理とトラン ザクション処理のみしかない.これらの技術を修得すれば,いかなるデータベースシステ ムについても理解が可能となるだろう.本講義ではこれらの技術を貫く美しい設計原理を 紹介すると共に,それらの巧妙精緻な実装技芸を解説する.

教材・参考文献

  • Abraham Silberschatz, Henry F. Korth, and S. Sudarshan. 2010. Database Systems Concepts (6th ed.). McGraw-Hill Education.

  • 論文を授業内で紹介する.

第1回 データシステム論への誘い

  1. ビッグデータアプリケーションの紹介

  2. データシステムの紹介

Point: データベースシステムは様々なアプリケーションの重要な基盤技術.進歩は早 いが,基礎理論は大きく変わらない

自己紹介

川島英之


ビッグデータ応用

生み出されている超大量のデータを役に立つように処理

  • SNSなどのウェブサービス

  • サイエンス分野で実験機器や観測機器が生み出すデータ

  • ネットワーク業者

  • スパコン

問合せ処理

DBMSには新たな技術が次々と登場しているが,根本的な部分は変わらない

  • DBMS = みんなで読み書きするテーブル

  • SQL (Structured Query Language) を使って問い合わせ

トランザクション処理

  • トランザクションの性質: ACID

  • Isolation

    他のトランザクションに影響を及ぼさないこと. 複数のトランザクションを並行処理した場合でも,結果はトランザクションを何ら かの順序で逐次処理した場合と一致しなければならない

  • Durability: 失敗した場合にロールバックできるようにしたい → WAL(ログ先行書き 込み)

最近の動向

NoSQLも大切だが,あくまでRelationalが基礎

  • VoltDB by Prof. Stonebraker

  • Dremel @Google

  • F1 @Google

  • MapReduce (Apache Spark)

まとめ

  • 巨大なデータは存在

  • Relational database は基礎

  • データシステムは重要分野

第2回 選択演算 (1)

  1. 点探索

  2. ハッシュ索引

Point: 欲しいデータを検索するには複数の方法がある.バイナリサーチやハッシュ法 を使うと,先頭から1つずつ調べるのと比べて大きく高速化できる

点検索と範囲検索.

SQL

単純な検索

線形探査

先頭から1つずつ調べる

  • 実装が楽

  • ディスク,CPUキャッシュの性質に適合

  • 遅い

二分探査/バイナリサーチ

整列されたデータの中央値と探しているデータとの大小関係を調べて, 探索範囲を半分にする.見つけるまで再帰的に繰り返す.

  • 高性能: \(O(\log N)\)

  • ソート済みデータにしか使えない

ハッシュ法

先にキーに対応する番地を求めておく.

  • ハッシュ関数によってキーを番地へ変換する(もっともシンプルな例はリストの長さで modをとる)

  • 分離連鎖法(separate chaining)/開番地法(open addressing) (線形走査法) がある

    • 分離連鎖法: 重複したキーは既存のキーに対して別のリストを作る

    • 線形走査法: 重複したキーは,空きが見つかるまで規定のステップで飛ばしながらリ ストの先を探していく

  • 高速: \(O(1)\) (重複がなければ)

第3回 選択演算 (2)

  1. 範囲検索

  2. 索引木

Point: 範囲で検索したい場合には,B+-Treeを使った探索木を作ると効果的

範囲検索が可能な索引について学ぶ

B+-Tree

r/lec-lds/b-tree.png

(from Algorithms Behind Modern Storage Systems, acmqueue 2018-05-14, page 5/21)

B+-Treeは,PostgreSQLや一部のファイルシステムなどまで汎用的に使われている.今の時代の中核構造.

  • 木構造

  • リーフノードはキーで整列

  • リーフノードはデータへのポインタを保有

  • 内部ノードはB+ノードへのポインタを保有

    • 内部ノードが保有するポインタの数を N で表す:

    • e.g. N=4 のとき,内部ノードは4つのポインタを持ち,3つのキーを持つ

  • 全リーフの高さが同じ

  • 探索コストは \(O(\log M)\)


  • 値の挿入(Leaf Insert) は,整列されるように適切なリーフノードを探してポインタを 挿入する

  • キーが3つを超えた場合には,リース/ノードをスプリットする.これは必要に応じてル ートに向かって再帰的に行われる

e.g. N=4で,キー 1..15 のB+-Treeを作る過程:

[1]
[1 2]
[1 2 3]
[[1 2]3[3 4]]
[[1 2]3[3 4 5]]
[[1 2]3[3 4]5[5 6]]
[[1 2]3[3 4]5[5 6 7]]
[[1 2]3[3 4]5[5 6]7[7 8]]
[[1 2]3[3 4]5[5 6]7[7 8 9]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10 11]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]11[11 12]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]11[11 12 13]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]11[11 12]13[13 14]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]11[11 12]13[13 14 15]]]
[[[1 2]3[3 4]5[5 6]]7[[7 8]9[9 10]11[11 12]]13[[13 14]15[15 16]]]

範囲の空間化

Spatial Indexes for High Dimension:

  • R-Tree

  • R*-Tree

  • X-Tree

  • SS-Tree

  • M-Tree

  • SR-Tree

  • A-Tree

第4回 集約演算

  1. グルーピング演算

  2. データレイアウト

Point: データをどのような順序でディスクに保存するかによって,処理の性質にトレ ードオフが生じる

NSMとDSM

  • テーブルは行と列からなる二次元の構造だが,ファイル空間は一次元.

  • ここで,テーブルをどのような順序でファイルに保存するかという選択が発生する:

    例えばこのようなテーブルがあったときに,

    ID

    Age

    Score

    01

    19

    90

    02

    21

    70

    • 横に切って(行単位)保存 → NSM (N-ary Storage Model)

      01

      19

      90

      02

      21

      70

      • PostgreSQL で利用される.RDBMSで一般的な方式

    • 縦に切って(列単位)保存 → DSM (Decomposed Storage Model)

      01

      02

      19

      21

      90

      70

      • 総和などの集約演算に強い

  • 最近の研究

  • NSMが向いているものも,DSMが向いている場合もある.結局はトレードオフ

Note

システムコールのレベルで見れば,read() write() などのオペレーションは, ページ単位でデータを扱う.そのため同じページに収まるならば,扱うデータが少なく なっても速くなるとは限らない

第5回 射影演算

  1. 重複除去

  2. 整列法

(休講でスキップ)

第6回 結合演算 (1)

  1. 入れ子ループ結合

  2. 効率的な結合方式

複数のテーブルを結合する処理は遅く,様々な高速化が試みられている

Join

Equi-Join:

SELECT * FROM Reserves R, Sailors S WHERE R.sid = S.sid

Join = 結合:

\begin{equation*} \begin{array}{|ll|c|ll|} \text{ID} & \text{Price} & & \text{ID} & \text{Name} \\ 1 & 110 & \Join & 1 & \text{Candy} \\ 2 & 200 & & 2 & \text{Chocolate} \end{array} \to \begin{array}{|lll|} \text{ID} & \text{Price} & \text{Name} \\ 1 & 110 & \text{Candy} \\ 2 & 200 & \text{Chocolate} \end{array} \end{equation*}

Joinのアルゴリズム

  • 結合は Nested Loops Join で実現できる

    • T個のテーブルを結合するには,実装上はT階層の入れ子ループになる:

      foreach tuple of R
        foreach tuple of S
          if (r == s) add <r,s> to result
    • N個のレコードを持つT個のテーブルを結合するには \(N^T\) 回の照合が必要に なり,非常に遅い.

    • → メモリに入りきらない場合は,さらにページごとのループの下の入れ子になる:

      Block Nested Loops Join

  • Simple Hash Join: 一回目のループでハッシュを計算しておくことで照合を高速化

    1. Rブロックを読み込み

    2. Rのハッシュを作成

      1. Sブロックを読み込み

    3. ハッシュを用いて照合

  • No Partitioned Parallel Hash Join: 並列化してさらに高速化

    • Simple Hash Joinを,複数のスレッドを用いて並列的に照合できるようにする

Note

ここで扱った Nested Loop Join と Simple Hash Join 以外に,照合する値で先に ソートしておいてからマージするなどの方法もある.

第7回 結合演算 (2)

  1. 並列結合アルゴリズム

  2. 並列結合の実現

並列Join

  • No Partitioned Parallel Hash Join

  • Partitioned Parallel Hash Join:

    r/lec-lds/pphj.png
    1. バケツ作成

      1. バケツ数を決定(N)

      2. Rをストレージから読みファ イルR1...RNに分割

      3. Sをストレージから読みファ イルS1...SNに分割

    2. スレッド毎に下記を実行:

      1. スレッドiはRiとSiを読む

      2. 結合処理を実行

Joinのさらなる高速化

  • スパコンの利用

  • Remote DMA (Naofumi Murata, Hideyuki Kawashima, Osamu Tatebe: Accelerating read atomic multi-partition transaction with remote direct memory access. BigComp 2017: 239-246)

研究:

  • An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory, SIGMOD 2016

  • Viktor Leis, Peter A. Boncz, Alfons Kemper, Thomas Neumann: Morsel-driven parallelism: a NUMA-aware query evaluation framework for the many-core age. SIGMOD Conference 2014: 743-754

第8回 問合せ最適化

  1. SQLから代数への変換

  2. データ転送法

Point: 問い合わせに対する処理の順番をよく考えると,計算量を大きく減らせることがある

問い合わせ処理の流れ:

r/lec-lds/query-flow.png

e.g.

SELECT S.sname
FROM Reserves R, Sailors S
WHERE R.sid = S.sid
AND R.bid = 100 AND S.rating > 5

→ Parsed Query:

\begin{equation*} \pi_{\rm sname}\left(\sigma_{\rm bid=100 \land rating > 5} \left(\text{Reserves} \Join_{\rm sid=sid} \text{Sailors}\right) \right) \end{equation*}

これを, Relational Algebra Tree として表す:

r/lec-lds/query-tree.png

Join Ordering

以下のように4つのテーブルを結合する,どのような順序で結合するかという複数の選択肢がある.

\(A \Join B \Join C \Join D\)

r/lec-lds/join-tree.png

\(n\) 個のテーブルを結合する場合:

  • ある木における順序のパタンは: \(n!\)

  • 木の構造の数は:

    \begin{align*} T(1) &= 1, \\ T(n) &= \sum_{i=1}^{n-1} T(i)T(n-i) \end{align*}

ここで,最適な結合順序を選ぶことで計算コストを最小化したい.

順序の決定方1: 総当たり法

  1. 全プランについてコスト計算

    • 結合コスト = \(\frac{|R||S|}{\text{max}(V(R,a),V(S,a))}\)

      • \(|R|\): Rのタプル数

      • \(V(R,a)\): Rの属性aのキー数

  2. 最小プランを選択

順序の決定方2: Selinger法

論文 1

  1. 入力テーブルの準備

    • \(\frac{|R||S|}{\text{max}(V(R,a),V(S,a))}\)

      • \(V(R,a)\): R中のユニークなaの数

  2. 結合サイズの推定

  3. 最良計画の導出

Joinの実現例

  • アルゴリズムレベル:

    • Nested loop join

    • Merge join

    • Hash join

  • ハードウェアレベル:

    • GPU

    • FPGA 2

    • Cell

  • ネットワークの利用:

    • Parallel hash join


1

Yasin Oge, Takefumi Miyoshi, Hideyuki Kawashima, Tsutomu Yoshinaga: A fast handshake join implementation on FPGA with adaptive merging network. SSDBM 2013: 44:1-44:4

2

P. Griffiths Selinger, et, al. Access path selection in a relational database management system. SIGMOD'79.

第9回 中間試験

問合せ処理に関しての試験を実施する. Examination about query processing

第10回 トランザクション

  1. トランザクションの概要

  2. 隔離性

トランザクション管理概観

  • 複数人で同時にアクセスしたいときにどうすればいいか?

    • ATMでの送金と残高の例

  • 復習: プロセスとスレッド

    • 典型的には100ミリ秒でのタイマ割り込みによってOSが複数のプロセスを切り替えて 並行に実行

    • ここから説明するトランザクションの仕組みは,マルチプロセス/マルチスレッドを 基本とする.

前提: データベースを経由することで, データアクセス時間は確実に劣化する. (e.g. トランザクション処理が 93.2% の時間を占めていることが示されている 3)

トランザクション ≒ ACID

ACID
  • Atomicity

  • Consistency

  • Isolation

  • Durability

このうち,

  • Isolation → 平行性制御法 に対応

  • Atomicity, Durability → ログ永続化法に対応 に対応

今回やるのは平行制御法

あるプロセス:

1> begin;
2> select * from lds;
  key
  1
3> update lds set key = 10
4> select * from lds;
  key
  10
5> commit;

commit されるまで,値の変更はローカルで,実際には反映されていない. 例えばえば 4> の時点で他のプロセスが値を読んでも1のままになっている. また 3> の時点で他のプロセスが値を書き換えようとしても,待ち状態になる.

Isolation

要約: 他のトランザクションに影響を及ぼさないこと

定義

  • 複数のトランザクションを並行処理した場合でも,トランザクションの影響を受けず, その結果はトランザクションを何らかの順序で逐次処理した場合 と一致しなければ ならない

  • 擬似並列 (pseudo parallel)=並行 (concurrent)

Serializability

逐次実行した時と等価な結果になるか?

厳密には Conflict Serializable (Final State, View などもある)

T1

T2

R(a)

R(a)

W(a)

W(a)

R(b)

R(b)

W(b)

W(b)

\(r_1(A)w_1(A)r_2(A)w_2(A)r_1(B)w_1(B)r_2(B)w_2(B)\)

T1とT2が並列に行われたときに,結果として上のようなDBでのアクセスパタンになったと すると,その結果が T1→T2 (T1が全て終わってからT2を実行した) or T2→T1 と 等価であれば,それは serializable なアクセスである.

一方で,NG (= 依存性を壊してしまう)パターンは:

  • 同一TXの2つの操作: \(r_i (X); w_i (Y);\)

  • 同一データへのWW (異なるTX): \(w_i(X);w_j(X)\)

  • 同一データへのRW (異なるTX): \(r_i(X);w_j(X)\)

これ以外ではどう順番を変えても問題ない.

ここで上のアクセスパタンが serializable か確認すると:

  • \(\color{blue}{r_1(A)w_1(A)}\color{red}{r_2(A)w_2(A)}\color{blue}{r_1(B)w_1(B)}\color{red}{r_2(B)w_2(B)}\)

    • T1を青,T2を赤に分けた.ここで真ん中の \(\color{red}{r_2(A)w_2(A)}\color{blue}{r_1(B)w_1(B)}\) は,TXもデータ も異なるため入れ替えても問題ない.

  • \(\color{blue}{r_1(A)w_1(A)r_1(B)w_1(B)}\color{red}{r_2(A)w_2(A)r_2(B)w_2(B)}\)

    • これは T1→T2 になっているため,serializable であることが確かめられた.

参考文献: Weikun & Vossen, Transactional Information Systems

3

Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. 2008. OLTP through the looking glass, and what we found there. In Proceedings of the 2008 ACM SIGMOD

第11回 並行性制御法 (1)

  1. 悲観的方式

  2. 楽観的方式

悲観的方法

(Pessimistic Concurrency Control)

ロック獲得をしてから,データのREAD&WRITEを行い,ロック解除という流れ. これは衝突することを前提とした 悲観的 な設計.

Strict Two-Phase Locking (Strict 2PL)
  • もしもトランザクションTがオブジェクトをread/modifyしたければ,Tはまず shared/exclusive ロックを要求する.

  • あるトランザクションにより保持される全てのロックは,トランザクション完了時に 解放される.ひとたびロックを解放したら追加ロックを要求できない

S

X

S

Y

N

X

N

N

デッドロックの問題

複数のトランザクションが,互いにロックしているリソースを要求しあうと,どちらも先 に進めなくなる,デッドロックが発生する.

これは待ちグラフを作ることで検出できる:

  • 各トランザクション \(T_i\) に対して,ノード \(N(T_i)\) を作成

  • トランザクション \(T_i\) が他のトランザクション \(T_j\) のかけているロ ックが解かれているのを待っているとき,有向エッジ \(N(T_i) \to N(T_j)\) を 引く

  • サイクルがあれば,victim を強制abort

デッドロックの回避:

Conservative 2PL

2PLの強化版.1つでもロック獲得を失敗したらしばらく待ってやり直す.データが順序 付けされている. 4

楽観的方法

(Optimistic CC)

データREAD → 検証(VALIDATE) → ロック獲得 → データWRITE → ロック解放

競合が稀な場合にはロックを使わず,コミット前に競合をチェックすることで並行度を高 められる.

Kung-Robinson Model 5

Tiは3つの相を有する: {READ, VALIDATE, WRITE}

\begin{align*} & \mathtt{READ~Phase:} \\ & TX_{start} \gets TX_{global} \quad\color{gray}{\text{自分が始めたときに終わってる人は誰か?}} \\ \\\hline\\ & \mathtt{WRITE~Phase:} \\ & \text{Acquire GIantLock} \quad\color{gray}{\text{自分の番だから他の人に邪魔はさせない}} \\ & TX_{end} \gets TX_{global} \\ & \text{valid $\gets$ true} \\ & \text{For $t$ from $TX_{start} + 1$ to $TX_{end}$} \quad\color{gray}{\text{範囲検索. Case 1は$TX_{start}$で除去}} \\ & \quad \text{if (writeset of $t$ intersects my readset)} \quad\color{gray}{\text{Case 2をチェック}}\\ & \quad\quad \text{valid $\gets$ false} \quad\color{gray}{\text{失敗}} \\ & \text{if(valid = true)} \quad\color{gray}{\text{成功}} \\ & \quad \text{writephase} \quad\color{gray}{\text{実際に書き込む}} \\ & \quad TX_{global} \gets TX_{global} + 1 \quad\color{gray}{\text{成功TX数を1つ追加し}} \\ & \quad TX_{mime} \gets TX_{global} \quad\color{gray}{\text{それを自分のIDとする}} \\ & \text{Release GiantLock} \quad\color{gray}{\text{ロック解除し他の人に譲る}} \end{align*}
  • OCCの最新技術: TicToc

    Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas. TicToc: Time Traveling Optimistic Concurrency Control. SIGMOD Conference 2016.

    • 時刻印を取りにいかず,計算することでスケール.

Anomalies

  • Lost update: 単一データで発生

    \(r_1(x) r_2(x) \color{red}{w_1(x)} w_2(x)\) ここで \(w_1(x)\) がlostして いる

  • Inconsistent read: 複数データで発生

    \(r_2(x) w_2(x) r_1(x) r_1(y) r_2(y) w_2(y)\)


4

Tianzheng Wang, Hideaki Kimura: Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores. PVLDB 10(2): 49-60 (2016)

5

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226 (1981)

第12回 並行性制御法 (2)

  1. ロックの仕組み

  2. 並行木

並行木

e.g. 並行索引木

  • B-link木

  • PLP

  • Bronson法

  • Masstree

  • OLFIT

  • Bw木

どうやって並行アクセスするか:

  • Tree-Locking (ツリー全体をロック)

    • B+-treeforserialupdates

    • 一人だけが更新可能

    • 並行性はない

    • 確実に安全

  • Lock-Coupling 6 (影響がある部分木だけをロックする)

    • B+-tree for concurrent updates

    • 上から下へロック範囲を徐々に狭める

    algorithm:

    While(m != leaf) {
      Lock(m)
      n <- m.child
      Lock(n)
      Unlock(m) // 親を解放
    }

第13回 障害回復

  1. 障害から回復する手法

  2. ログ永続化法

Crash Recovery

復習:

  • トランザクションの性質 ACID

  • PostgreSQL におけるトランザクション:

    # begin;
    # update dbgairon set key = 10;
    # select * from dbgairon ;
    # commit;

ARIES Algorithm

Motivation

  • Atomicity: transactions may abort - Rollback

  • Durability: what if DBMS stops running?

Principles

  • Write-Ahead Logging (WAL)
    • データベースオブジェクトに対するいかなる変更も,最初はログに記録される.

    • ログへの記録は永続的デバイスへ書かれる必要がある

    • この記録は永続的デバイス中のデータベースオブジェクトへの変更に先んじる

  • Analysis

  • Redo
    • ログ中の適切な点から開始して,全ての活動を繰り返す

    • データベースの状態を 故障時 へと戻す

  • Undo

    コミットされていないトランザクションをなくす.つまりコミットされたトランザク ションの活動のみを反映させる

How to WAL

  • ディスク上に散らばっているページを毎回更新(In-Place Update)すると,IOの回数が 増える上,ランダムライトが頻発し性能が劣化する.

  • ディスク上のページの更新は後回しにして,ログファイルに変更点のみをシーケンシャ ルに書き込むことで処理を高速化

トランザクションの流れ:

  1. Begin: トランザクション開始

    • Disk: A = 0

    • Memory: A = 0

  2. Update: データの更新

    • Disk: A = 0

    • Memory: A = 3

    • ログはメモリ上のログバッファに挿入される xid:1, type=UPDATE, page:A, before:0, after:3

  3. Commit: トランザクションの終了

    • コミットログのディスクへのwriteが終わった時点で,クライアントにトランザクションの完了を告げる xid:1, type=COMMIT, page:*, before:*, after:*

    • 参照は必ずメモリから行われる.かつ,メモリから消されるときには必ずディスク と同期が行われるため,データベースに書き込む必要はない

メモリ管理方式

Steal/No-Steal

  • Steal

    • オブジェクトOをコミット前にディスクに書き込む

    • バッファ不足解消のため

  • No-steal → Undo不要

    • オブジェクトOはコミット前にはディスクに書かれない

    • バッファが十分ある場合にのみ可能

Force/No-force

  • Force → Redo不要

    コミット時に変更内容はディスクの該当部分へ反映される

  • No-force

    • コミット時に変更内容はディスクの該当部分へ反映されない

一般的には Steal & No-forceが用いられる

速い不揮発性メモリを前提として,No-Steal & force が研究されている.

Recovery example

Redo(1); Redo(2); Redo(3); Redo(4);

LSN: Log Sequential Number

  • Undo中に失敗したら,最初からやり直すのは非効率的 → Undoをログに記録しておいて skipする

  • 終わった箇所を記録して,そこから再開

  • 最後に書き換えを行ったLSNが分かれば,それ以前のRedoはやる必要がないとわかる

Lockとlogの関係

  • 基本: Lock(A) → Sync(log(A)) → Unlock(A)

  • Question: Sync(log) の前に unlock(A) してもいいか?

    • → よくない.必ず SyncLock, Unlock の間になければいけない

リカバリのまとめ

基本:

  • ログ先行書き込み法

  • Redo: 歴史を繰り返す

  • Undo: 変な奴を消す

最適化:

  • PrevLSN: 次のUNDOへのポインタ

  • UNDOログ: UNDOを途中再開

  • Dirty Page Table: REDOをスキップ

発展: 並列ログ先行書き込み方式 P-WAL

WALの問題点: HDDに最適化された古い設計のままだが,SSDやioDriveの性能が活かせない (フラッシュストレージでは,複数チャネルへの並列アクセスによって最大性能)

  1. ログをまとめて書き込みI/O回数を少なくし,シーケンシャルに追記する

  2. Nスレッドで処理する場合でも,LSNの順序を保つためにWAL バッファーは1つしかなく て排他制御される

提案: 直接WALから並列WALへ

  1. 複数のWALバッファ: スレッド間での衝突が発生しない

  2. 複数のWALファイル: 非連続領域への並列書き込み

  3. Early Lock Release の適応

MapReduce

  • 数千台のマシンで並列な処理を行いたい

  • Map フェーズ:

    • 分割された入力に対して処理を行う

    • shuffling によって,結果を特定のマシンへと振り分ける

  • Reduce フェーズ:

    • 受け取った入力をまとめる処理を行って,最終的な出力を作る

実装

  • hadoop

  • apache spark


  • Bit Data Stream 処理もデータベース理論の基礎の上に成り立っている

    • social network

    • monitoring system

    • science

  • Fontiers of BigData? : Volume, Velocity, Variety

  • Mirror worlds. JavaSpace, tuplespace

  • Crash recovery: 技術の進歩は速く,教科書/論文は古くなっている. → 信じすぎず,自分で考える.自分で確かめる.

  • MapReduce: 温故知新

第14回 復習

期末試験へ向けた復習