それが僕には楽しかったんです。

僕と MySQL と時々 MariaDB

CMU Database Systems をひたすら追っていく ~20 Logging Schemes~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 23 日目の記事です。

はじめに

今日はログ周りの話。
WAL とか、ACID の原子性、耐久性、一貫性などを担保するための重要な要素。

Logging Schemes

リカバリアルゴリズムはデータベースに置いて一貫性、原子性、耐久性を確保する上で需要な要素となっている。
このリカバリアルゴリズムで行う大きく分けて２つにわかれる。

  • DBMS が障害から回復するために通常のトランザクション処理中に行うアクション
  • データベースの原子性、一貫性、耐久性を保証する状態に回復できなかった場合のアクション

またここのでキーワードとして以下の２つがある。

Failure Classification

DBMS で起こる障害は大きくわけて 3 つに分類できる。

Transaction Failures
System Failure
  • Software Failure: DBMS のソフトウェア的な問題でシステムを終了する必要がある場合
  • Hardware Failure: DBMS をホストしているマシンがクラッシュするなど
Storage Media Failure:
  • Non-Repairable Hardware Failure: ディスク障害、不揮発性ストレージの一部がクラッシュする。これから回復するにはアーカイブバージョンから復元するしかない。

Buffer Pool Management Policies

バッファプールを管理するポリシーの２つを紹介する。

例えば、No-Steal + Force で実装するなら。
変更がディスクに書き込まれなかった場合は、中止されたトランザクションによる変更を元に戻す必要はない。
また、コミット時に全ての変更がディスクに書き込まれることが保証されているため変更をやり直す必要はない。
ただし、トランザクションが変更する必要のある全てのデータがメモリに収まらない場合、トランザクションがコミットする前のダーティページをディスクに書き込まないため、そのトランザクションを実行できないという制限がある。

Steal Policy

DBMS がコミットされていないトランザクションが不揮発性ストレージ内のオブジェクトに対して最新のコミットを上書きするかどうか

  • Steal: 許可する
  • No-Streal: 許可しない
Force Policy

トランザクションがコミットされる前に DBMS がトランザクションによって行われた全ての更新がストレージに反映されることを保証するかどうか。

  • Force: 保証される
  • No-Force: 保証されない

Write-Ahead Logging

ディスクページに変更が加えられる前にデータベースに加えられた全ての変更のログをログファイルに記録する手法。
殆どの DBMS で使用されているが、リカバリするためにはログを追う必要があるので処理に時間が掛かる。
ログはDBを復旧するための UNDO, REDO に必要な全ての情報を持っている。
Steal + No-Force システムを例に解説する。

Implementation

更新されたページの関連する全てのログレコードはページ自体がストレージに書きこまれるよりも前に永続化される。

Deferred Updates

  • トランザクションがコミットされるまで DBMS がダーティレコードをディスクに書き込むのを防ぐ場合、変更前の値を保持する必要はない。
  • トランザクションのメモリ使用量が DBMS 側の使用可能なメモリ量より大きい場合は機能しない。
  • ログに元の値がない場合は UNDO することができない(Steal ポリシーはこのために使用する)

Checkpoint

WAL の大きな問題としログファイルが肥大化するという問題がある。
クラッシュ時にこのログファイルが肥大化していると、ログを追ってリカバリする処理に時間がかかることがある。
そのため、チェックポイントを設け定期的にバッファの持つ情報をディスクにフラッシュする必要がある。

チェックポイントはどの程度設けるのが良いという基準はなく、チェックポイントが多すぎるとパフォーマンスが低下し、少なすぎるとその意味が薄れてしまう。
そのため、DBMS が担う役割や要求パフォーマンスに左右される。

Blocking Checkpoint の実装
  • 新たなトランザクションの生成を止め、アクティブなトランザクションが全て完了するのを待つ
  • メモリに存在するログレコードとダーティブロックをストレージにフラッシュする。
  • ログにチェックポイントエントリを書き込みストレージにフラッシュする。

おわりに

次はリカバリについて

CMU Database Systems をひたすら追っていく ~19 Multi-Version Concurrency Control~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 22 日の記事です。

はじめに

今回は MySQL や PostgreSQL でも採用されている MVCC について。

Multi-Version Concurrency Control

