Раздел 10 · Databases

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

senior~100 мин

без входаВойди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

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

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

Зачем именно Effect. Буферный пул вскрывает в Effect новую грань. У DiskManager была ровно одна забота: ресурс, который надо закрыть. У пула заботы другие: общее изменяемое состояние (кадры, таблица страниц, стрелка часов), к которому могут одновременно потянуться несколько файберов, и вытеснение, которое посреди этого состояния делает ввод-вывод (сбрасывает грязную жертву на диск). Это типичная гонка: два читателя одновременно промахиваются мимо одной страницы и оба лезут её вытеснять. В голом коде ты бы городил ручной мьютекс и молился, чтобы не забыть его отпустить на ветке с ошибкой. Effect даёт семафор на один пермит: он оборачивает критическую секцию целиком, включая запись на диск, и отпускает пермит при ошибке и interrupt сам. А закрепление страницы (pin) станет ещё одним acquireRelease под scope, ровно как обещано в конце прошлого урока.

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

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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 остаётся, но прячется за кэшем: к нему обращается только сам пул, когда страницы не оказалось в памяти или когда пора что-то сбросить. И раз весь движок дальше зависит от пула, пул тоже станет сервисом на теге, который зависит от тега DiskManager. Так слои собираются друг на друга через Layer.provide, а не через new.

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

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

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

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

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. Вторая: запиненный кадр стрелка пропускает, его нельзя вытеснить, сколько ни проси новые страницы. Третья: грязную жертву перед вытеснением сбрасывают на диск, а чистую выкидывают молча. Дальше мы это запрограммируем, и алгоритм слово в слово совпадёт с TS-треком. Расходиться будет обёртка вокруг него.

Главное решение порта: пул это сервис на семафоре

Вот где Effect-порт расходится с голым TypeScript. В TS-треке BufferPool это класс с полями frames, pageTable, clockHand, который ты создаёшь через new BufferPool(disk, poolSize). Состояние живёт в полях экземпляра, методы мутируют их напрямую, и пока всё в одном потоке, этого хватает.

В Effect-порте три отличия, и все они вытекают из одного наблюдения: пул это общее изменяемое состояние, поверх которого делается ввод-вывод.

  1. Пул это сервис (Context.Service плюс Layer), а не класс. Состояние (кадры, таблица страниц, стрелка, счётчики) живёт в замыкании Live-слоя, ровно как дескриптор файла жил в замыкании DiskManager. Слой берёт DiskManager из контекста при постройке, поэтому его тип это Layer<BufferPool, never, DiskManager>: он поставляет BufferPool, но требует DiskManager.
  2. Слой ничем не владеет. У DiskManager был тот же Layer.effect, но его строящий эффект брал ресурс ОС (дескриптор) через acquireRelease, и потому слой уносил с собой финалайзер. У пула своего ресурса нет: его кадры это обычная память, которую соберёт сборщик мусора, а единственный настоящий ресурс (файл) принадлежит DiskManager уровнем ниже. Брать что-то под scope не из-за чего, строящий эффект просто собирает состояние и возвращает объект-реализацию.
  3. Таблицу страниц защищает семафор на один пермит, а не Ref и не транзакция над памятью. Причина учебная и важная: вытеснение делает ввод-вывод (сброс грязной жертвы на диск), а критическую секцию надо держать поверх этого ввода-вывода, иначе два файбера вытеснят один кадр. Ref.modify атомарен только для чистого перехода, внутри него нельзя писать на диск. Effect.tx тоже не спасает: он оптимистичный и при конфликте переигрывает тело транзакции с начала, а переиграть запись на диск нельзя. Семафор же оборачивает произвольный Effect, включая ввод-вывод, и держит секцию целиком.

Запомни третий пункт, это типичная развилка при переносе любого кэша на Effect. Правило: если критическая секция чисто меняет память, бери Ref или транзакцию на TxRef. Если внутри неё есть ввод-вывод, бери мьютекс через семафор. У буферного пула вытеснение пишет на диск, значит мьютекс.

Кадр пула: Frame

Начнём снизу, и снизу ничего нового нет. Кадр это слот пула: одна страница плюс метаданные закрепления и вытеснения. Это чистая изменяемая структура без ввода-вывода, поэтому Effect ей нечего добавить, и она дословно совпадает с TS-версией (только поля заданы через параметры конструктора).

