Своя СУБД на Rust · урок 2: буферный пул

Кому это. В уроке 1 Rust-трека ты завёл Page поверх Box<[u8; PAGE_SIZE]> и DiskManager поверх std::fs::File: один файл как массив страниц, чтение и запись по номеру, аллокация в конце файла, ошибки через Result. Слой работает, но у него то же неприятное свойство, что и у TS- и Effect-версий: каждое read_page идёт на диск, каждое write_page пишет немедленно. Прочитал одну страницу дважды, два системных вызова. Этот урок ставит между движком и диском кэш и снимает эту боль.

Зачем именно Rust. Буферный пул это первый слой, где у страницы появляется жизненный цикл: её закрепляют, с ней работают, закрепление снимают. В TS-треке это пара fetchPage/unpinPage, и следить за балансом приходится руками: забыл unpinPage на ветке с ранним return, и кадр закреплён навсегда. Effect-трек переносит снятие закрепления в финалайзер scope через acquireRelease. В Rust для этого не нужна библиотека: закрепление становится значением, которым кто-то владеет. fetch_page отдаёт PageGuard, и пока guard жив, страница закреплена. Guard умер (вышел из области видимости, уехал в drop, размотался при панике), и его Drop снял закрепление. Это тот же RAII, что закрывал File в уроке 1, только поднятый на уровень выше: там он охранял дескриптор ОС, здесь охраняет кадр кэша. Если идиома владения и Drop подзабылась, освежи урок про move, Copy и drop.

Важно про код. Как и в прошлый раз, ты пишешь свою реализацию с нуля, в своём крейте ourdb (только std, edition 2021, rust-version = "1.84"). Модуль урока это src/buffer_pool.rs, рядом с page.rs и disk.rs из урока 1. Каждый кусок кода приведён целиком и разобран. Печатай руками, запускай cargo test. Буферный пул это первый слой с нетривиальной политикой (вытеснение) и первый слой, где borrow checker начнёт спорить с наивным дизайном. Спор полезно пройти самому.

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

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

После этого урока весь движок ходит за страницами не к DiskManager, а к пулу. Более того, пул забирает DiskManager во владение: BufferPool::new(disk, size) принимает его по значению. В TS-треке диск оставался общим объектом, тест закрывал его сам, и ничто не мешало кому-то писать в файл в обход кэша. Здесь после new переменной disk больше нет, она переехала внутрь пула, и писать в файл мимо пула компилятор не даст.

Зачем вообще кэшировать страницы

Представь seq scan по таблице из урока 3: движок читает страницу 0, потом 1, потом 2. Без кэша каждое чтение это seek плюс read_exact, системный вызов и поход на устройство. Обращение к оперативной памяти стоит десятки наносекунд, к SSD сотни микросекунд, к вращающемуся диску миллисекунды. Разница в тысячи и десятки тысяч раз.

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

Это и есть работа буферного пула: кэш фиксированного числа страниц. Движок просит страницу, пул сначала смотрит, нет ли её уже в памяти (это попадание), и только при промахе идёт на диск. Память не бесконечна, поэтому кадров ограниченное число. Когда все заняты, а нужна новая страница, пул выбирает жертву и вытесняет её. Вся тонкость в одном вопросе: какую страницу выкинуть, чтобы не выкинуть ту, что понадобится через миллисекунду.

Pin и dirty: два флага кадра

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

Pin это счётчик, а не замок. Он говорит одно: «эту страницу сейчас используют, не вытесняй». Держать его могут несколько пользователей сразу, поэтому в кадре лежит pin_count, а не булев флаг. Когда счётчик падает до нуля, страница снова кандидат на вытеснение. Не путай pin с блокировками транзакций из урока 9: pin живёт микросекунды и ничего не знает об изоляции, блокировки живут до конца транзакции и управляют тем, кто что видит.

Второй флаг кадра это dirty. Кадр грязный, если страницу в памяти изменили. Чистую страницу можно выбросить молча, грязную перед вытеснением надо записать. В TS-треке об изменении сообщал тот, кто снимал закрепление: unpinPage(id, true). У нас guard сам запомнит, брал ли ты страницу на запись, и сообщит пулу в Drop.

Clock: дешёвое приближение LRU

Идеальная политика вытеснения выкидывает страницу, к которой дольше всего не обращались. Это LRU, и у него дорогая бухгалтерия: на каждое попадание страницу надо передвинуть в голову списка. Мутация общей структуры на каждый hit, а под конкуренцией ещё и борьба за её замок.

