取引
トランザクションは、始まりと終わりがあるデータに対する一連の操作です。
トランザクションとは、読み取り操作と書き込み操作を順次実行することです。 トランザクションの終了は、変更を保存する (コミット) か、変更をキャンセルする (ロールバック) かのいずれかになります。 データベースに関しては、トランザクションは XNUMX つのリクエストとして扱われる複数のリクエストで構成されます。
トランザクションは ACID プロパティを満たす必要があります
原子性。 トランザクションは完全に完了するか、まったく完了しません。
一貫性。 トランザクションを完了するときは、データに課せられた制限 (データベース内の制約など) に違反してはなりません。 一貫性とは、システムがある正しい状態から別の正しい状態に移行することを意味します。
分離。 並行して実行されるトランザクションは、たとえば、別のトランザクションで使用されるデータを変更するなど、相互に影響を及ぼしてはいけません。 並列トランザクションを実行した結果は、トランザクションが順次実行された場合と同じになるはずです。
持続可能性。 一度コミットされた変更は失われるべきではありません。
トランザクションログ
ログにはトランザクションによって行われた変更が保存され、システム障害が発生した場合でもデータのアトミック性と安定性が確保されます。
ログには、トランザクションによって変更される前後のデータの値が含まれます。 先行書き込みログ戦略では、開始前の以前の値に関するログ エントリと、トランザクション完了後の最終値に関するログ エントリを追加する必要があります。 システムが突然停止した場合、データベースは逆の順序でログを読み取り、トランザクションによって加えられた変更をキャンセルします。 中断されたトランザクションが発生すると、データベースはそれを実行し、それに関する変更をログに加えます。 障害発生時の状態では、データベースはログを順方向に読み取り、トランザクションによって加えられた変更を返します。 このようにして、すでにコミットされたトランザクションの安定性と、中断されたトランザクションのアトミック性が維持されます。
失敗したトランザクションを再実行するだけでは回復には不十分です。
例：ユーザーのアカウント 500$ 利用者はATMから現金を引き出すことにしました。2つの取引が行われます。1つ目は残高を読み取り、十分な残高があれば利用者に現金を払い出します。2つ目は残高から必要な金額を差し引きます。仮にシステム障害が発生し、1つ目の操作は失敗したが、2つ目の操作は成功したとします。この場合、システムを残高がプラスの初期状態に復元しない限り、利用者に再度現金を払い出すことはできません。
断熱レベル
コミットされた読み取り
ダーティ リードの問題は、トランザクションが別のトランザクションの中間結果を読み取ることができることです。
例。 初期残高値は $0 です。 T1 では残高に $50 が追加されます。 T2 は残高値 ($50) を読み取ります。 T1 は変更を破棄して終了します。 T2 は、不正な残高データを使用して実行を続行します。
解決策は、トランザクションによって変更されたデータの読み取りを禁止する固定データ (Read Committed) を読み取ることです。 トランザクション A が特定のデータ セットを変更した場合、トランザクション B はこのデータにアクセスするときに、トランザクション A が完了するまで待機する必要があります。
反復可能な読み取り
アップデートが失われる問題。 T1 は、T2 の変更に加えて変更を保存します。
例。 初期残高値は $0 で、1 つのトランザクションで同時に残高が補充されます。 T2 と T0 は残高 $2 を読み取ります。 次に、T200 は $0 に $1 を加算し、結果を保存します。 T100 は $0 に $100 を加算し、結果を保存します。 最終結果は 300 ドルではなく XNUMX ドルになります。
再現不可能な読み取りの問題。 同じデータを繰り返し読み取ると、異なる値が返されます。
例。 T1 は残高値 $0 を読み取ります。 その後、T2 は残高に $50 を追加して終了します。 T1 はデータを再度読み取り、前の結果との不一致を見つけます。
反復読み取りでは、XNUMX 回目の読み取りでも同じ結果が返されます。 あるトランザクションで読み取られたデータは、トランザクションが完了するまで他のトランザクションで変更することはできません。 トランザクション A が特定のデータ セットを読み取った場合、トランザクション B はこのデータにアクセスするときに、トランザクション A が完了するまで待機する必要があります。
順序付けされた読み取り (シリアル化可能)
ファントム読み取りの問題。 特定の条件に基づいてデータを選択する XNUMX つのクエリは、異なる値を返します。
例。 T1 は、残高が 0 ドルより大きく 100 ドル未満であるすべてのユーザーの数を要求します。 T2 は、残高が 1 ドルのユーザーから 101 ドルを差し引きます。 T1 はリクエストを再発行します。
順序付けされた読み取り (シリアル化可能)。 トランザクションは完全にシーケンシャルに実行されます。 リクエストの条件に該当する記録を更新または追加することは禁止されています。 トランザクション A がテーブル全体のデータを要求した場合、トランザクション A が完了するまで、テーブル全体が他のトランザクションのために凍結されます。
スケジューラ
並列トランザクション中に操作を実行する順序を設定します。
指定されたレベルの分離を提供します。 演算の結果が順序に依存しない場合、そのような演算は可換 (Permutable) です。 読み取り操作と異なるデータに対する操作は可換です。 読み取り-書き込み操作と書き込み-書き込み操作は交換的ではありません。 スケジューラのタスクは、実行結果がトランザクションの順次実行と同等になるように、並列トランザクションによって実行される操作をインターリーブすることです。
並列ジョブを制御する仕組み（同時実行制御）
楽観主義は競合の検出と解決に基づいており、悲観主義は競合の発生を防ぐことに基づいています。
楽観的なアプローチでは、複数のユーザーがデータのコピーを自由に使えるようになります。 最初に編集を完了した人が変更を保存し、他の人は変更をマージする必要があります。 楽観的なアルゴリズムでは競合が発生する可能性がありますが、システムは競合から回復する必要があります。
悲観的なアプローチでは、最初にデータを取得したユーザーが、他のユーザーがデータを受信できないようにします。 競合がほとんどない場合は、より高いレベルの同時実行性が提供されるため、楽観的な戦略を選択することが賢明です。
ロック
XNUMX つのトランザクションがデータをロックしている場合、他のトランザクションはデータにアクセスするときにロックが解除されるまで待機する必要があります。
ブロックは、データベース、テーブル、行、または属性にオーバーレイできます。 共有ロックは、複数のトランザクションによって同じデータに課すことができ、すべてのトランザクション (課したトランザクションを含む) の読み取りを許可し、変更と排他的キャプチャを禁止します。 排他的ロックは XNUMX つのトランザクションによってのみ課せられ、課せられたトランザクションのすべてのアクションを許可し、他のトランザクションによるすべてのアクションを禁止します。
デッドロックとは、トランザクションが無期限に続く保留状態になる状況です。
例。 最初のトランザクションは、XNUMX 番目のトランザクションによってキャプチャされたデータがリリースされるのを待ち、XNUMX 番目のトランザクションは、最初のトランザクションによってキャプチャされたデータがリリースされるのを待ちます。
デッドロック問題に対する楽観的な解決策では、デッドロックの発生は許容されますが、デッドロックに関係するトランザクションの XNUMX つをロールバックすることでシステムを回復します。
デッドロックは一定の間隔で検索されます。 検出方法の XNUMX つは時間によるものです。つまり、トランザクションの完了に時間がかかりすぎる場合にデッドロックが発生したとみなします。 デッドロックが見つかると、トランザクションの XNUMX つがロールバックされ、デッドロックに関係する他のトランザクションが完了できるようになります。 被害者の選択は、トランザクションの価値または年功序列 (Wait-Die および Wound-wait スキーム) に基づいて行うことができます。
すべてのトランザクション T タイムスタンプが割り当てられる TS トランザクションの開始時刻が含まれます。
待って、死ね。
もし TS(ティ) < TS(Tj)その後 Ti 待つ、そうでない場合 Ti ロールバックして、同じタイムスタンプで再度開始します。
若いトランザクションがリソースを取得し、古いトランザクションが同じリソースを要求した場合、古いトランザクションは待機することができます。 古いトランザクションがリソースを取得した場合、そのリソースを要求している若いトランザクションはロールバックされます。
傷、待ってください。
もし TS(ティ) < TS(Tj)その後 Tj それ以外の場合は、ロールバックして同じタイムスタンプで再度開始します。 Ti 待っている。
若いトランザクションがリソースを取得し、古いトランザクションが同じリソースを要求した場合、若いトランザクションはロールバックされます。 古いトランザクションがリソースを取得した場合、そのリソースを要求している新しいトランザクションは待機することができます。 優先順位に基づいた犠牲者の選択によりデッドロックは防止されますが、デッドロックになっていないトランザクションはロールバックされます。 問題は、トランザクションが何度もロールバックされる可能性があることです。 古いトランザクションはリソースを長期間保持する可能性があります。
デッドロック問題に対する悲観的な解決策では、デッドロックのリスクがある場合、トランザクションの実行を開始できません。
デッドロックを検出するには、トランザクションを頂点とするグラフ (待機グラフ、待機グラフ) が構築され、辺はデータの解放を待機しているトランザクションから、このデータをキャプチャしたトランザクションに向けられます。 グラフにループがある場合、デッドロックが発生したと見なされます。 待機グラフの構築は、特に分散データベースにおいては、費用のかかる手順です。
XNUMX フェーズ ロック - トランザクションが使用するすべてのリソースをトランザクションの開始時に捕捉し、終了時に解放することでデッドロックを防止します。
すべてのブロック操作は、最初のロック解除操作よりも前に行う必要があります。 これには、グリップが蓄積する成長フェーズと、グリップが解放される縮小フェーズの XNUMX つのフェーズがあります。 いずれかのリソースを取得できない場合、トランザクションは最初からやり直します。 たとえば、複数のトランザクションが同じリソースをめぐって競合した場合、トランザクションが必要なリソースを取得できない可能性があります。
XNUMX フェーズ コミットでは、すべてのデータベース レプリカでコミットが確実に実行されます。
各データベースは変更するデータを記録し、コーディネータにOK（投票フェーズ）で応答します。全員がOKを応答すると、コーディネータは全員にコミットを要求する信号を送信します。コミット後、 サーバー 少なくとも 1 つのサーバーが OK と応答しない場合、コーディネータはすべてのサーバーに変更をキャンセルする信号を送信します (完了フェーズ)。
タイムスタンプ方式
若いトランザクションに関係するデータにアクセスしようとすると、古いトランザクションがロールバックされる
各トランザクションにはタイムスタンプが割り当てられます TS 実行の開始時刻に対応します。 もし Ti 年上 Tjその後 TS(ティ) < TS(Tj).
トランザクションがロールバックされると、新しいタイムスタンプが割り当てられます。 各データオブジェクト Q トランザクションに関係するものには XNUMX つのラベルが付けられます。 W-TS(Q) — レコードを正常に完了した最も若いトランザクションのタイムスタンプ Q. R-TS(Q) — レコードの読み取りを実行した最も新しいトランザクションのタイムスタンプ Q.
取引時 T データの読み取りリクエスト Q 選択肢は XNUMX つあります。
もし TS(T) < W-TS(Q)つまり、データはより若いトランザクションによって更新され、その後トランザクションが更新されました。 T ロールバックします。
もし TS(T) >= W-TS(Q)、その後、読み取りが実行され、 R-TS(Q) されている MAX(R-TS(Q)、TS(T)).
取引時 T データ変更を要求する Q 選択肢は XNUMX つあります。
もし TS(T) < R-TS(Q)つまり、データはすでに若いトランザクションによって読み取られており、変更が加えられると競合が発生します。 取引 T ロールバックします。
もし TS(T) < W-TS(Q)つまり、トランザクションが新しい値を上書きしようとすると、トランザクション T はロールバックされます。 それ以外の場合は変更が行われ、 W-TS(Q) 等しくなる TS(T).
高価な待機グラフの構築は必要ありません。 古いトランザクションは新しいトランザクションに依存しているため、待機グラフにはサイクルがありません。 トランザクションは待機せず、すぐにロールバックされるため、デッドロックは発生しません。 カスケードロールバックが可能です。 もし Ti 転がり落ちて Tj 変更したデータを読みました Tiその後 Tj もロールバックする必要があります。 同時になら Tj すでにコミットされている場合、安定性の原則に違反することになります。
カスケード ロールバックに対するソリューションの XNUMX つ。 トランザクションは最後にすべての書き込み操作を完了しますが、他のトランザクションはその操作が完了するまで待つ必要があります。 トランザクションはコミットされるまで待機してから読み取られます。
Thomas write ルール - タイムスタンプ方式のバリエーションで、新しいトランザクションによって更新されたデータが古いトランザクションによって上書きされることを禁止します。
トランザクション T データ変更を要求する Q。 もし TS(T) < W-TS(Q)つまり、トランザクションが新しい値を上書きしようとすると、トランザクション T はタイムスタンプ方式のようにロールバックされません。
出所： habr.com
