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

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

Операция

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

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

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

Существует ряд различных подходов, позволяющих генерировать временные метки.

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

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

Каждая транзакция ( ) представляет собой упорядоченный список действий ( ). Перед тем, как транзакция выполнит свое первое действие ( ), она помечается текущей временной меткой , или любой другой строго полностью упорядоченной последовательностью: . Каждой транзакции также дается изначально пустой набор транзакций, от которых она зависит, , и изначально пустой набор старых объектов, которые она обновила, . ${\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 RT(O_{j})}$— это временная метка последней транзакции, которая считывала значение объекта ( , где — последняя транзакция, которая считывала значение объекта). ${\displaystyle TS(T_{r})}$ ${\displaystyle T_{r}}$
• ${\displaystyle WT(O_{j})}$— это временная метка последней транзакции, обновившей значение объекта ( , где — последняя транзакция, обновившая значение объекта). ${\displaystyle TS(T_{w})}$ ${\displaystyle T_{w}}$

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

Для каждого действия : ${\displaystyle A_{ix}}$

Если вы хотите прочитать значение : ${\displaystyle A_{ix}}$ ${\displaystyle O_{j}}$

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

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

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

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

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

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

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

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

В противном случае: совершить .

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

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

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

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

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

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

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

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

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

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

Физически нереализуемо

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

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

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

Обратите внимание, что упорядочивание по временным меткам в его базовой форме не создает восстанавливаемых историй. Рассмотрим, например, следующую историю с транзакциями и : ${\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 миллисекунды, может быть присвоена одна и та же временная метка, даже если они произошли в разное время.

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

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

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

• Управление многоверсионным параллелизмом
• Временная метка (вычисления)