こんにちは、 
id:alpicola です。今年4月に新卒入社してアプリケーションエンジニアとして働いています。
ウェブアプリケーションはその性質上、データベースに対して同時に大量の問い合わせを行います。そうした中でデータベースが個々の問い合わせを処理していくときに起こっていることは何か、どういう順序で処理が行われるのか、というのは興味深い話題かと思います。例えばデータベースに対して行った更新処理の結果が、更新を行ったクライアント以外のクライアントからも「見える」ようになるのはいつでしょうか。入社間もない頃、先輩エンジニア達にそうした疑問をぶつけてみたところ、「トランザクション分離レベル」というキーワードと、この分野の古典的な論文 A Critique of ANSI SQL Isolation Levels を教えてもらい、輪読会を社内で開催しました。この記事ではこの輪読会の模様をレポートしたいと思います。
なぜ分離レベルが必要か
分離レベルというものを考える背景・動機については、その論文に丁寧に書いてあるわけではないので、まず軽く触れておきます。
データベースには SELECT のような読み取りを行う操作と INSERT, UPDATE, DELETE といったデータベースの更新を行う操作がありますが、この記事では論文にならって、前者を read そして後者を write という風に簡単に記述することにします。さて、次のような二つのトランザクションがあったとしましょう。
read x write x abort
T1 ----+---------+------------------+--->
read x write y commit
T2 --------+-------+--------+--->commit はトランザクションの成功を表し abort は何らかの理由によってトランザクションをキャンセルすることを表現しています。
データベースは並列に与えられた二つのトランザクションの操作の列を、適当にスケジュールすることにより各々の操作を逐次的に処理していきます。スケジューリングの結果はいろいろ考えられて、例えば次のようなスケジューリングがなされた場合を考えてみてください。
read1 x write1 x read2 x abort1 ----+---------+---------+--------+---...
T1 が書き込んだコミットされる前の値（しかも後でロールバックされる）が T2 によって読み込まれています（このような現象は dirty read と呼ばれます）。もしT2 がその値を使って何か他のアイテムの書き込みを行なったとすると、問題を引き起こすかもしれません。
多くの場合望ましいスケジューリングは例えば次のようなものでしょう。
read1 x write1 x abort1 read2 x ----+---------+--------+--------+---...
分離レベルというのは、先に挙げたような「悪い」スケジューリングを行わないことを保証するものです。多くのデータベースは Read Committed と呼ばれる分離レベルを提供していて、利用者は「コミット前の値が読み込まれること (dirty read) はない」という前提のもとトランザクションを扱うことができます。
論文の紹介
タイトルの通り、 SQL の ANSI 規格の中で与えられている分離レベルの定義を理論的解析を行いながら批判している論文です。後半では今日のデータベースの分離レベル実装でも参照されることの多い Snapshot Isolation を紹介しています。
論文の主張をざっくりまとめると以下の二本立てになっていて
- ANSI 標準の分離レベルの定義は曖昧かつ不備があるため、それに代わる定義を提案する。この定義はロックを用いて定義される分離レベルとも対応づけができる。
- Snapshot Isolation が、望ましい分離レベルの特徴づけになっていることを示す。
次項からこの二つの主張を順に解説していきます。
分離レベル階層を再定義する
基本的な語彙の定義
ここからより形式的に議論ができるよう、いくつか言葉の定義を行います。
- History
- 上で説明したようなスケジューリングの結果得られる操作の列。論文では r1[x]w1[x]r2[x]a1...のような記法を使っており、ここでもそれを踏襲します。
- Conflict
- あるhistoryにおいて rw, wr, ww いずれかのペアで、同じアイテムを対象にし、かつ異なるトランザクションによって行われるものを conflict している、といいます。
- Equivalence（等価性）
- 二つの history は、両者が同じ conflict する操作のペアの集合を持つ時、等価であるといいます。
- Serializable
- ある history は、 serial な history（トランザクションを逐次的に実行する history）と等価になっているとき serializable といいます。
一般に、スケジューリングが正しいことは serializable であることと同一視されています。定義により、トランザクションを個別に逐次実行することは、自明に正しいスケジューリングになりますが、並列性が皆無です。実行効率を考えると並列度が高く、かつ（おおむね）正しいスケジューリングを行うことが目標になります。
なお、serializable の定義は一つに定まったものではありません。上の定義は厳密には conflict serializability と呼ばれるもので、いくつかある serializability の定義の中で最も強いものです。様々な serializability の定義が気になる人は、final state serializability, view serializability といった言葉で調べてみるとよいでしょう。
ANSI 標準の分離レベル階層
先に紹介した Read Committed は ANSI 標準で述べられている分離レベルの一つです。 ANSI が定義する分離レベルは起こってほしくない現象 (anomaly) について説明し、「〇〇が起こらない」ということを定義として採用しています。
- Read Uncommitted
- トランザクションがコミットする前の変更が他のトランザクションによって読まれることがある。
- Read Committed
- 上記の dirty read が起こらない。
- Repeatable Read
- Dirty read に加え、トランザクション内で一旦読み込んだデータが、他のトランザクションによって変更され、同じトランザクションで再び読み込んだ時に異なる値になっていること (non-repeatable read) が起こらない。
- Serializable
- Serializable なトランザクションの実行を提供する。dirty read や non-repeatable read に加えて、ある条件でアイテムの集合を読み込んだ後、他のトランザクションによるアイテムの書き込みがあり、同条件で再び読み込みを行なった時に異なる集合を得ること (phantom read) が起こらない。
わかりやすく見える定義ですが、論文が指摘する通り、これらの anomaly の定義には自然言語で表現されていることによる曖昧さがあり、広い意味で解釈したり、狭い意味で解釈したりできるという問題があります。そこで上で導入した語彙に基づき、分離レベルを history のクラスとして厳密に定義してみましょう。
- READ UNCOMMITTED
- あらゆる history を含むクラス。
- READ COMMITTED
- READ UNCOMMITTED のうち dirty read (A1) を含む history を除いたもの。
- REPEATABLE READ
- READ COMMITTED のうちfuzzy read (A2) を含む history を除いたもの。
- (ANOMALY) SERIALIZABLE
- REPEATABLE READ のうち phantom read (A3) を含む history を除いたもの。
ここではまず dirty read, fuzzy read, phantom read をより限定的な意味で解釈しており、それぞれ形式的には以下の history A1, A2, A3 のような表現になります。
A1: w1[x]...r2[x]...(a1 and c2 in any order) (Dirty Read) A2: r1[x]...w2[x]...c2...r1[x]...c1 (Fuzzy Read) A3: r1[P]...w2[y in P]...c2...r1[P]...c1 (Phantom Read)
なおここでいうところの SERIALIZABLE は、上で説明した serializable とは実質的に異なる概念です。ANSI 自体はどちらともつかない曖昧な書き方になっていますが、世間で一般に ANSI の SERIALIZABLE は、上の「dirty read, fuzzy read, phantom read が起こらない」という意味で使われることが多いようです。論文では区別しやすくするためこちらを便宜的に ANOMALY SERIALIZABLE と呼んでいます。serializable な history であれば dirty read, fuzzy read, phantom read がないというのは定義から明らかにいえるのですが、逆は成り立たず ANOMALY SERIALIZABLE は serializable でない history も含んでしまっています。その理由の一つとしては、後で説明する dirty write が許容されていることというのがあります。
ANSI 分離レベルの改良
論文で提案されている、新しい分離レベルの階層は以下のようになっています。
- READ UNCOMMITTED
- dirty write (P0) を含まない history のクラス。
- READ COMMITTED
- READ UNCOMMITTED のうち dirty read (P1) を含む history を除いたもの。
- REPEATABLE READ
- READ COMMITTED のうち fuzzy read (P2) を含む history を除いたもの。
- SERIALIZABLE
- REPEATABLE READ のうち phantom read (P3) を含む history を除いたもの。
排除する現象として新たに dirty write (P0) が一番低い階層に追加され、また dirty read, fuzzy read, phantom read も以下の A1, A2, A3 より少し広い範囲を含む P1, P2, P3 によって定義されています。
P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write) P1: w1[x]...r2[x]...(c1 or a1) (Dirty Read) P2: r1[x]...w2[x]...(c1 or a1) (Fuzzy or Non-Repeatable Read) P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom)
P1, P2, P3 は A1, A2, A3 と比べて、対象のトランザクションが commit するか abort するかに制限を設けていない分広い現象をカバーすることになります。例えば、次の H1
H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2r1[y=50]w1[y=90]c1
はトランザクション1が x の値を 40 だけ差し引いて y の値に加えるという操作を行い、トランザクション2がその途中の x の値だけ更新された状態を覗き見た状況を表現しています。逐次的な実行ではトランザクションの途中の状態は他のトランザクション見えないはずであるため、これは non-serializable な history であると分かります。この history は A1 には当てはまらない一方で P1 ではカバーされています。
論文はこちらの分離レベル階層の定義の方がよいとする根拠として
- A1でなくP1を採用することで上に挙げたような non-serializable な history を排除できる（P2, P3 に関してもそれぞれ A2, A3 で排除できない history を排除できることが論文では説明されています）
- Dirty write を禁止するとデータベースの制約違反のような non-serializable な挙動がいくらか排除できる
- ロックを使った実装ベースで定義される分離レベルの階層と一致がとれる
などを挙げています。さらにこの定義の SERIALIZABLE は全ての serializable な history を網羅はしていないものの、non-serializable なものは含んでいないようです。
今後この記事で READ COMMITTED や REPEATABLE READ, SERIALIZABLE といったときはこの改良版の分離レベルの定義を指すことにします。
ロックによる分離レベル定義との対応
さて上で言及したロックによって定義される分離レベルについて述べます。ここでは、read の操作は対象のアイテムに対する Read ロックを write の操作は Write ロックを取りに行くものとします。同じアイテムに対して複数のトランザクションが Read ロックを取ることは可能ですが、その他のケース（Read ロックを取られているときに Write ロックを取る、 Write ロックを取られているときに Read または Write ロックを取る）はロックが解放されるのを待つことになります。
さらにロックには次の二種類あるものとします。
- Short duration
- その操作を行う直前に確保し、操作の直後に解放するロック。
- Long duration
- その操作を行う直前に確保し、トランザクションが終了してから解放するロック。
ロックベースの分離レベルの階層を次の表に示します。
| 分離レベル | Read ロック | Write ロック |
|---|---|---|
| Locking READ UNCOMMITTED | - | Long duration |
| Locking READ COMMITTED | Short duration | Long duration |
| Locking REPEATABLE READ | Long duration (item) & short duration (predicate) | Long duration |
| Locking SERIALIZABLE | Long duration | Long duration |
"Long duration (item) & short duration (predicate)" は個別のitemの読み取りには long duration ロックを、述語を使って選択する場合には short duration ロックを使うという意味です。
ここで定義された階層と上の改良版 ANSI Isolation Levels が対応するのは直感的に理解しやすいのではないしょうか。例えば、short duration Read lock と long duration Write lock の組み合わせが防ぐものがまさに dirty read (P1) です。
Snapshot Isolation について
Snapshot Isolation は論文の後半で紹介されている分離レベルの一種です。前半で定義した（改良版）分離レベル階層に照らし合わせると READ COMMITED と REPEATABLE READ の間に位置するにも関わらず、dirty read, fuzzy read, phantom read を防いでおり anomaly の有無で見ると ANOMALY SERIALIZABLE を満足するという興味深い性質を持っています。ここからはこの Snapshot Isolation を定義から解説していきます。
Snapshot Isolation の定義
先に扱ったロックベースの分離レベルと同様に、 Snapshot Isolation も基準となるスケジューラーの実装を考え、その実装の元で実現しうる history の集合を分離レベルとして定義します。そこでまず Snapshot Isolation の（抽象的な）実装から説明します。これまで扱ってきたものと違い Snapshot Isolation は multiversion concurrency control (MVCC) の一種になっており、データベースのアイテムにバージョンの概念が導入されているのが特徴です。さらに以下のようなルールのもとでスケジューリングを行うのが Snapshot Isolation です。
- 各トランザクションは初めての read を行う前に Start タイムスタンプを発行する。
- 各トランザクションは commit する前に Commit タイムスタンプを発行する。
- "First-commiter-win" つまり commit を行うとするトランザクション T1 は下記の状況のときに commit できず abort する。
- 他のトランザクション T2 で [T1 の Start, T1 の Commit] 間の Commit タイムスタンプを持つものが T1 が書き込んだのと同じアイテムに書き込みを行なっていた時。
- トランザクション T1 が commit 成功した時、T1 が書き込んだバージョンのアイテムは、 T1 の Commit タイムスタンプより大きい Start タイムスタンプを持つトランザクションから見えるようになる。
まとめると、ロックなどを用いてコンフリクトを前もって防ぐ代わりに、トランザクションをcommitする前にタイムスタンプを利用してコンフリクトをチェックし必要なら abort するというスタイルになっています。こうした optimistic concurrency control と呼ばれる戦略はコンフリクトが少ない状況では効率的に動作します。
マルチバージョンな動作の例
これまで扱ってきたバージョンを持たない history (論文では single-valued history と呼ばれています）に対し、Snapshot Isolation ではバージョン付きの history を考えることになります。バージョン付きの history はアイテムにバージョンを表す添え字を付け加えることで表現することができます。例えば前に挙げた H1 を Snapshot Isolation で実行したときを考えてみましょう。
H1.SI: r1[x0=50]w1[x1=10]r2[x0=50]r2[y0=50]c2r1[y0=50]w1[y1=90]c1
トランザクション1が x を更新すると最初のバージョン x0 から x1 となります。この更新後もトランザクション2が読みこむのはバージョン x0 であるため、トランザクションの途中の状態は覗けないことになります。
分離レベルとしての形式的な定義
さて、一方で分離レベルはバージョンなし history の集合として定義してきたため、それに合わせるためにはバージョンありの history となしの history の対応を考える必要があるでしょう。論文によれば view equivalence をバージョンありの history に拡張することにより、あるバージョン付き history が与えらえれたときにそれと同等なバージョンなし history を得ることができるようです。先ほどのバージョン付き history に対しては次のものが対応するバージョンなしの（serializable な）history になります。
H1.SI.SV: r1[x=50]r1[y=50]r2[x=50]r2[y=50]c2w1[x=10]w1[y=90]c1
Snapshot Isolation の分離レベルとしての定義は、上のルールによるスケジューリングによって生成されうるバージョンあり history と同等のバージョンなし history の集合として与えることができます。
Snapshot Isolation の強さ
分離レベル L1 の許容するどの non-serializable な history も分離レベル L2 は許容するというとき、L1 は L2 以上の強さを持っているということにしましょう。Snapshot Isolaiton の分離レベルとしての強さについて、次のことがいえます。
- READ COMMITTED より強い。
- "First-commiter-win" ルールのおかげで P0 (dirty write) を排除できる。
- コミットするまでトランザクションの書き込みは他の書き込みから見えないようになっているため P1 (dirty read) は起こらない。
- REPEATABLE READ とは互いにどちらが強いわけでもないという関係。
- REPEATABLE READ で防げない A3 (phantom read) もバージョニングのおかげで Snapshot Isolation では起こらない。
- 一方 REPEATABLE READ が防ぐことのできる write skew（後述）という現象が Snapshot Isolation では起こりうる。
- A1, A2, A3 が起こらないため ANOMALY SERIALIZABLE よりは強い。
Snapshot Isolation は狭義の dirty read, fuzzy read, phantom read が起こらないという特性により、Oracle やバージョン 9.1 より前の PostgreSQL などのデータベースで "serializable mode" として採用されていたそうです。ただし Snapshot Isolation は本当の serializable ではなく write skew のような non-serializable な history を許しています。Write skew は異なる2つのアイテムを同時に読み込んだ2つのトランザクションがそれぞれ別のアイテムに書き込んだ結果、整合性が崩れるというもので、同じアイテムに対する競合する書き込みを防止する "first-commit-win" の裏を書くような anomaly です。形式的には次のように表現できます。
A5B: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)
おわりに
この論文が発表されたのは1995年なので、その後の Snapshot Isolation の発展について少し触れておこうと思います。先ほど書いた通り Snapshot Isolation では write skew が起こりうるのですが、Snapshot Isolation をベースにしつつ write skew を防ぎ serializable な history だけを許容するような分離レベルを実現する試みが行われています（Alan Fekete, Dimitrios Liarokapis, Elizabeth O'Neil, Patrick O'Neil and Dennis Shasha. TODS2005 や Michael Cahill. PhD Thesis など）。そうした Snapshot Isolation の拡張は Serializable Snapshot Isolation と呼ばれています。PostgreSQL 9.1 以降では Serializable Snapshot Isolation に基づいた分離レベルが実装されているそうです。
