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

ここからは、トランザクションの2つ目の重要な機能である「同時実行制御」について見ていきます。

私たちがデータベースを利用するとき、1人で占有しているという贅沢なことはまずありません。自分以外にも多くの人が、検索、更新、削除といった多様な処理を同時並行で実行しています。しかし、私たちはそのことを意識しません。ユーザが「今は誰それが私と同じテーブルを更新しているから、この処理は後でやろう」と考えなければいけないようなシステムは、実用に堪えないでしょう。せいぜいあるとすれば、混みあったときにパフォーマンスが悪くなることを懸念して作業をずらす配慮をするぐらいです。

私たちがこのように、データベースを使うに際して他人の存在に無頓着でいられるのは、DBMSがうまい具合に複数のユーザの処理をスケジューリングし、結果の整合性を担保してくれているからです。この性質をACIDのI（Isolation：分離性または独立性）と呼びます。

本節では、DBMSがどうやって分離性を保証しているのか、そのしくみを詳しく見ていくことにしましょう。そこでまずキーワードとして登場するのが、Serializabilityという概念です。日本語では、直列化可能性とか逐次化可能性と呼びます。

直列させれば分離性の担保ができる

硬い言葉ですが、その定義は別に難しくありません。今、たとえばTa、Tb、Tcという3つの同時実行されているトランザクションがあったとしましょう。これらの結果が（更新に限らず検索の結果も）「⁠正しい」ことは、どういう場合に言えるのでしょうか。

これに対する答えは、「⁠3つのトランザクションが順次実行された場合と同じ結果が得られる場合だ」というものです。要するに、並行で実行されるケースを考えるから話がややこしくなるわけで、そもそも並行でない（＝直列に）実行される場合の結果を考えて、それと同じならOK、ということです。直列実行とは、自分のトランザクションの裏側にほかのトランザクションがいないケースですから、これ以上ない厳格な定義です。DBMSが何らかの方法で、並行実行されているトランザクション群にこの性質を担保できれば、「⁠正しい結果」を常に保証できる、ということが言えるわけです（図4⁠）⁠。

どうすれば直列させられるの？

それでは、並行実行されているトランザクション群を直列にするためには、具体的にどんな方法を使えばよいのでしょう。

真っ先に考えつく単純な方法は、「⁠本当にトランザクションをシーケンシャルに実行するようスケジューリングする」というものです。Taが最初に開始されていたら、終わる前にTbが始まったとしても、待機させます。同様に、Tcも待たせます。こうすると、DBMSはある瞬間においては常に1つのトランザクションしか実行されていないことになります。これは必ず直列させられる方法ですが、これを同時実行制御と呼ぶのは、同時実行してないのですから「看板に偽りあり」です。

それでも、この方法が実用的なら使って悪いことはないのですが、実際はこの荒っぽいやり方は、多くの場合にトレードオフを許容できないぐらいのパフォーマンス低下（スループットおよびレスポンスタイムの悪化）を引き起こしてしまいます。

ではどうすればよいか？ そこでDBMSが取り入れた方法が、ロックによる解決です。

ロックによる解決

ロックとは、「⁠鍵」という名前のとおり、ある資源に対してほかのユーザが使用できないよう鍵をかけることです。データベースにおける資源とは、テーブル、インデックス、シーケンス、ビューなどオブジェクト全般が該当します。

ロックの種類には一般に共有ロック（Sロック）と排他ロック（Xロック）の2つがあり、SはShared、XはeXcludedの略です。それぞれ読み込みロック／書き込みロックとも呼ばれます。

排他ロックのほうはイメージしやすいものです。テーブルのある行を更新しようと思えば、その行に対するほかのトランザクションのアクセスを一切禁止する必要があります。一方、共有ロックのほうは、ほかの共有ロックと両立するという特性を持っています。これは「ロック」という言葉の意味からは矛盾しているように感じられますが、共有ロックは読み取り（SELECT）の対象にかけられるものであるため、ほかのSELECTを禁止する必要がないからです。だから、共有ロックといえども、排他ロックとは両立することはできないのです。

