Эта статья является конспектом книги «Designing Data-Intensive Applications».

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

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

Асимметрия записи и фантомы

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

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

Рис. 1 - Пример асимметрии записи, вызванной ошибкой в коде приложения

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

Такая аномалия носит название асимметрии записи (write skew). Это не «грязная» операция записи и не потеря обновления, поскольку две наши транзакции обновляют два различных объекта. Наличие конфликта тут менее заметно, но это, безусловно, состояние гонки: если две транзакции выполнялись бы одна за другой, то второй врач не получил бы отгула.

Асимметрию записи можно рассматривать как обобщение проблемы потери обновлений. Эта асимметрия может происходить при чтении двумя транзакциями одних и тех же объектов с последующим обновлением некоторых из них (различные транзакции могут обновлять разные объекты). В частном случае, когда различные транзакции обновляют один объект, происходит «грязная» операция записи или потеря обновления (в зависимости от хронометража).

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

BEGIN TRANSACTION;

SELECT * FROM doctors
WHERE on_call = true
AND shift_id = 1234 FOR UPDATE;

UPDATE doctors
SET on_call = false
WHERE name = 'Alice'
AND shift_id = 1234;

COMMIT;

Предложение FOR UPDATE указывает базе установить блокировку на все возвращенные данным запросом строки.

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

Такой эффект, при котором операция записи в одной транзакции меняет результат запроса на поиск в другой, называется фантомом (phantom).

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

Сериализуемость

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

Но если сериализуемость настолько лучше более слабых уровней изоляции, почему бы не использовать ее повсеместно? Для ответа на данный вопрос рассмотрим вероятные реализации сериализуемости и их производительность. Большинство современных БД, обеспечивающих сериализуемость, применяют один из трех методов:

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

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

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

Хотя эта идея довольно очевидна, создатели баз данных только относительно недавно решили, что однопоточный цикл выполнения транзакций оправдывает себя. Как случилось, что однопоточное выполнение стало считаться допустимым?

Этот пересмотр концепции был вызван двумя факторами.

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

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

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

Двухфазная блокировка (2PL). В течение долгого времени в базах данных широко использовался только один алгоритм сериализуемости: двухфазная блокировка (two-phase locking, 2PL).

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

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

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

Из-за столь большого количества блокировок часто встречается ситуация, когда транзакция A ждет снятия блокировки транзакции B и наоборот. Такая ситуация называется взаимной блокировкой (deadlock). База данных автоматически обнаруживает взаимные блокировки между транзакциями и прерывает одну из них, чтобы остальные могли продолжить работу.

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

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

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

Сериализуемая изоляция снимков состояния (SSI). В этом конспекте мы увидели довольно мрачную картину управления конкурентным доступом в БД. С одной стороны, имеющиеся реализации сериализуемости или демонстрируют низкую производительность (двухфазная блокировка), или плохо масштабируются (последовательное выполнение). С другой — слабые уровни изоляции показывают высокую производительность, но подвержены различным состояниям гонки (потеря обновлений, асимметрия записи, фантомы и т. д.). Так что же, сериализуемая изоляция и хорошая производительность — вещи принципиально взаимоисключающие?

Очень многообещающим представляется алгоритм под названием «сериализуемая изоляция снимков состояния» (serializable snapshot isolation, SSI). Он обеспечивает полную сериализуемость за счет лишь небольшого снижения производительности по сравнению с обычной изоляцией снимков состояния. SSI — относительно новый метод: он был впервые описан в 2008 году.

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

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

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

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

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

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

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

Выявление операций чтения устаревших версий MVCC объектов. Изоляция снимков состояния обычно реализуется с помощью MVCC. Транзакция, читающая из согласованного снимка состояния в базе данных MVCC, игнорирует все операции записи, которые были выполнены транзакциями, еще не зафиксированными на момент получения снимка состояния. На рис. 2 транзакция 43 видит, что Алиса находится на дежурстве (on_call = true), поскольку транзакция 42 не зафиксирована. Однако на момент фиксации транзакции 43 транзакция 42 уже зафиксирована. Это значит, что операция записи, проигнорированная при чтении из согласованного снимка состояния, теперь уже вступила в силу и исходные условия транзакции 43 более не соответствуют действительности.

Рис. 2 - Выявление чтения транзакцией устаревших значений из снимка состояния MVCC

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

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

Рис. 3 - Выявление при сериализуемой изоляции снимков состояния случаев модификации транзакцией данных, прочитанных другой транзакцией

На рис. 3 обе транзакции, 42 и 43, выполняют поиск дежурящих в смену 1234 врачей. При наличии индекса по shift_id база может воспользоваться его записью 1234, чтобы отметить факт чтения транзакциями 42 и 43 этих данных (если индекса нет, информацию можно отслеживать на уровне таблицы). Сама информация требуется только временно: после завершения выполнения транзакции (ее фиксации или прерывания) и завершения всех конкурентных транзакций БД может спокойно «забыть» о том, какие данные читались этой транзакцией.

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

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

Вывод

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

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

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

«Грязные» операции чтения. Клиент читает записанные другим клиентом данные до их фиксации. Уровень изоляции чтения зафиксированных данных и более сильные предотвращают «грязные» операции чтения.
«Грязные» операции записи. Клиент перезаписывает данные, которые другой клиент записал, но еще не зафиксировал. Практически все реализации транзакций предотвращают «грязные» операции записи.
Асимметрия чтения (невоспроизводимое чтение). Клиент видит различные части базы данных по состоянию на разные моменты времени. Чаще всего такую проблему предотвращают с помощью изоляции снимков состояния, при которой транзакция читает данные из согласованного снимка состояния, соответствующего определенному моменту времени. Обычно это реализуется благодаря многоверсионному управлению конкурентным доступом (MVCC).
Потерянные обновления. Два клиента выполняют в конкурентном режиме цикл чтения — изменения — записи. Один переписывает записанные другим данные без учета внесенных им изменений, так что данные оказываются потеряны. Некоторые реализации изоляции снимков состояния предотвращают эту аномалию автоматически, а в других требуется установка блокировки вручную (SELECT FOR UPDATE).
Асимметрия записи. Транзакция читает какие-либо данные, принимает на основе прочитанного значения решение о дальнейших действиях и выполняет операцию записи в базу данных. Однако на момент ее выполнения исходные условия, на основе которых принималось решение, более не соответствуют действительности. Эту аномалию предотвращает только сериализуемость.
Фантомные чтения. Транзакция читает объекты, соответствующие определенному условию поиска. Другой клиент выполняет операцию записи, которая каким-то образом влияет на результаты этого поиска. Изоляция снимков состояния предотвращает непосредственно фантомные чтения, но фантомы в контексте асимметрии записи требуют отдельной обработки, например, блокировок по диапазону значений индекса.

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

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

Ссылки на все части

Транзакции. Часть 2. Конспект книги «Designing Data-Intensive Applications»