Clock приближает LRU почти бесплатно. Кадры стоят по кругу, по ним ходит стрелка (отсюда «часы»). У каждого кадра один ссылочный бит ref_bit. Обращение к странице поднимает её бит, и всё, никаких списков. Когда нужна жертва, стрелка идёт по кругу:

• кадр запинен (pin_count > 0): пропускаем, его трогать нельзя;
• кадр с поднятым ref_bit: даём второй шанс, гасим бит и идём дальше;
• первый кадр с погашенным битом и без pin это жертва.

За один полный круг стрелка гасит все поднятые биты, поэтому за два круга жертва найдётся гарантированно, если хоть один кадр не запинен. Страница, к которой обращались недавно, переживёт хотя бы один проход стрелки. Ровно эту схему (clock-sweep) использует buffer manager Postgres.

Поиграй с ней вживую. Кнопки сверху запрашивают страницу (это fetch_page и сразу drop guard-а, типичный паттерн чтения). Следи за стрелкой ▼, ref-битами и счётчиками внизу. Запроси одну страницу дважды и посмотри, как поднятый бит спасает её от вытеснения. Запинь кадр и убедись, что стрелка его обходит. Пометь кадр грязным и поймай момент, когда его перед вытеснением пишут на диск.

Если повозился, ты уже видел три морали урока. Повторное обращение поднимает ref-бит и даёт странице второй шанс. Запиненный кадр стрелка обходит, сколько новых страниц ни проси. Грязную жертву перед вытеснением пишут на диск, чистую выкидывают молча. Дальше мы это запрограммируем.

Главное решение порта: pin это владение

Вот где Rust-порт расходится с двумя другими. Сравни, как три трека отвечают на один вопрос: кто и когда снимает закрепление.

Трек	Закрепить	Снять	Кто следит за балансом
TS	pool.fetchPage(id)	pool.unpinPage(id, dirty) руками	программист
Effect	withPin(id) под Scope	финалайзер acquireRelease	тип Scope в подписи
Rust	pool.fetch_page(id)?	Drop у PageGuard	компилятор

В Rust из этого решения вытекают ещё три, и все три это ответы на вопросы borrow checker-а.

1. Guard держит ссылку на пул. Drop у guard-а должен дотянуться до пула, чтобы уменьшить pin_count. Значит, внутри PageGuard<'a> лежит &'a BufferPool, и guard не может пережить пул: это уже не соглашение, а лайфтайм в типе.
2. Методы пула берут &self, а не &mut self. Если бы fetch_page брал &mut self, guard удерживал бы эксклюзивное заимствование пула, и второй fetch_page, пока жив первый guard, не скомпилировался бы. А движку это нужно постоянно: B+Tree держит запиненным родителя, пока спускается в ребёнка, тест урока закрепляет одну страницу дважды. Поэтому снаружи пул неизменяемый, а состояние спрятано в RefCell и меняется через внутреннюю изменяемость. Подробно RefCell разобран в уроке про умные указатели.
3. Pin и latch это разные вещи. Guard это право держать кадр в памяти, и держат его долго (через всю рекурсию по дереву). Сами байты guard отдаёт через latch: guard.read() или guard.write() берут мьютекс кадра на время одного выражения или блока. write() заодно помечает guard грязным.

Запомни пункт 2, это типичная развилка при переносе любого кэша на Rust. Наивный дизайн «у пула &mut self, у guard-а &mut Page» не выживает при первом же сценарии с двумя страницами одновременно. Рабочий дизайн: общий пул через &self, изменяемое ядро в RefCell, каждое заимствование ядра короткое и не выходит за тело метода.

Кадр и состояние: Frame и State

Начнём снизу. Кадр это слот пула: одна страница плюс метаданные для закрепления и вытеснения.

// src/buffer_pool.rs
use std::cell::RefCell;
use std::collections::HashMap;
use std::sync::{Arc, Mutex, MutexGuard, TryLockError};

use crate::disk::{DiskManager, PageId};
use crate::error::{invalid, Result};
use crate::page::Page;

/// Счётчики пула для hit rate.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct BufferPoolStats {
    pub hits: u64,
    pub misses: u64,
    pub evictions: u64,
}

struct Frame {
    page_id: PageId,
    page: Arc<Mutex<Page>>,
    /// Сколько guard-ов держат кадр. Запиненный (>0) вытеснять нельзя.
    pin_count: u32,
    /// Страница изменена в памяти и расходится с диском.
    dirty: bool,
    /// Ссылочный бит clock: страницу трогали с прошлого прохода стрелки.
    ref_bit: bool,
}

