データベースには、トランザクション、ACID特性、ロック、アノマリー、トランザクション分離レベルなどの多くの概念がありますが、それらがどのように関連しているかについて考えたことがありませんでした。

この投稿は、RDBの同時実行制御という観点からそれらの概念を自分の理解のためにまとめたものです。トランザクション分離レベルについて詳しく整理してくださっているスライドと記事の内容をベースにしています。

RDBの同時実行制御の概要

ここでは、RDBの同時実行制御とはなにか、なぜ必要なのか、どのように実現されているかの概要をまとめています。具体的には、同時実行制御の観点から、トランザクション、ACID特性、ロック、アノマリー、トランザクション分離レベル、MVCCについて簡単にまとめています。

RDBの同時実行制御とは

RDBにおける同時実行制御・並行制御 (Concurrency Control) とは、複数のトランザクションを効率的に処理しつつ、データの整合性を保つための技術です。

ここでの整合性とはデータに矛盾がないことを指します。具体的には、存在しないはずのデータを読み取ることや、前後で読み取ったデータが異なることがない状態を意味します。

トランザクションと同時実行制御

RDBには、連続した操作の単位としてトランザクションがあり、ACID特性を満たしていると言われています。ACID特性のなかでわかりやすいと思うのは原子性(Atomicity)で、一連の操作がすべて実行されるか、すべて実行されないかのどちらかであることを保証する性質です。トランザクション内の一部の操作が失敗した時点で、それ以前の操作はデータベースによってロールバックされ、なかったことにしてくれます。

ACID特性で同時実行制御と深く結びついているものは分離性(Isolation)です。分離性とは、トランザクションを実行する過程が外のトランザクションから独立して見えないという性質のことです。最も理想的なのは、複数のトランザクションが同時に実行されても、直列に実行されたような結果になるというもので、Serializableであるといいます。(後から出てくるトランザクション分離レベルで言うSERIALIZABLEもこれを満たしてはいません)

同時実行の問題とロック

トランザクションに分離性がない場合には、複数のトランザクションが同時に実行されると問題が発生する可能性があります。ここでは以下のような問題について考えていきます。

別のトランザクションの変更を上書きしてしまう問題
別のトランザクションがコミットしていない変更を読み取ってしまう問題

1の問題は、口座残高が十分にあるかを確認してから一定金額を引き落とす処理を一つのトランザクションとしたとき、これを同時に実行すると起きます。あるトランザクションが残高の確認をした直後で、一定金額を引き落とす前に、別のトランザクションが残高の確認をすると、意図しない残高を読み取り、最終的な残高がおかしくなってしまいます。

2の問題は、口座残高を減少させるトランザクションと、口座残高を読み取るトランザクションを同時に実行すると起きます。残高を減少させる処理が実行されたあと、別のトランザクションが残高を読み取ります。その後、残高を減少させるトランザクションが失敗した場合、残高を読み取っているトランザクションは、正しくない残高を持っていることになります。

これら問題を解決するために、対象の行をロックして別のトランザクションの読み取りを防ぐという方法が考えられます。問題1では口座確認の時点で、問題2では残高を減少させる時点でロックを取り、更新を含むトランザクションがコミットされるまで読み取りを待機させることができます。ロックには排他ロックと共有ロックがあり、共有ロック同士では複数のロックを獲得できるため、排他ロックを使ってロックを1つだけ獲得できるようにする必要はあります。

ロック解放のタイミングが重要なため、 S2PL (Strict Two Phase Lock) というロックが使用されます。このロックは2PLという仕組みの亜種で、トランザクションの終了でのみロックを解放することが保証されています。分離性を保つために重要なのは、トランザクションが終了してからロックを解放するということです。

データベースのロックはトランザクションの分離性を確保するための重要な機能ですが、**過度なロックの使用はパフォーマンスの低下を引き起こします。**パフォーマンスのためには、ロックの数を減らしたり、期間を短くする必要が出てきます。例えば、後述するMVCCによって問題2をロックを使用せずに解決しているデータベースが多くあります。

トランザクション分離レベル

ANSI(米国国家規格協会)は、分離性が無いことで発生する異常であるアノマリーに対して、それをどのくらい防ぐかというトランザクション分離レベルを定義しています。

トランザクション分離レベルでは、トランザクションの分離性を妥協してパフォーマンスを重視するような選択肢が用意されています。一番強い分離レベルでは、あらゆる操作にロックをかける挙動になっているデータベースもあるのですが、パフォーマンスの観点から現実的ではなかったり、ある程度の不整合は問題にならないことが多いので、分離性を妥協するための選択肢が用意されています。

