Расписание транзакций базы данных

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

Расписания являются фундаментальными понятиями в теории управления параллелизмом баз данных . На практике в большинстве систем баз данных общего назначения используются сериализуемые по конфликтам и строго восстанавливаемые расписания.

Обозначения

Обозначение сетки:

Столбцы: различные транзакции в расписании.
Строки: временной порядок операций (также известных как действия).

Операции (они же действия):

R(X): Соответствующая транзакция «читает» объект X (т. е. извлекает данные, хранящиеся в X). Это сделано для того, чтобы можно было изменять данные (например, X=X+4) во время операции «записи», а не просто перезаписывать их. Когда расписание представлено в виде списка, а не сетки, действие представляется в виде $Ri(X)$ где $i$ — число, соответствующее конкретной транзакции.
W(X): соответствующая транзакция «записывает» объект X (т. е. изменяет данные, хранящиеся в X). Когда расписание представлено в виде списка, а не сетки, действие представляется в виде $Wi(X)$ где $i$ — число, соответствующее конкретной транзакции.
Com.: представляет собой операцию «фиксации», в которой соответствующая транзакция успешно завершила свои предыдущие действия и сделала все свои изменения постоянными в базе данных.

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

Пример

Ниже приведен пример расписания:

Д
Т1	Т2	Т3
Р(Х)
Вт(Х)
С.
	Р(Я)
	В(Г)
	С.
		Р(З)
		W(Z)
		С.

В этом примере столбцы представляют различные транзакции в графике D. График D состоит из трех транзакций T1, T2, T3. Сначала T1 читает и записывает объект X, а затем фиксирует. Затем T2 читает и записывает в объект Y и фиксирует, и, наконец, T3 читает и записывает в объект Z и фиксирует.

Расписание D, приведенное выше, можно представить в виде списка следующим образом:

D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3

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

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

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

Виды расписания

— Полное расписание это расписание, которое содержит либо прерывание (также известное как откат ) , либо действие фиксации для каждой из своих транзакций. Последнее действие транзакции — либо зафиксировать, либо прервать ее. Чтобы сохранить атомарность , транзакция должна отменить все свои действия, если она прервана.

Серийный

Расписание является последовательным, если выполняемые транзакции не чередуются (т. е. серийное расписание — это расписание, в котором ни одна транзакция не начинается до тех пор, пока не завершится выполняющаяся транзакция).

График D является примером серийного расписания:

Д
Т1	Т2	Т3
Р(Х)
Вт(Х)
С.
	Р(Я)
	В(Г)
	С.
		Р(З)
		W(Z)
		С.

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

Расписание является сериализуемым , если оно эквивалентно (по своему результату) серийному расписанию.

В графике E порядок выполнения действий транзакций не такой, как в D, но в конечном итоге E дает тот же результат, что и D.

И
Т1	Т2	Т3
Р(Х)
	Р(Я)
		Р(З)
Вт(Х)
	В(Г)
		W(Z)
С.	С.	С.

Сериализуемость используется для поддержания данных в элементе данных в согласованном состоянии. Это основной критерий правильности расписания параллельных транзакций, поэтому он поддерживается во всех системах баз данных общего назначения. Расписания, которые не подлежат сериализации, могут привести к ошибочным результатам; что может быть чрезвычайно вредным (например, при работе с деньгами внутри банков). ^[1]^[2]^[3]

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

Противоречивые действия

Говорят, что два действия находятся в конфликте (конфликтующая пара), если и только если выполняются все три следующих условия:

Действия принадлежат разным транзакциям.
По крайней мере одно из действий является операцией записи.
Действия обращаются к одному и тому же объекту (чтение или запись). ^[4]^[5]

Аналогично, два действия считаются конфликтующими тогда и только тогда, когда они некоммутативны . Аналогично, два действия считаются конфликтующими тогда и только тогда, когда они являются конфликтом чтения-записи , записи-чтения или записи-записи .

Следующий набор действий противоречив:

R1(X), W2(X), W3(X) (3 конфликтующие пары)

При этом следующие наборы действий не противоречат друг другу:

R1(X), R2(X), R3(X)
R1(X), W2(Y), R3(X)

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

Конфликт материализуется , если запрошенная конфликтующая операция фактически выполняется: во многих случаях запрошенная/выполненная транзакцией конфликтующая операция задерживается и даже никогда не выполняется, обычно из-за блокировки объекта операции, удерживаемого другой транзакцией, или при записи в временное частное рабочее пространство транзакции и ее материализация, копирование в саму базу данных после фиксации; до тех пор, пока запрошенная/выполненная конфликтующая операция не выполняется над самой базой данных, конфликт не материализуется ; нематериализованные конфликты не представлены ребром на графе приоритетов.

