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

Кому это. В уроке 1 ты завёл DiskManager: один файл как массив страниц фиксированного размера, чтение и запись страницы по номеру, аллокация. Слой работает, но у него есть неприятное свойство: каждое readPage идёт на диск, а каждое writePage пишет немедленно. Прочитал одну и ту же страницу дважды, два похода к диску. Этот урок ставит между движком и диском кэш и снимает эту боль.

Зачем. Разрыв между памятью и диском это главная константа, вокруг которой устроены все СУБД. Обращение к оперативной памяти это десятки наносекунд, к SSD сотни микросекунд, к вращающемуся диску миллисекунды. Разница в тысячи и десятки тысяч раз. Любой движок, который ходит на диск за каждой страницей, обречён быть медленным. Буферный пул это слой, который держит горячие страницы в памяти и сводит дисковый ввод-вывод к минимуму. Заодно он даёт две вещи, без которых не построить остальной движок: контроль над тем, когда именно грязная страница уходит на диск (это понадобится для WAL в уроке 7), и понятие pin, защищающее страницу от вытеснения, пока с ней работают.

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

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

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

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

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

Представь seq scan по таблице из урока 3: движок читает страницу 0, потом 1, потом 2. Без кэша каждое чтение это системный вызов и поход на устройство. Но рабочая нагрузка почти никогда не равномерна. У данных есть локальность: одни страницы (корень индекса, верхушка популярной таблицы, страница каталога) читаются постоянно, другие почти никогда. Если горячую страницу прочитать с диска один раз и дальше держать в памяти, тысячи последующих обращений к ней станут бесплатными.

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

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

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

pin это счётчик, а не замок. Закрепление говорит ровно одно: “эту страницу сейчас используют, не вытесняй”. Несколько читателей могут держать pin на одну страницу одновременно, поэтому это pinCount, а не булев флаг. Закончив, каждый делает unpin, и когда счётчик падает до нуля, страница снова становится кандидатом на вытеснение. Важно не путать pin с блокировками транзакций из урока 8: pin живёт миллисекунды (пока идёт работа с буфером) и не имеет отношения к изоляции, блокировки живут до конца транзакции и управляют видимостью. Pin это чисто про управление памятью кэша.

Второй флаг кадра это dirty. Кадр грязный, если страницу в памяти изменили и она разошлась с диском. Чистый кадр можно выбросить молча, его копия на диске актуальна. Грязный перед вытеснением надо записать. Поэтому unpin принимает аргумент dirty: тот, кто менял страницу, говорит об этом при отпинивании.

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

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

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

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

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

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

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

Кадр пула: Frame

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

// src/buffer-pool.ts
import type { DiskManager } from '~/disk-manager.ts';
import { Page } from '~/page.ts';

/** Слот пула: страница плюс метаданные закрепления и вытеснения. */
class Frame {
  /** Номер страницы, которая сейчас лежит в кадре. */
  pageId: number;

  /** Сама страница (обёртка над буфером из урока 1). */
  page: Page;

  /** Сколько раз страница закреплена. Запиненную (>0) вытеснять нельзя. */
  pinCount = 0;

  /** Страница изменена в памяти и расходится с диском. */
  dirty = false;

  /** Ссылочный бит clock: страницу трогали с прошлого прохода стрелки. */
  refBit = false;

  constructor(pageId: number, page: Page) {
    this.pageId = pageId;
    this.page = page;
  }
}

/** Счётчики пула. Пригодятся для hit rate и EXPLAIN ANALYZE в уроке 6. */
export interface BufferPoolStats {
  hits: number;
  misses: number;
  evictions: number;
}

Четыре поля это вся механика урока. pageId и page это что лежит в кадре. pinCount это защита от вытеснения, dirty это надо ли писать перед вытеснением, refBit это второй шанс для clock. BufferPoolStats это три счётчика, по ним мы потом считаем долю попаданий: для отладки сейчас и для EXPLAIN ANALYZE в уроке 6.