Поля те же, что в TS-треке: что лежит в кадре (page_id, page), можно ли вытеснять (pin_count), надо ли писать перед вытеснением (dirty), второй шанс для clock (ref_bit). Frame без pub: снаружи модуля о кадрах знать незачем.

BufferPoolStats выводит Copy. Три u64 копируются дешевле, чем раздаются ссылками, и pool.stats() вернёт снимок по значению. В TS для того же самого писали { ...this.counters }, чтобы снаружи не подкрутили счётчики. Здесь копия получается сама, а подкрутить счётчики пула через копию невозможно. PartialEq нужен тестам: assert_eq!(pool.stats(), BufferPoolStats { .. }).

Интереснее всего тип страницы: Arc<Mutex<Page>>, а не просто Page. Вот почему.

Почему не Page прямо в кадре. Кадры лежат в Vec<Frame> внутри RefCell. Отдать guard-у &Page на элемент вектора значило бы держать заимствование RefCell всё время жизни guard-а. Тогда любой следующий fetch_page упал бы на borrow_mut() с паникой already borrowed, а вытеснение могло бы переложить страницу под живой ссылкой. Поэтому страница живёт в своей куче-аллокации, кадр держит на неё один Arc, guard держит второй. Заимствование RefCell заканчивается вместе с fetch_page, а guard остаётся с собственным владением страницей. Arc::clone это инкремент счётчика ссылок, байты страницы не копируются.

Почему Mutex, а не RefCell. Guard отдаёт байты через &self (на чтение) и через &mut self (на запись), а страница при этом общая с кадром. Значит, нужна внутренняя изменяемость и для страницы. Rc<RefCell<Page>> справился бы в одном потоке, но Rc не Send, и вся база стала бы непередаваемой между потоками. А в уроке 11 TCP-сервер положит Database под Mutex и отдаст её потокам соединений, и для этого каждый её кусок обязан быть Send. Arc<Mutex<Page>> передаваем. Параллелизма внутри движка при этом нет: мьютекс кадра работает как проверяемый latch, а не как очередь ожидания. Об этом ниже, в разделе про latch. Про Send и то, почему Rc его не реализует, подробно в уроке про потоки.

Дальше состояние пула целиком:

struct State {
    disk: DiskManager,
    frames: Vec<Frame>,
    page_table: HashMap<PageId, usize>,
    clock_hand: usize,
    stats: BufferPoolStats,
}

frames заполняется лениво: пока длина меньше pool_size, новая страница кладётся в новый кадр, дальше кадры только переиспользуются через вытеснение. page_table это карта page_id -> индекс кадра, она превращает вопрос «лежит ли страница в пуле» из линейного перебора в O(1). Инвариант держим сами: страница в пуле тогда и только тогда, когда её номер есть в карте и указывает на правильный кадр. clock_hand это позиция стрелки между поисками жертвы, она не сбрасывается. disk теперь живёт здесь же: пул им владеет.

В эталоне examples/our-db/rust у State есть ещё поле hooks: Option<Box<dyn FlushHooks>> и метод set_flush_hooks. Это хуки журнала (правило write-ahead и no-steal), они появятся в уроке 7. Сейчас их нет, и код от этого только проще.

Скелет BufferPool: &self и RefCell

pub struct BufferPool {
    pool_size: usize,
    state: RefCell<State>,
}

impl BufferPool {
    pub fn new(disk: DiskManager, pool_size: usize) -> Result<BufferPool> {
        if pool_size < 1 {
            return Err(invalid(format!("poolSize must be >= 1, got {pool_size}")));
        }
        Ok(BufferPool {
            pool_size,
            state: RefCell::new(State {
                disk,
                frames: Vec::with_capacity(pool_size),
                page_table: HashMap::new(),
                clock_hand: 0,
                stats: BufferPoolStats::default(),
            }),
        })
    }

    // ... методы дальше
}

Снаружи RefCell только pool_size: он не меняется после конструктора и читается без всякого заимствования. Всё, что меняется, лежит внутри. Пул нулевого размера отвергается ошибкой Error::Invalid через помощник invalid из error.rs урока 1. В TS здесь был throw new RangeError, в Effect Effect.fail, у нас обычный Err. Текст сообщения совпадает с эталоном TS, отсюда poolSize в camelCase.

Vec::with_capacity(pool_size) выделяет память под все кадры сразу. Вектор никогда не вырастет больше pool_size, поэтому перевыделений не будет вовсе.

Почему именно так, проще всего показать мысленным экспериментом. Допустим, ты написал пул «в лоб», с &mut self:

