Транзакции и механизмы их контроля
Транзакция это последовательное выполнение операций чтения и записи. Окончанием транзакции может быть либо сохранение изменений (фиксация, commit) либо отмена изменений (откат, rollback). Применительно к БД транзакция это нескольких запросов, которые трактуются как единый запрос.
Транзакции должны удовлетворять свойствам ACID
Атомарность. Транзакция либо выполняется полностью либо не выполняется вовсе.
Согласованность. При завершении транзакции не должны быть нарушены ограничения накладываемые на данные (например constraints в БД). Согласованность подразумевает, что система будет переведена из одного корректного состояния в другое корректное.
Изолированность. Параллельно выполняемые транзакции не должны влиять друг на друга, например менять данные которые использует другая транзакция. Результат выполнения параллельных транзакций должен быть таким, как если бы транзакции выполнялись последовательно.
Устойчивость. После фиксации изменения не должны быть утеряны.
Журнал транзакций
Журнал хранит изменения выполненные транзакциями, обеспечивает атомарность и устойчивость данных в случае сбоя системы
Журнал содержит значения, которые данные имели до и после их изменения транзакцией. Write-ahead log strategy обязывает добавлять в журнал запись о предыдущих значениях до начала, а о конечных после завершения транзакции. В случае внезапной остановки системы БД читает лог в обратном порядке и отменяет изменения сделанные транзакциями. Встретив прерванную транзакцию БД выполняет ее и вносит изменения о ней в журнал. Находясь в состоянии на момент сбоя, БД читает лог в прямом порядке и возвращает изменения сделанные транзакциями. Таким образом сохраняется устойчивость транзакций которые уже были зафиксированы и атомарность прерванной транзакции.
Простое повторное выполнение ошибочных транзакций недостаточно для восстановления.
Пример. На счету у пользователя 500$ и пользователь решает снять их через банкомат. Выполняются две транзакции. Первая читает значение баланса и если на балансе достаточно средств выдает деньги пользователю. Вторая вычитает из баланса нужную сумму. Допустим, произошел сбой системы и первая операция не выполнилась, а вторая выполнилась. В этом случае мы не можем повторно выдать деньги пользователю без возврата системы в изначальное состояние с положительным балансом.
Уровни изоляции
Чтение фиксированных данных (Read Committed)
Проблема грязного чтения (Dirty Read) заключается в том, что транзакция может прочесть промежуточный результат работы другой транзакции.
Пример. Начальное значение баланса 0$. Т1 добавляет к балансу 50$. Т2 считывает значение баланса (50$). Т1 отменяет изменения и завершается. T2 продолжает выполнение располагая неверными данными о балансе.
Решением является чтение фиксированных данных (Read Committed) запрещающее читать данные, измененные транзакцией. Если транзакция A изменила некоторый набор данных, то транзакция B при обращении за этими данными вынуждена ожидать завершения транзакции A.
Повторяемое чтение (Repeatable Read)
Проблема потерянных изменений (Lost Updates). Т1 сохраняет изменения поверх изменений Т2.
Пример. Начальное значение баланса 0$ и две транзакции одновременно пополняют баланс. T1 и T2 читают баланс равный 0$. Затем T2 прибавляет 200$ к 0$ и сохраняет результат. T1 прибавляет 100$ к 0$ и сохраняет результат. Итоговый результат 100$ вместо 300$.
Проблема неповторяемого чтения (Unrepeatable read). Повторное чтение одних и тех же данных возвращает разные значения.
Пример. Т1 читает значение баланса равное 0$. Затем Т2 добавляет к балансу 50$ и завершается. Т1 повторно читает данные и обнаруживает несоответствие с предыдущим результатом.
Повторяемое чтение (Repeatable Read) гарантирует что повторное чтение вернет тот же результат. Данные прочитанные одной транзакцией запрещено менять в других до завершения транзакции. Если транзакция A прочла некоторый набор данных, то транзакция B при обращении за этими данными вынуждена ожидать завершения транзакции A.
Упорядоченное чтение (Serializable)
Проблема фантомного чтения (Phantom Reads). Два запроса выбирающие данные по некоему условию возвращают разные значения.
Пример. T1 запрашивает количество всех пользователей баланс которых больше 0$ но меньше 100$. T2 вычитает 1$ у пользователя с балансом 101$. T1 повторно выполняет запрос.
Упорядоченное чтение (Serializable). Транзакции выполняются как полностью последовательные. Запрещается обновлять и добавлять записи, подпадающие под условия запроса. Если транзакция A запросила данные всей таблицы, то таблица целиком замораживается для остальных транзакций до завершения транзакции A.
Планировщик (Scheduler)
Устанавливает очередность в которой должны выполняться операции при параллельно протекающих транзакциях
Обеспечивает заданный уровень изолированности. Если результат выполнения операций не зависит от их очередности, то такие операции коммутативны (Permutable). Коммутативны операции чтения и операции над разными данными. Операции чтения-записи и записи-записи не коммутативны. Задача планировщика чередовать операции выполняемые параллельными транзакциями так, чтобы результат выполнения был эквивалентен последовательному выполнению транзакций.
Механизмы контроля параллельных заданий (Concurrency Control)
Оптимистический основан на обнаружении и разрешении конфликтов, пессимистический на предотвращении возникновения конфликтов
При оптимистическом подходе несколько пользователей получают в свое распоряжение копии данных. Первый завершивший редактирование сохраняет изменения, остальные же должны осуществить слияние изменений. Оптимистический алгоритм позволяет конфликту произойти, но система должна восстановиться после конфликта.
При пессимистическом подходе первый пользователь захвативший данные препятствует получению данных остальным. Если конфликты редки разумно выбрать оптимистическую стратегию, так как она обеспечивает более высокий уровень параллелизма.
Блокировка (Locking)
Если одна транзакция заблокировала данные, то остальные транзакции при обращении к данным обязаны ждать разблокировки
Блок может накладываться на базу данных, таблицу, ряд или аттрибут. Совместный захват (Shared Lock) может быть наложен на одни данные несколькими транзакциями, разрешает всем транзакциям (включая наложившую) чтение, запрещает изменение и монопольный захват. Монопольный захват (Exclusive Lock) может быть наложен только одной транзакцией, разрешает любые действия наложившей транзакции, запрещает любые действия остальным.
Взаимоблокировкой считается ситуация когда транзакции оказываются в режиме ожидания, длящемся бесконечно долго
Пример. Первая транзакция ждет освобождения данных захваченных второй, в то время как вторая ждет освобождения данных, захваченных первой.
Оптимистическое решение проблемы взаимоблокировок позволяет взаимоблокировке произойти, но затем восстанавливает систему откатывая одну из транзакций, участвующих во взаимоблокировке
С определенной периодичностью производится поиск взаимоблокировок. Один из способов обнаружения — по времени, то есть считать что взаимоблокировка произошла если транзакция выполняется слишком долго. Когда взаимоблокировка найдена, то одна из транзакций откатывается, что дает возможность другим транзакциям участвующим во взаимоблокировке завершиться. Выбор жертвы может быть основан на стоимости транзакций или их старшинстве (Wait-Die и Wound-wait схемы).
Каждой транзакции T присваивается временная метка TS содержащая время начала выполнения транзакции.
Если TS(Ti) < TS(Tj), то Ti ждет, иначе Ti откатывается и начинается заново с той же временной меткой.
Если молодая транзакция захватила ресурс, а более старая запрашивает тот же ресурс, то старшей транзакции позволено ожидать. Если более старая транзакция захватила ресурс, то молодая транзакция запрашивающая этот ресурс будет откачена.
Если TS(Ti) < TS(Tj), то Tj откатывается и начинается заново с той же временной меткой, иначе Ti ждет.
Если более молодая транзакция захватила ресурс, а более старая транзакция запрашивает этот же ресурс, то молодая транзакция будет откачена. Если более старая транзакция захватила ресурс, то более молодой транзакции, запрашивающей этот ресурс позволено ожидать. Выбор жертвы основанный на старшинстве предотвращает появление взаимоблокировок, но откатывает транзакции которые не находятся в состоянии взаиомблокировки. Проблема заключается в том, что транзакции могут откатываться много раз, т.к. более старая транзакция может долго удерживать ресурс.
Пессимистическое решение проблемы взаимоблокировок не позволяет транзакции начать выполнение если есть риск возникновения взаимоблокировки
Для обнаружения взаимоблокировки строится граф (граф ожидания, wait-for-graph), вершины которого транзакции, а ребра направлены от транзакций ожидающих освобождения данных к транзакции захватившим эти данные. Считается что взаимоблокировка произошла, если граф имеет зацикленность. Построение графа ожидания, особенно в распределенных БД, дорогостоящая процедура.
Двухфазная блокировка — предотвращение взаимоблокировок путем захвата всех ресурсов используемых транзакцией в начале транзакции и освобождения их в конце
Все блокирующие операции должны предшествовать первой разблокирующей. Имеет две фазы — Growing Phase при которой происходит накопление захватов и Shrinking Phase при которой происходит освобождение захватов. При невозможности захвата одного из ресурсов транзакция начинается сначала. Возможна ситуация когда транзакция не сможет захватить требуемые ресурсы, например если несколько транзакций будут конкурировать за одни ресурсы.
Двухфазный коммит обеспечивает выполнение коммита на всех репликах БД
Каждая БД вносит информацию о данных которые будут изменены в лог и отвечает координатору ОК (Voting Phase). После того как все ответили ОК координатор отсылает сигнал обязывающий всех произвести коммит. После коммита сервера отвечают ОК, если хоть один не ответил ОК, то координатор отсылает сигнал отмены изменений всем серверам (Completion Phase).
Метод временных меток
Более старая транзакция откатывается при попытке доступа к данным, задействованным более молодой транзакцией
Каждой транзакции назначается временная метка TS соответствующая времени начала выполнения. Если Ti старше Tj, то TS(Ti) < TS(Tj).
Когда транзакция откатывается, ей назначается новая временная метка. Каждый объект данных Q задействованный транзакцией помечается двумя метками. W-TS(Q) — временная метка самой молодой транзакции, успешно выполнившей запись над Q. R-TS(Q) — временная метка самой молодой транзакции, выполнившей запись чтения над Q.
Когда транзакция T запрашивает чтение данных Q возможны два варианта.
Если TS(T) < W-TS(Q), то есть данные были обновлены более молодой транзакцией, то транзакция T откатывается.
Если TS(T) >= W-TS(Q), то чтение выполняется и R-TS(Q) становится MAX(R-TS(Q), TS(T)).
Когда транзакция T запрашивает изменение данных Q возможны два варианта.
Если TS(T) < R-TS(Q), то есть данные уже были прочитаны более молодой транзакцией и если произвести изменение, то возникнет конфликт. Транзакция T откатывается.
Если TS(T) < W-TS(Q), то есть транзакция пытается перезаписать более новое значение, транзакция T откатывается. В остальных случаях изменение выполняется и W-TS(Q) становится равным TS(T).
Не требуется дорогостоящего построения графа ожидания. Более старые транзакции зависят от более новых, следовательно в графе ожидания нет циклов. Нет взаимоблокировок, поскольку транзакции не ожидают, а сразу откатываются. Возможны каскадные откаты. Если Ti откатилась, а Tj прочитала данные которые изменила Ti, то Tj тоже должна откатиться. Если при этом Tj уже была закоммичена, то возникнет нарушения принципа устойчивости.
Одно из решений каскадных откатов. Транзакция выполняет все операции записи в конце, причем остальные транзакции обязаны ожидать завершения этой операции. Транзакции ожидают коммита перед чтением.
Транзакция (информатика)
Транза́кция (англ. transaction ) — группа последовательных операций с базой данных, которая представляет собой логическую единицу работы с данными. Транзакция может быть выполнена либо целиком и успешно, соблюдая целостность данных и независимо от параллельно идущих других транзакций, либо не выполнена вообще и тогда она не должна произвести никакого эффекта. Транзакции обрабатываются транзакционными системами, в процессе работы которых создаётся история транзакций.
Различают последовательные (обычные), параллельные и распределённые транзакции. Распределённые транзакции подразумевают использование больше чем одной транзакционной системы и требуют намного более сложной логики (например, two-phase commit — двухфазный протокол фиксации транзакции). Также, в некоторых системах реализованы автономные транзакции, или под-транзакции, которые являются автономной частью родительской транзакции.
Содержание
Пример транзакции
Пример: необходимо перевести с банковского счёта номер 5 на счёт номер 7 сумму в 10 денежных единиц. Этого можно достичь, к примеру, приведённой последовательностью действий:
- Начать транзакцию
- Окончить транзакцию
Эти действия представляют собой логическую единицу работы «перевод суммы между счетами», и таким образом, являются транзакцией. Если прервать данную транзакцию, к примеру, в середине, и не аннулировать все изменения, легко оставить владельца счёта номер 5 без 10 единиц, тогда как владелец счета номер 7 их не получит.
Свойства транзакций
Одним из наиболее распространённых наборов требований к транзакциям и транзакционным системам является набор ACID (Atomicity, Consistency, Isolation, Durability). Вместе с тем, существуют специализированные системы с ослабленными транзакционными свойствами [1] .
Уровни изоляции транзакций
В идеале транзакции разных пользователей должны выполняться так, чтобы создавалась иллюзия, что пользователь текущей транзакции — единственный. Однако в реальности, по соображениям производительности и для выполнения некоторых специальных задач, СУБД предоставляют различные уровни изоляции транзакций. Уровни описаны в порядке увеличения изоляции транзакций и надёжности работы с данными
- 0 — Неподтверждённое чтение (Read Uncommitted, Dirty Read, грязное чтение) — чтение незафиксированных изменений своей транзакции и параллельных транзакций, возможны нечистые, неповторяемые чтения и фантомы
- 1 — Подтверждённое чтение (Read Committed) — чтение всех изменений своей транзакции и зафиксированных изменений параллельных транзакций, нечистые чтения невозможны, возможны неповторяемые чтения и фантомы;
- 2 — Повторяемое чтение (Repeatable Read, Snapshot) — чтение всех изменений своей транзакции, любые изменения, внесённые параллельными транзакциями после начала своей, недоступны, нечистые и неповторяемые чтения невозможны, возможны фантомы;
- 3 — Упорядоченный — (Serializable, сериализуемый) — упорядоченные (сериализуемые) транзакции. Идентичен ситуации, при которой транзакции выполняются строго последовательно, одна после другой, то есть результат действия которых не зависит от порядка выполнения шагов транзакции (запрещено чтение всех данных, изменённых с начала транзакции, в том числе и своей транзакцией). Фантомы невозможны.
Чем выше уровень изоляции, тем больше требуется ресурсов, чтобы их поддерживать.
В СУБД уровень изоляции транзакций можно выбрать как для всех транзакций сразу, так и для одной конкретной транзакции. По умолчанию в большинстве баз данных используется уровень 1 (Read Committed). Уровень 0 используется в основном для отслеживания изменений длительных транзакций или для чтения редко изменяемых данных. Уровни 2 и 3 используются при повышенных требованиях к изолированности транзакций.
Реализация
Полноценная реализация уровней изоляции и свойств ACID представляет собой нетривиальную задачу. Обработка поступающих данных приводит к большому количеству маленьких изменений, включая обновление как самих таблиц, так и индексов. Эти изменения потенциально могут потерпеть неудачу: закончилось место на диске, операция занимает слишком много времени (timeout) и т. д. Система должна в случае неудачи корректно вернуть базу данных в состояние до транзакции.
Первые коммерческие СУБД (к примеру, IBM DB2), пользовались исключительно блокировкой доступа к данным для обеспечения свойств ACID. Но большое количество блокировок приводит к существенному уменьшению производительности. Есть два популярных семейства решений этой проблемы, которые снижают количество блокировок:
-
(write ahead logging, WAL) (shadow paging) [2] .
В обоих случаях, блокировки должны быть расставлены на всю информацию, которая обновляется. В зависимости от уровня изоляции и имплементации, блокировки записи также расставляются на информацию, которая была прочитана транзакцией.
При упреждающей журнализации, используемой в Sybase и MS SQL Server до версии 2005, все изменения записываются в журнал, и только после успешного завершения — в базу данных. Это позволяет СУБД вернуться в рабочее состояние после неожиданного падения системы. Теневые страницы содержат копии тех страниц базы данных на начало транзакции, в которых происходят изменения. Эти копии активизируются после успешного завершения. Хотя теневые страницы легче реализуются, упреждающая журнализация более эффективна [3]
Дальнейшее развитие технологий управления базами данных привело к появлению безблокировочных технологий. Идея контроля за параллельным доступом с помощью временных меток (timestamp-based concurrency control) была развита и привела к появлению многоверсионной архитектуры MVCC. Эти технологии не нуждаются ни в журнализации изменений, ни в теневых страницах. Архитектура, реализованная в Oracle 7.х и выше, записывает старые версии страниц в специальный сегмент отката, но они все ещё доступны для чтения. Если транзакция при чтении попадает на страницу, временная метка которой новее начала чтения, данные берутся из сегмента отката (то есть используется «старая» версия). Для поддержки такой работы ведётся журнал транзакций, но в отличие от «упреждающей журнализации», он не содержит данных. Работа с ним состоит из трёх логических шагов:
- Записать намерение произвести некоторые операции
- Выполнить задание, копируя оригиналы изменяемых страниц в сегмент отката
- Записать, что всё сделано без ошибок
Журнал транзакций в сочетании с сегментом отката (область, в которой хранится копия всех изменяемых в ходе транзакции данных) гарантирует целостность данных. В случае сбоя запускается процедура восстановления, которая просматривает отдельные его записи следующим образом:
- Если повреждена запись, то сбой произошёл во время проставления отметки в журнале. Значит, ничего важного не потерялось, игнорируем эту ошибку.
- Если все записи помечены как успешно выполненные, то сбой произошёл между транзакциями, здесь также нет потерь.
- Если в журнале есть незавершённая транзакция, то сбой произошёл во время записи на диск. В этом случае мы восстанавливаем старую версию данных из сегмента отката.
Firebird вообще не имеет ни журнала изменений, ни сегмента отката, а реализует MVCC, записывая новые версии строк таблиц прямо в активное пространство данных. Так же поступает MS SQL 2005. Теоретически это даёт максимальную эффективность при параллельной работе с данными, но ценой является необходимость «сборки мусора», то есть удаления старых и уже не нужных версий данных.
Транзакции, ACID, CAP
Это тоже база данных, но ручная
Поговорим об базах данных. Сегодня транзакции, ACID и CAP-теорема — теория, которая важна для следующих статей.
Транзакции
Транзакция — это набор действий с данными, объединенный в логическую единицу. Она либо выполняется целиком, либо нет. Классический пример с операцией перевода денег со счета на счет:
Если эти операции выполнять вне транзакции, то ошибка в любой из них оставит оба счета в несогласованном состоянии: например, выйдет так, что деньги снимутся с одного счета, а на другой не придут. С транзакцией таких проблем нет — при ошибке откатятся все операции и для пользователя ничего не изменится.
Все звучит просто, когда с базой данных работает один пользователь: он выполняет транзакции одна за другой и не имеет никаких проблем с тем, что одна транзакция помешает другой. Все меняется, когда пользователей становится много.
Вот что может случиться при параллельном выполнении неизолированных транзакций.
Потерянное обновление
Когда две транзакции записывают разные значения в одну и ту же ячейку, одно из изменений теряется.
Грязное чтение
Когда читаются данные, которые в этот момент изменяются транзакцией, а потом транзакция откатывается и данные исчезают.
Неповторяющееся чтение
Когда несколько раз читаются данные, которые в этот момент изменяются транзакцией — каждый раз данные могут отказаться другими.
Фантомное чтение
Одна транзакция в ходе своего выполнения несколько раз выбирает множество строк по одним и тем же критериям. Другая транзакция в интервалах между этими выборками добавляет или удаляет строки или изменяет столбцы некоторых строк, используемых в критериях выборки первой транзакции, и успешно заканчивается. В результате получится, что одни и те же выборки в первой транзакции дают разные множества строк.
Изоляция транзакций
Чтобы параллельные транзакции могли выполняться, не мешая друг другу, придумали концепцию изоляции транзакций. Всего есть четыре уровня изоляции, но некоторые базы данных вводят свои уровни.
Чтение неподтверждённых данных (read uncommitted)
Самый низкий уровень изоляции. Можно свободно читать незафиксированные изменения других транзакций, но запись идет строго последовательно. Таким образом, исключается только проблема потерянных обновлений: гарантируется, что в итоге в ячейку запишут нужное значение все транзакции по очереди.
Обычно для этого используют блокировку на запись ячеек, предназначенных для изменения в рамках текущей транзакции. На чтение блокировки не ставятся.
Чтение подтверждённых данных (read committed)
Можно свободно читать все изменения своей транзакции и зафиксированные изменения чужих транзакций. Исключаются потерянные обновления и грязное чтение, остаются проблемы неповторяемых чтений и фантомов.
Повторяемое чтение (repeatable read)
Можно читать все изменения только своей транзации. Данные, измененные другими транзакциями, недоступны. Остается только проблема фантомных чтений.
Сериализуемый (serializable)
Транзакции полностью изолируются друг от друга, каждая выполняется так, как будто параллельных транзакций не существует.
Это набор из четырех требований к транзакционной системе, обеспечивающих максимально надежную и предсказуемую работу. Не все базы данных полностью реализуют ACID.
Атомарность (atomicity)
Атомарность гарантирует, что каждая транзакция будет выполнена полностью или не будет выполнена совсем. Не допускаются промежуточные состояния.
Согласованность (consistency)
Согласованность — это требование, подразумевающее, что в результате работы транзакции данные будут допустимыми. Это вопрос не технологии, а бизнес-логики: например, если количество денег на счете не может быть отрицательным, логика транзакции должна проверять, не выйдет ли в результате отрицательных значений.
Изолированность (isolation)
Гарантия того, что параллельные транзакции не будут оказывать влияния на результат других транзакций. Мы разобрались с изоляцией выше.
Долговечность (durability)
Изменения, получившиеся в результате транзакции, должны оставаться сохраненными вне зависимости от каких-либо сбоев. Иначе говоря, если пользователь получил сигнал о завершении транзакции, он может быть уверен, что данные сохранены.
CAP-теорема
Она гласит, что в распределенной системе можно обеспечить только два свойства из трех: согласованность, доступность и устойчивость к разделению. Помогает понимать, как конкретная распределенная система будет работать и чего от нее ожидать.
Согласованность данных (consistency)
Когда во всех узлах в каждый момент времени данные согласованы друг с другом, то есть не противоречат друг другу. Если в одном из узлов в ячейке базы данных есть данные, такие же данные есть на всех остальных узлах.
Доступность (availability)
Когда любой запрос может быть обработан системой, вне зависимости от ее состояния.
Устойчивость к разделению (partition tolerance)
Когда расщепление системы на несколько изолированных секций не приводит к некорректному отклику от каждой из секций: отвалилась сеть между двумя узлами, но каждый из них может корректно отвечать своим клиентам.
Все распределенные базы данных так или иначе в лучшем случае реализуют два свойства из трех, жертвуя оставшимся.
В следующей статье — о редких базах данных, которых вы не увидите в обычных проектах. Там нам и пригодится вся эта теория.