По какому признаку граф зависимостей показывает, что конкурентное выполнение транзакций неэквивалентно ни одному последовательному порядку?
Признак — наличие цикла в графе зависимостей транзакций. Если цикл есть, конкурентное выполнение не является конфликтно-сериализуемым: невозможно выстроить транзакции в последовательный порядок, сохраняющий все существенные зависимости. Если граф ацикличен, его топологическая сортировка задаёт эквивалентный последовательный порядок.
Последовательное выполнение транзакций проще для рассуждения: каждая транзакция видит полностью завершённое состояние предыдущей. Но такое выполнение плохо использует параллелизм, поэтому теория сериализуемости появилась как способ разрешить конкурентное выполнение без потери корректности последовательного результата.
Граф зависимостей даёт практический критерий для одного из распространённых вариантов сериализуемости — конфликтной сериализуемости. Он позволяет анализировать порядок конфликтующих операций, не перебирая все возможные состояния базы данных.
Две транзакции могут обращаться к одному объекту данных, перемежая операции чтения и записи. Если порядок этих операций создаёт взаимные требования вроде «первая должна идти раньше второй» и одновременно «вторая должна идти раньше первой», результат нельзя объяснить никаким последовательным запуском.
Такое выполнение опасно даже тогда, когда каждая отдельная транзакция корректна. Оно может привести к результату, который не соответствует ни одному допустимому порядку обслуживания транзакций, поэтому проверка только итоговых значений недостаточна.
В графе каждая транзакция представлена вершиной. Для двух операций разных транзакций добавляют ориентированное ребро от транзакции, чья конфликтующая операция выполнена раньше, к другой транзакции.
Конфликт возникает, когда операции относятся к одному объекту данных, принадлежат разным транзакциям и хотя бы одна из них является записью. Поэтому учитываются пары чтение–запись, запись–чтение и запись–запись. Два чтения одного объекта конфликтом не считаются.
Например, если транзакция A записала объект до чтения этого объекта транзакцией B, появляется ребро A → B. Если позднее другая пара операций требует B → A, возникает цикл A → B → A.
Цикл означает противоречие ограничений порядка. Чтобы сохранить зависимость A → B, A должна идти раньше B, но зависимость B → A требует обратного. Поэтому эквивалентного последовательного расписания нет.
При отсутствии циклов граф можно топологически отсортировать. Полученный порядок транзакций сохраняет направление всех конфликтов, значит, расписание конфликтно-сериализуемо. Это не означает, что транзакции фактически выполнялись последовательно: независимые операции могли выполняться параллельно.
Критерий ограничен конфликтной сериализуемостью. Существуют расписания, которые могут быть сериализуемыми в более общем смысле, но не проходят этот критерий. На практике СУБД часто предотвращают циклические зависимости блокировками либо обнаруживают опасные зависимости и прерывают одну из транзакций; конкретный механизм зависит от СУБД и уровня изоляции.
Сервис резервирования изменяет остаток доступных мест, а параллельный сервис обновляет цену той же позиции. При неудачном дизайне операции могут выполняться в разном порядке: первая транзакция сначала меняет остаток, а затем читает цену, вторая сначала меняет цену, а затем читает остаток. Граф получает зависимости в обе стороны и содержит цикл.
Вариант с игнорированием проблемы проще, но может сохранить некорректное конкурентное расписание. Полная сериализация всех транзакций устраняет цикл, однако снижает пропускную способность и увеличивает ожидание.
Более подходящее решение — унифицировать порядок обращения к общим объектам, например всегда сначала обрабатывать позицию товара, затем запись цены, и дополнительно применять подходящий механизм блокировок или проверки сериализуемости. Это устраняет источник циклов, сохраняет параллелизм независимых операций и уменьшает число взаимных ожиданий.
Вопрос: Достаточно ли отсутствия цикла в графе, чтобы гарантировать корректность бизнес-правил?
Ответ: Нет. Ацикличность гарантирует только конфликтную сериализуемость рассмотренного расписания. Если само последовательное выполнение не проверяет бизнес-инвариант, сериализация лишь воспроизведёт эту ошибку. Кроме того, граф должен учитывать все операции и конфликты, относящиеся к анализируемому расписанию.
Вопрос: Почему два чтения одного объекта не создают ребро между транзакциями?
Ответ: Чтения не изменяют состояние и не требуют разного порядка для сохранения результата. Перестановка двух чтений не меняет значения данных, которые они видят в рамках фиксированного расписания. Поэтому для конфликтной сериализуемости значимы пары, где хотя бы одна операция записывает объект.
Вопрос: Что означает цикл в графе для механизма блокировок?
Ответ: Цикл зависимостей не всегда буквально означает цикл ожидания блокировок, но показывает несовместимый порядок конфликтующих операций. При строгом двухфазном блокировании такой конфликт может проявиться как взаимная блокировка, которую СУБД должна обнаружить и разрешить откатом одной транзакции. При неблокирующих подходах, например оптимистической проверке сериализуемости, одна из транзакций может быть прервана уже при фиксации из-за обнаруженного опасного цикла.