DBアタマアカデミー

第2回トランザクションを知ればデータベースがわかる―「データ復旧」「同時実行制御」行う“不完全な”しくみ(3)

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

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

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

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

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

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

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

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

図4 直列に実行された場合と結果が同じなら結果の正しさを担保できる
図4 直列に実行された場合と結果が同じなら結果の正しさを担保できる 図4 直列に実行された場合と結果が同じなら結果の正しさを担保できる

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

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

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

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

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

ロックによる解決

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

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

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

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

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

表2 共有ロック(S)と排他ロック(X)の両立可能性
 
A
XS
BX××
S×

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

スラッシング

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

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

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

図5 ロックによるスラッシングの発生
図5 ロックによるスラッシングの発生
『Database Management Systems 3rd ed.』P.534の図を一部日本語訳

デッドロック

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

図6 デッドロック
図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 ダーティリード、繰り返し不可能な読み出し、ファントムの発生と分離レベルの関係(Yは発生し得ることを、Nは発生しないことを示す)
分離レベルダーティリード繰り返し不可能な読み出しファントム
非コミット読み取りYYY
コミット済み読み取りNYY
再読み込み可能読み取りNNY
直列化可能NNN

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

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

表4 DBMSと分離レベルの対応(◎=デフォルト、○=対応、-=非対応)
分離レベルOracleSQL ServerDB2PostgreSQL MySQL(InnoDB)
非コミット読み取り
コミット済み読み取り
再読み込み可能読み取り
直列化可能

PostgreSQLは、非コミット済み読み取りと再読み込み可能読み取りを設定した場合、それぞれ1つ上位の分離レベルで動作する

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

データベースの基本精神

速くて不味いのと、遅くて美味しいのと、どちらか選びなさい。

まとめ

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

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

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

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

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

演習問題

あなたの使うDBMSが、チェックポイントを実行してデータファイルへの変更データの同期を行うタイミングを調べなさい。

演習問題の解答は筆者の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」がトランザクション制御について簡明かつわかりやすい情報を与えてくれます。

おすすめ記事

記事・ニュース一覧