// мысленный эксперимент: так в ourdb НЕ сделано
pub fn fetch_page(&mut self, page_id: PageId) -> Result<PageGuard<'_>> { /* ... */ }

let parent = pool.fetch_page(0)?;
let child = pool.fetch_page(1)?; // error[E0499]: cannot borrow `pool` as mutable more than once at a time

PageGuard<'_> привязан к заимствованию пула. С &mut self это эксклюзивное заимствование, и пока жив parent, второе получить нельзя. Спуск по B+Tree, где родитель запинен, пока ты читаешь ребёнка, не написать. С &self оба guard-а держат разделяемые заимствования пула, а их сколько угодно.

Цена решения: правила заимствования для State проверяются не компилятором, а во время выполнения. Два одновременных borrow_mut() дадут панику already mutably borrowed. Поэтому в модуле одно правило: каждый метод берёт self.state.borrow_mut() в начале, отпускает в конце, и никогда не роняет guard и не зовёт другой публичный метод пула, пока держит заимствование. Иначе Drop guard-а позовёт unpin, unpin захочет borrow_mut(), и программа упадёт.

PageGuard: закрепление, которое снимет Drop

Теперь главный тип урока.

/// Запиненная страница. Drop снимает pin (и помечает кадр грязным, если был `write`).
pub struct PageGuard<'a> {
    pool: &'a BufferPool,
    page_id: PageId,
    page: Arc<Mutex<Page>>,
    dirty: bool,
}

impl PageGuard<'_> {
    pub fn id(&self) -> PageId {
        self.page_id
    }

    /// Latch на чтение байтов страницы.
    pub fn read(&self) -> MutexGuard<'_, Page> {
        latch(&self.page)
    }

    /// Latch на запись: страница станет грязной при снятии pin.
    pub fn write(&mut self) -> MutexGuard<'_, Page> {
        self.dirty = true;
        latch(&self.page)
    }
}

impl Drop for PageGuard<'_> {
    fn drop(&mut self) {
        self.pool.unpin(self.page_id, self.dirty);
    }
}

Четыре поля. pool нужен Drop-у, чтобы дотянуться до пула. page_id нужен unpin, чтобы найти кадр. page это собственный Arc на страницу, через него идёт latch. dirty это память guard-а о том, брали ли страницу на запись.

Разберём, что тут проверяет компилятор, а что держится на договорённостях.

Guard не переживёт пул. Лайфтайм 'a связывает guard с заимствованием &'a BufferPool. Попробуй уронить пул, пока guard жив:

let guard = pool.fetch_page(0)?;
drop(pool); // error[E0505]: cannot move out of `pool` because it is borrowed
println!("{}", guard.read().lsn());

В TS такой код компилируется и ломается в рантайме: страница указывает на буфер пула, который уже никто не ведёт. Здесь он не собирается.

Latch не переживёт pin. read() и write() возвращают MutexGuard<'_, Page>, заимствующий сам PageGuard. Значит, держать байты страницы дольше, чем живёт закрепление, нельзя. И ещё одно следствие: write() берёт &mut self, поэтому одновременно читать и писать через один guard компилятор тоже не даст:

let mut guard = pool.fetch_page(0)?;
let page = guard.read();
guard.write().set_lsn(1); // error[E0502]: cannot borrow `guard` as mutable because it is also borrowed as immutable
println!("{}", page.lsn());

Грязность едет к кадру в Drop. write() ставит self.dirty = true до того, как отдать latch. Сам кадр об этом пока не знает: флаг переезжает в frame.dirty в unpin, когда guard умирает. Это ровно контракт TS-версии unpinPage(id, dirty), только аргумент dirty теперь вычисляется сам: был вызов write(), значит грязная. Забыть передать true после правки страницы больше нельзя.

Drop работает и при панике. Если код с живым guard-ом паникует, при размотке стека Rust вызывает Drop всех живых значений, и закрепление снимается. Это аналог финалайзера, который в Effect отрабатывал при ошибке и interrupt. Единственный способ утечь закреплением в безопасном Rust это явно сказать std::mem::forget(guard): forget безопасен, потому что утечка не нарушает память. Кадр тогда останется запиненным навсегда, и рано или поздно пул ответит «exhausted». Но такой код ты увидишь на ревью, в отличие от забытого unpinPage в одной из пяти веток.

Есть приятная идиома, которую стоит запомнить сразу. Короткая правка страницы пишется одним выражением:

pool.fetch_page(0)?.write().set_lsn(123);

Здесь два временных значения: PageGuard из fetch_page и MutexGuard из write(). Временные значения живут до конца выражения и уничтожаются в порядке, обратном созданию. Сначала отпускается latch, потом Drop guard-а снимает pin с dirty = true. Ни одной лишней строки, и закрепление не утекает.