ANSIが想定しているアノマリーは以下のとおりです。

Dirty Read
- 他のトランザクションでコミットされていない値を読み込んでしまう
Fuzzy Read
- 以前に読み込んだ値を再度読み込んだとき、他のトランザクションによるコミットによって値が変わってしまう
Phantom Read
- 複数行の集合を一度参照したあと、他のトランザクションのコミットによって集合が変わってしまう

ANSIが定義しているトランザクション分離レベルは以下のとおりです。

READ UNCOMMITTED
- Dirty Readが起こる
READ COMMITTED
- Dirty Readは起こらないが、Fuzzy Readが起こる
REPEATABLE READ
- Fuzzy Readは起こらないが、Phantom Readが起こる
SERIALIZABLE
- 上記すべてのアノマリーが起こらない

ANSIがこれらを定義したあとにも様々なアノマリーが見つかり、トランザクション分離レベルが更新されたり、新しい分離レベルが増えたのですが、この投稿ではあまり深く掘り下げず、ANSIの定義に従ってまとめていきます。

MVCCによるスナップショット参照

多くのデータベースでは、ロックを取る代わりに、MVCC (MultiVersion Concurrency Control) と呼ばれるアルゴリズムによって、スナップショットを参照する仕組みが実装されており、分離性とパフォーマンスがある程度両立できています。これによって、上で紹介しているANSIのアノマリーは、普通のSELECT文でもロック無しで防ぐことができます。

この仕組みではSQL文の種類によって、スナップショットと現在のデータのどちらを参照するかが異なっています。

SELECT
- 一貫性読み取り (Consistent Read) と呼ばれるアクション
- スナップショットを参照する
- ロックを取らない
SELECT ... FOR (SHARE | UPDATE)
- ロック読み取り (Locking Read) と呼ばれるアクション
- 現在のデータを参照する
- ロックを取る
INSERT・UPDATE・DELETE
- 書き込み (Write) と呼ばれるアクション
- 現在のデータを参照する
- ロックを取る

この仕組みでは、スナップショット取得のタイミングより前にコミットされた変更のみが見えるようになっているため、Dirty Readは発生しません。スナップショットを取得するタイミングでアクティブな(アボートもコミットもされていない)トランザクションはわかるので、そのトランザクションによる変更を無視できます。

MySQLとPostgreSQLでは、トランザクション分離レベルによってスナップショットを取得するタイミングが異なり、それによって防げるアノマリーが変わってきます。READ COMMITTEDの場合は各一貫性読み取りの直前に取得され、REPEATABLE READの場合はトランザクションの最初の一貫性読み取り時に取得されます。トランザクションの最初の読み取りでスナップショットが取得される場合、他のトランザクションがコミットしてもスナップショットは変わらないため、Fuzzy Readを防ぐことができます。

RDBMSごとの同時実行制御

ここでは、MySQLとPostgreSQLがどのように同時実行制御を実現しているかをまとめています。それぞれ異なる技術でトランザクション分離レベルを実現している箇所があるため、その違いについてまとめています。

MySQL

MySQLのトランザクション分離レベルは、基本的にANSIのトランザクション分離レベルのように動作しますが、REPEATABLE READでの一貫性読み取りとロック読み取りの混在には注意が必要です。ロック読み取りはスナップショットではなく実際のデータを参照するので、一貫性読み取りと結果が異なってしまい、実際にはREAD COMMITTED相当の動作になってしまいます。

REPEATABLE READ以上を使用すると、ロック読み取り/書き込みでは常にロックを取る動作になっています。ロック読み取り/書き込みでは、レコードをロックするレコードロックがFuzzy Readを防ぎ、値の範囲をロックするギャップロックがPhantom Readを防ぎます。

SERIALIZABLEでは一貫性読み取りがロック読み取りになり、共有ロックを取るようになります。

PostgreSQL

PostgreSQLのトランザクション分離レベルは、REPEATABLE READでPhantom Readが発生しないため、ANSIのトランザクション分離レベルよりやや強いです。MySQLでもそうなのですが、PostgreSQLはMySQLのようにトランザクション分離レベルのダウングレードは発生しません。

REPEATABLE READ以上を使用すると、ロック読み取り/書き込みではギャップロックの代わりに更新競合検査を使用して競合を防ぐことができます。更新競合検査は、これまでのロック (悲観ロック) とは異なり、更新で競合が発生した時点で競合更新エラーが発生する楽観ロックのような仕組みです。楽観ロックはエラーの機会が増え、エラーハンドリングの必要が出てくるので、競合が少ない場合に使われます。