これは単に同時実行制御に収まらない広い概念として存在している。過去10年間に実装されたあたらしい DBMS では最も広く利用されているらしい。
これが何かというと、DBMS は DB 内の単一論理オブジェクトにたいして複数の物理バージョンを維持する。
具体的には以下のような処理を行う。

Key Properties

書き込みは読み込みをブロックしない。読み込みも書き込みをブロックしない。
読み取り専用トランザクションはロックを取得せずに一貫したスナップショットを読み取る。
DBMS がスナップショットで実行できるクエリをサポートする。

Version Storage

DBMS が論理オブジェクトの物理バージョンを持つ方法のこと。具体的にはポインタフィールドを使用して論理タプル毎にバージョンチェーンを作成する。
これによって DBMS は実行時に特定のトランザクションから見えるバージョンを見つけることができる。
インデックスは常にチェーンの先頭を指し、スレッドは読み取るべきバージョンを見つけるまでチェーンを検索する。

Append Onky Storage

新しいバージョンは同じテーブルスペースに追加される。

  • Oldest To Newest: 新しいバージョンをチェーンの最後に追加する
  • Newest To Oldest: チェーンの先頭は最新となるため高速に検索できるが、インデックスはバージョンごとに更新する必要がある。
Time Travel Storage

古いバージョンは別のテーブルスペースにコピーされる。

Delta Storage

変更された属性の元の値が別のデルタレコードスペースにコピーされる。

Garbage Collection

DBMS は時間の経過とともに DB から開放可能な物理バージョンを削除する必要がある。
これには２つのアプローチがある。

Tuple Level Garbage Collection
  • Background Vacuuming: 個別のスレッドが定期的にテーブルをスキャンし、開放可能なバージョンを探す
  • Cooperative Cleaning: ワーカスレッドはバージョンチェーンを検索するときに再利用可能なバージョンを検索する
Transaction Level

各トランザクションは独自のRWセットを追跡する。トランザクションが完了すると GC は回収するタプルを特定することができる。
DBMS は終了したトランザクションによって作成された全てのバージョンが不可視になるタイミングを決める。

おわりに

次はログ周りだったかな

CMU Database Systems をひたすら追っていく ~17 Two-Phase Locking~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 21 日目の記事です。

はじめに

今日は Two-Phase Locking について。

Transaction Locks

ラッチというのは以前にも何度か解説していると思うがこれからはロックの話。
ロックには２つ種類がある。

またトランザクションは以下のようにロックマネージャーを用いて実行・管理される。

  • トランザクションはロックマネージャにロックを要求する
  • ロックマネージャは要求のあったオブジェクトに対するロックの状態に基づいて要求を許可、ブロックする
  • トランザクションはロックを不要になった段階で開放する
  • ロックマネージャは内部のロックテーブルを更新し、待機中のトランザクションにロックを付与する。

Two Phase Locking

Two Phase Locking (2PL) は悲観的な同時実行制御プロトコルであり、トランザクションがその場でDB内のオブジェクトにアクセスできるかどうかを決定する。
トランザクションが競合した場合は、2PL で十分に対応できる。しかし、トランザクションが ABORT し、他のトランザクションをロールバックする必要がある場合は無駄な処理が生まれる。
以下の手順を具体的にはとる。

Phase1: Growing
  • 各トランザクションはロックマネージャから必要なロックを要求する
  • ロックマネージャはロック要求を許可または拒否する。
Phase2 Shrinking

Strict Two-Phase Locking

S2PL ではトランザクションが終了時のみロックを開放する。2PL のように Shrinking、縮小フェーズが存在しない。
トランザクションによって書き込まれた値がそのトランザクションが終了するまで他のトランザクションによって読み取られたり、書き込まれたりしない場合スケジュールが厳密となるため有用となる。
このアプローチではカスケードアボートが発生せず、ABORT された場合はトランザクションの変更を元に戻すだけでよい。

2PL Deadlock Handling

Two-Phase Locking ではデッドロックを解消するために検出する場合と防止する２つの方法がある。

検出するアプローチ

DBMS はノードをトランザクションとし、トランザクションが他のトランザクションがロックを開放するのを待っている場合そのベクトルをエッジとして待機グラフを作成する。
デッドロックが検出されると、いくつかの手法を用いてそれを解消する。

この開放するトランザクション(victim) は以下のように選択される。

  • 最も古い or 新しいタイムスタンプを持つもの
  • 進行状況
  • すでにロックされているアイテムの数。
  • ロールバックする必要のあるトランザクション数
  • 過去に再開された回数

防止するアプローチ

トランザクションがロックを取得しようとしたとき、そのロックが別のトランザクションによって保持されている場合はタイムスタンプによる優先度によってデッドロックを防止する挙動を取る。
これによってロックは待機したあと許可されるのは１つになるためデッドロックが発生しない。
以下の手法で防止する。

  • Wait-Die： T1 の優先度が高い場合は、T1 は T2 を待つ。それ以外の場合は T1 を ABORT する
  • Wound-Wait: T1 の優先度が高い場合は T2 は中止される。それ以外の場合は T1 は待機する

おわりに

次は MVCC

CMU Database Systems をひたすら追っていく ~16 Concurrency Control Theory~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 20 日目の記事です。

はじめに

どうも、最近キアヌリーブスが出演する映画を片っ端から見ているけんつです。
ジョンウィックがめちゃくちゃ面白い。

SQL のパーサを yacc を使って実装することが時間的に厳しいので妥協して普通に勉強します。
今回は Concurrency Control Theory ということで同時実行制御についてです。

Transactions

トランザクションは、データベース上のSQLによる一連の操作を処理する上で基本的な単位となる。
ただこのトランザクションを直列で実行した結果と同じになるように、同時に制御することは困難でいくつかの手法や、トランザクションそのものの性質を知る必要がある。

Definitions

その前に諸々定義、説明していく。
まず、トランザクションが実行された結果としては COMMIT, ABORT の 2 通りしかない。
トランザクションが実行され状態が COMMIT になった場合は全ての変更がデータベースに保存されていることが保証される。
ABORT になった場合はそのトランザクションによる変更はトランザクション実行前と同じ状態になっていることが保証される。

また、どういった基準でデータが正しいかということを判断するために ACID 特性というものが存在する。

次にそれぞれの特性の詳細を追っていく。

ACID: Atomicity

トランザクションは完了するかしないかの二択しかもたないという性質。これを実現するのには２つの手法が考えられる。

Shadow Paging

DBMS はページのコピーを作成し、トランザクションはそのコピーに対して変更を加える。トランザクションが完了した段階でそのコピーを反映するという手法。
これは原子性と同時に永続性も担保できるが、最近ではほとんど使われていないらしい。

Logging

こっちは一般的な方法で、全てのアクションに対するログを取ることで ABORT されたトランザクションの操作を取り消すことができる。
WAL なんかはまさにこれ。

ACID: Consistency

DBMS が保持するデータは全て整合性が担保されるべきで、クエリは常に正しい結果を返す必要がある。

DBMS における一貫性

データは整合性制約に順守した形でのみ操作される必要がある。
トランザクションは過去にコミットされたトランザクションの影響を大きく受ける。

トランザクションにおける一貫性

トランザクション開始前にデータベースが一貫性を保っている場合はそのトランザクションが完了したあとも一貫性を保つ必要がある。
トランザクションの一貫性が確保されるかどうかはアプリケーションに依存する。

ACID: Isolation

DBMS はトランザクションがまるで直列に実行されたかのように、並列に実行する必要がある*1。
そのため、分離性がある程度のレベルで担保されていないとデータに不整合が発生してしまう。それらをどうやって防いでいくかという話。

Concurrency Control

同時実行制御には２つのカテゴリが存在する。

  • 悲観的同時実行制御：トランザクションが競合することを前提に同時実行制御を行う。そもそも問題が発生すること自体を防ぐ。
  • 楽観的同時実行制御：トランザクションが競合することは稀であると想定して、問題が起こった時に対処するように制御する。

これらを実現するためにスケジューリングが存在し、同時実行制御は直列で実行した場合と同等の実行スケジュールを生成することに重点が置かれる

ACID: Durability

コミットされたトランザクションによる全ての変更は、クラッシュしたり再起動後も永続化されている必要がある。
これは Shadow Page や Logging によって担保することができる。

おわりに

次は Two Phase Locking について

*1:適切にロックなどを挟むが

CMU Database Systems をひたすら追っていく ~10 Query Processing~

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」19日目の記事です

はじめに

どうも、最近という出だしでブログ記事を 19 個も連続で書くと流石にそろそろネタがなくなってくるけんつです。
今回は SQL の実行周りに関連する話で、久々に CMU の講義に戻ってきます。

