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

僕と MySQL と時々 MariaDB

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