1. Репликация
  2. Репликация с несколькими ведущими узлами
  3. Конкурентные операции
  4. Секционирование
  5. Транзакции
  6. Слабые уровни изоляции

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

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

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

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

Read committed

Он обеспечивает две гарантии.

  • При чтении из БД клиент видит только зафиксированные данные (никаких «грязных» операций чтения).
  • При записи в БД можно перезаписывать только зафиксированные данные (никаких «грязных» операций записи).

Никаких «грязных» операций чтения

Представьте, что транзакция записала какие-то данные в базу, но еще не была зафиксирована или была прервана. Может ли другая транзакция увидеть эти незафиксированные данные? Если да, то такая операция чтения называется «грязной»(dirty read).

Выполняемые при уровне изоляции транзакций read committed (чтение зафиксированных данных) транзакции должны предотвращать «грязные» операции чтения.

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

Несколько причин, по которым следует избегать «грязных» операций чтения.

  • Когда в транзакции необходимо обновить значения нескольких объектов, «грязная» операция чтения означает, что другие транзакции могут увидеть часть обновлений, но не все.
  • В случае прерывания транзакции необходимо откатить все уже выполненные ею операции записи. Если база допускает «грязные» операции чтения, то транзакции могут видеть данные, которые потом подвергнутся откату, то есть так и не зафиксированные в БД.

Никаких «грязных» операций записи

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

Если более ранняя операция записи является частью еще не зафиксированной транзакции, тогда более поздняя транзакция перезаписывает незафиксированное значение. Это называется «грязной» операцией записи.

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

Реализация read committed

read committed — очень популярный уровень изоляции. Он используется по умолчанию в Oracle 11g, PostgreSQL, SQL Server 2012, MemSQL и многих других базах данных.

Чаще всего базы используют блокировки строк для предотвращения «грязных» операций записи: прежде чем модифицировать конкретный объект (строку или документ), транзакция должна сначала установить блокировку на этот объект. Данная блокировка должна удерживаться вплоть до фиксации или прерывания транзакции. Удерживать блокировку на конкретный объект может только одна транзакция одновременно, другой транзакции, желающей выполнить операцию записи в этот объект, придется дождаться фиксации или прерывания первой транзакции и лишь затем получить на него блокировку и продолжить свою работу. Подобные блокировки выполняются базами автоматически в режиме read committed (и на более сильных уровнях изоляции). ‰ Как же предотвратить «грязные» операции чтения? Одна из возможностей: воспользоваться теми же блокировками и потребовать, чтобы желающие прочитать объект транзакции устанавливали блокировку, освобождая ее сразу же после чтения. Это гарантирует, что чтение не будет производиться при «грязном», незафиксированном значении объекта (поскольку в данное время блокировка удерживается транзакцией, выполняющей операцию записи).

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

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

Snapshot isolation и repeatable read

На первый взгляд уровня изоляции read committed вполне достаточно для транзакций: оно позволяет прерывать транзакции (что требуется для атомарности), предотвращает чтение промежуточных результатов транзакций и предотвращает смешивание конкурентных операций записи. Конечно, это полезные возможности и намного более сильные гарантии, чем у систем без транзакций.

Однако на этом уровне изоляции все еще существует множество возможных ошибок конкурентного доступа.

Допустим, у Алисы есть в банке $1000 сбережений, разбитых между двумя счетами, на каждом из которых лежит по $500. Транзакция переводит $100 с одного принадлежащего Алисе счета на другой. Если ей не повезло и она посмотрит на перечень балансов своих счетов в момент обработки этой транзакции, то увидит баланс одного счета до поступления входящего платежа (когда баланс равен $500), а другой — после выполнения исходящего платежа (когда новый баланс равен $400). Алисе покажется при этом, что общая сумма на ее счетах равна $900 — $100 как будто провалились сквозь землю.

Подобная аномалия носит название невоспроизводимого чтения (nonrepeatable read) или асимметрии чтения (read skew).

В некоторых ситуациях подобные временные несоответствия недопустимы.

  • Резервное копирование. Резервная копия представляет собой копию всей базы данных, и ее создание на большой БД может занять несколько часов. Операции записи в базу продолжают выполняться во время создания резервной копии. Следовательно, может оказаться, что одни части копии содержат старые версии данных, а другие — новые. В случае восстановления БД из подобной резервной копии упомянутые расхождения (например, пропавшие деньги) станут из временных постоянными.
  • Аналитические запросы и проверки целостности. Иногда приходится выполнять запросы, просматривающие значительные части базы данных. Подобные запросы — частое явление в аналитике. Они также могут быть частью периодической проверки целостности (мониторинга на предмет порчи данных). Если подобные запросы будут видеть разные части БД по состоянию на различные моменты времени, то их результаты будут совершенно бессмысленными.

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

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

