Информатика · объяснение и практика

Согласованный снимок не защищает ограничение между разными строками

Построить аномалию write skew при изоляции снимка и показать, почему отсутствие одновременной записи одной строки не обеспечивает сериализуемость.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Таблицы, базы данных и SQL · Учебная карта

Главная мысль

При изоляции снимка транзакции могут читать один согласованный прошлый снимок и успешно записывать разные строки. Если правило связывает эти строки, обе локально разумные записи вместе способны нарушить инвариант. Такая аномалия называется write skew.

Метод и постановка

Сформулируйте инвариант до рассмотрения уровня изоляции. Например, из двух дежурных хотя бы один обязан оставаться на смене. Каждая транзакция читает обоих, убеждается, что второй остаётся, и снимает со смены только себя. Отдельная запись соответствует правилу при данных, которые транзакция видела.

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

Проверка и границы вывода

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

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

Пример

Сначала A=дежурит и B=дежурит. T₁ читает обе строки, видит B на смене и пишет A=нет. T₂ на старом снимке видит A на смене и пишет B=нет. Записи не пересекаются.

После обеих фиксаций нет ни одного дежурного. В порядке T₁ затем T₂ вторая увидела бы A=нет и не сняла бы B. Симметрично другой порядок тоже сохранил бы одного дежурного.

От чтения к действию

А теперь — вы

Почему проверка конфликтов записи одной строки может пропустить write skew?

Частые вопросы

Снимок сам по себе несогласован?

Нет. Каждый снимок может быть корректным прошлым состоянием; проблема в совместимости решений.

После ошибки сериализации повторяют только UPDATE?

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

Углублённый разбор

Опасная структура антизависимостей SSI

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

Перед началом: Изоляция снимка; Граф версионных зависимостей.

Антизависимость направлена от читателя старой версии

Если T₁ прочитала старую версию x, а конкурентная T₂ записала новую версию, невидимую этому снимку, возникает rw-антизависимость T₁→T₂. Для последовательного объяснения такого чтения T₁ должна предшествовать T₂. Это направление противоположно интуиции «писатель перед читателем», которая подходит к чтению уже записанной версии, то есть wr-зависимости.

При изоляции снимка каждый цикл сериализации содержит два соседних rw-ребра T₁→T₂→T₃ с соответствующим ограничением порядка фиксаций: T₃ фиксируется первой в рассматриваемом цикле. Поэтому контроль таких структур позволяет предотвращать все циклы, не дожидаясь обнаружения полного пути обратно. При цикле длины два крайние транзакции структуры могут совпадать.

Необходимый фрагмент цикла не является достаточным

В ориентированном графе путь из двух рёбер может существовать без обратного пути. Поэтому наличие опасной цепочки совместимо с ацикличным графом и корректным последовательным объяснением. Консервативное прерывание в такой ситуации является ложноположительным относительно действительного цикла, но не нарушает обещание сериализуемости успешно завершённых транзакций.

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

Различайте предсказание риска и доказательство аномалии

В отчёте полезно записать для каждого rw-ребра объект и старую версию, которую увидел читатель. Отдельно укажите начала снимков и фиксации. Иначе можно ошибочно построить антизависимость между транзакциями, которые вовсе не были конкурентными. Для сравнения построение замыкающего ребра должно опираться на дополнительное чтение, а не на произвольную стрелку рисунка.

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

Цепочка без обратного пути

Условие. Все три транзакции читают исходный снимок x=y=u=0. T₁ читает x и пишет u=1; T₂ читает y и пишет x=1; T₃ пишет y=1. Фиксации идут T₃,T₂,T₁. Найдите зависимости и последовательное объяснение.

  1. Чтение x=0 в T₁ даёт rw-ребро T₁→T₂. Чтение y=0 в T₂ даёт rw-ребро T₂→T₃. Запись u никем не читается.
  2. Получилась опасная цепочка с первой фиксацией T₃, но обратного пути T₃→T₁ нет. Граф остаётся ацикличным.
  3. Последовательный порядок T₁,T₂,T₃ воспроизводит оба нулевых чтения и итоговые записи. Порядок фиксаций конкурентных транзакций не обязан совпадать с порядком их сериализации.
  4. Если дополнительно T₃ прочитает u=0 на том же старом снимке, появится T₃→T₁. Тогда цикл действительно замкнётся и ни один последовательный порядок не сохранит все три чтения.