// src/buffer-pool.ts
import { Context, Effect, Layer, Ref, Semaphore } from 'effect';
import type * as Scope from 'effect/Scope';

import { DiskManager } from '~/disk-manager.ts';
import { BufferPoolError, type IoError } from '~/errors.ts';
import { Page } from '~/page.ts';

/** Слот пула: страница плюс метаданные закрепления и вытеснения. */
class Frame {
  constructor(
    public pageId: number,
    public page: Page,
    /** Сколько раз страница закреплена. Запиненную (>0) вытеснять нельзя. */
    public pinCount: number,
    /** Страница изменена в памяти и расходится с диском. */
    public dirty: boolean,
    /** Ссылочный бит clock: страницу трогали с прошлого прохода стрелки. */
    public refBit: boolean,
  ) {}
}

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

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

Размеченная ошибка пула: BufferPoolError

У файлового слоя из урока 1 уже есть IoError. У пула появляются свои сбойные ситуации, и в TS-треке они были обычными throw new Error(...). В Effect мы заведём для них размеченную ошибку и положим её в канал E, чтобы вызывающий мог поймать её точечно через Effect.catchTag. Добавь в errors.ts второй класс рядом с IoError.

// src/errors.ts (добавляем рядом с IoError)
import { Data } from 'effect';

/**
 * Ошибка буферного пула (урок 2). reason различает случаи: unpin страницы не в пуле,
 * unpin сверх pin-счётчика, переполнение пула (все кадры запинены). message несёт
 * человекочитаемую расшифровку.
 */
export class BufferPoolError extends Data.TaggedError('BufferPoolError')<{
  readonly reason: 'not-in-pool' | 'not-pinned' | 'exhausted';
  readonly message: string;
}> {}

Поле reason это машинно-различимая причина, по ней тесты и вызывающий код понимают, что именно стряслось, не разбирая текст. message это пояснение для человека. Где в TS-версии был throw new Error('... is not pinned'), в порте будет Effect.fail(new BufferPoolError({ reason: 'not-pinned', ... })): тот же смысл, но сбой виден в типе и не выскочит исключением мимо канала ошибок.

Интерфейс сервиса и тег

Опишем, что пул умеет, и заведём ключ, по которому его достают из контекста. Сначала маленький тип PinnedPage под закрепление через scope (к нему вернёмся в конце урока), потом сам интерфейс.

/** Запиненная страница: сама страница плюс способ пометить её release грязным. */
export interface PinnedPage {
  readonly page: Page;
  /** Пометить, что при снятии pin страницу нужно отдать как грязную (dirty=true). */
  readonly markDirty: Effect.Effect<void>;
}

export interface BufferPoolImpl {
  /**
   * Запинить страницу и вернуть её (hit или чтение с диска в свободный/освобождённый
   * кадр). Может упасть BufferPoolError('exhausted'), если вытеснять некого.
   */
  readonly fetchPage: (pageId: number) => Effect.Effect<Page, IoError | BufferPoolError>;
  /** Выделить новую страницу на диске и принести её в пул запиненной. */
  readonly newPage: Effect.Effect<readonly [number, Page], IoError | BufferPoolError>;
  /** Снять одно закрепление; dirty=true помечает кадр грязным. */
  readonly unpinPage: (pageId: number, dirty: boolean) => Effect.Effect<void, BufferPoolError>;
  /** Сбросить одну страницу на диск (если она в пуле) и снять флаг dirty. */
  readonly flushPage: (pageId: number) => Effect.Effect<void, IoError>;
  /** Сбросить на диск все грязные кадры. */
  readonly flushAll: Effect.Effect<void, IoError>;
  /** Сколько страниц всего в файле-куче. Делегирует диску. */
  readonly pageCount: Effect.Effect<number, IoError>;

  /**
   * Запинить страницу на время жизни scope: финалайзер снимает pin (с учётом markDirty).
   * Идиоматичная замена пары fetchPage/unpinPage для слоёв доступа (heap, btree).
   */
  readonly withPin: (
    pageId: number,
  ) => Effect.Effect<PinnedPage, IoError | BufferPoolError, Scope.Scope>;
  /** Как withPin, но для свежевыделенной страницы; возвращает её номер. */
  readonly withNewPage: Effect.Effect<
    readonly [number, PinnedPage],
    IoError | BufferPoolError,
    Scope.Scope
  >;

