Правило записи Томаса - Thomas write rule - Wikipedia

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

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

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

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

Если (при создании транзакций) T1 назначается временная метка, которая предшествует T2 (т.е. в соответствии с логическим порядком, T1 идет первым), тогда должна быть видна только запись T2. Если, однако, запись T1 выполняется после записи T2, то нам нужен способ обнаружить это и отменить запись.

Один из практических подходов к этому - пометить каждое значение меткой времени записи (WTS), которая указывает метку времени последней транзакции для изменения значения. Применение правила записи Thomas требует только проверки, чтобы увидеть, больше ли метка времени записи объекта, чем метка времени транзакции, выполняющей запись. Если да, то запись отбрасывается.

В приведенном выше примере, если мы называем TS (T) отметкой времени транзакции T, а WTS (O) отметкой времени записи объекта O, то запись T2 устанавливает WTS (C) в TS (T2). Когда T1 пытается записать C, он видит, что TS (T1) TS (T2)) должна затем записать в C, она получит TS (T3)> WTS (C), и запись будет разрешена.

Рекомендации

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

©