多版型同時実行制御
多版型同時実行制御（MCCまたはMVCC）は、データベース管理システムでデータベースへの同時アクセスを提供するために、またプログラミング言語でトランザクションメモリを実装するために一般的に使用される、ロックなしの同時実行制御方法です。[ 1 ]
説明
同時実行制御がない場合、誰かがデータベースから読み取りを行っていると同時に、別の誰かがデータベースに書き込みを行っている場合、読み取り側は書き込み途中のデータや矛盾したデータを見る可能性があります。例えば、 2つの銀行口座間で電信送金を行う際、元の口座からお金が引き出され、振込先の口座に入金される前に、読み取り側が銀行の残高を読み取ると、銀行からお金が消えたように見えます。分離とは、データへの同時アクセスを保証する特性です。分離は、同時実行制御プロトコルによって実装されます。最も簡単な方法は、すべての読み取り側を書き込み側が完了するまで待機させることです。これは読み取り/書き込みロックと呼ばれます。ロックは、特に長時間の読み取りトランザクションと更新トランザクション間で競合を引き起こすことが知られています。MVCCは、各データ項目の複数のコピーを保持することでこの問題を解決することを目的としています。このように、データベースに接続している各ユーザーは、特定の瞬間におけるデータベースのスナップショットを見ることができます書き込み者によって行われた変更は、変更が完了するまで (または、データベース用語では、トランザクションがコミットされるまで)、 データベースの他のユーザーには表示されません。
MVCCデータベースは、データの更新が必要な場合、元のデータ項目を新しいデータで上書きするのではなく、新しいバージョンのデータ項目を作成します。そのため、複数のバージョンが保存されます。各トランザクションが参照するバージョンは、実装されている分離レベルによって異なります。MVCCで実装される最も一般的な分離レベルは、スナップショット分離です。スナップショット分離では、トランザクションは開始時点のデータの状態を参照します。
MVCCは、ある時点における一貫性のあるビューを提供します。MVCCにおける読み取りトランザクションは通常、タイムスタンプまたはトランザクションIDを使用してDBのどの状態を読み取るかを判断し、それらのバージョンのデータを読み取ります。このように、読み取りトランザクションと書き込みトランザクションは互いに分離されており、ロックは必要ありません。ただし、ロックは不要であるにもかかわらず、Oracleなどの一部のMVCCデータベースではロックが使用されます。書き込みは新しいバージョンを作成し、同時読み取りは古いバージョンにアクセスします。
MVCC では、古くなって読み込まれなくなるバージョンをどのように削除するかという課題が生じます。場合によっては、古くなったバージョンを定期的にスキャンして削除するプロセスが実装されます。これは多くの場合、テーブル全体を走査し、各データ項目の最新バージョンで書き換える stop-the-world プロセスです。PostgreSQLは、VACUUM FREEZEプロセスでこのアプローチを採用しています。他のデータベースでは、ストレージブロックをデータ部分と UNDO ログの 2 つの部分に分割しています。データ部分は常に最後にコミットされたバージョンを保持します。UNDO ログは、データの古いバージョンを再作成することを可能にします。この後者のアプローチの主な固有の制限は、更新集中型のワークロードが発生すると UNDO ログ部分のスペースが不足し、スナップショットを取得できないためトランザクションが中止されることです。ドキュメント指向データベースでは、ドキュメント全体をディスクの連続したセクションに書き込むことで、システムがドキュメントを最適化することも可能になります。つまり、更新時にドキュメント全体を書き換えることができるため、断片的なデータを切り取ったり、リンクされた非連続なデータベース構造で維持したりする必要はありません。
実装
MVCCは、タイムスタンプ（TS）と増分トランザクションIDを使用して、トランザクションの一貫性を実現します。MVCCは、オブジェクトの複数のバージョンを維持することで、トランザクション（T ）がデータベースオブジェクト（P ）の読み取りを待機する必要がないようにしています。オブジェクトPの各バージョンには、読み取りタイムスタンプ（RTS）と書き込みタイムスタンプ（WTS ）の両方があり、特定のトランザクションT iは、そのトランザクションの読み取りタイムスタンプRTS（T i） に先行するオブジェクトの最新バージョンを読み取ることができます
トランザクションT iがオブジェクトPに書き込みを実行しようとしており、同じオブジェクトに対して別のトランザクションT kも実行されている場合、オブジェクトの書き込み操作( WTS ) が成功するには、読み取りタイムスタンプRTS ( T i ) が読み取りタイムスタンプRTS ( T k ) より前である必要があります (つまり、RTS ( T i ) < RTS ( T k ) )。同じオブジェクトに対して、読み取りタイムスタンプ ( RTS )が先行する他の未処理のトランザクションがある場合、書き込みは完了しません。店舗で列に並んでいる人と同じように、前の人がレジのトランザクションを完了するまで、前の人がレジのトランザクションを完了することはできません。
言い換えると、すべてのオブジェクト（P）にはタイムスタンプ（TS）がありますが、トランザクションT iがオブジェクトに書き込みを行おうとし、そのトランザクションのタイムスタンプ（TS）がオブジェクトの現在の読み取りタイムスタンプよりも前の場合（TS（T i）< RTS（P）、）、トランザクションは中止され、再開されます。（これは、後のトランザクションが既に古い値に依存しているためです。）それ以外の場合、T iはオブジェクトPの新しいバージョンを作成し、新しいバージョンの読み取り/書き込みタイムスタンプTSをトランザクションTS ← TS（T i）のタイムスタンプに設定します。[ 2 ]
このシステムの欠点は、データベースにオブジェクトの複数のバージョンを保存するコストです。一方で、読み取りはブロックされないため、データベースからの値の読み取りが主なワークロードでは重要です。MVCCは真のスナップショット分離の実装に特に優れています。これは、他の同時実行制御手法では不完全であったり、パフォーマンスコストが高かったりすることが多いものです。
MVCC を使用してデータベースのレコード (行) を保持する構造は、 Rustでは次のようになります。
struct Record { /// トランザクション識別子スタンプを挿入します。insert_transaction_id : u32 ,/// トランザクション識別子スタンプを削除します。delete_transaction_id : u32 ,/// データの長さ。data_length : u16 ,///レコードの内容。data : Vec < u8 > , }| オフセット | オクテット | 0 | 1 | 2 | 3 | ||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| オクテット | ビット | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| 0 | 0 | 取引識別子を挿入 | |||||||||||||||||||||||||||||||
| 4 | 32 | 取引識別子を削除 | |||||||||||||||||||||||||||||||
| 8 | 64 | データ長 | |||||||||||||||||||||||||||||||
| 10 | 80 | データ… | |||||||||||||||||||||||||||||||
| 14 | 112 | ||||||||||||||||||||||||||||||||
| ⋮ | ⋮ | ||||||||||||||||||||||||||||||||
- 挿入トランザクション識別子：32ビット
- 挿入用のMVCCトランザクション識別子
- 削除トランザクション識別子: 32 ビット
- 削除の MVCC トランザクション ID。
- データ長: 16ビット
- データの長さ。
- データ: 変数
- レコードに保存されるコンテンツ。
例
同時読み取り・書き込み
時刻 = 1 におけるデータベースの状態は次のようになります
| 時間 | オブジェクト1 | オブジェクト2 |
|---|---|---|
| 0 | T0による「Foo」 | T0による「Bar」 |
| 1 | T1による「Hello」 |
T0はオブジェクト1="Foo"、オブジェクト2="Bar"と書き込みました。その後、T1はオブジェクト1="Hello"と書き込み、オブジェクト2は元の値のままになりました。オブジェクト1の新しい値は、T1のコミット後に開始されるすべてのトランザクションで0の値を置き換えます。この時点で、オブジェクト1のバージョン0はガベージコレクションの対象となります
長時間実行トランザクション T2 が、T1 がコミットされた後にオブジェクト 2 とオブジェクト 1 の読み取り操作を開始し、同時に更新トランザクション T3 がオブジェクト 2 を削除してオブジェクト 3="Foo-Bar" を追加する場合、データベースの状態は時刻 2 で次のようになります。
| 時間 | オブジェクト1 | オブジェクト2 | オブジェクト3 |
|---|---|---|---|
| 0 | T0による「Foo」 | T0による「バー」 | |
| 1 | T1による「Hello」 | ||
| 2 | T3による（削除） | T3による「Foo-Bar」 |
時刻2の時点で、オブジェクト2の新しいバージョン（削除済みとしてマークされています）と新しいオブジェクト3があります。T2とT3は同時に実行されるため、T2はT3が書き込みをコミットする前のデータベースのバージョンを参照します。そのため、T2はオブジェクト2 = "Bar"、オブジェクト1 = "Hello"を読み取ります。このようにして、多版型同時実行制御はロックなしでスナップショット分離読み取りを可能にします
歴史
多版型同時実行制御（MVCC）は、当時コンピュータ・コーポレーション・オブ・アメリカに勤務していたフィル・バーンスタインとネイサン・グッドマンによる1981年の論文「分散データベースシステムにおける同時実行制御」[ 3 ]で詳細に説明されています。バーンスタインとグッドマンの論文は、デビッド・P・リードによる1978年の論文[ 4 ]を引用しており、MVCCについて非常に明確に説明し、独自の研究であると主張しています
MVCCを搭載した最初の商用データベースソフトウェア製品は、1984年にリリースされたVAX Rdb/ELN [ 5 ]であり、Digital Equipment CorporationのJim Starkeyによって開発されました。Starkeyは[ 6 ]、 2番目に商業的に成功したMVCCデータベースであるInterBaseを開発しました。[ 7 ]
参照
参考文献
- ^ 「Clojure - 参照とトランザクション」 . clojure.org . 2019年4月12日閲覧
- ^ Ramakrishnan、R.、Gehrke、J. (2000)。データベース管理システム。オズボーン/マグロウヒル。
- ^ Bernstein, Philip A. ; Goodman, Nathan (1981). 「分散データベースシステムにおける同時実行制御」 . ACM Computing Surveys . 13 (2): 185– 221. doi : 10.1145/356842.356846 .
- ^ Reed, DP (1978).分散型コンピュータシステムにおける命名と同期. MIT学位論文. hdl : 1721.1/16279 . 2022年11月12日閲覧。
- ^ Gallant, John (1984年4月9日). 「RDBは賛否両論」 . Computerworld . 2021年9月13日閲覧。
- ^ 「Re: [Firebird-devel] isc_dpb_dbkey_scope | Firebird」 .
- ^ 「マルチバージョン同時実行制御に関するそれほど技術的ではない議論」 . firebirdsql.org . 2020年11月12日閲覧。
さらに詳しい参考文献
- ゲルハルト・ヴァイクム、ゴットフリート・フォッセン著、『トランザクショナル情報システム：同時実行制御と回復の理論、アルゴリズム、実践』、モーガン・カウフマン、2002年、ISBN 1-55860-508-8
