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

僕と MySQL と時々 MariaDB

docker-compose を使って MySQL8 の レプリケーションを構築する

MySQL

はじめに

どうも、最近アローを見ていてフラッシュに出てくるアローのキャストと同じで感動してるけんつです。フェリシティいいよね。
ようやくアドカレが終わったので、気分転換にやろうやろうと思っていた MySQL のレプリケーションを docker-compose で構築する方法でもまとめます。

qiita とかみたら実例があるけども、それを見たらあまり勉強にならないのでなるべく MySQL 8 の公式ドキュメントを見ながら構築していく。

今回はいつの間にか降ってきていた MySQL 8.0.18 の docker コンテナを使ってやっていく。

MySQL のレプリケーション

そもそも MySQL におけるレプリケーションとはそもそも何なのかと言うと、Master のデータを１つ以上の Slave にコピーできる機能。
そしてこのレプリケーション機能は、デフォルトで非同期なので Slave は Master からのデータを受け取るために永続的に接続している必要がない。
また構成に応じて全てのデータベース、選択したデータベース、テーブルなどを選択して複製することができる。

レプリケーションを取る利点しては以下の通り。

  • スケールアウト： 複数のスレーブに負荷を分散する。書き込みに関することはマスターで行う必要があるが。読み込みに関してはスレーブを利用させることで負荷を減らす。
  • データセキュリティ: データはスレーブに複製され、スレーブはレプリケーションプロセスを一時停止させることができるためマスターデータを壊すこと無くスレーブでバックアップを実行することができる。
  • 分析; 理由はスケールアウトと似ている。負荷の高い情報の読み取りを行うような分析に関することではマスターの負荷を上げることなくスレーブで実行できる。
  • 長距離データ配布: マスターへの永続的なアクセスを必要とせず、レプリケーションを使用してデータをローカルコピーできる。

レプリケーション形式

MySQL には 3 つのレプリケーション形式が存在する。
ひとつは Statement Based Replication(SBR) と呼ばれるもので、 SQL ステートメント全体を複製する。
もうひとつは Row Based Replication(RBR) と呼ばれるもので、変更があった行だけを複製する。
３つ目として、これら２つを状況に応じてキリ開ける Mixed Based Replication というものがある。

デフォルトでは SBR が有効になる。

目的とする構成

まず、Master 1 台に対して Slave 1 台の構成を目指す。
Slave2 という設定が github レポジトリにはあるがそれは今後 GTID レプリケーションを構成する用の設定なので無視していい

成果物

github.com

Binary Log File Position Based Replication の構築

Master サーバの設定

レプリケーションを構築するためにはマスターでバイナリロギングが有効になっている必要がある。MySQL 8ではデフォルトで有効になっている。MySQL 5.7 以下ではデフォルトで有効にならないため、設定する必要がある。
バイナリログはデフォルトで /var/lib/mysql/ に binlog*** という命名で作成される。これは log_bin_basename で変更可能。
また、server_id という 1~2^32 - 1 の正の整数値で指定するサーバを一意に求めることの出来る ID を設定する必要がある。また、これは設定しない場合はデフォルトで 0 が設定されているがその状態だとマスターはスレーブからの接続を拒否するため必ず設定する必要がある。
それらを踏まえて my.cnf(master.cnf) に以下の設定を追加する。

[mysqld]
...
server_id=1

確認する。

MySQL [(none)]> select @@global.log_bin;
+------------------+
| @@global.log_bin |
+------------------+
|                1 |
+------------------+
1 row in set (0.00 sec)

MySQL [(none)]> select @@global.server_id;
+--------------------+
| @@global.server_id |
+--------------------+
|                  1 |
+--------------------+
1 row in set (0.00 sec)

おっけーっぽい。

Slave の設定

こちらも同様に server_id を設定する必要がある。
レプリケーションを取りたい MySQL サーバ同士で ID が被らないように以下の様に設定を追加する。

slave1.cnf

[mysqld]
...
server_id=2

設定を確認する。

MySQL [(none)]> select @@global.log_bin;
+------------------+
| @@global.log_bin |
+------------------+
|                1 |
+------------------+
1 row in set (0.00 sec)

MySQL [(none)]> select @@global.server_id;
+--------------------+
| @@global.server_id |
+--------------------+
|                  2 |
+--------------------+
1 row in set (0.00 sec)

一応 log_bin の設定値を確認したが Slave でバイナリロギングを有効にする必要は実はない。
有効になっていれば、データバックアップとクラッシュリカバリに Slave のバイナリロギングを利用することができるらしい。

レプリケーションユーザを作成する

必ずレプリケーション専用のユーザを作らないといけないわけではないが、レプリケーションのユーザ名とパスワードは mysql.slave_master_info にプレーンテキストとして保存されるため必要最低限の権限を与えた専用ユーザを作成するべきらしい。
といってもやることはユーザを作成して REPLICATION SLAVE の GRANT を付与するだけ。

