Протоколы фиксации/отката изменений

Одна транзакция, например перевод средств с одного банковского счета на другой, отмена бронирования авиабилета или регистрация студента на курсе в университете, может потребовать нескольких действий на уровне базы данных. Например, для перевода средств между банковскими счетами необходимо уменьшить баланс одного счета и увеличить баланс другого. Между двумя этими шагами информация в базе данных может быть противоречивой. Действительно, в краткий миг между списанием средств с первого счета и зачислением их на другой наблюдается недостача средств. Аналогично, когда место в самолете передается другому пассажиру, есть момент, когда для пассажира нет свободного места или когда список пассажиров на одного человека больше максимально допустимого размера.

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

Рассмотрим вопрос неполадок. Цель СУБД — гарантировать, что неполадка не зафиксирует базу данных в противоречивом состоянии. Часто это достигается поддержкой журнала, содержащего записи о каждой транзакции, на энергонезависимом носителе, например на диске. Перед тем как транзакции будет разрешено изменить базу данных, все необходимые обновления должны быть зарегистрированы в журнале. Таким образом, в журнале хранятся постоянные записи о каждом действии выполняемых транзакций.

Момент, когда все шаги транзакции уже зарегистрированы в журнале, называется точкой фиксации транзакции (commit point). Именно в этот момент у СУБД есть вся необходимая информация для восстановления всей транзакции, если это будет необходимо. И в этот момент СУБД подтверждает транзакцию в том смысле, что принимает на себя ответственность за гарантированное отражение всех действий транзакции в базе данных. В случае неполадок оборудования СУБД при помощи информации своего журнала может восстановить транзакции, выполненные после последнего резервного копирования.

Если проблема произошла до того, как транзакция достигла точки фиксации, СУБД может оказаться в ситуации частично выполненной транзакции, которую невозможно завершить. В этом случае журнал можно использовать для отката (roll back), отмены уже выполненных действий транзакции. Например, при неполадках СУБД может восстановить базу, отменив все незавершенные (неподтвержденные) на момент возникновения проблем транзакции.

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

Чтобы подчеркнуть сложную природу СУБД, необходимо заметить, что в процессе отката также кроются некоторые проблемы. Откат одной транзакции может воздействовать на записи базы данных, которые уже использовались другими транзакциями. Например, отменяемая транзакция обновила баланс банковского счета, а другая транзакция уже выполнила свои действия на основе обновленного значения. Это означает, что такие дополнительные транзакции также необходимо отменить, что может привести к откату каких-либо еще транзакций. Подобная проблема называется каскадным откатом (cascading rollback).

Блокировка

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

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

Для защиты от таких проблем, как проблема неправильной суммы или потерянного обновления, планировщики используют протокол блокирования, который помечает, что элементы базы данных в данный момент используются транзакциями. Такие метки называются блокировками, а помеченные элементы — заблокированными. Применяются два типа блокировки: блокировка с обеспечением совместного доступа и исключающая блокировка. Они обозначают два типа доступа транзакций к элементам данных — совместный и исключающий. Если транзакции не требуется изменять значение элемента данных, ей подойдет совместный доступ, то есть другие транзакции также смогут просматривать элемент данных. Однако если транзакция будет изменять значение элемента, ей необходим исключающий доступ, чтобы другие транзакции не могли обратиться к элементу до ее завершения.

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

Для случаев, когда запрос транзакции на доступ к данным отклоняется, существует множество алгоритмов. Один из них — транзакция просто ожидает освобождения запрошенного элемента. Но этот подход может привести к тупику: если двум транзакциям понадобится исключающий доступ к одним и тем же двум элементам, они могут блокировать выполнение друг друга, получив доступ к одному элементу и ожидая доступа к другому. Чтобы избежать подобных мертвых точек, в некоторых СУБД более старым транзакциям отдается приоритет. То есть если более старой транзакции потребуется доступ к элементу данных, заблокированному новой транзакцией, эта новая транзакция освободит все свои элементы, и ее действия будут отменены (по журналу). Затем старая транзакция получит доступ к нужному элементу данных, а новая транзакция будет запущена еще раз. Если новая транзакция будет периодически выгружаться, ее срок жизни увеличится, и она, в конце концов, станет одной из старых транзакций. Этот протокол, называемый протоколом выгрузки и ожидания (старая транзакция выгружает новую, новая ожидает завершения старых), гарантирует, что в конечном итоге каждая транзакция будет выполнена.