latch: мьютекс, который не ждёт

/// Взять latch кадра. Движок однопоточный (сервер держит Database под Mutex), поэтому
/// занятый latch значит, что этот же поток держит страницу дважды: это баг, а не ожидание.
fn latch(page: &Mutex<Page>) -> MutexGuard<'_, Page> {
    match page.try_lock() {
        Ok(guard) => guard,
        Err(TryLockError::Poisoned(poisoned)) => poisoned.into_inner(),
        Err(TryLockError::WouldBlock) => panic!("page latch is already held"),
    }
}

Почему try_lock, а не lock. Движок однопоточный: в каждый момент его вызывает ровно один поток. Если latch страницы занят, его держит этот же поток, например через второй guard на ту же страницу. Обычный lock() в такой ситуации не вернётся никогда: мьютексы std не реентерабельные, и документация обещает либо дедлок, либо панику без гарантий. try_lock сразу превращает ошибку в громкую панику с понятным текстом. Компилятор ловит такой конфликт внутри одного guard-а, а между двумя guard-ами на одну страницу ловит уже эта функция:

let first = pool.fetch_page(0)?;
let mut second = pool.fetch_page(0)?; // та же страница, pin_count = 2
let page = first.read();
second.write().set_lsn(1); // panic: page latch is already held

Почему Poisoned не ошибка. Мьютекс std становится отравленным, если кто-то запаниковал, держа его. Для страницы это значит «паника случилась посреди правки байтов». Отказываться от страницы навсегда нет смысла: на диске её состояние восстановит журнал из урока 7, а в памяти мы просто продолжаем работать. Поэтому into_inner() и дальше.

Где тут раздвоение понятий pin и latch, видно по коду кучи из следующего урока. Guard живёт весь метод, а latch берётся на одно выражение:

let mut guard = self.pool.fetch_page(page_id)?;
let actual = guard.read().free_space(); // latch на чтение, отпущен в конце строки
// ...
let mut page = guard.write();           // latch на запись до конца блока

fetch_page: сердце пула

Главный метод. Контракт: вернуть закреплённую страницу, то есть guard.

    /// Запинить страницу: попадание растит pin и ставит ref-бит, промах читает с диска
    /// в свободный или отбитый вытеснением кадр.
    pub fn fetch_page(&self, page_id: PageId) -> Result<PageGuard<'_>> {
        let mut state = self.state.borrow_mut();
        if let Some(&index) = state.page_table.get(&page_id) {
            state.stats.hits += 1;
            let frame = &mut state.frames[index];
            frame.pin_count += 1;
            frame.ref_bit = true;
            let page = Arc::clone(&frame.page);
            return Ok(self.guard(page_id, page));
        }
        state.stats.misses += 1;
        let page = state.disk.read_page(page_id)?;
        let page = self.acquire_frame(&mut state, page_id, page)?;
        Ok(self.guard(page_id, page))
    }

Попадание. page_table.get нашёл индекс, страница в памяти. Растим pin_count, поднимаем ref_bit, клонируем Arc на страницу и заворачиваем его в guard. На диск не ходим, ради этого пул и существует. Обрати внимание на Some(&index): паттерн сразу копирует usize из &usize, и заимствование карты на этом заканчивается. Поэтому следующей строкой можно мутировать state.stats, а потом взять &mut state.frames[index].

Промах. Считаем miss, читаем страницу через DiskManager::read_page из урока 1 и отдаём её acquire_frame, который пристроит страницу в кадр и вернёт Arc. ? на read_page поднимает Error::Io (или Error::Invalid на коротком чтении) прямо наверх. Счётчик промахов при этом уже вырос: промах был, просто неудачный.

Где кончается заимствование state. state это RefMut<State>, и он живёт до конца функции. Guard создаётся внутри этой области, но сам RefMut не держит: в нём только &BufferPool, Arc и два простых поля. Когда fetch_page вернётся, RefMut уничтожится, а guard поедет к вызывающему. Это и есть правило «заимствование ядра не выходит за тело метода».

Конструктор guard-а тривиален, его вынесли, чтобы не повторять литерал:

    fn guard(&self, page_id: PageId, page: Arc<Mutex<Page>>) -> PageGuard<'_> {
        PageGuard {
            pool: self,
            page_id,
            page,
            dirty: false,
        }
    }

pool: self работает потому, что self здесь уже &BufferPool. Лайфтайм '_ в возвращаемом типе выведен из &self: guard живёт не дольше заимствования пула.