Ответ. Исходная цепочка сериализуема; добавленное чтение u в T₃ создаёт настоящий цикл.

Проверка. Перебор шести последовательных порядков на исходных данных находит T₁,T₂,T₃; после добавления чтения u=0 допустимых порядков нет.

Где легко ошибиться. Не называйте любую пару соседних rw-антизависимостей доказанным циклом. Опасная структура — консервативный сигнал; для аномалии нужен полный несовместимый набор зависимостей.

Проверьте понимание

Доказывает ли исходная цепочка T₁→T₂→T₃ существование цикла?

Вопросы к этой главе

Ложноположительное прерывание нарушает сериализуемость?

Нет. Оно отклоняет часть безопасных историй, уменьшая конкурентность, но не разрешает опасным транзакциям успешно зафиксироваться вместе.

Почему T₁ тоже что-то записывает?

Это исключает особые оптимизации чисто читающей транзакции из иллюстрации. Запись u пока никем не читается и сама по себе не замыкает цепочку.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Ports and Grittner: Serializable Snapshot Isolation

    Прочитаны §3.2 Theorem1 о двух соседних rw-антизависимостях, порядок commit и §3.3.1 о false positives. Собственная ацикличная цепь и её замыкание третьим чтением построены отдельно; не утверждается точный выбор жертвы конкретной версии PostgreSQL.

Материализация инварианта для конфликта записи

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

Перед началом: Write skew; Атомарная транзакция со снимком.

Инвариант получает явно записываемый представитель

Пусть суммарные резервы разных строк не должны превышать бюджет B. Если каждая транзакция читает старую сумму и пишет только собственную строку, записи могут не пересекаться. Введём строку с остатком R=B−Σ резервов. Каждый успешный резерв размера d обязан в одной транзакции проверить R≥d, уменьшить R на d и создать соответствующую запись резерва.

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

Доказательство идёт по успешно зафиксированным шагам

Изначально R=B и резервов нет. Если перед транзакцией равенство R=B−Σ резервов верно, то атомарное добавление d к резервам и вычитание d из R сохраняет его. Проверка R≥d обеспечивает R≥0 после шага. Значит, по индукции любой последовательный порядок успешно выполненных резервирований сохраняет и учётное равенство, и бюджетное ограничение.

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

Общий конфликт уменьшает независимость операций

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

Повторять после конфликта нужно всю транзакцию. Повтор старой команды «записать остаток четыре» без свежей проверки может потерять чужое изменение. Конкретные СУБД различаются по ожиданиям, ошибкам и проверкам обновлений, поэтому необходимо опираться на документированную модель. Здесь предполагается обнаружение конкурирующих записей одного объекта, а не универсальное поведение любой настройки с названием snapshot.

Две заявки по шесть при бюджете десять

Условие. Изначально R=10 и резервов нет. Две конкурентные транзакции хотят зарезервировать по 6 в разных предметных строках; обе читают R=10. Как общий остаток меняет исход?

  1. Без общего записываемого объекта обе могли бы создать свои строки и получить суммарный резерв 12, превышающий бюджет десять.
  2. В новой схеме каждая пытается записать R=4 вместе со своим резервом. Общая строка создаёт конфликт записи; пусть первая транзакция фиксируется, а вторая откатывается.
  3. После полного повтора вторая читает уже R=4. Условие 4≥6 ложно, поэтому новый резерв не создаётся.
  4. Итог: один резерв размера шесть и остаток четыре. Равенство R+Σ резервов=10 выполнено, а отрицательного остатка и потерянной записи нет.

Ответ. Успешен один резерв; остаток равен 4. Вторая заявка после повтора отклоняется.

Проверка. Перебор двух порядков успешной попытки и повторной проверки даёт симметричные допустимые исходы с одним резервом; индукционное равенство проверяется после каждого атомарного шага.

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

Проверьте понимание

Каков итоговый остаток после корректного повтора?

Вопросы к этой главе

Можно просто блокировать свою строку резерва?

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

Отмена тоже требует обновления остатка?