  /** Снимок счётчиков. */
  readonly stats: Effect.Effect<BufferPoolStats>;
  /** Доля попаданий среди обращений, 0 если обращений ещё не было. */
  readonly hitRate: Effect.Effect<number>;
  /** Сколько кадров занято сейчас. Для тестов и отладки. */
  readonly residentPages: Effect.Effect<number>;
  /** Лежит ли страница в пуле. */
  readonly isCached: (pageId: number) => Effect.Effect<boolean>;
  /** Текущее число закреплений страницы, 0 если её нет в пуле. */
  readonly pinCountOf: (pageId: number) => Effect.Effect<number>;
  /** Грязный ли кадр страницы, false если её нет в пуле. */
  readonly isDirty: (pageId: number) => Effect.Effect<boolean>;
}

export class BufferPool extends Context.Service<BufferPool, BufferPoolImpl>()(
  'our-db/BufferPool',
) {}

Прочитай подпись как контракт. fetchPage и newPage могут сбоить двумя способами: IoError (диск) или BufferPoolError (вытеснять некого), и это видно в канале E. unpinPage сбоит только BufferPoolError (диска не касается). Геттеры (stats, hitRate, residentPages и прочие) это Effect без ошибок: они только читают память. Заметь, что часть операций это функции (принимают аргумент), а часть это сами Effect-значения (newPage, flushAll, pageCount, stats): у них нет аргументов, их выполняют через yield*, а не зовут как pool.stats().

withPin стоит особняком: в его типе третий параметр это Scope.Scope. Это значит, что закрепление живёт внутри scope, и финалайзер снимет его при выходе. Реализацию разберём в конце, когда будет на чём.

Live-слой: состояние в замыкании

Теперь сама реализация. Слой строится один раз: захватывает диск из контекста, заводит семафор и замыкается на изменяемом состоянии пула. Покажу make по частям, все объявления const ниже живут внутри одного Effect.gen, а в самом конце он возвращает собранный сервис.

export const BufferPoolLive = (poolSize: number): Layer.Layer<BufferPool, never, DiskManager> =>
  Layer.effect(BufferPool, make(poolSize));

const make = (poolSize: number): Effect.Effect<BufferPoolImpl, never, DiskManager> =>
  Effect.gen(function* () {
    if (poolSize < 1) {
      return yield* Effect.die(new RangeError(`poolSize must be >= 1, got ${poolSize}`));
    }

    const disk = yield* DiskManager;
    // мьютекс на таблицу страниц: один разрешённый вход держит критическую секцию
    // целиком, включая ввод-вывод вытеснения
    const mutex = yield* Semaphore.make(1);

    // изменяемое состояние пула в замыкании слоя
    const frames: Frame[] = [];
    const pageTable = new Map<number, number>();
    let clockHand = 0;
    const counters = { hits: 0, misses: 0, evictions: 0 };

    const advanceHand = (): void => {
      clockHand = (clockHand + 1) % frames.length;
    };

    /** Записать кадр на диск. */
    const flushFrame = (frame: Frame): Effect.Effect<void, IoError> =>
      disk.writePage(frame.pageId, frame.page);

    // дальше: поиск жертвы, acquireFrame, операции, и в конце return BufferPool.of(...)

Разберём по частям.

yield* DiskManager достаёт диск из контекста. С этого момента у замыкания есть всё, что нужно для ввода-вывода. Semaphore.make(1) создаёт семафор на один пермит, тот самый мьютекс. Дальше четыре изменяемых поля в замыкании: frames (сами кадры, массив растёт лениво до poolSize), pageTable (карта pageId -> индекс кадра, чтобы ответ на “лежит ли страница N в пуле” был O(1)), clockHand (позиция стрелки между поисками жертвы, не сбрасывается), counters (статистика).

poolSize < 1 это ошибка программиста, а не сбой окружения: пул на ноль кадров бессмыслен. Поэтому Effect.die, а не Effect.fail: это дефект, а не ожидаемая ошибка, поэтому канал E у make остаётся never. Если кто-то передал нулевой размер пула, программа честно падает, и чинить надо вызов, а не ловить это в рантайме.

flushFrame пока тривиален: просто disk.writePage. В уроке 7, когда появится WAL, сюда добавится правило write-ahead (сбросить журнал до lsn страницы перед записью самой страницы) и политика no-steal (не вытеснять страницу с незафиксированными изменениями). Мы держим его отдельной функцией именно ради этого расширения, но сейчас он делает ровно одно действие.

дальше после входа

Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.

Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.

войти