Многоверсионность в двух словах

Кузьменко Д.В. www.ibase.ru
26.12.2003
исправления: 20.01.2004

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

Физика

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

Рис. 1	Рис. 2
Допустим, существует транзакция TR1 и некая таблица, в которой есть записи. Когда TR1 обращается к данным, она считывает то что есть	Теперь появляется вторая транзакция TR2. Она также будет читать те же самые данные. Однако, если она изменит запись в таблице,

Рис. 3	Рис. 4
то для этой записи ядро сервера создает новую версию записи и кладет ее рядом.	Поскольку все записи и их версии в заголовке имеют номер транзакции, их создавшей, то дальше видимость конкретной версии для конкретной транзакции определяется уже сравнением этих самых номеров.

Вот и все. Как результат - "писатели" не мешают "читателям".

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

Лирика

Конечно, это не все. На самом деле механизм сложнее, и сейчас мы углубимся в его изучение.

Состояния транзакций

Когда сервер получает команду стартовать транзакцию, он делает следующее:

выделяет номер для новой транзакции. Это обычный "автоинкремент", и в статистике (gstat -h) указан как Next Transaction.
выделяет 2 бита в Transaction Inventory Page - специальных страницах базы данных, предназначенных для учета состояния транзакции

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

Состояний у транзакции может быть четыре (два бита):

Активная
Committed
Rolled back
in Limbo

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

Видимость версий

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

Read Committed и Snapshot

У InterBase и Firebird существует всего два основных типа транзакций - ReadCommitted и Snapshot (их параметры см. в статье). Различия между ними таковы:

транзакция ReadCommitted для проверки состояния конкурирующих транзакций обращается к глобальному TIP
транзакция Snapshot при старте делает снимок TIP, и дальше для проверки состояния транзакций работает только с ним

Таким образом, конкретная транзакция ReadCommitted дополнительно видит состояния всех транзакций, стартовавших после нее. То есть, если считываемая версия имеет номер транзакции > 500 (для примера выше), и эта транзакция committed, то транзакция 500 эту версию "видит".

Для Snapshot "новых" транзакций как таковых не существует. Т.е. даже если обнаруживается версия записи, имеющая номер транзакции 520, то в той копии TIP, которым располагает транзакция Snapshot N 500, состояния такой транзакции нет. А раз нет, значит эту версию ей видеть нельзя.

Исходя из изложенного, можно сформировать формулу "видимости версий":

Версия записи видна, если
(где tr_id - идентификатор транзакции конкретной версии записи)

tr_id = self (т.е. транзакция сама создала версию)
все tr_id < self, которые committed (для транзакций любого типа)
все tr_id > self, которые committed, если read_committed

Сколько версий?

А сколько надо? Собственно, при каждом обновлении записи создается новая версия. Значит, committed-версий у одной записи может быть сколько угодно (я видел примерно 800 тысяч версий у одной записи). А вот не-committed версия может существовать только одна.

То есть, если две транзакции пытаются обновить одну и ту же запись, "неуспевшая" получает сообщение deadlock. Этот случай является единственным случаем "блокирования" в InterBase и Firebird(на тему применения такой "блокировки" есть статья).

Commit, Rollback

В ряде случаев сервер самостоятельно может изменить состояние транзакции, несмотря на то, как транзакция была завершена (даже если коннект с БД оборвался).

Commit никогда ни во что другое не превращается, это понятно.
Rollback может превратиться в Commit, если
1. изменений в транзакции не было
2. изменения в транзакции были самостоятельно отменены по exception
3. изменений в транзакции было мало (понятие "мало" расширено в InterBase 7.1 SP 1. например, теперь "мало" - это update 100 тысяч записей), например менее 50 тысяч. В этом случае сервер сначала отменяет все произведенные в такой транзакции изменения при помощи механизма savepoints, а затем изменяет состояние транзакции с активного на Commit вместо Rollback.
Active превращается в Rollback (или Commit, см. пункт 2), если сервер при попытке проверить состояние транзакции обнаружил, что коннект, ее стартовавший, оборвался.

Дополнительно нужно отметить, что в Firebird появилось (и сейчас во всех версиях InterBase/Firebird/Yaffil) специальное поведение для транзакций read only read committed - такая транзакция сразу после старта получает состояние committed, а не active. То есть, она может быть активной чуть ли не вечно, без какого-либо влияния на производительность сервера, сборку мусора и т.п.

Кооперативные домохозяйки

На данном этапе возникает предположение - если версии записей накапливаются бесконечно, то с таким сервером просто нельзя будет работать!

Разумеется, у сервера есть механизмы, позволяющие избавиться от ненужных версий. Этот механизм называется "кооперативная сборка мусора".

Этот механизм можно охарактеризовать так - "посуду моет тот, кто хочет поесть". Не очень привлекательно, зато в данном случае весьма эффективно. Т.е. писатели не собирают мусор. Мусор собирают только читатели, и то, если хотят прочитать конкретную запись.

Когда сервер читает запись (под чтением имеется в виду select, update и delete. причем update и delete сюда входят потому, что перед обновлением или удалением сервер должен прочитать, что же он будет обновлять или удалять), то конечно, на самом деле он считывает с диска страницу (или больше) целиком (а не одну запись). И в его распоряжении оказываются все версии конкретной записи. Теперь у сервера есть две задачи:

Определить видимые версии для данной транзакции, и выдать их по запросу
Найти никому не нужные версии записи, и удалить их.

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

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

Это

Oldest Active Transaction - самый меньший номер транзакции, которая до сих пор находится в состоянии Active
Oldest Interesting Transaction - самый меньший номер транзакции, которая находится не в committed-состоянии. Т.е. это или OAT, или номер самой "старой" транзакции в состоянии Rollback или in Limbo.
Oldest Snapshot Transaction - немного посложнее, чем просто номер snapshot:
- read only read committed не имеют такого номера
- read write read committed имеют OST равный своему собственному номеру
- snapshot имеет OST равный OAT

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

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

замечание: в InterBase 6.0 SuperServer сборщик мусора выделен в отдельный thread. Это означает, что когда "читатель" обнаруживает мусорные версии записей, он не собирает мусор сам, а сообщает о наличии мусора в конкретном месте сборщику мусора. Однако, приоритет сборщика мусора достаточно низкий, поэтому зачастую он просто или не успевает собирать мусор вообще, или не поспевает за накапливающимся мусором. В результате, то небольшое замедление, которое возникало бы при явной сборке мусора при чтении версий, превращается в существенные "тормоза" или из-за работы сборщика мусора, или из-за накопления мусорных версий, и большим затратам времени сервера на их чтение.

Итог

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

Литература

(с) KDV, www.ibase.ru