Да. Освобождение d единиц и удаление или изменение резерва должны сохранять то же учётное равенство в одной транзакции. Иначе доступный бюджет станет неверным.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • PostgreSQL18: Repeatable Read and concurrent updates

    Прочитана невозможность обновить строку, изменённую после начала снимка, и требование полного повтора транзакции. Собственная схема остатка бюджета материализует общий конфликт записи; это модельный расчёт, не выполненная SQL-миграция.

Незавершённая транзакция тоже должна видеть согласованное состояние

Отменённая транзакция уже могла выполнить вычисления по прочитанным данным. Поэтому для transactional memory недостаточно проверить лишь успешно зафиксированную часть истории. Opacity требует согласованного последовательного объяснения наблюдений также для отменённых и ещё живых транзакций.

Перед началом: Сериализуемость транзакций; Чтение версии.

Откат записи не отменяет опасное наблюдение

Проверка сериализуемости только committed-транзакций может проигнорировать читателя, которому уже вернули несовместимые значения. В программе с общей памятью такой читатель способен вычислить неверный адрес, нарушить предположение о длине массива или зациклиться ещё до попытки commit. Последующий abort не стирает исполненные инструкции. Поэтому состояние, видимое незавершённому коду, является самостоятельной частью договора.

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

Живые префиксы нельзя отложить до успешного commit

Незавершённые транзакции при проверке дополняются согласованным завершением; до запроса commit их нельзя произвольно сделать committed, чтобы оправдать чужие чтения. В нашем примере писатель уже завершён, поэтому неоднозначности его статуса нет. Читателю требуется один последовательный момент относительно всего писателя, а не до него по x и после него по y.

Реализация должна обеспечивать корректное наблюдение на каждом возникающем префиксе исполнения. В формулировке статьи 2008 свойство отдельной истории задаётся через допустимое завершение; само множество таких историй не объявляется замкнутым по префиксам. Это различие не меняет практического требования: нельзя разрешить опасное чтение сейчас и обещать исправить его будущим abort. Проверяется весь уже наблюдённый набор возвратов.

Обнаружить конфликт нужно до выдачи несовместимого результата

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

Это сильнее простого требования не читать незавершённые записи. Даже чтения только начальных или уже committed-значений могут сочетаться в несуществовавший вид одной транзакции. Не следует путать этот пример с write skew: здесь нарушено согласование наблюдений одного отменённого читателя, а не общий инвариант после двух успешных независимых записей.

Отменённый читатель смешал две версии

Условие. Изначально x=y=0. Транзакция R читает x→0. Затем W записывает x=1,y=1 и успешно фиксируется. После этого R читает y→1 и отменяется. Других транзакций и записей нет. Достаточно ли законности committed-проекции?

  1. После удаления R остаётся единственная W, которая законно переводит (0,0) в (1,1). Committed-проекция сериализуема.
  2. Для полного последовательного объяснения есть лишь два относительных порядка R и W. Если R раньше W, оба её чтения обязаны вернуть 0; чтение y→1 невозможно.
  3. Если W раньше R, оба чтения R обязаны вернуть 1; чтение x→0 невозможно. Перекрытие интервалов разрешает оба порядка, но ни один не подходит.
  4. Отмена R не изменяет уже возвращённые 0 и1. Следовательно полная история не opaque, хотя итоговое состояние и committed-проекция выглядят корректно.

Ответ. Committed-проекция законна, opacity нарушена из-за несовместимого наблюдения отменённой R.

Проверка. Независимый перебор двух последовательных порядков даёт вектор чтений R либо (0,0), либо (1,1). Наблюдавшийся (0,1) отсутствует. Если вместо возврата второго чтения R немедленно отменить, этот конкретный контрпример исчезнет.

Где легко ошибиться. Не вычёркивайте отменённые чтения из проверки безопасности кода. Abort исключает их записи из общего состояния, но не переписывает уже выполненные наблюдения.

Проверьте понимание

Как классифицируется заданная история с отменённой R?

Вопросы к этой главе

Читатель здесь видел dirty read?

Нет. Ноль был начальным значением, единица y прочитана после commit W. Ошибка в сочетании двух законных по отдельности значений внутри одного транзакционного наблюдения.

Можно ли позволить R прочитать старое y=0 после commit W?