以下のシェルスクリプトを slave 用 mysql コンテナの docker-entrypoint-initdb.d 以下にマウントする。
またレプリケーション専用アカウントの情報は適宜 docker-compose yaml に追加する

#!/bin/sh

mysql -u root -v mysql <<SQL
        CREATE USER '${MYSQL_REPLICATION_USER:+repl}'@'%' IDENTIFIED BY '${MYSQL_REPLICATION_PASSWORD:+repl}';
        GRANT REPLICATION SLAVE ON *.* TO '$MYSQL_REPLICATION_USER'@'%';
SQL
余談

MySQL のコンテナを使う場合に、MYSQL_USER 等が設定されていると自動でユーザが作成されるが
MySQL_DATABASE が設定されていない場合は USAGE が、設定されている場合はその Database に対して ALL が GRANT として設定されるらしい。

レプリケーションマスターバイナリログのポジション取得

まず、レプリケーションを構築するにはやることがある。
初回起動時は docker-compose yaml の値をもとにユーザなどが作成されるがバイナリログを有効にしているためこれらのログが存在する。
そのため、master のバイナリログをリセットする必要がある。*1

その前提の元に、データスナップショットを取るために必要な手順を追っていく。

まずはバイナリログのどこからレプリケーションを開始するのが正しいかを判断するためにバイナリログのポジションを取得する。
この際に、更新が走ってしまうとバイナリログの位置が変わってしまうため READ LOCK をかける。

この２つを行うため、さっきのシェルスクリプトに以下の SQL を追加する。

#!/bin/sh

...

mysql -u root -v mysql <<SQL
    RESET MASTER;
    FLUSH TABLES WITH READ LOCK;
SQL

次に SHOW MASTER STATUS を参照してバイナリログファイルとポジションを取得する。
それらの情報は Slave を Master に接続するために必要となる。

#!/bin/sh
...

binlogfile=`mysql -u root -h master -e "SHOW MASTER STATUS\G" | grep File: | awk '{print $2}'`
position=`mysql -u root -h master -e "SHOW MASTER STATUS\G" | grep Position: | awk '{print $2}'`

mysqldump を使って master のスナップショットを作成する

次に、スナップショットを作成する。今回は全てのデータベースを対称にするため以下のようにする。
めんどうなのでついてに master のスナップショットを slave に突っ込む。

#!/bin/sh
...
mysqldump -u root -h master --all-databases --master-data > /tmp/master.sql
mysql -u root < /tmp/master.sql

slave1.cnf

[mysqld]
...
skip-slave-start
    • skip-slave-start が無いと、この mysqldump を実行した段階でスレーブが開始してしまうためスレーブ側で STOP SLAVE を実行する必要がある。

Slave を開始する

CHANGE MASTER TO で、接続先と開始するログファイルにポジションを指定して START SLAVE によって開始する。
そのあとで Master の READ LOCK を取っているからそれをアンロックする。

なぜか skip-slave-start が有効にならなかったので STOP SLAVE をしている

#!/bin/sh
...

mysql -u root -v -e "STOP SLAVE";
mysql -u root -v -e "RESET SLAVE";
mysql -u root -v -e "CHANGE MASTER TO MASTER_HOST='master', MASTER_USER='root', MASTER_PASSWORD='', MASTER_LOG_FILE='${binlogfile}', MASTER_LOG_POS=${position};"
mysql -u root -v -e "START SLAVE;"

mysql -u root -h master -v -e "UNLOCK TABLES;"

動作確認

$ docker-compose exec slave1 mysql -e 'show slave status \G'
...
             Slave_IO_Running: Yes
            Slave_SQL_Running: Yes
...
$ docker-compose exec slave1 mysql -e "select * from sample.hello;"
+----+--------+
| id | lang   |
+----+--------+
|  1 | Golang |
|  2 | SQL    |
|  3 | PHP    |
|  4 | Java   |
|  5 | C      |
+----+--------+
$ docker-compose exec master mysql -e "insert into sample.hello(lang) values ('Scala')"
$ docker-compose exec slave1 mysql -e "select * from sample.hello;"+----+--------+
| id | lang   |
+----+--------+
|  1 | Golang |
|  2 | SQL    |
|  3 | PHP    |
|  4 | Java   |
|  5 | C      |
|  6 | Scala  |
+----+--------+

できてるっぽい。

おわりに

もう少しこのレプリケーション周りのオプションだったり、バイナリログ周りは追っていく必要がありそうだけどとりあえずできた。

*1:MySQL :: MySQL 8.0 Reference Manual :: 13.4.1.2 RESET MASTER Statement https://dev.mysql.com/doc/refman/8.0/en/reset-master.html