表2は、ある資源XにトランザクションAが先にロックをかけていて、トランザクションBがあとからロックを取得しようとした場合の両立可能性を示すマトリクスです。両立可能なのは、共有ロック同士のみ、ということがわかります。

このように、使う資源を必要レベルに応じて占有／共有する、という方法で、DBMSは直列可能性を担保できます。しかし、このロック方式もまた、無視できない問題を2つ抱えています。

ロックのコスト：スラッシングとデッドロック

スラッシング

DBMSがロックを行うとき、具体的にはロックの取得と解放という2つの動作をしています。そして、ロックが取得されている資源にほかのトランザクションがアクセスをかけてきたら、共有ロック同士でない限り「ブロック」を行います。あとから来たトランザクションをロック解放まで待たせるわけです。よく駅や空港のトイレで行列ができるのを見かけますが、あれなどまさにブロックされたトランザクション群の典型です[5]⁠。トイレの便座を共有ロックで、というわけにはいきませんね。

このしくみから必然的に導かれる結果は、並行トランザクション数が一定数を超えると、1つのトランザクションが待機させられる頻度と時間が増え、平均のパフォーマンスが悪くなるということです。システムの特性（更新が多いのか、検索が多いのか）やハードウェア性能にも左右されるため、一般的な閾値（いきち）は負荷試験をやって測るしかありませんが、このようにロックによるパフォーマンス低下が起きる現象をスラッシング（thrashing）と呼びます。

一度スラッシングが発生するところまでトランザクションの多重度が上がると、それ以上の多重度では性能は劣化する一方となります（図5⁠）⁠。そのため、対策としては限界多重度を超えない程度に流量制限を行うか、ロック粒度を小さくするなどアプリケーションロジックの見直しを行うか、などを考えなければなりません。

デッドロック

他方デッドロックは、スラッシングのような程度の問題とは異なり、論理的な問題であり、それだけに発生条件も厳密です。簡単に言えば、複数のトランザクションが複数の資源をロックする場合（今は単純化のため、2つとしましょう⁠）⁠、互いに相手の資源解放を待つ状態となり、永遠に待機する閉路に陥ることです（図6⁠）⁠。

• ① Aが資源Xを排他ロックする
• ② Bが資源Yを排他ロックする
• ③ Aが資源Yを排他ロックしようとするが、Bの先行ロックにより待機状態となる
• ④ Bが資源Xを排他ロックしようとするが、Aの先行ロックにより待機状態となる

このデッドロックを解消する方法は、どちらか一方のロックを強制的に解放してやることです。デッドロック検知のしくみを持っているDBMS[6]もありますし、またトランザクションに待機の上限時間を設定することで、長時間待機しているトランザクションを破棄（アボート）させるという方法もあります。

アプリケーションの作成側としてデッドロックを発生させないため注意することは、論理的に図6のような閉路を作らないよう設計することはもちろん、なるべく不要なロックを取得しない、ロックの粒度を可能な限り小さくする、といった方針に従うことが必要となります。

私たちは不完全さに我慢できるか？

ここまでで、トランザクションの結果の正しさを保証する基準としての直列化可能性という概念、そしてそれを実現するための一般的なメカニズムがロックだが、この方法にはスラッシングとデッドロックという代償が発生することを見てきました。残念ながらこの問題を副作用なく解決する手段はありません。前回も述べたように、「⁠この世にフリーランチはない」は絶対の法則です。

ロックのコストを下げる方法として、一つの道があります。それは、トランザクションが直列化可能ではないことを認めて、いい加減な結果に我慢するという妥協策です。実は、多くのDBMSがこの妥協策を採用していて、直列化可能であるよりも低いレベルの分離性をサポートしています。

ANSI標準では、次のような4つのトランザクションの分離レベルが定義されています。すでに見たように、一番下の直列化可能が最も厳しく、トランザクション相互の干渉を一切許さず、上にいくほどほかのトランザクションの干渉を受けやすくなります。

• 非コミット読み取り（Read Uncommitted）
• コミット済み読み取り（Read Committed）
• 再読み込み可能読み取り（Repeatable Read）
• 直列化可能（Serializable）

いい加減であることの代償は？

直列化可能以外の3つのレベルにおいては、トランザクションの相互干渉による分離性の侵犯が起きます。それは、次の3つの現象として現れます。