При их перекрытии это может соответствовать последовательному порядку R перед W. Для данного примера согласованный старый вид допустим; порядок реального времени запрещал бы такой перенос, если бы R началась только после завершения W.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Guerraoui, Kapałka: On the Correctness of Transactional Memory, §5.1–5.2

    Прямое открытие сначала вернуло 403; затем поисковая индексированная PDF-копия дала читаемый текст. Прочитаны Complete(H), legal transactions, real-time order и Definition1. В версии 2008 множество отдельных opaque histories не объявлено prefix-closed; реализация должна обеспечивать условие для каждого возникающего префикса. Complexity lower bound не используется.

Оптимистическая транзакция валидирует прочитанное перед записью

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

Перед началом: Наборы чтения и записи транзакции; Сериализуемость и конфликт чтения с записью.

Три фазы и выбранная модель

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

Достаточное правило проверяет каждую транзакцию U, опубликованную после начала T: необходимо WS(U)∩RS(T)=∅. Если пересечение непусто, T отменяют. Это консервативная проверка целого интервала, а не точная реализация всех вариантов оптимистического контроля. Изменение прочитанного ключа до фактического чтения тоже может вызвать лишний отказ, но не ложное разрешение устаревшего вычисления.

Почему учитывается чтение, а не только будущая запись

Успешная валидация разрешает поместить T после всех ранее опубликованных транзакций в последовательном объяснении. Их записи не затронули RS(T) за проверяемый интервал, поэтому использованные значения не устарели. Изменения WS(T) становятся видимыми только теперь. Две транзакции могут писать разные ключи и всё равно конфликтовать, если решение каждой зависело от ключа, изменённого другой.

Пусть x=y=0 и прикладное ограничение требует x+y≤1. Обе транзакции читают x, y. T1 при двух нулях намерена установить x=1, а T2 — y=1. У них непересекающиеся наборы записи{x} и{y}, но общий набор чтения{x, y}. Без проверки обе частные идеи дали бы недопустимое состояние(1,1).

Отмена и границы гарантии

Если T1 валидируется первой, она проходит проверку и публикует x=1. T2 обнаруживает WS(T1)∩RS(T2)={x} и отменяется, не публикуя y=1. После перезапуска она видит(1,0), поэтому исходное условие двух нулей уже не выполняется. Проверку нельзя отделить от записи незащищённым промежутком: туда могла бы попасть новая фиксация, которую проверка не учла.

Ключевые множества не описывают фантомы автоматически. Запрос «в таблице нет строк этого типа» зависит и от возможных вставок; ему нужны отслеживание предиката или другой подходящий механизм. Показанное правило гарантирует корректность рассмотренной модели при полном учёте зависимостей. Оно не обещает безопасность внешних действий, выполненных до проверки, или отсутствие повторных отмен под высокой конкуренцией.

Разные записи, общая причина для отмены

Условие. При x=y=0 обе транзакции прочитали x, y. T1 собирается записать x=1, T2 — y=1, каждая только при двух нулях. T1 валидируется и публикуется первой. Примените указанную последовательную валидацию и проверьте x+y≤1.

  1. Для обеих RS={x, y}; WS(T1)={x}, WS(T2)={y}. До T1 после их начала никто не публиковался.
  2. T1 проходит проверку и атомарно публикует x=1. Состояние становится(1,0).
  3. T2 проверяет новую публикацию T1: пересечение{x}∩{x, y}={x} непусто. T2 отменяется, хотя наборы записи взаимно не пересекаются.
  4. Перезапущенная T2 читает(1,0). Условие двух нулей ложно, запись y=1 не выполняется. Ограничение x+y≤1 сохранено.

Ответ. Первая транзакция фиксируется, вторая отменяется по конфликту записи с её набором чтения. Итог после повторной проверки —(1,0).

Проверка. Если разрешить обе частные записи, получилось бы(1,1) с суммой 2. Перестановка порядка валидации симметрично оставляет(0,1), также с суммой 1.

Где легко ошибиться. Не проверяйте только пересечение двух наборов записи: устаревшее прочитанное условие может привести к ошибке даже при разных изменяемых ключах.

Проверьте понимание

Что должна сделать T2 после публикации x=1 транзакцией T1?

Вопросы к этой главе

Почему проверка с записью должна быть защищена вместе?

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

Любая отмена означает, что сериализация была невозможна?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Kung–Robinson1981: optimistic concurrency control

    Фазы чтения, валидации и записи и вариант с последовательной финальной проверкой. Двухключевой пример и явно ограниченная консервативная проверка составлены для главы.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться