Управление параллелизмом на основе временных меток - Timestamp-based concurrency control

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

Операция

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

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

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

Для создания отметки времени использовалось несколько различных способов.

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

Формальный

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

Каждый объект ${\displaystyle (O_{j})}$ в базе данных даны два поля меток времени, которые используются только для управления параллелизмом: ${\displaystyle RTS(O_{j})}$ время, когда значение объекта было в последний раз использовано транзакцией, ${\displaystyle WTS(O_{j})}$ - время последнего обновления значения объекта транзакцией.

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

За каждое действие ${\displaystyle A_{ix}}$:

Если ${\displaystyle A_{ix}}$ желает использовать ценность ${\displaystyle O_{j}}$:

Если ${\displaystyle WTS(O_{j})>TS(T_{i})}$ тогда прервать (более свежий поток перезаписал значение),

В противном случае обновите набор зависимостей ${\displaystyle DEP(T_{i}).\mathrm {add} (WTS(O_{j}))}$ и установить ${\displaystyle RTS(O_{j})=\max(RTS(O_{j}),TS(T_{i}))}$;

Если ${\displaystyle A_{ix}}$ желает обновить значение ${\displaystyle O_{j}}$:

Если ${\displaystyle RTS(O_{j})>TS(T_{i})}$ тогда прервать (более свежий поток уже полагается на старое значение),

Если ${\displaystyle WTS(O_{j})>TS(T_{i})}$ тогда пропускать (в Правило записи Томаса ),

В противном случае сохраните предыдущие значения, ${\displaystyle OLD(T_{i}).\mathrm {add} (O_{j},WTS(O_{j}))}$, набор ${\displaystyle WTS(O_{j})=TS(T_{i})}$, и обновите значение ${\displaystyle O_{j}}$.

Пока есть транзакция в ${\displaystyle DEP(T_{i})}$ что еще не закончилось: ждать

Если есть транзакция в ${\displaystyle DEP(T_{i})}$ это прервалось тогда прервать

Иначе: совершить.

К прервать:

Для каждого ${\displaystyle (\mathrm {old} O_{j},\mathrm {old} WTS(O_{j}))}$ в ${\displaystyle OLD(T_{i})}$

Если ${\displaystyle WTS(O_{j})}$ равно ${\displaystyle TS(T_{i})}$ затем восстановить ${\displaystyle O_{j}=\mathrm {old} O_{j}}$ и ${\displaystyle WTS(O_{j})=\mathrm {old} WTS(O_{j})}$

Неофициальный

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

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

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

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

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

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

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

Для объяснения терминов восстанавливаемый (RC), избегает каскадных прерываний (ACA) и строгий (ST), видеть Расписание (информатика).

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

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

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

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

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

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

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

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

Смотрите также

• Многовариантный контроль параллелизма
• Отметка времени (вычисления)