Frame намеренно не экспортируется: это внутренняя деталь пула, снаружи о кадрах знать незачем.

Скелет BufferPool

Теперь сам пул. Сначала поля и конструктор, потом методы по одному.

export class BufferPool {
  private readonly disk: DiskManager;
  private readonly poolSize: number;

  /** Кадры пула, заполняются лениво до poolSize, дальше переиспользуются. */
  private readonly frames: Frame[] = [];

  /** pageId -> индекс кадра в frames. */
  private readonly pageTable = new Map<number, number>();

  /** Стрелка часов: индекс кадра, с которого начнётся следующий поиск жертвы. */
  private clockHand = 0;

  private readonly counters: BufferPoolStats = { hits: 0, misses: 0, evictions: 0 };

  constructor(disk: DiskManager, poolSize: number) {
    if (poolSize < 1) {
      throw new RangeError(`poolSize must be >= 1, got ${poolSize}`);
    }
    this.disk = disk;
    this.poolSize = poolSize;
  }

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

Разберём структуру данных, она важнее, чем код методов.

frames это сами кадры. Массив заполняется лениво: пока он короче poolSize, новая страница добавляется в конец (свободный кадр есть). Как только длина достигла poolSize, новых кадров не создаём, а переиспользуем существующие через вытеснение. Так пул никогда не занимает больше poolSize страниц памяти.

pageTable это карта pageId -> индекс кадра. Без неё ответ на вопрос “лежит ли страница N в пуле” стоил бы линейного перебора кадров на каждое обращение. С картой это O(1). Инвариант, который мы будем держать руками: если страница в пуле, её pageId есть в pageTable и указывает на правильный кадр; при вытеснении запись из карты удаляется.

clockHand это позиция стрелки часов между поисками жертвы. Она не сбрасывается: где остановились в прошлый раз, оттуда и продолжим. Это и делает clock круговым обходом, а не поиском с нуля.

counters это статистика. Считаем тут же, в горячем пути, это почти бесплатно.

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

Главный метод. Движок зовёт его, чтобы получить страницу по номеру. Контракт: вернуть закреплённую (запиненную) страницу. Закреплённую, потому что вызывающий собирается с ней работать, и до его unpin вытеснять её нельзя.

  /**
   * Запинить страницу и вернуть её. Если страница уже в пуле, это попадание (hit):
   * растим pin_count, ставим ref-бит. Иначе промах: читаем с диска в свободный или
   * освобождённый вытеснением кадр.
   */
  fetchPage(pageId: number): Page {
    const cached = this.pageTable.get(pageId);
    if (cached !== undefined) {
      const frame = this.frames[cached]!;
      frame.pinCount++;
      frame.refBit = true;
      this.counters.hits++;
      return frame.page;
    }

    this.counters.misses++;
    const page = this.disk.readPage(pageId);
    const index = this.acquireFrame(pageId, page);
    return this.frames[index]!.page;
  }

Две ветки.

Попадание. pageTable.get(pageId) вернул индекс, значит страница в памяти. Растим pinCount (теперь у неё на одного пользователя больше), поднимаем refBit (к ней только что обратились, дать второй шанс при вытеснении), считаем hit и отдаём страницу. На диск не ходим. Это и есть смысл всего пула.

Промах. Страницы в памяти нет. Считаем miss, читаем её с диска через DiskManager.readPage из урока 1, и зовём acquireFrame, чтобы пристроить её в кадр (свободный или отбитый у жертвы). acquireFrame уже вернёт страницу закреплённой, его код ниже.

Восклицательный знак в this.frames[cached]! это non-null assertion: мы только что достали индекс из pageTable, значит кадр по нему точно есть, и компилятор с noUncheckedIndexedAccess можно успокоить. Инвариант pageTable держим сами, поэтому assertion тут честный.