Своя СУБД на Rust · урок 10: vacuum, заморозка и сборка мёртвых версий

Кому это. В уроке 8 удаление стало MVCC-пометкой, а в уроке 9 транзакции начали конкурировать. DELETE ставит xmax и оставляет слот живым, UPDATE пишет xmax старой версии и вставляет новую. Мёртвые версии копятся на страницах, а таблица распухает.

Зачем. Сегодня пишем vacuum: проход по куче, который находит мёртвые версии, уплотняет страницу, чистит индекс и замораживает старые живые версии.

Зачем именно Rust. Vacuum это проход, которому нужно сразу пять вещей: пул страниц, схема для разбора кортежей, реестр статусов, горизонт и lsn для штампа. Вместо функции с пятью аргументами в Rust удобнее собрать их в структуру ссылок Vacuum<'a> и дать ей метод run. Решение о судьбе версии становится маленьким enum Verdict с тремя вариантами, а классификатор остаётся чистой функцией, которой хватает &Tuple. И снова сработает дисциплина latch-ей из прошлых уроков: страницу сначала читаем под guard.read() в отдельном блоке, и только когда этот latch умер, берём guard.write().

Важно про объём. Новый файл один, vacuum.rs. Остальное это небольшие добавки: бит frozen в кортеже, одна ветка в видимости, метод горизонта у менеджера транзакций, примитив переписи страницы. Наш vacuum, как и checkpoint, требует отсутствия открытых транзакций. В отличие от Effect-трека, Rust-эталон сразу чистит индекс и сбрасывает карту свободного места: удаление из B+Tree и FSM он уже умеет.

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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
└────────────────────────────────────────────────┘

Идея vacuum

Мёртвая версия не видна и уже не станет видна никакому живому снимку. Таких два рода: вставка откатанной транзакции и версия, удалённая зафиксированной транзакцией, чьё удаление видят уже все. Их можно физически стереть.

Горизонт удаляемости это граница, от которой отсчитывается «давно». Нет открытых транзакций: горизонт это следующий xid, удаляемо всё зафиксированное. Есть: горизонт это минимальный xmin их снимков, и старая открытая транзакция держит версии, которые ещё вправе увидеть.

Заморозка решает отдельную проблему. xid у нас это u32, и однажды он переполнится. Древний xmin, который был «маленьким и давно зафиксированным», вдруг окажется «большим», будто из будущего, и видимость спрячет вечно живую строку. Это xid-wraparound. Защита простая: версию, чей xmin зафиксирован и старше горизонта, помечаем битом frozen, и видимость перестаёт сравнивать её xmin со снимком.

Кстати, в Rust переполнение u32 не случится молча. self.next_xid += 1 на u32::MAX в отладочной сборке паникует, а в релизной заворачивается по модулю. Заморозка нужна именно для второго случая: реальный движок обязан переживать заворачивание счётчика, а не падать на нём.

Бит frozen в кортеже

В заголовке кортежа из урока 3 есть поле infomask на 16 бит. Один бит там уже занят флагом «есть NULL». Второй достаётся заморозке:

// src/tuple.rs

pub const INFOMASK_XMIN_FROZEN: u16 = 0x0002;

/// Логическая строка плюс заголовок версии (MVCC).
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Tuple {
    pub values: Vec<Value>,
    pub xmin: Xid,
    pub xmax: Xid,
    /// xmin заморожен vacuum-ом: версия видна по xmin всегда (урок 10).
    pub frozen: bool,
}

// в encode:
    let infomask = if has_null { INFOMASK_HAS_NULL } else { 0 }
        | if frozen { INFOMASK_XMIN_FROZEN } else { 0 };

// в deserialize:
        Ok(Tuple {
            values,
            xmin,
            xmax,
            frozen: infomask & INFOMASK_XMIN_FROZEN != 0,
        })

Бит лежит на диске, поле frozen: bool в памяти. Формат страницы не меняется: старые кортежи читаются с frozen: false. if ... { … } else { 0 } | if ... { … } else { 0 } работает, потому что if в Rust это выражение: два флага склеиваются побитовым ИЛИ без промежуточных переменных.

Видимость замороженной версии

Ветка уже стояла в is_visible из урока 8, сегодня она начинает срабатывать:

// src/txn/snapshot.rs (напоминание)

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);
    // ...
}

tuple.frozen стоит первым в ||, и для замороженной версии остальные проверки не вычисляются вовсе. Ни реестр статусов, ни снимок для неё не нужны. Удаление по-прежнему проверяется: замороженную версию можно удалить, как любую другую.

Горизонт удаляемости

// src/txn/mod.rs (в impl TransactionManager)

    /// Горизонт vacuum (RecentGlobalXmin): минимум snapshot.xmin по открытым, иначе
    /// следующий xid (всё зафиксированное удаляемо).
    pub fn vacuum_horizon(&self) -> Xid {
        self.active
            .values()
            .map(|txn| txn.snapshot.xmin)
            .fold(self.next_xid, Xid::min)
    }

fold(self.next_xid, Xid::min) одной строкой выражает оба случая: без открытых транзакций итератор пуст, и результат это начальное значение, следующий xid. С ними это минимум xmin их снимков. Xid::min передаётся как функция, без замыкания: u32::min уже имеет нужную сигнатуру fn(u32, u32) -> u32. Сейчас vacuum зовётся только без открытых транзакций, но горизонт написан для любого числа открытых транзакций, под упражнение про конкурентный vacuum.

Перепись страницы

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

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

    /// Переписать область данных из живых кортежей (vacuum). Массив слотов сохраняет
    /// длину: живой кортеж остаётся в своём слоте (RID стабилен), мёртвый становится
    /// DEAD_SLOT. Vacuum гарантирует, что `live` помещаются на страницу.
    pub fn vacuum_rewrite(&mut self, slot_count: u16, live: &[(u16, Vec<u8>)]) {
        self.set_lower((HEADER_SIZE + slot_count as usize * SLOT_SIZE) as u16);
        self.set_upper(PAGE_SIZE as u16);
        for slot in 0..slot_count {
            self.set_slot(slot, DEAD_SLOT);
        }
        for (slot, data) in live {
            let tuple_offset = self.place(data);
            self.set_slot(*slot, tuple_offset);
        }
    }

Три шага: массив слотов той же длины, upper снова у конца страницы, все слоты мертвы. Потом каждый живой кортеж кладётся под upper и получает свой прежний номер. Мёртвые слоты остаются DEAD_SLOT навсегда и не переиспользуются: RID стабилен, и индекс не начинает врать. Цена: массив слотов не сжимается, четыре байта на каждый мёртвый слот остаются занятыми.

live: &[(u16, Vec<u8>)] это срез пар «номер слота и готовые байты». Метод не знает ни про схему, ни про видимость: что живо и как сериализовано, решил вызывающий. Примитив страницы остаётся тупым и проверяемым отдельным тестом.