トーマスの書き込みルール

コンピュータサイエンス、特にデータベース分野において、トーマス書き込みルールとは、タイムスタンプベースの同時実行制御におけるルールの一つです。これは「古い書き込みを無視する」と要約できます。

これは、より最近のトランザクションがすでにオブジェクトの値を書き込んでいる場合、より最近のトランザクションが最終的にそれを上書きするため、より最近のトランザクションは書き込みを実行する必要がないことを示しています。

トーマス書き込みルールは、トランザクションの開始時に事前定義された論理順序が割り当てられる状況に適用されます。例えば、トランザクションの作成時に単調に増加するタイムスタンプが割り当てられる場合があります。このルールは、トランザクションの実行順序の変更によって異なる出力が生成されることを防ぎます。出力は常に事前定義された論理順序と一致します。

例えば、3つの変数（A、B、C）と、2つのアトミック操作（C := A (T1)、C := B (T2)）を持つデータベースを考えてみましょう。各トランザクションには、読み取り（AまたはB）と書き込み（C）が含まれます。これらのトランザクション間の唯一の競合は、Cへの書き込みです。これらのトランザクションの操作スケジュールの一例を以下に示します。

${\displaystyle {\begin{bmatrix}T_{1}&T_{2}\\&読み取り(A)\\読み取り(B)&\\&書き込み(C)\\書き込み(C)&\\コミット&\\&コミット\end{bmatrix}}\Longleftrightarrow {\begin{bmatrix}T_{1}&T_{2}\\&読み取り(A)\\読み取り(B)&\\&書き込み(C)\\&\\コミット&\\&コミット\\\end{bmatrix}}}$

（トランザクション作成時に）T1にT2より前のタイムスタンプが割り当てられている場合（つまり、論理順序ではT1が先の場合）、T2の書き込みのみが可視となるはずです。しかし、T1の書き込みがT2の書き込みより後に実行される場合は、これを検出して書き込みを破棄する方法が必要です。

これに対する実用的なアプローチの一つは、各値に書き込みタイムスタンプ（WTS）を付与することです。これは、値を変更した最後のトランザクションのタイムスタンプを示します。トーマス書き込みルールを適用するには、オブジェクトの書き込みタイムスタンプが書き込みを実行するトランザクションのタイムスタンプよりも大きいかどうかを確認するだけで済みます。大きい場合、書き込みは破棄されます。

上記の例で、TS(T)をトランザクションTのタイムスタンプ、WTS(O)をオブジェクトOの書き込みタイムスタンプとすると、T2の書き込みによってWTS(C)がTS(T2)に設定されます。T1がCへの書き込みを試みると、TS(T1) < WTS(C) となり、書き込みは破棄されます。その後、3番目のトランザクションT3（TS(T3) > TS(T2)）がCへの書き込みを試みると、TS(T3) > WTS(C) となり、書き込みは許可されます。

参考文献

• ロバート・H・トーマス (1979). 「複数コピーデータベースの同時実行制御における多数決アプローチ」ACM Transactions on Database Systems . 4 (2): 180– 209. doi : 10.1145/320071.320076 .

©