Реализация snapshot isolation

Подобно уровню изоляции read committed, реализации snapshot isolation обычно используют блокировки записи для предотвращения «грязных» операций записи. Это значит, выполняющая операцию записи транзакция может блокировать выполнение другой транзакции, записывающей в тот же объект. Однако операции чтения не требуют никаких блокировок. С точки зрения производительности основной принцип изоляции снимков состояния звучит как «чтение никогда не блокирует запись, а запись — чтение». Благодаря этому база данных способна выполнять длительные запросы на чтение, продолжая в то же время обработку операций записи, без какой-либо конкуренции блокировок между ними.

БД должна хранить для этого несколько различных зафиксированных версий объекта, поскольку разным выполняемым транзакциям может понадобиться состояние базы на различные моменты времени. Вследствие хранения одновременно нескольких версий объектов этот метод получил название многоверсионного управления конкурентным доступом (multiversion concurrency control, MVCC).

Если базе необходима только изоляция read committed, но не уровня snapshot isolation, достаточно было бы хранить только две версии объекта: зафиксированную версию и перезаписанную, но еще не зафиксированную версию.

Однако поддерживающие изоляцию снимков состояния подсистемы хранения обычно используют MVCC и для изоляции read committed. При этом обычно при чтении таких данных применяется отдельный снимок состояния для каждого запроса, а при snapshot isolation — один и тот же снимок состояния для всей транзакции.

Обновление превращается внутри базы данных в удаление и создание. Например, транзакция 13 снимает $100 со счета 2, изменяя баланс с $500 на 400. Таблица accounts после этого содержит две строки для счета 2: строку с балансом $500, помеченную как удаленную транзакцией 13, и созданную транзакцией 13 строку с балансом $400.

Правила видимости для согласованных снимков состояния

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

  1. В начале каждой транзакции база данных создает список всех остальных выполняемых на текущий момент транзакций (но еще не зафиксированных или прерванных). Все выполненные этими транзакциями изменения игнорируются, даже если впоследствии они будут зафиксированы.
  2. Все операции записи, выполненные прерванными транзакциями, игнорируются.
  3. Все операции записи, выполненные транзакциями с более поздним идентификатором транзакции (то есть начавшиеся после запуска текущей транзакции), игнорируются независимо от того, были ли они зафиксированы.
  4. Результаты всех остальных операций записи видны запросам приложения.

Другими словами, объект является видимым, если одновременно справедливы следующие два условия:

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

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

Индексы и snapshot isolation

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

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

Другой подход используется в СУБД CouchDB, Datomic и LMDB. Хотя они тоже задействуют B-деревья, но применяют схему дописывания данных/копирования при записи (append-only/copy-on-write), при которой происходит не перезапись страниц дерева при обновлении, а создание новой копии каждой из модифицированных страниц. Родительские страницы вплоть до корневой вершины дерева меняются так, чтобы указывать на новые версии их дочерних страниц. Страницы, на которые операция записи не повлияла, не копируются и остаются неизменяемыми.

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

repeatable read и путаница с названиями

snapshot isolation — удобный уровень изоляции, особенно в случае транзакций только для чтения. Однако множество баз данных используют для него различные названия. В Oracle он называется уровнем сериализации (serializable), а в PostgreSQL и MySQL — воспроизводимым чтением (repeatable read).

Предотвращение потери обновлений

Обсуждавшиеся до сих пор уровни read committed и snapshot isolation в основном гарантировали, что транзакция только для чтения может встречаться в случае конкурентных операций записи. Вопрос двух транзакций, выполняющих одновременно операции записи, мы почти не затрагивали. Мы обсудили только «грязные» операции записи — одну из возможных разновидностей конфликтов двойной записи (write-write conflict).

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

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

  • увеличение счетчика или обновление баланса счета (требует чтения текущего значения, вычисления нового значения и записи обратно старого);
  • выполнение локального изменения в составном значении, например, добавления элемента в список в JSON-документе (требует синтаксического разбора документа, выполнения изменения и записи обратно модифицированного документа);
  • одновременное редактирование двумя пользователями страницы «Википедии», причем каждый из них сохраняет свои изменения путем отправки на сервер всего содержимого страницы, перезаписывая данные, содержащиеся в этот момент в базе.

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

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

