Введение

Порядок выполнения транзакций в базах данных и системах обработки транзакций

В области баз данных и обработки транзакций (управления транзакциями) расписание (или история) системы представляет собой абстрактную модель, описывающую порядок выполнения набора транзакций, работающих в системе. Как правило, это список операций (действий), упорядоченных по времени, выполняемых набором транзакций, выполняемых совместно в системе. Если временной порядок между определенными операциями не определен системой, используется частичный порядок. Примерами таких операций являются запрос на чтение, чтение, запись, откат, фиксация, запрос блокировки, установка блокировки и т.д. Часто в расписании включается лишь подмножество типов операций транзакций. Расписания являются фундаментальными понятиями в теории управления параллелизмом баз данных. На практике большинство общесистемных баз данных используют расписания, которые являются серийно-эквивалентными и строго восстанавливаемыми.

Длительность и порядок действий

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

Типы расписания

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

Сериализируемый

График считается сериализуемым, если он эквивалентен (по результату) последовательному графику. В графике E порядок выполнения действий транзакций отличается от порядка в графике D, но в конечном итоге E дает тот же результат, что и D. +ET1T2T3R(X)R(Y)R(Z)W(X)W(Y)W(Z)Com. Com. Com. Сериализуемость используется для поддержания согласованности данных в элементах данных. Это основной критерий корректности расписания параллельных транзакций и, следовательно, поддерживается во всех системах управления базами данных общего назначения. Графики, которые не являются сериализуемыми, могут приводить к ошибочным результатам, что может быть крайне опасно (например, при работе с денежными средствами в банках). Если приложению требуется определенный порядок между некоторыми транзакциями, он обеспечивается независимо от базовых механизмов сериализации. Эти механизмы обычно не учитывают какой-либо конкретный порядок и генерируют некий непредсказуемый частичный порядок, который, как правило, совместим с несколькими последовательными порядками этих транзакций.

Конфликт-сериализация

Расписание считается конфликтно сериализуемым, если оно конфликтно эквивалентно одному или нескольким последовательным расписаниям. Эквивалентно, расписание конфликтно сериализуемо тогда и только тогда, когда его граф предшествования является ациклическим, если рассматриваются только зафиксированные (committed) транзакции. Следует отметить, что если граф определен так, чтобы включать также незафиксированные транзакции, то могут возникать циклы с участием незафиксированных транзакций без нарушения конфликтной сериализуемости. Расписание K конфликтно эквивалентно последовательному расписанию <T1, T2>, но не <T2, T1>. +KT1T2R(A)R(A)W(B)Com. W(A)Com. Конфликтную сериализуемость можно обеспечить перезапуском любой транзакции в цикле графа предшествования, или путем реализации двухфазной блокировки, упорядочения по меткам времени или сериализуемой изоляции снимков.

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

В восстанавливаемом расписании транзакции фиксируются только после того, как все транзакции, изменения которых они читали, были зафиксированы. Расписание становится невосстановимым, если транзакция читает и использует изменения из другой транзакции, а затем фиксируется и откатывается. FF2JT1T2T1T2T1T2R(A)R(A)R(A)W(A)W(A)W(A)R(A)R(A)R(A)W(A)W(A)W(A)Фиксация. ОткатФиксация. ОткатОткат.
Эти расписания восстанавливаемые. Расписание F восстанавливаемо, потому что T1 фиксируется до T2, что делает значение, прочитанное T2, корректным. Затем T2 может зафиксироваться. В расписании F2, если T1 откатилась, T2 должна быть откатена, потому что значение A, которое она прочитала, неверно. В обоих случаях база данных остается в согласованном состоянии. Транзакция J невосстановима, потому что T2 фиксируется до T1, несмотря на то, что ранее прочитала значение, записанное T1. Поскольку T1 откатилась после фиксации T2, значение, прочитанное T2, неверно. Поскольку транзакцию нельзя откатить после ее фиксации, расписание невосстановимо.

Строгое

График называется строгим, если для любых двух транзакций T1 и T2, если операция записи транзакции T1 предшествует конфликтующей операции транзакции T2 (чтение или запись), то событие фиксации или отката транзакции T1 также предшествует этой конфликтующей операции транзакции T2. Любой строгий график является каскадным, но не наоборот. Строгость обеспечивает эффективное восстановление баз данных после сбоев.