График транзакций базы данных

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

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

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

Обозначение

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

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

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

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

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

Пример

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

В этом примере столбцы представляют различные транзакции в расписании 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 — пример последовательного графика:

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

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

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

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

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

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

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

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

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

Следующий набор действий является конфликтующим:

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

При этом следующие наборы действий не являются конфликтующими:

• Р1(Х), Р2(Х), Р3(Х)
• Р1(Х), Ш2(Y), Р3(Х)

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

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

Эквивалентность конфликта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Не выполнено первое условие эквивалентности представлений, поскольку T1 прочитал начальное значение для B в S1 и S2, но T2 прочитал начальное значение для B в S3.
2. Не выполнено второе условие эквивалентности представлений, поскольку T2 прочитал значение, записанное T1 для B в S1 и S2, но T1 прочитал значение, записанное T2 для B в S3.
3. Третье условие эквивалентности представлений не выполнено, поскольку 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

Просмотр-сериализуемый

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

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

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

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

Извлекаемый

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

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

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

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

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

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

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

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

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

Строгий

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

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

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

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

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

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

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

Смотрите также

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

Ссылки

1. Филип А. Бернстайн , Вассос Хадзилакос, Натан Гудман (1987): Управление параллелизмом и восстановление в системах баз данных (бесплатная загрузка PDF), Addison Wesley Publishing Company, ISBN  0-201-10715-5
2. Герхард Вейкум , Готфрид Воссен (2001): Транзакционные информационные системы, Elsevier, ISBN 1-55860-508-8 
3. Морис Херлихи и Дж. Элиот Б. Мосс. Транзакционная память: архитектурная поддержка структур данных без блокировок. Труды 20-го ежегодного международного симпозиума по компьютерной архитектуре (ISCA '93). Том 21, выпуск 2, май 1993 г.
4. "Конфликтная сериализуемость в СУБД". GeeksforGeeks . 2015-12-29 . Получено 2023-11-27 .
5. Зильбершатц, Абрахам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции систем баз данных (седьмое изд.). Нью-Йорк, Нью-Йорк: McGraw-Hill Education. стр. 814. ISBN 978-1-260-08450-4.
6. Рамакришнан, Рагху; Герке, Йоханнес (2000). Системы управления базами данных . Серия по информатике (2-е изд.). Бостон: МакГроу-Хилл. п. 540. ИСБН 978-0-07-232206-4.
7. Гарсия-Молина, Гектор; Ульман, Джеффри Д.; Видом, Дженнифер (2009). Системы баз данных: полная книга . Международное издание Pearson (2-е изд.). Верхняя Сэддл-Ривер, Нью-Джерси: Pearson/Prentice Hall. стр. 891–892. ISBN 978-0-13-187325-4.
8. Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): "Сериализуемая изоляция для моментальных снимков баз данных", Труды международной конференции ACM SIGMOD 2008 года по управлению данными , стр. 729-738, Ванкувер, Канада, июнь 2008 г., ISBN 978-1-60558-102-6 (награда за лучшую статью SIGMOD 2008 г.) 
9. "Cascadeless in DBMS". GeeksforGeeks . 2019-08-06 . Получено 2023-11-29 .