Транзакции.

Атомарное хранение

Предположим, что у нас имеется диск с двумя операциями:

put (block, address) Помещает данные в блок на диске по некоторому адресу

get (address) −> block Возвращает блок по данному адресу

Желаемый результат или событие для вызова put − состоит в том, что все данные должны быть записаны по указанному адресу. Единственный ожидаемое нежелательное событие − то, что данные записаны частично из-за поломки сервера. В случае необратимого нежелательного события диск записывает неправильные данные по неправильному адресу.

Желаемое событие для get − в том, чтобы возвратить предварительно записанные данные в правильном виде даже после отказа и восстановления. Мы не планируем нежелательных событий. Пример нежелательного события − данные, возвращаемые с ошибками.

Нежелательные необратимые события можно определить, классифицировать, как ожидаемые и обратимые, и спроектировать для них процедуру восстановления (например, записать данные с кодом, исправляющим данную ошибку).

Алгоритм, реализующий стабильную память, впервые был описан в 1961 проектировщиками системы резервирования мест для компании SABRE American Airlines, но все еще является очень удобным (например, файловая система LFS использует его, чтобы записывать контрольные точки). Основная идея, как сделать диск атомарным, состоит в том, чтобы записывать блок данных дважды, маркируя каждый блок номером версии:

atomic-put (data) =

version := version + 1

put (version, V1) // V1 ← version

put(data, Dl) // D1 ← data

put (version, V2) // V2 ← version

put (data, D2) // D2 ← data

atomic-get () =

Vldata := get(Vl)

Dldata := get(Dl)

V2data := get(V2)

D2data := get(D2)

if Vldata = V2data

then return Dldata

else return D2data

Здесь VI, Dl, V2, и D2 − дисковые адреса. Версия − глобальная переменная, сохраненная в оперативной памяти.