アドカレを通して CMU Database Systems をひたすら追ってみて

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

はじめに


以下の記事に触発されて CMU Database Systems を追っていって途中から DBMS の自作に切り替えてアドカレにしてみて、色々と思うところやどこまでできたのかをまとめられたらいいなと思う。

buildersbox.corp-sansan.com

題材

　
www.youtube.com

なにをやったか

CMU Database Systems を追った

DBMS について体系的に学習するために以下の講義を追った。

  • 01 Relational Data Model
  • 02 Advanced SQL
  • 03,04 Database Storage
  • 05 Buffer Pools
  • 06 Hash Tables
  • 07, 08 Tree Indexes
  • 09 Index Concurrency Control
  • 10 Query Processing
  • 16 Concurrency Control Theory
  • 17 Two-Phase Locking
  • 19 Multi-Version Concurrency Control
  • 20 Logging Schemes
  • 21 Database Recovery

ほとんどが DBMS の中でも DB Storage に関する内容。
ところどころ抜けている部分は JOIN アルゴリズムだったり、内部的にクエリで得た検索結果をソートしたりといった内容で、後半で行った DBMS の実装に含めないことにした部分。

DBMS の実装の一部

Database Storage については実装を進めた。やってくるクエリを直列で捌くぐらいなら問題内程度の実装にはなっている。
そのあたりは 11 ~ 18 日あたりの雑な記事を参照するとわかりそう。

クエリのパーサ何かはこの後書くけど諸事情で断念したので、終盤のトランザクション周りとクエリあたりは実装できていない。

既存の実装を調べた

途中で、実際に MySQL, PostgreSQL ではどのように実装されているのかというところも諸々調べてみた。

rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com

ストレージだけ実装した

前述の通り、トランザクションは実装できていないけどひとまずストレージだけは実装した。
構成要素としては以下の通り

  • Catalog
  • Tuple
  • Page
  • Buffer Pool
  • B Tree Index
  • Clock Sweep Cache
  • LRU Cache
  • Disk Manager

Page, Tuple は Protocol Buffer を使わず、 gob も使わず自前で byte 列にシリアライズしている。
Buffer Pool 周りは PostgreSQL 8*1を参考に実装している。
ひとまず、ページに対してタプル*2の追加はできるし、テーブルという単位でそれらを管理することもできる
あとは B Tree では int32 相当の値と string の検索に対応することもできた。

やってみて

辛さ半分、楽しさ半分

辛いところ

最初にあげた記事にもあるようにコンピュータ・サイエンスの基本的な知識が要求されるため、現役学部生といえど情報工学を専攻している身には新しく学ぶことになる前提知識が多くてかなり大変だった。
この一連の流れを通して学習することが、CS の基本知識 + DBMS の理論についてなのでかなり盛りだくさんだったのは言うまでもなく苦労の連続だった。

そして最も厳しかったのは B Tree や Buffer Pool の実装で、これはデータ構造とアルゴリズムの実装が連続するため知識としてもっていても
またそれらを実装できるのは全く別の話なのでかなり時間を食ってしまったし、わかるとできるを結びつけるのを締め切りに迫られながらやるのはかなりメンタルに来るものがある。

楽しかったところ

まず、DBMS に関して体系的に学べたのは新しい発見の連続でこれはかなりワクワクする内容だった。特にストレージ周りは新しく学ぶことばかりで、日々の勉強が楽しかった。このワクワク、なかなか伝わりにくいとは思うが新しく学んだことを試行錯誤しながら実装するのはめちゃくちゃ楽しい。


以前、 Linux Kernel モジュールを書いていたことがあるのだけど講義内で出てくる仮想記憶や mmap などのシステムコールについても解説があり
自分のなかで断片として持っていた知識が「あぁ実際にはこういう実装に使えるのか。それでこの DBMS はこういう実装になっているのか」とつながっていく感覚もさらに実装の幅が広がったのもワクワクの連続だった。


また、既存の DBMS についての実装もかなり追ったので MySQL*3 の binlog, LRU Cache や PostgreSQL の BufferPool に関連する本来ブラックボックスのようになっているものの裏側をきちんと理解することが出来てので当初の目的通り最低限そういった知見が得られたのは非常に良かったと思う。

Golang 力があがった

これは sansan の荒川さんのレポジトリを参考にして作っていたというのが関係している。
github.com

例えば、Slice と Array の使い方だったり、 B Tree のような構造の実装であったりとすごく得るものがあった。
B Tree で Node がもつ Item で Interface を使っていたが、interface の使い方で普段は迷うことが多いのですごく参考になった。

また実装に入った段階で出来るだけ異なるアプローチや仕組みを実装しようと思っていたので、常に試行錯誤の連続も何度も書いて消してを繰り返したので必然的に Golang 力があがった。

あとは Goroutine 周り。あまりヘビーな使い方をしたことがなかったが、ラッチ相当の機能を実装するために sync.RWMutex なんかを多用したため、そのあたりの排他制御に関する知見と実装方法にたいする理解も深まった。

既存の実装への理解が深まった

楽しかったところにもあったが、これもひとつ大きな副次的効果だと思う。めちゃくちゃ調べて

blog.jcole.us
blog.jcole.us

こういった Page の物理的構成に関する記事を見て参考にしたり

http://www.interdb.jp/pg/pgsql08.html

こういったものも参考にしたので、自然と既存の実装について理解がかなり深まった。
MySQL のドキュメントもかなり参照した。

反省点

SQL に対する理解と見通しが甘かった

今回はこれに尽きる。

後々、JOIN やサブクエリ等の実装もしたかったので、再帰降下構文解析でなく goyacc で実装しようとは最初から思っていたのだが
簡単に出来ると思っていて*4、ストレージの実装にかなりの時間を使ったのだが実際やってみると B Tree や Buffer Pool の実装の比にならないほど難航した。
そのため、その後に控えていたトランザクションの実装をする時間がなくなってしまったという事態になってしまった。

めちゃくちゃ見通しが甘かった。

CS の基礎が不足している

これも想像以上に時間がかかった理由になっている。
本来 DBMS の理論の学習に時間を割くべきだが、そこで前提とされている CS に関する基礎知識が不足していたためにところどころで遅れを招いた。
これは普段から、如何にライブラリ何かがいい感じにしてくれるバックグラウンドにあるものを理解できていないかというところが露呈したと思っている。
どうにかそのあたりも勉強しないといけないと痛感した。

終わりに

これでひとまずアドカレは終わりとするが、いい感じのところまで行っているから実装を続けていきたい。
あと、作っていて思ったけどオンメモリ KVS みたいな NoSQL の実装をやってみたくなったり
既存の実装を追っている内に MySQL についてもっと勉強したくなったので、今回学んだことを活かして何かしらデータベース周りを勉強していきたい。

あとこれは必ずやっていきたいが、そういう実装や学習を通して特にトランザクションやロギング、リカバリあたりを簡単にまとめるのではなくしっかり理解して行きたい

それではこれで一人アドカレを終わりにする。

*1:たまたま有志による内部構成のドキュメントが見つかった

*2:いわゆる列というやつ

*3:正確には InnoDB

*4:これが無謀な見通しだった

CMU Database Systems をひたすら追っていく ~21 Database Recovery~

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

はじめに

今回は実際にリカバリをどのように行うかという話。

Aries

Algorithm for Recovery and Isolation Exploiting Semantics の略で IBM が 1990 年代に研究したもの。
これを完全に採用しているものは少ないが、この手法に類似した方法を取っている。

ARIES の処理手順

  • WAL: ディスクに変更が書き込まれる前に変更をストレージに書き込む。
  • Repeating History during redo: 再起動時にアクションをリトレースし、クラッシュ前の正確な状態に戻す。
  • Logging Changes during undo: UNDO アクションを記録して、処理に失敗した場合はそのアクションを再度繰り返さないようにする。

WAL Records

ログレコード形式を拡張して、追加情報を持つ必要がある。全てのログレコードに LSN*1を追加することで対応する。

  • 各ページには Page LSN が含まれ、最新の更新を示す。
  • またフラッシュされた最大の LSN も持つ
  • ディスクに書き込まれる前に、 page LSN <= flushed LSN となるようにログをフラッシュする

Normal Execution

Transaction Commits

  • COMMIT レコードをログに追加する。
  • トランザクションの COMMIT レコードへの全てのログはディスクにフラッシュされる。
  • コミットに成功すると TXN-END レコードを書き込む。これは内部でのみ使用されるためすぐにフラッシュする必要がない。

Transaction Abort

Compensation Log Record

  • CLR という更新レコードのアクションを取り消すためのアクションを記述する
  • 次に取り消される LSN も undo Next ポインタとして持っておく

アルゴリズム

  • ABORTレコードを書き込む
  • 更新を逆順い再生して、変更を削除する。更新毎に CLR エントリを書き込み以前の値を復元する
  • 最後に TXN-END ログレコードを書き込む

ARIES Recovery

ARIES は 3 つのフェーズで構成されている。
クラッシュ後は起動時にそのフェーズを逐次実行していく。

  • Analysis: WAL を読んでバッファプール内のダーティページとクラッシュ時のアクティブなトランザクションを確認する
  • Redo: ログ内の適切なポイントから始める全てのアクションを繰り返す
  • Undo: クラッシュする前にコミットしなかったトランザクションのアクションを元に戻す

おわりに

簡単にまとめたけど、これを一つずつちゃんとまとめないと理解できない気がしてきた

*1:ログシーケンス番号

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:適切にロックなどを挟むが