並行性制御

情報技術および計算機科学における並行性制御（へいこうせいせいぎょ、英: Concurrency Control）または同時実行制御（どうじじっこうせいぎょ）とは、特にプログラミングとOSとマルチプロセッシングとデータベースにおいて、並行処理の結果が可能な限り素早くかつ正しく得られることを保証することである。

コンピュータシステムは、ソフトウェアもハードウェアも、モジュールまたはコンポーネントで構成される。各コンポーネントは何らかの一貫性規則に従って正しく動作するよう設計されている。コンポーネント間でメッセージをやり取りするか（記憶装置内で）データを共有して並行動作する際、あるコンポーネント間の一貫性が他のコンポーネントによって妨害されることがある。並行性制御の一般的な領域は、同時並行的に相互作用しながら動作するコンポーネント間の一貫性を保つための規則、技法、設計方法論、理論を提供し、結果としてシステム全体の一貫性と正確性を提供する。並行性制御をシステムに導入することは、一般に若干の性能低下を生じる操作上の制約を適用することを意味する。操作一貫性と正確性は、妥当な以上の性能低下を伴わずに可能な限り効率的に達成されるべきである。

データベースにおける並行性制御

ここでデータベースと称しているのは、汎用のデータベース管理システム (DBMS) に限らず、トランザクションを行うあらゆるシステムである。DBMSはデータベースの並行性制御問題と同時にOS一般の並行性制御問題とも関わりが深い。

データベースについて、トランザクションがデータ完全性を失うことなく安全に実行されることを保証する手法である。並行性制御は特にデータベース管理システム (DBMS) に適用され、トランザクションがACID原則（後述）に従って安全に実行されることを保証する。DBMSはシリアライズ可能 (Serializable) で復旧可能 (Recoverable) なスケジュールだけを許すよう設計されなければならず、中断されたトランザクションを取り消す際にコミット済みのトランザクションの結果が失われないことを保証しなければならない。

データベース管理システム (DBMS)[1][2]、他のトランザクションオブジェクト、および関連する分散アプリケーション（例えば、グリッド・コンピューティングやクラウドコンピューティング）の並行性制御は、それぞれのデータベースのデータ完全性を損なうことなく同時並行にトランザクションを実行することを保証する。したがって並行性制御は、事実上あらゆる汎用データベースシステムにおいて、複数のトランザクションが時間的に重なりつつ同じデータにアクセスする際の正確性の基本要件である。その結果、1970年代初めにデータベースシステムが出現して以来ずっと関連した様々な研究成果が蓄積されていき、データベースシステムの並行性制御理論が確立している[1][2]。直列化可能性理論は、並行性制御の技法と機構を効率的に設計し分析することを可能にする。抽象データ型に対するアトミックなトランザクションについての並行性制御理論もある[3]。そちらの理論の方が洗練されていて複雑で適用範囲が広く、最近では上述の古典的理論よりもデータベースの教科書でよく採用されている。どちらの理論も一長一短であり、ある意味では相補的でもある。

正確性を確保するため、DBMSは「直列化可能な」トランザクションスケジュールのみを保証するのが普通だが、アプリケーションが正確性をあまり求めていない場合のみ直列化可能性を意図的に緩和して性能を向上させることもある。トランザクションが失敗した場合の正確性を確保するには、スケジュールが回復可能性という属性を持つ必要がある。DBMSはまた、「コミット」されたトランザクションの結果が失われないことを保証し、「中断」（ロールバック）されたトランザクションの結果が関連するデータベースに残存しないことも保証する。トランザクション全体の特性は一般に後述するACID原則にまとめられる。データベースが分散されるか、分散環境で協調動作する必要がある場合（例えば、1990年代初めの連合データベースや21世紀のクラウドコンピューティング）、並行性制御機構の効果的分散に注目が集まる。

トランザクションとACID原則

詳細は「トランザクション」および「ACID (コンピュータ科学)」を参照

「データベース・トランザクション」（または「アトミック・トランザクション」）の概念は、衝突がいつでも発生しうる不完全な環境でのデータベースシステムの動作をよく理解し、その上で衝突から回復できるよう発展してきた。データベース・トランザクションは仕事の単位であり、データベース上のいくつかの操作（データベースオブジェクトの読み取り、書き込み、ロック取得など）をカプセル化するのが一般的で、データベースや他のシステムでの抽象概念である。個々のトランザクションは、どのプログラム/コードの実行がそのトランザクションに含まれているかで境界が明確に定義され、プログラマが特別なトランザクションコマンドを使って決定する。データベースシステムは全てのトランザクションが以下の原則に従うことを要求する。

原子性 (Atomicity)
操作は全体が行われるか全く行われないかのいずれかである。換言すればトランザクションは外から見て不可分に行われる。
一貫性 (Consistency)
全てのトランザクションはデータベースの一貫した状態を保つ。データベースについて事前に決定された完全性規則（データベースのオブジェクトについての制約）に従う。トランザクションは、データベースをある一貫した状態から別の一貫した状態へと遷移させる。データベースを変化させるのはトランザクションだけであり、データベースの状態は常に一貫している。途中で中断されたトランザクションは（原子性により）トランザクション開始前のデータベース状態を変更しない。
独立性 (Isolation)
トランザクション同士が互いに影響を与えることはできない。さらに言えば、中断されたトランザクションの効果は他のトランザクションから見えない。独立性を提供することが並行性制御の主な目的である。
永続性 (Durability)
コンピュータシステムがクラッシュしても成功したトランザクションの結果は失われない。一般に不揮発性メモリにトランザクションの効果とそのコミットというイベントを記録しておく。

アトミック・トランザクションの概念から、時間をかけてビジネストランザクション管理（英語版） (BTM) へと発展したが、BTMは実際にはワークフローの実装でありアトミックではない。しかし、そのように発展したトランザクションもコンポーネントとしてアトミック・トランザクションを利用している。

並行性制御機構

分類

並行性制御機構は以下のように大別される。

楽観的
操作が実際に行われるまでトランザクションの同期を遅延させる。衝突は起きないだろうと想定しているが、実際に操作するまでわからない。コミットによってACID原則を破る状態になるなら、トランザクションを中断させる。中断されたトランザクションは即座に再試行され、オーバーヘッドを生じる。中断されるトランザクションが少なければ、楽観的並行性制御はよい戦略である。
悲観的
最初からトランザクションが並行して実行されるもの見なして同期を行う。ブロックが発生する可能性はより高く想定され、予期されている。そのため、若干の性能低下が見込まれる。
準楽観的
楽観的と悲観的の中間であり、状況によって当初から同期する場合と遅延させる場合を使い分ける。

カテゴリが異なれば、性能も異なる。トランザクションの完了レート（スループット）は、トランザクションの種類の比率、計算の並列性レベルなどに左右される。トレードオフに関する知識が入手でき、選択が可能なら、最も性能が高くなる方式を選択すべきである。

2つ以上のトランザクションが互いにブロックしあう状況からデッドロックが生じ、関連するトランザクション群は処理を続行できなくなり、完了不可能となる。楽観的でない機構の多くはデッドロックを発生させる可能性があり、ストールしているトランザクションを意図的に中断させ、即座に再試行させることで問題を解決するしかない。一般にデッドロックはそう頻繁に発生するものではない。

ブロック、デッドロック、中断はいずれも性能を低下させるので、どのような並行性制御を選択するかはトレードオフの問題である。

技法

並行性制御には多数の技法が存在する。その多くは上述の分類のどれであっても実装可能である。主な技法[4]にはそれぞれ多数の派生があり、複数の技法を組み合わせたものもある。

ロック （例えば ツーフェーズロック - 2PL）
データに割り当てられたロックでそのデータへのアクセスを制御する。トランザクションはデータ（データベースオブジェクト）にアクセスする際にロックを獲得し、そのロックが解放されるまで他のトランザクションはブロックされる可能性がある（ブロックされるかどうかは、ロックの種類とアクセスの種類に依存する）。
相反グラフ（英語版）検査
スケジュールの有向グラフに閉路がないか調べ、あればトランザクションを中断することで閉路を断つ。
時刻印順序付け (Timestamp Ordering; TO)
時刻印をトランザクションに割り当て、時刻印の順序でデータへのアクセスを制御またはチェックする。
コミットメント順序付け (Commit ordering; CO)
トランザクションをコミット事象の順序で制御またはチェックする。

上掲の技法に加えて以下のような並行性制御技法も使われている。

多版型並行性制御 (MVCC)
データベースオブジェクトが更新される度に新たな版を生成することで並行性と性能の向上を図る。トランザクションのリード操作はスケジュール技法に従って、適切な版に対して行う。
索引並行性制御
ユーザーデータではなく索引へのアクセス操作を同期させる。性能向上策のひとつ。
個別作業空間モデル（遅延更新）
個々のトランザクションがデータアクセスのための個別の作業空間を持ち、更新したデータはトランザクションがコミットしたときのみ外界から見えるようになる[2]。このモデルは従来とは異なる並行性制御を提供し、多くの利点がある。

データベースシステムでの最も一般的な機構は1970年代以降「強く厳密な（厳格な）ツーフェーズロック」(SS2PL, Rigorous 2PL) であり、ツーフェーズロック (2PL) と コミットメント順序付け (CO) の特殊ケース（派生）である。悲観的機構に分類される。歴史的経緯から長い名前がついているが、機構は単純で「トランザクションが終わった後のみ、そのトランザクションが確保した全ロックを解放する」というものである。SS2PLはこの機構によって生成される全スケジュールも指し、SS2PLスケジュールはSS2PL属性を持つ。