Конфликтная эквивалентность

Расписания S1 и S2 называются конфликтно-эквивалентными тогда и только тогда, когда выполняются оба следующих двух условия:

Оба расписания S1 и S2 включают один и тот же набор транзакций, так что каждая транзакция выполняет одни и те же действия в одном и том же порядке.
Оба расписания имеют одинаковый набор конфликтующих пар (так что действия в каждой конфликтующей паре выполняются в одинаковом порядке). ^[6] Это эквивалентно требованию, чтобы все конфликтующие операции (т. е. операции в любой конфликтующей паре) располагались в одном и том же порядке в обоих расписаниях.

Аналогично, два расписания называются конфликтно-эквивалентными тогда и только тогда, когда одно можно преобразовать в другое путем замены пар неконфликтующих операций (независимо от того, являются ли они смежными или нет), сохраняя при этом порядок действий для каждой транзакции. ^[4]

Аналогично, два расписания называются конфликтно-эквивалентными тогда и только тогда, когда одно можно преобразовать в другое путем замены пар неконфликтных соседних операций с разными транзакциями. ^[7]

сериализуемый конфликт

Расписание называется сериализуемым по конфликтам, если оно конфликтно-эквивалентно одному или нескольким последовательным расписаниям.

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

Расписание K конфликтно-эквивалентно последовательному расписанию <T1,T2>, но не <T2,T1>.

К
Т1	Т2
Р(А)
	Р(А)
Вт(Б)
С.
	В(А)
	С.

Сериализация конфликтов может быть реализована путем перезапуска любой транзакции в цикле в графе приоритетов или путем реализации двухфазной блокировки , упорядочивания временных меток или сериализуемой изоляции моментальных снимков . ^[8]

Посмотреть эквивалентность

Два расписания S1 и S2 называются эквивалентными по представлению, если выполняются следующие условия:

Если транзакция $T_{i}$ в S1 считывает начальное значение объекта X, а также выполняет ту же транзакцию $T_{i}$ в С2.
Если транзакция $T_{i}$ считывает значение (для объекта X), записанное транзакцией $T_{j}$ в S1 он должен сделать это S2.
Если транзакция $T_{i}$ в S1 выполняется окончательная запись для объекта X, как и та же транзакция $T_{i}$ в С2.

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

В приведенном ниже примере расписания S1 и S2 эквивалентны просмотру, но ни S1, ни S2 не эквивалентны просмотру расписанию S3.

С1		С2		S3
Т1	Т2	Т1	Т2	Т1	Т2
Р(А)		Р(А)		Р(А)
В(А)		В(А)		В(А)
Р(Б) ⁽¹⁾			Р(А)		Р(А)
Вт(Б)			В(А)		В(А)
С.		Р(Б) ⁽¹⁾			Р(Б) ⁽¹⁾
	Р(А)	Вт(Б)			Вт(Б)
	В(А)	С.		Р(Б) ⁽²⁾
	Р(Б) ⁽²⁾		Р(Б) ⁽²⁾	Вт(Б) ⁽³⁾
	Вт(Б) ⁽³⁾		Вт(Б) ⁽³⁾	С.
	С.		С.		С.

Условия, при которых S3 является эквивалентным по представлению S1 и S2, не были удовлетворены в соответствующих верхних индексах по следующим причинам:

Не удалось выполнить первое условие эквивалентности представлений, поскольку T1 прочитал начальное значение для B в S1 и S2, а T2 прочитал начальное значение для B в S3.
Не удалось выполнить второе условие эквивалентности представления, поскольку T2 прочитал значение, записанное T1 для B в S1 и S2, но T1 прочитал значение, записанное T2 для B в S3.
Не удалось выполнить третье условие эквивалентности представлений, поскольку T2 выполнил окончательную запись для B в S1 и S2, а T1 выполнил окончательную запись для B в S3.

Чтобы быстро проанализировать, являются ли два расписания эквивалентными по представлению, запишите оба расписания в виде списка, в котором нижний индекс каждого действия указывает, какому условию эквивалентности представления они соответствуют. Расписания эквивалентны просмотру тогда и только тогда, когда все действия имеют одинаковый индекс (или его отсутствие) в обоих расписаниях:

S1: R1(A) _{первоначальное чтение} , W1(A), R1(B) _{начальное чтение} , W1(B), Com1, R2(A) _{запись T1} , W2(A) _{окончательная запись} , R2(B) _{запись T1} , W2(B) _{окончательная запись} , Com2
S2: _{первоначальное чтение} R1(A) , W1(A), R2(A) _{запись T1} , _{окончательная запись} W2 (A), _{первоначальное чтение} R1 (B), W1(B), Com1, R2(B) _{запись T1} , W2(B) _{окончательная запись} , Com2
S3: _{первоначальное чтение} R1(A) , W1(A), R2(A) _{запись T1} , _{окончательная запись} ( W2 (A), первоначальное чтение R2 _B ), W2(B), R1(B) _{запись T2} , W1 (B) _{окончательная запись} , Com1, Com2

сериализуемый для просмотра

Расписание является сериализуемым для просмотра, если оно эквивалентно некоторому последовательному расписанию. Обратите внимание, что по определению все расписания, сериализуемые при конфликтах, сериализуются в представлении.

Г
Т1	Т2
Р(А)
	Р(А)
Вт(Б)

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

ЧАС
Т1	Т2	Т3
Р(А)
	В(А)
	С.
В(А)
С.
		В(А)
		С.

Приведенный выше пример не является сериализуемым по конфликтам, но сериализуемым для просмотра, поскольку он имеет последовательное расписание, эквивалентное представлению <T1,| Т2,| Т3>.

Поскольку определение того, является ли расписание сериализуемым в представлении, является NP-полным , сериализуемость представления не представляет большого практического интереса. ^{[ нужна ссылка ]}

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

В восстанавливаемом расписании транзакции фиксируются только после фиксации всех транзакций, изменения которых они прочитали. Расписание становится невосстановимым, если транзакция $T_{i}$ читает и полагается на изменения из другой транзакции $T_{j}$ , а потом $T_{i}$ совершает и $T_{j}$ аборт.

Ф		Ф2		Дж
Т1	Т2	Т1	Т2	Т1	Т2
Р(А)		Р(А)		Р(А)
В(А)		В(А)		В(А)
	Р(А)		Р(А)		Р(А)
	В(А)		В(А)		В(А)
С.		Прервать			С.
	С.		Прервать	Прервать

Эти графики подлежат восстановлению. Расписание F можно восстановить, поскольку T1 фиксируется раньше T2, что делает значение, считанное T2, правильным. Тогда T2 может взять на себя обязательства. В расписании F2, если T1 прерван, T2 должен прервать работу, поскольку считанное значение A неверно. В обоих случаях база данных остается в согласованном состоянии.

Расписание J не подлежит восстановлению, поскольку T2 зафиксирован до T1, несмотря на то, что ранее было прочитано значение, записанное T1. Поскольку T1 прерван после фиксации T2, значение, считанное T2, неверно. Поскольку транзакцию невозможно отменить после ее фиксации, расписание невозможно восстановить.

Бескаскадный

Бескаскадные расписания (также известные как «расписания предотвращения каскадных прерываний (ACA)») — это расписания, которые позволяют избежать каскадных прерываний, запрещая грязное чтение . Каскадное прерывание происходит, когда прерывание одной транзакции приводит к прерыванию другой транзакции, поскольку она прочитала и использовала изменения первой транзакции в объекте. Грязное чтение происходит, когда транзакция считывает данные из незафиксированной записи в другой транзакции. ^[9]

Следующие примеры аналогичны приведенным в обсуждении возможности восстановления:

Ф		Ф2
Т1	Т2	Т1	Т2
Р(А)		Р(А)
В(А)		В(А)
	Р(А)		Р(А)
	В(А)		В(А)
С.		Прервать
	С.		Прервать

В этом примере, хотя F2 и можно восстановить, это не позволяет избежать каскадные прерывания. Видно, что если T1 прервется, T2 придется также быть прервано, чтобы сохранить правильность расписания поскольку T2 уже прочитал незафиксированное значение, записанное T1.

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

F3
Т1	Т2
	Р(А)
Р(А)
В(А)
	В(А)
Прервать
	Совершить

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

Строгий

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

Любой строгий график является бескаскадным, но не наоборот. Строгость позволяет эффективно восстанавливать базы данных после сбоя.

Отношения классов сериализуемости

Следующие выражения иллюстрируют иерархические (включающие) отношения между классами сериализуемости и восстанавливаемости :

Серийный ⊂ сериализуемый по конфликтам ⊂ сериализуемый по просмотру ⊂ все расписания
Последовательный ⊂ строгий ⊂ бескаскадный (ACA) ⊂ восстанавливаемый ⊂ все расписания

Диаграмма Венна (ниже) графически иллюстрирует приведенные выше положения.

Диаграмма Венна для классов сериализуемости и восстанавливаемости

См. также

График (управление проектом)
Сильная строгая двухфазная блокировка (SS2PL или Rigorousness).
Создание сериализуемой изоляции моментальных снимков ^[8] в изоляции моментальных снимков .
Глобальная сериализуемость , где проблема глобальной сериализуемости и предлагаемые решения. описывается
Линеаризуемость — более общая концепция параллельных вычислений .

Ссылки

^ Филип А. Бернштейн , Вассос Хадзилакос, Натан Гудман (1987): Управление параллелизмом и восстановление в системах баз данных (бесплатная загрузка PDF), Addison Wesley Publishing Company, ISBN 0-201-10715-5
^ Герхард Вейкум , Готфрид Воссен (2001): Транзакционные информационные системы , Elsevier, ISBN 1-55860-508-8
^ Морис Херлихи и Дж. Элиот Б. Мосс. Транзакционная память: архитектурная поддержка структур данных без блокировок. Материалы 20-го ежегодного международного симпозиума по компьютерной архитектуре (ISCA '93). Том 21, выпуск 2, май 1993 г.
^ Jump up to: ^а ^б «Сериализуемость конфликтов в СУБД» . Гики для Гиков . 29 декабря 2015 г. Проверено 27 ноября 2023 г.
^ Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. п. 814. ИСБН 978-1-260-08450-4 .
^ Рамакришнан, Рагху; Герке, Джон (2000). Системы управления базами данных . Серия по информатике (2-е изд.). Бостон: МакГроу-Хилл. п. 540. ИСБН 978-0-07-232206-4 .
^ Гарсиа-Молина, Гектор; Уллман, Джеффри Д.; Видом, Дженнифер (2009). Системы баз данных: полная книга . Международное издание Пирсона (2-е изд.). Река Аппер-Сэддл, Нью-Джерси: Пирсон/Прентис-Холл. стр. 891–892. ISBN 978-0-13-187325-4 .
^ Jump up to: ^а ^б Майкл Дж. Кэхилл, Уве Рем, Алан Д. Фекете (2008): «Сериализуемая изоляция для баз данных моментальных снимков» , Труды международной конференции ACM SIGMOD 2008 года по управлению данными , стр. 729-738, Ванкувер, Канада, июнь 2008 г., ISBN 978-1-60558-102-6 (награда SIGMOD за лучшую бумагу 2008 г.)
^ «Бескаскадность в СУБД» . Гики для Гиков . 06.08.2019 . Проверено 29 ноября 2023 г.

[Bernstein872-1] Филип А. Бернштейн , Вассос Хадзилакос, Натан Гудман (1987): Управление параллелизмом и восстановление в системах баз данных (бесплатная загрузка PDF), Addison Wesley Publishing Company, ISBN 0-201-10715-5

[Weikum012-2] Герхард Вейкум , Готфрид Воссен (2001): Транзакционные информационные системы , Elsevier, ISBN 1-55860-508-8

[Herlihy1993-3] Морис Херлихи и Дж. Элиот Б. Мосс. Транзакционная память: архитектурная поддержка структур данных без блокировок. Материалы 20-го ежегодного международного симпозиума по компьютерной архитектуре (ISCA '93). Том 21, выпуск 2, май 1993 г.

[:0-4] Jump up to: ^а ^б «Сериализуемость конфликтов в СУБД» . Гики для Гиков . 29 декабря 2015 г. Проверено 27 ноября 2023 г.

[5] Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. п. 814. ИСБН 978-1-260-08450-4 .

[6] Рамакришнан, Рагху; Герке, Джон (2000). Системы управления базами данных . Серия по информатике (2-е изд.). Бостон: МакГроу-Хилл. п. 540. ИСБН 978-0-07-232206-4 .

[7] Гарсиа-Молина, Гектор; Уллман, Джеффри Д.; Видом, Дженнифер (2009). Системы баз данных: полная книга . Международное издание Пирсона (2-е изд.). Река Аппер-Сэддл, Нью-Джерси: Пирсон/Прентис-Холл. стр. 891–892. ISBN 978-0-13-187325-4 .

[Cahill082-8] Jump up to: ^а ^б Майкл Дж. Кэхилл, Уве Рем, Алан Д. Фекете (2008): «Сериализуемая изоляция для баз данных моментальных снимков» , Труды международной конференции ACM SIGMOD 2008 года по управлению данными , стр. 729-738, Ванкувер, Канада, июнь 2008 г., ISBN 978-1-60558-102-6 (награда SIGMOD за лучшую бумагу 2008 г.)

[9] «Бескаскадность в СУБД» . Гики для Гиков . 06.08.2019 . Проверено 29 ноября 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]