Serializable snapshot isolation Postgresql
SSI (Serializable Snapshot Isolation или Сериализуемая изоляция снимков) является инновационным уровнем изоляции, поддерживаемым Postgresql. В данном разделе представлена краткая информация по данному уровню изоляции, более подробную информацию по данному вопросу Вы найдете здесь: Serializable Snapshot Isolation in PostgreSQL.
В дальнейшем мы будем оперировать следующими терминами.
- Граф предшествования (граф сериализации);
- Аномалия сериализации (e.g. Write-Skew)
Если Вы не знакомы с данными терминами, рекомендуем ознакомиться со следующими материалами:
- Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, “Database System Concepts”, McGraw-Hill Education, ISBN-13: 978-0073523323
- Thomas M. Connolly, and Carolyn E. Begg, “Database Systems”, Pearson, ISBN-13: 978-0321523068
Базовая стратегия SSI
Если в графе предшествования присутствует цикл, то возникает аномалия сериализации. Это можно объяснить на примере простейшей аномалии под названием white skew.
На рисунке ниже описана следующая ситуация: Transaction_A читает Tuple_B, а Nransaction_B читает Tuple_A. Затем Transaction_A записывает Tuple_A, а Transaction_B записывает Tuple_B. В этом случае возникают два rw-конфликта, образующих цикл в графе предшествования, возникает аномалия сериализации Write-Skew.
Концептуально существует три типа конфликтов: wr-конфликты (грязное чтение), ww-конфликты (потерянное обновление) и rw-конфликты. Wr- и ww-конфликты не нуждаются в подробном описании, поскольку PostgreSQL с легкостью предотвращают их. Таким образом, при реализации SSI в PostgreSQL необходимо учитывать только rw-конфликты.
Базовая стратегия SSI в рамках Postgresql:
- Зафиксировать все объекты (кортежи, страницы и т.д.), к которым обращаются транзакции, как блокировки SIRead;
- Обнаружить rw-конфликты с помощью блокировок SIRead;
- Прервать транзакцию при обнаружении аномалии сериализации в следствие обнаружениях rw-конфликтов.
SSI в PostgreSQL
Для реализации стратегии, описанной выше, в PostgreSQL реализовано множество функций и структур данных. Однако здесь мы рассматриваем только две структуры данных: блокировки SIRead и rw-конфликты, хранящиеся в общей памяти.
Блокировки SIRead:
Блокировки SIRead, также называемые предикатными блокировками, представляет собой пару из объекта и (виртуального) txid, хранящей информацию о том, кто получил доступ к объекту.
SIRead-блокировки запускаются функцией CheckForSerializableConflictOut всякий раз, когда DML-команда выполняется в режиме SERIALIZABLE. Например, если txid 100 читает Tuple_1, создается SIRead-блокировка {Tuple_1, {100}}. Если другая транзакция, например txid 101, считывает Tuple_1, блокировка SIRead обновляется до {Tuple_1, {100,101}}.
Обратите внимание на то, что при чтении индексной страницы также создается блокировка SIRead, поскольку индексная страница читается только в том случае, если применяется функция Index-Only Scan, подробно описанная в разделе 7.2.
Блокировка SIRead имеет три уровня: кортеж, страница и отношение.
Если создаются блокировки SIRead всех кортежей в пределах одной страницы, они объединяются в одну блокировку SIRead, а все блокировки SIRead связанных с ней кортежей удаляются, что позволяет значительно сократить место в памяти.
То же самое справедливо и для страниц.
При использовании последовательного сканирования блокировка SIREAD на уровне отношения создается независимо от наличия индексов и/или предложений WHERE. Обратите внимание, что в некоторых ситуациях такая реализация может привести к ложноположительному обнаружению аномалий сериализации. Более подробную информацию Вы найдете в разделе 5.9.4.
rw-конфликты:
rw - конфликт - это триплет из блокировки SIRead и двух txid, которые читают и записывают блокировку SIRead.
Функция CheckForSerializableConflictIn вызывается всякий раз, когда команда INSERT, UPDATE или DELETE выполняется в режиме SERIALIZABLE, и создает rw-конфликты при обнаружении конфликтов путем проверки блокировок SIRead.
Например, предположим, что txid 100 читает Tuple_1, а затем txid 101 обновляет Tuple_1. В этом случае функция CheckForSerializableConflictIn, вызванная командой UPDATE в txid 101, обнаруживает rw-конфликт с Tuple_1 между txid 100 и 101 и создает rw-конфликт {r=100, w=101, {Tuple_1}}.
Обе функции CheckForSerializableConflictOut и CheckForSerializableConflictIn, а также функция PreCommit_CheckForSerializationFailure, которая вызывается при выполнении команды COMMIT в режиме SERIALIZABLE, проверяют аномалии сериализации, используя созданные rw-конфликты. Если они обнаруживают аномалии, то фиксируется только транзакция, зафиксированная первой, остальные транзакции прерываются (по схеме " first-committer-win").
Как работает SSI
В данном подразделе мы поговорим о том, как SSI разрешает проблему аномалии write-skew. Воспользуемся простой таблицей ’tbl’:
testdb=# CREATE TABLE tbl (id INT primary key, flag bool DEFAULT false); testdb=# INSERT INTO tbl (id) SELECT generate_series(1,2000); testdb=# ANALYZE tbl;
Транзакции Tx_A и Tx_B выполняют следующие команды (рис. 60).
Предположим, что все команды используют index scan. Поэтому при выполнении команд они считывают как кортежи кучи, так и индексные страницы, каждая из которых содержит индексный кортеж, указывающий на соответствующий кортеж кучи. См. рис. 61.
- T1: Tx_A выполняет команду SELECT. Эта команда считывает кортеж кучи (Tuple_2000) и одну страницу первичного ключа (Pkey_2);
- T2: Tx_B выполняет команду SELECT. Эта команда считывает кортеж кучи (Tuple_1) и одну страницу первичного ключа (Pkey_1);
- T3: Tx_A выполняет команду UPDATE для обновления Tuple_1;
- T4: Tx_B выполняет команду UPDATE для обновления Tuple_2000;
- T5: Tx_A фиксируется;
- T6: Tx_B фиксируется; однако быстро прерывается в следствие Write-Skew аномалии.
На рисунке 62 показано, как PostgreSQL обнаруживает и устраняет Write-Skew аномалию, описанную в приведенном выше примере.
T1:
- L1 и L2 относятся к Pkey_2 и Tuple_2000 соответственно.
- При выполнении команды SELECT в Tx_A функция CheckForSerializableConflictOut создает блокировки SIRead. В этом сценарии функция создает две блокировки SIRead: L1 и L2.
T2:
- При выполнении команды SELECT в Tx_B функция CheckForSerializableConflictOut создает две блокировки SIRead: L3 и L4.
- L3 и L4 относятся к Pkey_1 и Tuple_1 соответственно.
T3:
- При выполнении команды UPDATE для Tx_A до и после ExecUpdate вызываются CheckForSerializableConflictOut и CheckTargetForConflictsIN.
- В этом сценарии CheckForSerializableConflictOut ничего не делает.
- CheckForSerializableConflictIn создает rw-конфликт C1, который является конфликтом обоих Pkey_1 и Tuple_1 между Tx_B и Tx_A, поскольку и Pkey_1, и Tuple_1 были прочитаны Tx_B и записаны Tx_A.
T4:
- При выполнении команды UPDATE для Tx_B, CheckForSerializableConflictIn создает rw-конфликт C2, который является конфликтом Pkey_2 и Tuple_2000 между Tx_A и Tx_B.
- В этом сценарии C1 и C2 создают цикл в графе предшествования; таким образом, Tx_A и Tx_B находятся в несериализуемом состоянии. Однако обе транзакции Tx_A и Tx_B не были зафиксированы, поэтому CheckForSerializableConflictIn не прерывает Tx_B. Обратите внимание, что это происходит потому, что реализация SSI в PostgreSQL основана на схеме " first-committer-win ".
T5:
- Когда Tx_A пытается выполнить фиксацию, вызывается функция PreCommit_CheckForSerializationFailure, которая может обнаружить аномалии сериализации. В этом сценарии Tx_A фиксируется, потому что Tx_B все еще выполняется.
T6:
- Когда Tx_B пытается выполнить фиксацию, PreCommit_CheckForSerializationFailure обнаруживает аномалию сериализации, таким образом, Tx_B прерывается.
Другие сценарии
Кроме того, если команда UPDATE выполняется Tx_B после фиксации Tx_A (в точке T5), Tx_B немедленно прерывается, поскольку CheckForSerializableConflictIn, вызванная командой UPDATE Tx_B, обнаруживает аномалию сериализации (рис. 63(1)).
Если в T6 вместо COMMIT выполняется команда SELECT, Tx_B немедленно прерывается, потому что CheckForSerializableConflictOut, вызванная командой SELECT в Tx_B, обнаруживает аномалию сериализации (рис. 63(2)).
Здесь Вы найдете информацию о более сложных аномалиях.
Ложноположительные аномалии сериализации
При уровне изоляции SERIALIZABLE сериализуемость одновременных транзакций всегда гарантирована, поскольку ложноотрицательные аномалии сериализации исключены. Однако при некоторых обстоятельствах могут быть обнаружены ложноположительные аномалии. Ниже описаны ситуации, в которых PostgreSQL обнаруживает ложноположительные аномалии.
Ложноположительный сценарий 1
Рисунок 64 иллюстрирует сценарий, при котором возникает ложноположительная аномалия сериализации.
При реализации последовательного сканирования PostgreSQL создает блокировку SIRead на уровне отношения. На рисунке 65 (1) показаны блокировки SIRead и rw-конфликты, возникающие при последовательном сканировании. В этом случае создаются rw-конфликты C1 и C2, которые связаны с блокировкой SIRead D tbl, которые создают цикл в графе предшествования. Таким образом, обнаруживается ложноположительная аномалия Write-Skew.
Ложноположительный сценарий 2
Даже при использовании index scan, если обе транзакции Tx_A и Tx_B получают одну и ту же блокировку SIRead на уровне индекса, PostgreSQL обнаружит ложноположительную аномалию. На рисунке 66 показана именно такая ситуация.
Предположим, что страница Pkey_1 содержит два элемента, один из которых указывает на Tuple_1, а другой - на Tuple_2.
Когда Tx_A и Tx_B выполняют команды SELECT и UPDATE, Pkey_1 считывается и записывается как Tx_A, так и Tx_B. В этом случае rw-конфликты C1 и C2, оба из которых связаны с Pkey_1, создают цикл в графе предшествования; таким образом, обнаруживается ложноположительная аномалия Write-Skew.
(Если Tx_A и Tx_B получают блокировки SIRead разных индексных страниц, ложное срабатывание не обнаруживается, и обе транзакции могут быть зафиксированы).