SERIALIZABLEでは一貫性読み取りやロック読み取り/書き込みで SIReadロック (Snapshot Isolation Readロック) という楽観ロックが使われます。このロックで競合が発生した場合には、直列化異常と呼ばれるエラーが発生します。これは、ANSIのアノマリー後に出てきた、直列化異常というアノマリーを防ぐことができます。

RDBMSごとのMVCCの実装概要

ここでは、MySQLとPostgreSQLのMVCCの実装の概要をまとめています。また、それぞれのデータベースで基本的な操作であるINSERTやUPDATE、DELETEがどのように実装されているかの概要にも触れています。

MySQLのMVCC

MySQLでは、行の変更履歴であるUndo Logと、スナップショットとして使われるReadViewによってMVCCが実装されています。

Undo Logとは、各レコードが持っている変更履歴のリストで、更新があるたびに更新前の値がUndo Logの先頭に追加されていきます。MySQLでの削除は実際にレコードが削除されるのではなく、削除フラグの更新操作として記録されるため、Undo LogはInsert Undo Log、Update Undo Logの2種類があります。

各トランザクションにはTRX_IDが割り振られており、このIDは作成順にカウントされていくため、タイムスタンプとして使用されています。レコードやUndo Logには、更新を行ったトランザクションのIDとしてTRX_IDが書き込まれています。

MySQLのMVCCは、ReadViewと呼ばれるデータをトランザクション毎に持っており、スナップショットとして利用しています。このデータは、READ COMMITTEDでは各一貫性読み取り毎に、REPEATABLE READではトランザクション後の最初の一貫性読み取り時に作成されます。ReadViewは以下のような値を持っており、データの可視性を判定するために使用します。

m_creator_trx_id
- ReadViewを作成するトランザクションのID
m_ids
- ReadViewが作成された時点で、アクティブなトランザクションのIDのリスト
- アクティブ(コミットされていない)ということは、そのトランザクションは無視できる
m_low_limit_id
- ReadViewが作成された時点で、次に割り当てられるTRX_ID
- このTRX_IDよりも大きいトランザクションは、作成時点でまだ開始していないトランザクションとみなせるので、無視できる
m_up_limit_id
- m_idsが空でなければ最小値、空であればm_low_limit_id
- このTRX_IDよりも小さいトランザクションは、コミットされているトランザクションとみなせるので、見ることができる

ReadViewと、レコードやUndo LogのTRX_IDを以下のように比較することによって、ReadViewを作成した時点でそのデータが見えるかどうかを判断することができます。

TRX_IDがm_creator_trx_idであるか、m_up_limit_idよりも小さければ見える
TRX_IDがm_low_limit_id以上である場合は見えない
TRX_IDがm_idsに含まれていれば見えない、含まれていなければ見える

上記のようにデータのTRX_IDとReadViewによって可視性を判定できるので、レコードとUndo Logで可視性の判定を繰り返すことによって、現在のスナップショット(ReadView)でどの値が見えているかを決定できます。SELECT時に、まずはレコードのTRX_IDで可視性を判断し、見えていれば値を返し、見えていなければUndo Logに進み、見えていなければ更にUndo Logに進みます。これを繰り返し、見える値がなければそのデータは現在のスナップショットには存在しないと判断できます。

MySQLではパフォーマンスの低下を防ぐために、削除マークの付いたノードなどを削除するpurgeを行う必要があります。セカンダリインデックスのリーフノードには削除フラグしかなく、スナップショットの可視性に関する情報は存在しません。そのため、実際に見えるレコードなのかを判断するためにクラスタ化インデックスにアクセスする必要があり、カバリングインデックスが効かなくなってしまいます。purgeによって不要なUndo Logや削除フラグの付いたレコードやリーフノードを実際に削除することで、パフォーマンス低下を防ぐことができます。

purgeの対象はアクティブなトランザクションよりも古いトランザクションなので、長時間アクティブなトランザクションがあるとパフォーマンスが低下する可能性があります。長時間アクティブなトランザクションが存在すると、そのトランザクションが関心を持つテーブルに関係なく、それ以降のトランザクションのUndo Logが捨てられなくなってしまうため、パフォーマンスが低下しやすいです。

PostgreSQLのMVCC

PostgreSQLでは、レコードのxmin・xmaxと、CLOG、SnapshotDataによってMVCCを実装し、Snapshot Isolationを実現しています。

