Loading article…
マルチバージョン並行性制御（MCCまたはMVCC）は、データベース管理システムでデータベースへの同時アクセスを提供するため、またプログラミング言語でトランザクションメモリを実装するために一般的に使用される、ロックを使用しない並行性制御方法です。[ 1 ]
並行性制御がない場合、誰かがデータベースから読み取っているのと同時に別の誰かがデータベースに書き込んでいると、読み手は書き込み途中のデータや矛盾したデータを見る可能性があります。たとえば、 2つの銀行口座間で電信送金を行う場合、元の口座からお金が引き出され、宛先の口座に入金される前に、読み手が銀行の残高を読み取ると、お金が銀行から消えたように見えます。分離性とは、データへの同時アクセスを保証する特性です。分離性は、並行性制御プロトコルによって実装されます。最も簡単な方法は、書き込みが完了するまですべての読み手を待たせることであり、これは読み書きロックとして知られています。ロックは、特に長時間の読み取りトランザクションと更新トランザクションの間で競合を引き起こすことが知られています。MVCCは、各データ項目の複数のコピーを保持することでこの問題を解決することを目的としています。このようにして、データベースに接続している各ユーザーは、特定の時点でのデータベースのスナップショットを見ることができます。書き込み者が行った変更は、変更が完了するまで（データベース用語で言えば、トランザクションがコミットされるまで）、データベースの他のユーザーには表示されません。
MVCCデータベースがデータを更新する必要がある場合、元のデータ項目を新しいデータで上書きするのではなく、データ項目の新しいバージョンを作成します。そのため、複数のバージョンが保存されます。各トランザクションが参照するバージョンは、実装されている分離レベルによって異なります。MVCCで実装される最も一般的な分離レベルはスナップショット分離です。スナップショット分離では、トランザクションはトランザクション開始時点のデータの状態を参照します。
MVCCは、時点整合性のあるビューを提供します。MVCCにおける読み取りトランザクションは通常、タイムスタンプまたはトランザクションIDを使用して、読み取るデータベースの状態を決定し、これらのバージョンのデータを読み取ります。そのため、読み取りトランザクションと書き込みトランザクションはロックを必要とせずに互いに分離されます。ただし、ロックは不要であるにもかかわらず、Oracleなどの一部のMVCCデータベースではロックが使用されています。書き込みは新しいバージョンを作成し、同時読み取りは古いバージョンにアクセスします。
MVCC では、古くなって二度と読まれなくなるバージョンを削除する方法という課題が生じます。場合によっては、古くなったバージョンを定期的にスキャンして削除するプロセスが実装されます。これは多くの場合、テーブル全体を走査して各データ項目の最新バージョンで書き換える、ストップ ザ ワールド プロセスです。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は、真のスナップショット分離を実現することに特に優れており、他の並行性制御手法では、不完全にしか実現できなかったり、パフォーマンスに大きなコストがかかったりすることがよくあります。
Rustでは、MVCCを使用したデータベースのレコード（行）を保持する構造は次のようになります。
struct Record { /// トランザクション識別子のスタンプを挿入します。insert_transaction_id : u32 ,/// トランザクション識別子のスタンプを削除します。delete_transaction_id : u32 、/// データの長さ。data_length : u16 、/// レコードの内容。data : Vec < u8 > , }時刻 1 におけるデータベースの状態は次のようになる可能性がある。
T0はオブジェクト1に「Foo」、オブジェクト2に「Bar」を書き込みました。その後、T1はオブジェクト1に「Hello」を書き込み、オブジェクト2は元の値のままにしました。オブジェクト1の新しい値は、T1がコミットした後に開始されるすべてのトランザクションにおいて、0の値に上書きされます。この時点で、オブジェクト1のバージョン0はガベージコレクションの対象となります。
長時間実行されるトランザクション T2 が、T1 がコミットされた後にオブジェクト 2 とオブジェクト 1 の読み取り操作を開始し、同時に更新トランザクション T3 がオブジェクト 2 を削除してオブジェクト 3="Foo-Bar" を追加する場合、時刻 2 におけるデータベースの状態は次のようになります。
時刻2時点で、オブジェクト2の新しいバージョンが存在し、これは削除済みとしてマークされています。また、新しいオブジェクト3も存在します。T2とT3は同時に実行されるため、T2は時刻2より前のデータベースバージョン、つまりT3が書き込みをコミットする前のバージョンを参照します。そのため、T2はオブジェクト2="Bar"とオブジェクト1="Hello"を読み取ります。このようにして、マルチバージョン同時実行制御は、ロックなしでスナップショット分離読み取りを可能にします。
マルチバージョン並行性制御は、当時コンピュータ・コーポレーション・オブ・アメリカに勤務していたフィル・バーンスタインとネイサン・グッドマンによる1981年の論文「分散データベースシステムにおける並行性制御」[ 3 ]で詳細に説明されている。バーンスタインとグッドマンの論文は、MVCCを非常に明確に説明し、それを独自の研究であると主張するデビッド・P・リードによる1978年の博士論文[ 4 ]を引用している。
MVCCを搭載した最初の商用データベースソフトウェア製品は、1984年にリリースされたVAX Rdb/ELNでした[ 5 ]。これは、Digital Equipment CorporationのJim Starkeyによって開発されました。Starkeyはその後[ 6 ]、 2番目に商業的に成功したMVCCデータベースであるInterBaseを開発しました[ 7 ]。