Управление параллелизмом на основе временных меток

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

Операция

Предположения

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

Создание временной метки

Несколько различных подходов могут генерировать временные метки.

Использование значения системных часов в начале транзакции в качестве отметки времени.
Использование поточно-ориентированного общего счетчика, который увеличивается в начале транзакции в качестве отметки времени.
Комбинация двух вышеуказанных методов.

Формальное определение

Каждая транзакция ( $T_{i}$ ) представляет собой упорядоченный список действий ( $A_{ix}$ ). Прежде чем транзакция выполнит свое первое действие ( $A_{i1}$ ), он отмечен текущей временной меткой или любой другой строго упорядоченной последовательностью: $TS(T_{i})=NOW()$ . Каждой транзакции также дается изначально пустой набор транзакций, от которых она зависит. $DEP(T_{i})=[]$ и изначально пустой набор старых объектов, которые он обновил, $OLD(T_{i})=[]$ .

Каждый объект $(O_{j})$ в базе данных есть два поля временных меток, которые используются только для управления параллелизмом:

$RT(O_{j})$ — это временная метка последней транзакции, которая прочитала значение объекта ( $TS(T_{r})$ , где $T_{r}$ — последняя транзакция, считывающая значение объекта).
$WT(O_{j})$ — это временная метка последней транзакции, обновившей значение объекта ( $TS(T_{w})$ , где $T_{w}$ — последняя транзакция, обновившая значение объекта).

Для всех $T_{i}$ :

За каждое действие

A_{ix}

:

Если

A_{ix}

хочет прочитать значение

O_{j}

:

Если

WT(O_{j})>TS(T_{i})

затем прервать (более поздний поток перезаписал значение),

В противном случае обновите набор зависимостей.

DEP(T_{i}).\mathrm {add} (WT(O_{j}))

и установить

RT(O_{j})=\max(RT(O_{j}),TS(T_{i}))

;

Если

A_{ix}

желает обновить значение

O_{j}

:

Если

RT(O_{j})>TS(T_{i})

затем прервать (более новый поток уже использует старое значение),

Если

WT(O_{j})>TS(T_{i})

затем пропустите ( Правило записи Томаса ),

В противном случае сохраните предыдущие значения,

OLD(T_{i}).\mathrm {add} (O_{j},WT(O_{j}))

, набор

WT(O_{j})=TS(T_{i})

и обновите значение

O_{j}

.

Пока есть транзакция в

DEP(T_{i})

это еще не закончилось: подожди

Если есть транзакция в

DEP(T_{i})

это прервано, тогда прервись

В противном случае: зафиксируйте .

Чтобы прервать :

Для каждого

(\mathrm {old} O_{j},\mathrm {old} WT(O_{j}))

в

OLD(T_{i})

Если

WT(O_{j})

равно

TS(T_{i})

затем восстановить

O_{j}=\mathrm {old} O_{j}

и

WT(O_{j})=\mathrm {old} WT(O_{j})

Неформальное определение

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

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

Если транзакция хочет прочитать объект,

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

Если транзакция хочет записать объект,

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

Физически неосуществимо

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

Транзакция T пытается прочитать X, но TS(T) < WT(X). Причина: Это означает, что X был записан другой транзакцией после начала T.
Транзакция T пытается записать X, но TS(T) < RT(X). Причина: Это означает, что более поздняя транзакция прочитала X до того, как он был записан T.

Возможность восстановления

Обратите внимание, что упорядочение временных меток в своей базовой форме не создает восстанавливаемую историю. Рассмотрим, например, следующую историю транзакций $T_{1}$ и $T_{2}$ :

W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}

Это может быть создано планировщиком TO, но не подлежит восстановлению, так как $T_{2}$ фиксирует, даже если прочитал незафиксированную транзакцию. Чтобы гарантировать создание восстанавливаемой истории, планировщик может хранить список других транзакций, из которых прочитала каждая транзакция , и не допускать фиксации транзакции до тех пор, пока этот список не будет состоять только из зафиксированных транзакций. Чтобы избежать каскадных прерываний, планировщик может помечать данные, записанные незафиксированными транзакциями, как «грязные» и никогда не позволять операции чтения начинаться с таким элементом данных до тех пор, пока он не будет помечен. Чтобы получить строгую историю, планировщик не должен допускать никаких операций с «грязными» элементами.

Проблемы реализации

Разрешение временной метки

Это минимальное время, прошедшее между двумя соседними метками времени. Если разрешение временной метки слишком велико (грубое), вероятность равенства двух или более временных меток увеличивается, что позволяет некоторым транзакциям фиксироваться в неправильном порядке. Например, для системы, которая создает сто уникальных меток времени в секунду, двум событиям, которые происходят с интервалом в 2 миллисекунды, может быть присвоена одна и та же метка времени, даже если они произошли в разное время.

Блокировка временной метки

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

См. также