UPDATE counters SET value = value + 1 WHERE key = 'foo';

Аналогично документоориентированные базы данных, например MongoDB, предоставляют возможность использовать атомарные операции для локальных изменений частей JSON-документов, а СУБД Redis позволяет применять их для модификации таких структур данных, как очереди по приоритету. ‰ Атомарные операции обычно реализуются путем эксклюзивной блокировки объекта при чтении, чтобы никакие другие транзакции не могли его прочитать до фиксации изменения. Этот метод иногда называют чтением по установленному курсору (cursor stability). Другой вариант — просто выполнять все атомарные операции в отдельном потоке выполнения.

Явные блокировки

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

BEGIN TRANSACTION;

SELECT * FROM figures
WHERE name = 'robot' AND game_id = 222
FOR UPDATE;

-- Проверяем допустимость хода, после чего обновляем
-- возвращенную предыдущим SELECT позицию фигуры.
UPDATE figures SET position = 'c4' WHERE id = 1234;

COMMIT;

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

Автоматическое обнаружение потери обновлений

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

Преимуществом такого подхода является возможность эффективно выполнять эту проверку в связке с изоляцией снимков состояния. Конечно, на уровнях repeatable read PostgreSQL, serializable Oracle и snapshot isolation SQL Server происходит автоматическое обнаружение потери обновлений и прерывание проблемных транзакций. Однако при воспроизводимом чтении в базах данных MySQL/InnoDB потерянные обновления не обнаруживаются.

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

Compare And Set

В базах данных без транзакций иногда встречается операция «сравнение с обменом» (compare-and-set). Цель этой операции — избежать потери обновлений благодаря тому, что обновления допускаются, только если значение не менялось с момента его прошлого чтения. При несовпадении текущего значения с прочитанным ранее обновление не выполняется и выполнение цикла чтения — изменения — записи необходимо повторить.

Разрешение конфликтов и репликация

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

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

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

Атомарные операции способны хорошо работать в контексте репликации, особенно если они коммутативны (то есть результат при их использовании в разном порядке в различных репликах остается тем же самым). Например, приращение счетчика или добавление элемента в множество — коммутативные операции. На этой идее основаны типы данных базы данных Riak 2.0, предотвращающие потери обновлений между репликами. В случае конкурентного обновления значения различными клиентами Riak автоматически сливает воедино эти обновления таким образом, что они не теряются.

С другой стороны, метод разрешения конфликтов «выигрывает последний» (last write wins, LWW) склонен к потере обновлений.

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

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

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

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

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

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

Характеристики асимметрии записи

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

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

Способов предотвратить потери обновлений не так много.

  • Атомарные однообъектные операции не помогут, поскольку в транзакции участвует несколько объектов.
  • К сожалению, не поможет и автоматическое обнаружение потерянных обновлений, встречающееся в некоторых реализациях изоляции снимков состояния: асимметрия записи автоматически не обнаруживается ни при repeatable read в PostgreSQL или MySQL/InnoDB, ни при сериализуемых транзакциях Oracle, ни на уровне snapshot isolation SQL Server. Автоматическое предотвращение асимметрии записи требует настоящей сериализуемости.
  • Некоторые базы данных позволяют создавать ограничения целостности, за соблюдением которых затем следит сама база (например, ограничения уникальности, ограничения внешних ключей или ограничения, накладываемые на конкретное значение). Однако для спецификации наличия хотя бы одного дежурного врача понадобилось бы ограничение, налагаемое на несколько объектов. В большинстве баз нет встроенной поддержки подобных ограничений, но их можно реализовать с помощью триггеров или материализованных представлений, в зависимости от базы данных.
  • Если использовать уровень сериализуемости невозможно, то вторым лучшим решением будет, вероятно, явная блокировка строк, необходимых для транзакции.

Асимметрия записи вследствие фантомов

Проблема возникает по одной схеме.

  1. Запрос SELECT проверяет некое требование путем поиска удовлетворяющих определенному условию строк.

  2. В зависимости от результата первого запроса код приложения решает, что делать дальше

  3. Если приложение решает продолжить выполнение, то производит операцию записи (INSERT, UPDATE или DELETE) в базу данных и фиксирует транзакцию.

    Результат данной операции записи изменяет входные условия принимаемого на шаге 2 решения. Другими словами, если бы пришлось повторить запрос SELECT из шага 1 после фиксации операции записи, то результат мог бы оказаться другим, поскольку эта операция изменила множество строк, удовлетворяющих условию поиска.

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

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

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

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

Источники

Комментарии в Telegram-группе!