この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 20 日目の記事です。
はじめに
どうも、最近キアヌリーブスが出演する映画を片っ端から見ているけんつです。
ジョンウィックがめちゃくちゃ面白い。
SQL のパーサを yacc を使って実装することが時間的に厳しいので妥協して普通に勉強します。
今回は Concurrency Control Theory ということで同時実行制御についてです。
Transactions
トランザクションは、データベース上のSQLによる一連の操作を処理する上で基本的な単位となる。
ただこのトランザクションを直列で実行した結果と同じになるように、同時に制御することは困難でいくつかの手法や、トランザクションそのものの性質を知る必要がある。
Definitions
その前に諸々定義、説明していく。
まず、トランザクションが実行された結果としては COMMIT, ABORT の 2 通りしかない。
トランザクションが実行され状態が COMMIT になった場合は全ての変更がデータベースに保存されていることが保証される。
ABORT になった場合はそのトランザクションによる変更はトランザクション実行前と同じ状態になっていることが保証される。
また、どういった基準でデータが正しいかということを判断するために ACID 特性というものが存在する。
- Atomicity(原子性) : 全てのトランザクションは完了するかしないかの二択しか取らない。
- Consistency(一貫性) : 処理することで不整合をもたらすトランザクションは実行されない。整合性の保証。
- Isolation(分離性) : トランザクションは他のトランザクションの影響を受けない。
- Durability(永続性) : トランザクションがコミットされるとその結果が失われないことを保証する。
次にそれぞれの特性の詳細を追っていく。
ACID: Atomicity
トランザクションは完了するかしないかの二択しかもたないという性質。これを実現するのには２つの手法が考えられる。
Shadow Paging
DBMS はページのコピーを作成し、トランザクションはそのコピーに対して変更を加える。トランザクションが完了した段階でそのコピーを反映するという手法。
これは原子性と同時に永続性も担保できるが、最近ではほとんど使われていないらしい。
Logging
こっちは一般的な方法で、全てのアクションに対するログを取ることで ABORT されたトランザクションの操作を取り消すことができる。
WAL なんかはまさにこれ。
ACID: Consistency
DBMS が保持するデータは全て整合性が担保されるべきで、クエリは常に正しい結果を返す必要がある。
ACID: Isolation
DBMS はトランザクションがまるで直列に実行されたかのように、並列に実行する必要がある*1。
そのため、分離性がある程度のレベルで担保されていないとデータに不整合が発生してしまう。それらをどうやって防いでいくかという話。
ACID: Durability
コミットされたトランザクションによる全ての変更は、クラッシュしたり再起動後も永続化されている必要がある。
これは Shadow Page や Logging によって担保することができる。
おわりに
次は Two Phase Locking について
*1:適切にロックなどを挟むが