Своя СУБД на Rust · урок 8: транзакции, откат и видимость

Кому это. В прошлом уроке у движка появился журнал. INSERT и CREATE переживают падение, старт проигрывает журнал. Но дыра осталась: ROLLBACK движок не знает, а DELETE стирает слот на странице и после падения может воскреснуть.

Зачем именно Rust. Сегодня появятся BEGIN, COMMIT и ROLLBACK, кортеж научится версиям через xmin/xmax, и видимость строки начнёт решать движок. Это MVCC, на которой стоит Postgres. На Rust этот урок интересен тем, что borrow checker вмешается в проектирование трижды. Исполнителю нужно одновременно писать в журнал транзакции и читать статусы фиксации, и оба лежат в одном TransactionManager: понадобится метод, который делит структуру на две непересекающиеся ссылки. Откат должен трогать страницы, которых менеджер транзакций не видит: он примет замыкание impl FnMut(&UndoEntry) -> Result<()>. А граница no-steal нужна хукам внутри пулов, до которых &self менеджера не дотянуться: она уедет в Arc<AtomicU64>.

Важно про объём. Это самый плотный урок воркшопа, но почти всё опирается на готовое: журнал из прошлого урока, исполнитель из шестого. Менеджер транзакций сразу умеет держать несколько открытых транзакций, но снаружи сегодня видна одна, сессионная (BEGIN в SQL), плюс autocommit. Хэндлы для нескольких транзакций и блокировки появятся в уроке 9. Снимок почти всегда тривиален, а форма у него уже правильная.

Где мы в движке

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Планировщик, binder, каталог                    │  урок 6
│  Парсер SQL (рекурсивный спуск + Pratt)          │  урок 5
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  MVCC (видимость, версии кортежа)                │  урок 8  ← мы здесь
│  Блокировки (2PL), конкуренция                   │  урок 9
│  Менеджер транзакций (xid, состояния)            │  урок 8  ← мы здесь
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2
│  DiskManager (страницы поверх файла)              │  урок 1
└────────────────────────────────────────────────┘

Идея версий

В уроке 3 мы заложили в заголовок кортежа два поля, xmin и xmax, и до сих пор писали туда константы. Сегодня они заработают. xmin это номер транзакции, создавшей версию. xmax это номер транзакции, удалившей её, или 0, если версия жива. DELETE больше не стирает слот: он пишет свой xid в xmax, и слот остаётся живым. UPDATE это xmax у старой версии плюс вставка новой. Будет ли строка видна, решает не страница, а вопрос «какая транзакция её создала, какая удалила и зафиксировались ли они к моменту моего снимка».

Отсюда три следствия. Удаление становится записью журнала SET_XMAX, которую можно проиграть. Откат становится простым: снять свои пометки и сделать свои вставки мёртвыми. А восстановление учится игнорировать незафиксированное: если COMMIT транзакции в журнал не попал, её записи redo пропускает.

Версии в странице: set_xmax

// src/page.rs (добавляем в impl Page)

/// Смещение xmax внутри заголовка кортежа (см. tuple.rs).
const TUPLE_XMAX: usize = 4;

    /// Записать xmax кортежа в слоте на месте (MVCC-удаление, урок 8).
    pub fn set_xmax(&mut self, slot: u16, xmax: u32) {
        let at = self.get_slot(slot) as usize + TUPLE_XMAX;
        put_u32(&mut self.data[..], at, xmax);
    }

    pub fn get_xmax(&self, slot: u16) -> u32 {
        get_u32(&self.data[..], self.get_slot(slot) as usize + TUPLE_XMAX)
    }

    /// Живой ли слот: существует и указывает на кортеж, а не на DEAD_SLOT.
    pub fn is_slot_live(&self, slot: u16) -> bool {
        slot < self.slot_count() && self.get_slot(slot) != DEAD_SLOT
    }

Четыре байта на месте, без разбора и пересборки кортежа: xmax лежит по смещению 4 от начала его заголовка. Куча оборачивает это в MVCC-удаление:

// src/heap.rs

    /// MVCC-удаление (урок 8): xmax = xid в кортеже на месте, слот остаётся живым.
    pub fn mark_deleted(
        &self,
        rid: Rid,
        xid: Xid,
        journal: Option<&mut dyn Journal>,
    ) -> Result<()> {
        let mut guard = self.pool.fetch_page(rid.page_id)?;
        // на мёртвом слоте смещение 0, и xmax лёг бы в lsn заголовка страницы
        if !guard.read().is_slot_live(rid.slot) {
            return Err(invalid(format!(
                "markDeleted: слот {}:{} уже мёртв",
                rid.page_id, rid.slot
            )));
        }
        let mut page = guard.write();
        page.set_xmax(rid.slot, xid);
        if let Some(journal) = journal {
            let lsn = journal.log_set_xmax(xid, self.relation_id, rid.page_id, rid.slot, xid)?;
            page.set_lsn(lsn);
        }
        Ok(())
    }