今日の動画

www.youtube.com

Query Processing

Query Plan

Query がどのように実行されるかというと、まず SQL が DBMS に投げられるとそれを構文解析に通してツリー構造を作る。
そのツリー構造をもとにどのように実行するか決定する。このとき、実行計画では可能な限りインデックススキャンを利用する必要がある。

Processing Model

DBMSではどのようにクエリプランを実行するかということを定義する。ワークロードに対して色々なトレードオフをもつ様々なモデルが存在する。
ここではそれらについて解説する。

Iterator Model

殆どの DBMS で採用されているモデルで以下のような特徴がある。

- next がコールされる度にオペレータは単一のタプルを返すかタプルが無い場合は Null を返す
- オペレータは子の next を呼び出してタプルを取得して処理するループを実装する

  • DBMS が次のタプルを取得する前にできるだけ多くの演算子を介してタプルを処理する
  • ただし、一部の JOIN, Subquery, ORDER BY などはタプルを全て取得するまでブロックする。

Access Methods

Access Methods とはそのままで、SQL を解析した結果のクエリプランに基づいてクエリを実行する際にどうやってテーブルにアクセスするかという話
大きく分けて２つある。

Sequential Scan

これは順番にアクセスしていくやつ。

  • Prefetch: 各ページにアクセスする際に、DBMS がディスクからのロードなどを極力挟まないように事前に数ページまとめて保持しておく
  • 並列化： 複数のスレッドやプロセスをつかって並行スキャンしていく。
  • Zone Map: 各タプル属性の集計を事前に計算しておく。DBMS はゾーンマップを最初にチェックすることで、ページにアクセスする必要があるかどうかを判断できる。検索するページの総数を減らす目的がある
  • Late Materialization: 各オペレータは次のオペレータが必要する最小限の情報を渡す。
  • Heap Clustering: タプルをクラスタインデックスで指定された順序を使用して、ページに格納する。
Index Scan

一つ以上のインデックスを選択して、クエリに必要なタプルを見つける。
複数のインデックスを使用する場合、DBMS は一致するレコードIDの集合を生成する。Bitmap, Hash Table, Bloom Filter などを使用することが多い。

おわりに

書かれていることが少なかったので自分で調べていく必要がありそう。
OLTP を目指していきたいので Iterator Model を実装する必要があるのかな？

SystemPage の実装

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 18 日目の記事です。

はじめに

どうも、最近ダクソリマスタードで RTA をやりはじめたけんつです。黒騎士斧槍めちゃ強いですね。
今回もめちゃくちゃ短いが、SystemPageの実装についてです。

SystemPage と言っているけどおそらく catalog といったほうがよくてテーブルの情報を持っているやつです

実装

import "encoding/json"

type SystemPage struct {
	MaxPageId   uint64   `json:"MaxPageId"`
	TableName   string   `json:"TableName"`
	ColumnTypes []string `json:"ColumnType"`
	ColumnNames []string `json:"ColumnName"`
}

func NewSystemPage(tableName string) *SystemPage {
	return &SystemPage{
		MaxPageId:   0,
		TableName:   tableName,
		ColumnTypes: []string{},
		ColumnNames: []string{},
	}
}

func SerializeSystemPage(s *SystemPage) []byte {
	buf, err := json.Marshal(*s)
	if err != nil {
		panic(err)
	}
	return buf
}

func DeserializeSystemPage(data []byte) (*SystemPage, error) {
	var sys SystemPage
	err := json.Unmarshal(data, &sys)
	if err != nil {
		return nil, err
	}
	return &sys, nil
}

これに関しては語ることがない。
テーブルの情報を持っていたかった。以上。

おわりに

こんな短くていいのか？

Disk Manager の実装について

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」17 日目の記事です。

はじめに

どうも、最近そろそろ DBMS 作るのでなく MySQL とかの勉強をしたいなと思い始めたけんつです。
今日はディスク周りの話です。
といってもすることがあまりないのでめちゃくちゃ短くなりそうです。

データの永続化

ディレクトリ構成

.toybox
├── hello
│   └── page_0
├── sys
│   └── hello.json
└── world
    └── page_0

