В информатике , управление параллелизмом метка времени на основе алгоритма является управление параллелизмом без блокировки метод. Он используется в некоторых базах данных для безопасной обработки транзакций с использованием временных меток .
Операция
Предположения
- Каждое значение временной метки уникально и точно представляет момент времени.
- Две одинаковые отметки времени не могут быть одинаковыми.
- Отметка времени с более высоким значением появляется позже, чем отметка времени с более низким значением.
Создание метки времени
Для создания отметки времени использовалось несколько различных способов.
- Используйте значение системных часов в начале транзакции в качестве отметки времени.
- Используйте поточно-безопасный общий счетчик, который увеличивается в начале транзакции в качестве отметки времени.
- Комбинация двух вышеперечисленных методов.
Формальный
Каждая транзакция () - это упорядоченный список действий (). Прежде чем транзакция выполнит свое первое действие (), он помечен текущей меткой времени или любой другой строго упорядоченной последовательностью:. Каждой транзакции также дается изначально пустой набор транзакций, от которого она зависит,, и изначально пустой набор старых объектов, которые он обновил, .
Каждый объект в базе данных даны два поля меток времени, которые используются только для управления параллелизмом: время, когда значение объекта было в последний раз использовано транзакцией, время, когда значение объекта было в последний раз обновлено транзакцией.
Для всех :
- За каждое действие :
- Если желает использовать ценность :
- Если затем прервать (более свежий поток перезаписал значение),
- В противном случае обновите набор зависимостей и установить ;
- Если желает обновить значение :
- Если затем прервать (более свежий поток уже полагается на старое значение),
- Если затем пропустите ( правило записи Томаса ),
- В противном случае сохраните предыдущие значения, , набор , и обновите значение .
- Если желает использовать ценность :
- Пока есть транзакция в что еще не закончилось: подождите
- Если есть транзакция в что прервана , то прерывания
- В противном случае: совершить .
Чтобы прервать :
- Для каждого в
- Если равно затем восстановить а также
Неофициальный
Каждый раз, когда транзакция начинается, она получает отметку времени. Эта временная метка указывает порядок, в котором должна происходить транзакция, относительно других транзакций. Таким образом, учитывая две транзакции, которые влияют на один и тот же объект, операция транзакции с более ранней меткой времени должна выполняться до операции транзакции с более поздней меткой времени. Однако, если операция неправильной транзакции фактически представлена первой, она прерывается, и транзакция должна быть перезапущена.
Каждый объект в базе данных имеет метку времени чтения , которая обновляется при чтении данных объекта, и метку времени записи , которая обновляется всякий раз, когда данные объекта изменяются.
Если транзакция хочет прочитать объект,
- но транзакция началась до отметки времени записи объекта, это означает, что что-то изменило данные объекта после начала транзакции. В этом случае транзакция отменяется и ее необходимо перезапустить.
- и транзакция началась после того, как объект метки времени записи , это означает , что она безопасна для чтения объекта. В этом случае, если метка времени транзакции находится после метки времени чтения объекта, метка времени чтения устанавливается равной метке времени транзакции.
Если транзакция хочет записать в объект,
- но транзакция началась до отметки времени чтения объекта, это означает, что что-то посмотрело на объект, и мы предполагаем, что это взяло копию данных объекта. Таким образом, мы не можем писать в объект, поскольку это сделало бы любые скопированные данные недействительными, поэтому транзакция прерывается и должна быть перезапущена.
- и транзакция началась до отметки времени записи объекта, это означает, что что-то изменило объект с тех пор, как мы начали нашу транзакцию. В этом случае мы используем правило записи Томаса и просто пропускаем нашу операцию записи и продолжаем как обычно; транзакцию не нужно прерывать или перезапускать
- в противном случае транзакция выполняет запись в объект, а метка времени записи объекта устанавливается равной метке времени транзакции.
Восстанавливаемость
Обратите внимание, что упорядочение временных меток в его базовой форме не создает восстанавливаемых историй. Рассмотрим, например, следующую историю транзакций а также :
Это может быть создано планировщиком TO, но не может быть восстановлено, поскольку совершает, даже если прочитал из незафиксированной транзакции. Чтобы убедиться, что он создает восстанавливаемые истории, планировщик может хранить список других транзакций, из которых каждая транзакция читала , и не позволять транзакции фиксироваться до того, как этот список будет состоять только из зафиксированных транзакций. Чтобы избежать каскадных прерываний, планировщик мог пометить данные, записанные незафиксированными транзакциями, как грязные , и никогда не позволять операции чтения начинаться с такого элемента данных, пока он не был отменен. Чтобы получить строгую историю, планировщик не должен допускать никаких операций с грязными элементами.
Проблемы реализации
Разрешение отметки времени
Это минимальное время, прошедшее между двумя соседними отметками времени. Если разрешение метки времени слишком велико (грубое), вероятность того, что две или более метки времени будут равны, увеличивается, что позволяет некоторым транзакциям совершаться в неправильном порядке. Например, если предположить, что у нас есть система, которая может создавать сто уникальных временных меток в секунду, и учитывая два события, которые происходят с интервалом в 2 миллисекунды, им, вероятно, будет предоставлена одна и та же временная метка, даже если они действительно произошли в разное время.
Блокировка метки времени
Несмотря на то, что этот метод является неблокирующим, поскольку объект не заблокирован от одновременного доступа на время транзакции, запись каждой временной метки для объекта требует чрезвычайно короткой блокировки объекта или его прокси.