ダーティリード

Taが列の値を変更しているが、まだコミットしていない場合でも、Tbが変更後の値を読み出す。たとえば、あるテーブルの列値が「10」であるレコードをTaが「20」に変更した場合、コミット前でもTbがSELECTした結果が「20」になる。確定前の「汚れた」データを読み出してしまうことから付いた名前

繰り返し不可能な読み出し

最初に、Taがある列値「10」を読み出したとする。そのあと、Tbが列値を「20」に変更し、コミットも行った。そのあと、Taが再度SELECTを実行すると、（⁠「⁠10」ではなく）変更後の「20」が読み出される。Taが最初に読み出した値「10」が再現しないことから付いた名前

ファントム

最初に、Taが範囲検索を行い、3行のレコードを読み出したとする。そのあと、Tbがちょうどその範囲に収まるデータを1行INSERTし、コミットも行った。そのあと、Taが再度同じSELECT文を実行すると、選択されるレコード数が4行になる（もし直列化可能であれば、最初と同じ3行が選択されなければならない⁠）⁠。消えたり現れたりするデータが「幽霊」に似ていることから付いた名前

これら3つの現象がどの分離レベルで起きるかをマトリクスにまとめると、表3のようになります。

直列化可能の場合は、一切の干渉が起きないため、3つの現象すべてと無縁です。それから一段階ずつ緩くなるにつれて、干渉による侵犯も1つずつ増えていくことになります。

そうすると、気になるのはどの程度までのいい加減さなら認められるか、という問題です。これはシステムに求められる厳密性にも依存するので一概に決めることはできないのですが、ほとんどのDBMSが「コミット済み読み取り」をデフォルトの分離レベルとして設定しています（表4⁠）⁠。

これはつまり、ダーティリードのみ阻止して、残り2つの現象は許容するということです。まあだいたい、これぐらいが一般的なシステムの要件としても許容できるレベルということなのでしょう。

まとめ

本稿では、リレーショナルデータベースにおけるトランザクションの概念と、その内部的な扱い方について見てきました。データベースにとってトランザクションが満たすべき重要な性質は、ACIDという4つの概念によって定義されています。それらを満たすためにDBMSが採用している方法が、WAL、ロールフォワード／ロールバック、ロックなどの技術です。

これら個々の技術に共通することは、「⁠厳密さとパフォーマンスのトレードオフに対する妥当な解を見つけるための努力だ」ということです。データファイルを直接更新するコストが十分に小さければWALは必要ありませんし、複数の分離レベルもまた、いい加減さをどの程度許容するかを選ぶためのアイデアです。トレードオフは、地球上のすべての物が重力の法則に縛られるように、システムの世界を支配する第一原理なのです。

それでは、今回のポイントをまとめましょう。

• リレーショナルデータベースのトランザクションはA（原子性）によって、「⁠すべてか無」の原則に支配されている
• DBMSは更新ログ（ジャーナル）へ先行書き込みを行うしくみ（WAL）を持っている
• 同時実行制御はロックのメカニズムで実現される
• ロックは厳密さを保証する方法だが、常にパフォーマンスとのトレードオフとなるため、（⁠I 分離性）のレベルについて選択が必要

今回の演習問題は次のものです。

演習問題の解答は筆者のWebサイトで公開します。それでは、次回またお会いしましょう。

参考資料

『データベースシステム概論 第6版』

（C.J.Date著、藤原譲訳、丸善、1997年）

トランザクションについては「第13章　復旧⁠」⁠、「⁠第14章　並行性」でコンパクトに解説されており、入門に最適です。本書はおそらく日本語で読める一番優れた概論ですが、10年以上前に書かれているため、やや情報は古くなっています（原書は第8版まで出ていますが、邦訳は第6版が最新⁠）⁠。

『Database Management Systems 3rd ed.』

（Raghu Ramakrishnan、Johannes Gehrke著、McGraw Hill Higher Education、2002年）

「Chapter 16 Overview of Transaction Management⁠」⁠、「⁠Chapter 17 Currency Control」および「Chapter 18 Crash Recovery」がトランザクション制御について簡明かつわかりやすい情報を与えてくれます。