目標

並行性制御は、個々のトランザクションが完全性規則に従うようにし、結果的にシステム全体が完全性を保つようにする。正確性を保つと同時に可能な限り性能を向上させることが目標である。プロセス群、コンピュータ群、コンピュータネットワーク群においてトランザクションが分散されることが多くなるにつれ、並行性制御の必要性は増大している。並行性制御は、データ復旧 (Data recovery) とレプリケーションにも影響を受ける。

正確性

直列化可能性
正確性を維持するため、並行性制御機構の多くは直列化可能性を備えたスケジュールを生成する。直列化可能性は独立性の最も高いレベルである。直列化可能性は、性能向上のため（例えば、スナップショット分離（英語版））や高度に分散されたシステムでの可用性向上のために緩和されることもあるが（結果整合性を参照）、それはその用途での正確さが緩和によって影響を受けない場合のみである（金融関係のトランザクションでは直列化可能性は緩和できない）。
回復可能性 (recoverability)
回復可能性とは、中断されたトランザクションが生じた場合に正確さを維持するスケジュールの属性である。回復可能性がある場合、中断されたトランザクションが更新したデータをコミットされたトランザクションが読み込んでいるということが発生しない。

分散正確性

ITの急激な進歩によってコンピュータネットワークの性能が向上し、ローカルな処理と分散処理の違いは曖昧になりつつある。そのためローカルな技法を極めて効率的に分散環境（例えば、コンピュータ・クラスターやマルチコアプロセッサ）に適用するのが一般的となっている。しかし、ローカルな技法には限界があり、分散のスケールが拡大すると対応できない。

分散直列可能性とコミットメント順序付け
データベースシステムを分散化したり、分散環境で協調動作する場合（例えば、1990年代初めの連合データベースや最近のグリッド・コンピューティング、クラウドコンピューティング、スマートフォンのネットワークなど）、トランザクションも分散化される。分散トランザクションは複数プロセスにまたがるトランザクションであり、さらにコンピュータ間や地理的に離れたサイト間をまたぐこともある。これを処理するには効率的な分散並行性制御機構を必要とする。分散システムのスケジュールで直列化可能性を効率的に達成するには、ローカルな運用を意図して設計された機構では不可能な工夫を必要とする（グローバル直列化可能性を参照）。これは主に、ネットワークやコンピュータによるレイテンシによって並行性制御情報の分散が高くつくことによる。唯一広く知られている分散技法はコミットメント順序付け (Commit ordering, CO) であり、特許取得後の1991年に公表された[5]。これは、トランザクションのコミットイベントを時系列に順序付けする技法である。COでは並行性制御情報を分散する必要がなく、信頼性/性能/スケーラビリティの観点で効率的な汎用技法となっており、異なる並行性制御機構を採用したシステムから成るヘテロジニアスな環境でも使用可能である[4]。COはコミットイベントの順序を決定するだけで、具体的な機構には関与しない。1991年に公表されるまで、そのような技法は存在しないと言われていたし、発表後も誤解する専門家が多く見られた。COの重要な副作用として、分散デッドロック状態の自動的な解消がある。コミットメント順序付けの結果生成されるスケジュールの属性もCOと呼ばれる。
先述したSS2PLはCOの派生（特殊ケース）と見ることもでき、効率的に分散またはグローバルな直列化可能性を達成することができる。COと同様に分散デッドロックを自動的に解消でき、同時に正確性と直列化可能性を備えている。このような好ましい特徴を持ち、よく知られたロック実装機構であることから、SS2PLは広く採用されている。SS2PLは1980年に登場して以来広く採用され、デファクトスタンダードとなっている。ただしSS2PLはブロックする性質のある悲観的機構であるため、制限がもっと緩いCO（楽観的CO）を使って性能向上を図る場合もある。
分散衝突状態の直列化可能性は、効率的かつ汎用的に対処するのが難しい。「分散CO」では、各ローカルコンポーネントが何らかのCOを持ち、全体を2相コミット (2CP) による投票戦略で制御する。各ローカルコンポーネントがSS2PLであれば、分散COの特殊ケースである「分散SS2PL」となる（この場合、2相コミットによらなくても自動的に投票戦略が実施される）。これはCOが知られていない1980年代から使われていた[6][7]。
参照とコミットの順序付けについてはCOの公表以前から研究されており[1]、COのスケジュール属性は "dynamic atomicity" と呼ばれていた[8]。COのアルゴリズムの正確な記述は1992年に公表された[5]（等価な概念である "dynamic atomicity" については1988年まで遡ることができる）。最近（2009年）ではCOは4つの主要な並行性制御技法の1つとされており、他の技法の相互運用を可能にするものとされている[4]。
分散回復可能性
分散回復可能性はコミットメント順序付けとよく似た直接的な方法で効率的に達成できる。各データベースはローカルに適用し、2相コミット (2PC) の戦略を採用する[9]。
分散正確性（回復可能性）と分散コミットメント順序付け（直列化可能性）を含む分散SS2PLは自動的に投票戦略を採用し、全てのローカルな並行性制御機構としてSS2PLを採用すれば、全体で分散SS2PLが実現する[5]。

