Томас пишет правило

В информатике , особенно в области баз данных , правило записи Томаса является правилом управления параллелизмом на основе меток времени . Это можно резюмировать как игнорирование устаревших записей .

В нем говорится, что если более поздняя транзакция уже записала значение объекта, то менее поздней транзакции не нужно выполнять запись, поскольку более поздняя транзакция в конечном итоге перезапишет его.

Правило записи Томаса применяется в ситуациях, когда предопределенный логический транзакциям при их запуске назначается порядок. Например, транзакции может быть присвоена монотонно увеличивающаяся временная метка при ее создании. Правило не позволяет изменениям порядка выполнения транзакций создавать разные выходные данные: выходные данные всегда будут соответствовать предопределенному логическому порядку.

Например, рассмотрим базу данных с тремя переменными (A, B, C) и двумя атомарными операциями C := A (T1) и C := B (T2). Каждая транзакция включает в себя чтение (A или B) и запись (C). Единственным конфликтом между этими транзакциями является запись на C. Ниже приведен один из возможных графиков операций этих транзакций:

${\begin{bmatrix}T_{1}&T_{2}\\&Read(A)\\Read(B)&\\&Write(C)\\Write(C)&\\Commit&\\&Commit\end{bmatrix}}\Longleftrightarrow {\begin{bmatrix}T_{1}&T_{2}\\&Read(A)\\Read(B)&\\&Write(C)\\&\\Commit&\\&Commit\\\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), и отменяет запись. Если бы третья транзакция T3 (с TS(T3) > TS(T2)) затем выполнила запись в C, она получила бы TS(T3) > WTS(C), и запись была бы разрешена.

Ссылки

• Роберт Х. Томас (1979). «Консенсусный подход большинства к управлению параллелизмом для баз данных с несколькими копиями» . Транзакции ACM в системах баз данных . 4 (2): 180–209. дои : 10.1145/320071.320076 .

©