Это еще не все, но давайте вначале посмотрим, насколько атомарны эти операции. Предположим, что данные на диске правильны, и полны, и читаются, скажем, как {#2, "seat 25", #2, "seat 25"}, где #2 − номер версии, a "seat 25" является данными для системы бронирования мест.

Предположим, сервер потерпел аварию где-нибудь в atomic-put ("seat 31"), а после восстановления мы пытаемся получить atomic-get. Здесь возможны четыре случая в зависимости от того, который put в atomic-put не был выполнен:

Невыполненный put	Информация на диске	Atomic-get возвратит
первый	{#2, “seat 25”, #2, “seat 25”}	“seat 25”
второй	{#3, “seat 25”, #2, “seat 25”}	“seat 25”
третий	{#3, “seat 31”, #2, “seat 25”}	“seat 25”
четвертый	{#3, “seat 31”, #3, “seat 25”}	“seat 31”

Во всех случаях, операция atomic-get вернет правильное значение: старое или новое. Она не может возвратить частично записанное значение. Поэтому операция atomic-put полностью выполняется или полностью не выполняется! Диск − атомарный.

Однако, мы сделали два предположения: во-первых, что не может произойти никаких необратимых событий (т.е., данные всегда возвращаются в корректной форме); и во-вторых, диск находится в корректном и целостном состоянии при пуске команды atomic-put. Если захотим, то мы можем исправить первую проблему с помощью контрольных сумм. Вторая нуждается в дополнительном внимании: перед выполнением следующей команды put после отказа диска, мы должны восстановить диск, чтобы вернуть его назад в правильное состояние. Вот та же программа, но расширенная с помощью операций по восстановлению ошибок:

atomic-put (data) =

recover()

version := version + 1

put (version, V1) // V1 ← version

put(data, Dl) // D1 ← data

put (version, V2) // V2 ← version

put (data, D2) // D2 ← data

atomic-get () =

Vldata := get(Vl)

Dldata := get(Dl)

V2data := get(V2)

D2data := get(D2)

if Vldata = V2data

then return Dldata

else return D2data

recover() =

Vldata := get(Vl)

Dldata := get(Dl)

V2data := get(V2)

D2data := get(D2)

if Vldata = V2data then

if Dldata != D2data

then put(Dldata, D2) // D2 ← D1

else put(D2data, Dl) // D1 ← D2

put(V2data, VI) // V1 ← V2

version := Vldata

Каждый раз, когда вызывается atomic-put, мы сначала проверяем, что диск находится в правильном состоянии, вызывая процедуру восстановления. Поскольку процедура восстановления выполняет операции put, то мы должны удостовериться, что поломка при восстановлении не перемешает данные на диске. Имеются 3 вызова put, поэтому надо рассмотреть три случая:

put(Dldata, D2). Эта операция невидима для atomic-get, потому что Vldata равна V2data, следовательно, atomic-get игнорирует содержание D2.

put(D2data, Dl). Эта операция невидима для atomic-get, потому что atomic-get в этом случае игнорирует содержание D1.

put(V2data, VI). Эта операция невидима для atomic-get, потому что в этом месте D1 и D2 уже обозначают одно и тоже, так что не имеет значения, какой из них мы читаем.

Таким образом, аварии при восстановлении не будут запутывать диск. Фактически, вся программа до put (version, V2) в самой процедуре atomic-put идемпотентна: диск может выходить из строя несколько раз, но мы можем повторять выполнение программы несколько раз без ошибочных результатов. Пункт, в котором операция put(version, V2) достигает цели − это пункт, в котором новые данные становятся видимыми для atomic-get.

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

Транзакции

Атомарный диск является для данного случая примером общей идеи. Все, что мы хотим, это взять произвольную последовательность операций, заключить их в скобки begin-atomic и end-atomic, и результат должен быть неделимым относительно отказов и параллелизма. К сожалению, никто не показал, как это сделать для произвольной последовательности команд. Однако если ввести некоторые ограничения на последовательность команд, то мы можем сделать это:

begin-atomic

pre-commit operations

commit

post-commit operations

end-atomic

Ограничение на операции pre-commit − то, что здесь в случае неудачи мы должны отступить, не оставляя следа. Ограничение на post-commit − то, что необходимо завершение в любом случае. (Операция commit фиксирует результат на диск.) Обратите внимание, что наш атомарный диск точно следует этим предписаниям с операцией put (version, V2), которая является пунктом commit. (Операции до этого пункта идемпотентны; операция после commit, put (data, D2), будет выполнена обязательно из-за процесса восстановления, который разработан нами.)

Простой пример того, как действовать для реализации этой модели, состоит в следующем. Когда мы задействуем begin-atomic, мы делаем копию всего состояния программы. Все операции в pre-commit работают с копиями, не делая никаких изменений в первоначальном состоянии. Затем, когда мы закончили с операциями pre-commit, то атомарно обмениваем копию с оригиналом (например, перебрасывая указатель). В фазе post-commit, мы освобождаем память от старого состояния. Результат − то, что мы всегда имеем или старую, или новую версию состояния программы, даже если система терпит крах во время записи. Многие текстовые процессоры использует этот подход.

Используя этот принцип, мы можем правильно двигаться от одного состояния к другому, когда их разделяет операция commit. Если корректно начальное состояние, то состояние после пункта commit будет также верно. Кроме того, если мы проектируем так, что любая другая атомарная операция выполняется полностью до или после скобок begin-atomic-end-atomic, тогда у нас не возникает проблем с параллелизмом.

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

tid := begin-transaction()

value := read(address, tid)

write (value, address, tid)

commit (tid)

or,

tid := begin-transaction()

value := read(address, tid)

write (value, address, tid)

abort (tid)

Транзакция − последовательность команд чтения и записи, каждая помечена идентификатором транзакции (tid в примере). Транзакция заканчивается выполнением или отменой.

Главный вопрос, как эффективно реализовать этот интерфейс? Для этого мы должны лучше понять параллелизм. Желательное поведение должно состоять в том, что, логически, атомарная операция выполняется полностью до или после любой другой операции. Условие правильности, которое поддерживает эту основную идею, но оставляет мало дополнительной свободы для реализации: если запущены несколько атомарных операций, то результат должен быть идентичным некоторому последовательному плану выполнения этих атомарных операций. (Последовательный список набора операций содержит те же самые операции, но упорядоченные таким образом, чтобы никакие две операции не наложились во времени.) Это условие правильности называется сериализуемостъ. Теперь, чтобы установить правильность работы системы, можно обсуждать последовательное выполнение вместо параллельного, которое намного тяжелее для обсуждения, а реализация все же может использовать параллелизм.

Предположим, что у нас имеются три параллельные атомарные операции:

A =	B =	C =
begin-atomic x := 0 x := x+1 end-atomic	begin-atomic x := 0 x := x+2 end-atomic	begin-atomic x := 0 x := x+3 end-atomic

Если мы преобразовываем эти операции в последовательную форму в некотором порядке, то для х возможны конечные результаты: 1, 2, и 3. Поэтому, любое параллельное выполнение действий с результатом 1, 2 или 3 правильно; любой другой результат неправилен. Пример: последовательность {А1, В1, А2, В2, С1, С2} − является правильной, так как х получает значение 3; последовательность {А1, В1, С1, А2, В2, С2} − неправильна, так как х получает значение 6.

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