他の観点

復旧
どんなシステムも障害はつきもので、障害発生時の復旧 (Data recovery) は必須である。並行性制御機構が生成するスケジュールの特性が復旧の容易さや効率に影響を与える可能性がある。例えば、厳格性は効率的復旧のために望ましい属性である。
レプリケーション
高可用データベースではオブジェクトは複製されることが多い。複製は必要なら同期して更新されなければならない。このために並行性制御が影響を受けることがある[10]。

OSにおける並行性制御

マルチタスクOS、特にリアルタイムOSは、動作中の全タスクが同時に動作しているかのように見せる必要があるが、ハードウェアの制限があるため実際にある時点で同時に動作しているタスクはごく少数である。マルチタスクは全タスクが互いに完全に独立しているなら単純である。しかし複数のタスクが同一資源を使用しようとした場合や、タスク間で情報を共有しようとした場合、混乱と矛盾をもたらすことがある。並行計算はこの問題を解決するためにある。データベースと同様にロックを使用する解法もあるが、その場合デッドロックなどの問題を引き起こす危険性も生じる。他にはブロックしないアルゴリズムもある。

参考文献

  • Bernstein, Philip A.; Hadzilacos, Vassos; Goodman, Nathan (1987) (PDF). Concurrency Control and Recovery in Database Systems. Addison Wesley Publishing Company. ISBN 0-201-10715-5. http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx 
  • Weikum, Gerhard; Vossen, Gottfried (2001). Transactional Information Systems. Elsevier. ISBN 1-55860-508-8. http://www.elsevier.com/wps/find/bookdescription.cws_home/677937/description#description 
  • Lynch, Nancy; Merritt, Michael; Weihl, William; Fekete, Alan (August 1993). Atomic Transactions in Concurrent and Distributed Systems. Elsevier: Morgan Kauffman. ISBN 978-1-55860-104-8. http://www.elsevier.com/wps/find/bookdescription.cws_home/680521/description#description 
  • Raz, Yoav (1992年). "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment". Proceedings of the Eighteenth International Conference on Very Large Data Bases. the Eighteenth International Conference on VLDB. Vancouver. pp. 292–312. 2007年5月23日時点のオリジナルよりアーカイブ。 (PDF), also DEC-TR 841, Digital Equipment Corporation, November 1990
  • Andrew S. Tanenbaum, Albert S Woodhull (2006): Operating Systems Design and Implementation, 3rd Edition, Prentice Hall, ISBN 0-13-142938-8
  • Silberschatz, Avi; Galvin, Peter; Gagne, Greg (2008). Operating Systems Concepts, 8th edition. John Wiley & Sons. ISBN 0-470-12872-0 
  • ミック (2010).「第2回　トランザクションを知ればデータベースがわかる―「データ復旧」「同時実行制御」を行う“不完全な”しくみ（3）」DEVELOPER STAGE. gihyo.jp

脚注

  1. ^ a b c Bernstein 1987
  2. ^ a b c Weikum & Vossen 2001
  3. ^ Lynch 1993
  4. ^ a b c Philip A. Bernstein, Eric Newcomer (2009): Principles of Transaction Processing, 2nd Edition, Morgan Kaufmann (Elsevier), June 2009, ISBN 978-1-55860-623-4 (page 145)
  5. ^ a b c Raz 1992
  6. ^ Raz 1992, p. 293
  7. ^ Bernstein 1987, p. 78
  8. ^ Lynch 1993, p. 201
  9. ^ Raz 1992, p. 307
  10. ^ Gray, J.; Helland, P.; O’Neil, P.; Shasha, D. (1996). "The dangers of replication and a solution" (PDF). Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. pp. 173–182. doi:10.1145/233269.233330。

関連項目

外部リンク

  • Portland Pattern Repository: Synchronization Strategies
  • Portland Pattern Repository: Category Concurrency
  • 表
  • 話
  • 編
  • 歴
概念
オブジェクト
SQL
  • SELECT
  • INSERT
  • UPDATE
  • MERGE
  • DELETE
  • JOIN
  • CREATE
  • DROP
  • COMMIT
  • ROLLBACK
  • TRUNCATE
  • ALTER
  • WHERE
  • SAVEPOINT
構成要素
データベース製品
関係データベース管理システムの比較
データベース接続クライアント
カテゴリ カテゴリ