Как базы данных выполняют атомарный ввод-вывод?

Ответ 1

Я помню, как однажды обнаружил, что документы BerkeleyDB действительно очень полезны, чтобы понять, как эти реализации могут работать, потому что это/была довольно низкоуровневая база данных, которая реализовала транзакции без всей инфраструктуры планирования реляционных/запросов.

Не все базы данных (даже те, о которых вы упоминаете) работают совершенно одинаково. Последующая реализация PostgreSQL существенно отличается от реализации моментального снимка Oracle и SQL Server, хотя все они основаны на одном и том же подходе (MVCC: multi-version concurrency).

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

MVCC - это метод, с помощью которого параллельные транзакции, которые хотят читать строки, а не блокируются вами, могут получить доступ к "перед изображением" . Каждая транзакция имеет идентификатор и способ определения данных транзакций, которые он может "видеть" и не может: разные правила для создания этого набора используются для реализации разных уровней изоляции. Поэтому, чтобы получить семантику "повторяемого чтения", транзакция должна найти "перед изображением" для любой строки, которая была обновлена ​​транзакцией, которая была запущена после нее, например. Вы могли бы наивно реализовать это, если транзакции просматривают журнал транзакций перед изображениями, но на практике они хранятся где-то в другом месте: следовательно, у Oracle есть отдельные повторные и отмененные пробелы - повторение - это журнал транзакций, отмена которых перед образами блоков для одновременные транзакции; SQL Server хранит перед изображениями в tempdb. Напротив, PostgreSQL всегда создает новую копию строки всякий раз, когда она обновляется, поэтому перед изображениями живут сами блоки данных: у этого есть некоторые преимущества (фиксация и откат - очень простые операции, без дополнительного пространства для управления) с компромиссами (эти устаревшие версии строк должны быть очищены в фоновом режиме).

В случае PostgreSQL (и это БД, я больше всего знаком с внутренними) каждой версии строки на диске имеет некоторые дополнительные свойства, которые транзакции должны проверять, чтобы решить, является ли эта версия строки "видимой" для них. Для простоты учтите, что они имеют "xmin" и "xmax" - "xmin" указывает идентификатор транзакции, который создал версию строки "xmax" (необязательный) идентификатор транзакции, который удалил его (что может включать в себя создание новой версии строки для представляют обновление для строки). Итак, вы начинаете с строки, созданной txn # 20:

xmin xmax id value
20   -    1  FOO

а затем txn # 25 выполняет update t set value = 'BAR' where id = 1

20   25   1  FOO
25   -    1  BAR

До тех пор, пока txn # 25 не будет завершен, новые транзакции будут знать, что его изменения не будут видны. Таким образом, транзакция, просматривающая эту таблицу, будет иметь версию "FOO" , так как ее xmax является невидимой транзакцией.

Если txn # 25 откатывается назад, новые транзакции не будут сразу пропустить его, но рассмотрят, было ли txn # 25 зафиксировано или откат. (PostgreSQL управляет таблицей поиска "фиксация статуса", чтобы служить этому, pg_clog). Так как txn # 25 откат, его изменения не видны, поэтому снова выполняется версия "FOO" . (И версия "BAR" пропущена, так как ее транзакция xmin невидима)

Если txn # 25 зафиксировано, тогда версия строки "FOO" теперь не принимается, поскольку ее транзакция xmax видна (т.е. изменения, сделанные этой транзакцией, теперь видны). Напротив, выполняется версия строки "BAR", так как ее транзакция xmin видна (и она не имеет xmax)

Пока txn # 25 все еще выполняется (снова это можно прочитать из pg_clog), любая другая транзакция, которая хочет обновить строку, будет ждать завершения txn # 25, пытаясь сделать общую блокировку идентификатора транзакции, Я подчеркиваю этот момент, почему PostgreSQL обычно не имеет "блокировок строк" ​​как таковых, а только блокировок транзакций: в каждой строке нет блокировки в памяти. (Блокировка с помощью select ... for update выполняется установкой xmax и флагом для указания, что xmax просто указывает на блокировку и удаление)

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

Механизм изоляции моментальных снимков SQL Server, по-моему, во многом похож на Oracle, используя tempdb для хранения блоков, которые меняются, а не для выделенного файла.

Надеюсь, этот бессвязный ответ был полезен. Все это из памяти настолько велики, что возможны дезинформации, особенно для реализаций без postgresql.

• http://devcenter.heroku.com/articles/postgresql-concurrency
• https://gist.github.com/1781649 - демонстрационная версия MVCC на PostgreSQL
• http://simpledbm.googlecode.com/files/mvcc-survey-1.0.pdf

Ответ 2

Обзор высокого уровня для Oracle:

Каждый сеанс Oracle уникален, и каждый сеанс может иметь активную транзакцию 1 *. Когда транзакция начинается, Oracle назначает ей монотонно увеличивающийся номер изменения системы (SCN). Поскольку Oracle обновляет/вставляет/удаляет строки, Oracle блокирует интересующие строки в таблице и поддерживает индекс, обновляя заголовок в написанных блоках, а также сохраняя "исходные" блоки в пространстве откат (отмена) оракула. Oracle также записывает записи повторного журнала в буфер памяти, описывая изменения, внесенные как в таблицу, так и в индексные блоки, а также блоки отмены. Обратите внимание, что сделанные изменения производятся в памяти, а не непосредственно на диске.

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

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

Итак, как это реализовать ACID:

Атомность: моя сессия, моя транзакция, все идет или ничего не происходит. Когда я совершаю, я ничего не могу сделать, пока фиксация не закончится.

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

Независимость: помните эти номера изменений системы? Если вы не вносите изменений, Oracle знает, что такое SCN, когда вы запускаете инструкцию или объявляете курсор. Поэтому, если у вас есть длинный оператор, из которого данные меняются из-под вас, Oracle проверяет, чтобы данные AS AS WAS COMMITTED выполнялись при запуске вашего заявления. Это многоконтактный контроль согласованности, и это довольно сложно. Oracle не реализует все уровни изоляции, вызванные различными стандартами SQL - например, Oracle никогда не разрешает чтение грязных или phantom.

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

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

Ответ 3

Ayende предложил мне в Twitter, что я смотрю Munin, фактический механизм хранения данных, который он использует для RavenDB и Raven MQ.