Эта статья является конспектом книги Designing Data-Intensive Applications.
В предыдущем конспекте мы рассмотрели грязную операцию записи это разновидность состояния гонки, возникающая при попытке конкурентной записи в одни объекты различными транзакциями. К этой категории проблем также относится ситуация потери обновления.
Однако на этом список возможных состояний гонки, возникающих при конкурентных операциях записи не заканчивается. В этом конспекте рассмотрим более сложные примеры конфликтов и то, как с ними бороться. Далее затронем изоляцию уровня сериализуемости, в том числе различные методы, которые обеспечивают сериализуемость. И в конце подведем итоги по транзакциям.
Асимметрия записи и фантомы
Представим, что мы создаем приложение для врачей, предназначенноедля организации смен дежурств в больнице. Больницы обычно стараются, чтобыв каждый момент времени было по возможности несколько дежурных врачей, ноточно не меньше одного. Врачи могут отказываться от дежурств при условии, что хотя бы один их коллега остается на дежурстве.
Теперь представим, что Алиса и Боб два дежурных доктора на конкретной смене.Оба плохо себя чувствуют, и оба решили попросить отгул. К сожалению, они нажали на кнопку запроса отгула примерно в одно время. Происходящее после этогопоказано на рис. 1.
Рис. 1 - Пример асимметрии записи,
вызванной ошибкой в коде приложения
В каждой из транзакций приложение сначала проверяет наличие в данный моментдвух или более дежурных врачей. При положительном результате оно считает, чтоможно безопасно дать одному из врачей отгул. Поскольку база данных используетизоляцию снимков состояния, обе проверки возвращают 2 и выполнение обеих транзакций продолжается. Алиса и Боб успешно обновляют свой график и получают отгул. Происходит фиксация обеих транзакций, после чего оказывается, что ни одного дежурного врача нет. Требование наличия хотя бы одногодежурного врача оказалось нарушено.
Такая аномалия носит название асимметрии записи (write skew). Это не грязная операция записи и не потеря обновления, поскольку две наши транзакции обновляют два различных объекта. Наличие конфликта тут менее заметно, но это, безусловно, состояние гонки:если две транзакции выполнялись бы одна за другой, то второй врач не получил быотгула.
Асимметрию записи можно рассматривать как обобщение проблемы потери обновлений. Эта асимметрия может происходить при чтении двумя транзакциямиодних и тех же объектов с последующим обновлением некоторых из них (различныетранзакции могут обновлять разные объекты). В частном случае, когда различныетранзакции обновляют один объект, происходит грязная операция записи илипотеря обновления (в зависимости от хронометража).
Если использовать уровень сериализуемости невозможно, то вторым лучшим решением будет, вероятно, явная блокировка строк, необходимых для транзакции. В примере с врачами можно написать примерно следующиезапросы:
BEGIN TRANSACTION;SELECT * FROM doctorsWHERE on_call = trueAND shift_id = 1234 FOR UPDATE;UPDATE doctorsSET on_call = falseWHERE 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). Довольно свежий алгоритм,лишенный практически всех недостатков предыдущих подходов. В нем используется оптимистический подход, благодаря чему транзакции выполняются без блокировок. Перед фиксацией транзакции выполняется проверка,и если выполнение было несериализуемым, то транзакция прерывается безфиксации.