Комментарий в начале стоит прочитать дважды. У мёртвого слота смещение 0, и set_xmax записал бы четыре байта по адресу 0 + 4, то есть прямо в поле lsn заголовка страницы. Ни паники, ни ошибки, просто тихо испорченная страница. Проверка is_slot_live превращает эту ловушку в Err. Обрати внимание и на latch: guard.read() живёт только до конца условия if, поэтому следующий guard.write() не столкнётся с ним. Latch в нашем пуле это try_lock, который паникует при повторном захвате, и такой порядок «прочитал, отпустил, взял на запись» придётся соблюдать везде.

Видимость: снимок и правило

Видимость отвечает на вопрос: видит ли транзакция me версию кортежа под своим снимком. Нужны две структуры: реестр статусов транзакций и сам снимок.

// src/txn/snapshot.rs
use std::collections::{HashMap, HashSet};

use crate::tuple::{Tuple, Xid};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TxnState {
    InProgress,
    Committed,
    Aborted,
}

/// Реестр статусов транзакций. Незнакомый xid считается откатанным; ниже floor (водяной
/// знак последнего checkpoint) всё зафиксировано без явной записи, аналог обрезания CLOG.
#[derive(Clone, Debug, Default)]
pub struct CommitStatus {
    states: HashMap<Xid, TxnState>,
    floor: Xid,
}

impl CommitStatus {
    pub fn new() -> CommitStatus {
        CommitStatus::default()
    }

    /// Явная запись приоритетна; всё ниже floor это committed.
    pub fn get(&self, xid: Xid) -> TxnState {
        match self.states.get(&xid) {
            Some(state) => *state,
            None if xid != 0 && xid < self.floor => TxnState::Committed,
            None => TxnState::Aborted,
        }
    }

    pub fn set(&mut self, xid: Xid, state: TxnState) {
        self.states.insert(xid, state);
    }

    pub fn raise_floor_to(&mut self, watermark: Xid) {
        self.floor = self.floor.max(watermark);
    }

    /// Перенять floor и явные статусы другого реестра (после recovery).
    pub fn absorb(&mut self, other: CommitStatus) {
        self.raise_floor_to(other.floor);
        self.states.extend(other.states);
    }
}

CommitStatus это карта xid -> состояние плюс водяной знак floor. Три ветки match в get читаются как правила. Явная запись главнее всего. Ниже водяного знака зафиксировано всё, кроме сентинела 0. Остальное, включая xid, о котором мы никогда не слышали, считается откатанным: если транзакция не успела записать COMMIT, она не зафиксирована. Защитное условие None if ... в match это ровно та форма, в которой правило проще всего прочитать.

// src/txn/snapshot.rs (продолжение)

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Snapshot {
    /// Самый старый активный xid (горизонт vacuum).
    pub xmin: Xid,
    /// Верхняя граница, эксклюзивно: xid >= xmax ещё не начинались.
    pub xmax: Xid,
    /// Активные транзакции на момент снимка, кроме самой себя.
    pub active: HashSet<Xid>,
}

/// Зафиксирована ли транзакция x к моменту снимка.
pub fn committed_as_of(x: Xid, snapshot: &Snapshot, status: &CommitStatus) -> bool {
    x != 0
        && status.get(x) == TxnState::Committed
        && x < snapshot.xmax
        && !snapshot.active.contains(&x)
}

/// Видна ли версия транзакции `me` под её снимком. Свои записи видны сразу.
pub fn is_visible(tuple: &Tuple, snapshot: &Snapshot, me: Xid, status: &CommitStatus) -> bool {
    let inserter_visible =
        tuple.frozen || tuple.xmin == me || committed_as_of(tuple.xmin, snapshot, status);
    if !inserter_visible {
        return false;
    }
    if tuple.xmax == 0 {
        return true;
    }
    !(tuple.xmax == me || committed_as_of(tuple.xmax, snapshot, status))
}

Снимок это три поля. committed_as_of проверяет четыре условия: не сентинел, зафиксирована, началась раньше снимка и не была активной в момент снимка. Последние два и есть суть изоляции: транзакция, которая зафиксировалась после моего снимка, для меня не зафиксирована.

is_visible читается в два шага. Создатель версии должен быть виден: либо версия заморожена (это поле появится в уроке 10), либо создал её я сам, либо создатель зафиксирован к моему снимку. Удаление не должно быть видно: xmax пуст, либо его поставил кто-то, чей коммит я ещё не вижу. Свои записи и свои удаления видны сразу, иначе транзакция не смогла бы прочитать то, что только что вставила.

Функции свободные и чистые: ни &self, ни ввода-вывода. Им передают ссылки на снимок и реестр, и тесты видимости пишутся без базы, на руками собранных кортежах.

Поиграй с правилом: виджет даёт выставить xmin, xmax, статусы и снимок и показывает, какая ветка is_visible решила судьбу версии.