各トランザクションにXIDが割り振られており、このIDは作成順にカウントされていくため、タイムスタンプとして使用されています。XIDが小さいトランザクションが先、XIDが大きいトランザクションがあとから作成されたことになります。

PostgreSQLでは、DELETEは論理削除を行い、UPDATEは論理削除とレコードの作成を実行します。INSERTではレコードを作成してxmin列に自身のXIDを書き込み、DELETEではレコードのxmax列に自身のXIDを書き込みます。UPDATEではDELETEしたあとに新しい値でINSERTをするような処理を行います。そのため、テーブルの領域には削除したレコード、更新前のレコードが一旦すべて保存されます。

CLOGは、各トランザクションがどのような状態になっているかを追跡するためのログです。XIDと、そのトランザクションがコミット済み (Committed)、進行中 (In Progress)、アボート (Abort) のいずれかであることが記録されています。

PostgreSQLのMVCCの実装では、トランザクションごとに持っているSnapshotDataというデータをスナップショットとして使用します。このデータはREAD COMMITTEDではSQL毎に、REPEATABLE READではトランザクション後の最初のSQLが実行された時点で作成されます。SnapshotDataは以下のような値を持っており、データの可視性を判定するために使用します。

xip
- SnapshotDataを作成する時点で、進行中のトランザクションのXIDのリスト
- このリストに含まれるトランザクションは、作成時点で終了していないため無視できる
xmax
- このXID以上のトランザクションはまだ開始されていないことを表す
- このXID以上のトランザクションは、作成時点で開始されていないため無視できる
xmin
- このXID未満のトランザクションはすでに終了していることを表す
- このXIDよりも小さいトランザクションは、コミット済みかアボートのどちらかなので、CLOGを参照して可視性を判定できる

xminとxmaxがレコードとSnapshotData両方に存在して紛らわしいので、レコードにあるものはxmin列・xmax列と呼びます。

SnapshotDataとレコードのxmin・xmax、CLOGを比較することで、SnapshotDataを作成した時点の可視性を判定できます。xmin列の可視性がある場合にはレコードが見える、xmax列の可視性がある場合にはレコードが見えないことになります。以下は、一つのXIDの可視性を判定する流れです。

XIDが自身のトランザクションのIDと一致していれば可視
XIDがxmax以上なら不可視
XIDがxmin未満ならCLOGを参照し、コミット済みなら可視、アボートなら不可視
XIDがxipに含まれていれば不可視。含まれている場合にはCLOGを参照し、コミット済みなら可視、アボートなら不可視

上記のような判定方法を全レコードのxmin列・xmax列で行うことで、現在のスナップショット(SnapshotData)でテーブルの中のどのレコードが見えるかを判断できます。

PostgreSQLではクエリで無駄なレコードをスキャンしてパフォーマンスを低下させないために、vacuumを実行する必要があります。PostgreSQLではDELETEでもテーブル領域からデータは削除されず、UPDATEでデータが追加されていくため、データを削除するためにはvacuumを実行します。vacuumの対象となるのは、進行中のXIDの最小値なので、長時間トランザクションを実行していると、vacuumによる削除を阻害することになります。

また、vacuumはVisibility Mapを更新することで、インデックスアクセスのパフォーマンス低下を防いでくれます。レコードには可視性を判断する情報がありますが、インデックスには削除フラグしかなく、スナップショットごとの可視性情報がないため、可視性を確認するためにテーブルにアクセスする必要があります。常にアクセスすると効率が悪いため、Visibility Mapというものを利用して、ブロック単位で不可視なレコードが存在するかを管理しており、存在する場合のみテーブルにアクセスします。vacuumによる削除を行わないと、Visibility Mapの更新が行われず、テーブルアクセスが増えてしまいます。

さいごに

データベースに出てくる様々な概念を調べ、同時実行制御の観点からまとめました。

RDBの同時実行制御の出発点は、「ロックによって整合性は確保できるものの、パフォーマンスが低下するため、可能な限りロックを最小限にする必要がある」というところにあると感じています。2PLでは遅いということでトランザクション分離レベルが策定され、ロックを行わないMVCCによる参照が使われているところからそう感じました。

現代のRDBMSでは、製品ごとに異なる実装アプローチが採用されており、SQLやトランザクション分離レベル毎に挙動が異なっています。ここでまとめた知識が、実際のデータベース運用で発生する同時実行制御の問題解決の足がかりになることを願っています。

参考資料

Discussion