ディスク周りの永続化は↑のようなディレクトリ構成のもと実行される。
カタログと言われるテーブル情報を保持するデータは sys ディレクトリ以下にテーブルごとの json ファイルとしてまとめて保存されている。

テーブル毎の Page データは page_[pageid] といったファイルにバイナリを書き込んでいる。

何故こうなったか

Page

これはとくにない。テーブル毎にディレクトリを作って、PageId 0 から一意に id を割り振りたかった。
バイナリにシリアライズしたのは、今後いろんな対応をする上で楽になると思ったから。

System Page

Buffer Pool を作っていて、新しく Page を追加する際に PageId を割り振る必要があるのだがテーブル毎に
メモリ、ディスクの両方で(この場合は主にディスクを考慮している)ページをどれだけ保持しているかを確認したかったから。
そのためにディスクも含めて一番大きい pageId がいくつなのかを知る必要があった。

実装

今回は Direct I/O を使っていない
やっていることも簡単でファイルの RW だけ
一応 Page, SysPage 毎に分けているけどこれを書いていて、もう少し抽象化した方がいいなと思った

package storage

import (
	"io/ioutil"
	"os"
	"path"
	"path/filepath"
	"strconv"
)

type DiskManager struct {
}

const (
	RootDir             = ".toybox"
	PagePrefix          = "page_"
	SystemPageDirectory = "sys"
	SystemPageFileExt   = ".json"
)

func NewDisk() *DiskManager {
	return &DiskManager{}
}

func (d *DiskManager) SavePage(tableName string, pageId uint64, page *Page) error {
	buf, err := SerializePage(page)
	if err != nil {
		return err
	}

	tablePath := filepath.Join(RootDir, tableName)
	_, err = os.Stat(tablePath)
	if os.IsNotExist(err) {
		err := os.MkdirAll(tablePath, 0777)
		if err != nil {
			panic(err)
		}
	}

	pid := strconv.FormatUint(pageId, 10)
	pagePath := path.Join(RootDir, tableName, PagePrefix+pid)
	return ioutil.WriteFile(pagePath, buf[:], 0777)
}

func (d *DiskManager) SaveSystemPage(tableName string, sysPage *SystemPage) error {
	json := SerializeSystemPage(sysPage)

	tablePath := filepath.Join(RootDir, SystemPageDirectory)
	_, err := os.Stat(tablePath)
	if os.IsNotExist(err) {
		err := os.MkdirAll(tablePath, 0777)
		if err != nil {
			panic(err)
		}
	}

	sysPagePath := path.Join(RootDir, SystemPageDirectory, tableName+SystemPageFileExt)
	return ioutil.WriteFile(sysPagePath, json, 0777)
}

func (d *DiskManager) LoadPage(tableName string, pageId uint64) (*Page, error) {

	pid := strconv.FormatUint(pageId, 10)
	pagePath := path.Join(RootDir, tableName, PagePrefix+pid)

	_, err := os.Stat(pagePath)
	if os.IsNotExist(err) {
		return nil, err
	}

	bytes, err := ioutil.ReadFile(pagePath)
	if err != nil {
		return nil, err
	}

	var buf [PageByteSize]byte
	copy(buf[:], bytes)
	return DeserializePage(buf)
}

func (d *DiskManager) LoadSystemPage(tableName string) (*SystemPage, error) {

	pagePath := path.Join(RootDir, SystemPageDirectory, tableName+SystemPageFileExt)
	_, err := os.Stat(pagePath)
	if err != nil {
		return nil, err
	}

	bytes, err := ioutil.ReadFile(pagePath)
	if err != nil {
		return nil, err
	}
	return DeserializeSystemPage(bytes)
}

func (d *DiskManager) LoadAllSystemPage() (map[string]*SystemPage, error) {

	path := path.Join(RootDir, SystemPageDirectory)
	files, err := ioutil.ReadDir(path)

	if err != nil {
		return nil, err
	}

	systems := make(map[string]*SystemPage)
	for _, file := range files {
		p := filepath.Join(path, file.Name())
		bytes, err := ioutil.ReadFile(p)
		if err != nil {
			return nil, err
		}

		sysPage, err := DeserializeSystemPage(bytes)
		if err != nil {
			return nil, err
		}
		systems[file.Name()[:len(file.Name())-5]] = sysPage
	}

	return systems, nil
}

おわりに

次は、SystemPage (Catalog) の話なのでまた短い。