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

Кому это. В уроке 1 Go-трека ты разложил страницу по байтам через encoding/binary и завёл disk.Manager: один файл как массив страниц, ReadAt и WriteAt по смещению id * page.Size, ошибка из каждой операции, которая трогает диск. Слой работает, но у него то же неприятное свойство, что и у TS-версии: каждое ReadPage идёт на диск, а каждое WritePage пишет немедленно. Прочитал одну страницу дважды, два системных вызова. Этот урок ставит между движком и диском кэш и снимает эту боль.

Зачем именно Go. В уроке 1 Go был удобен своей прямотой: массив байтов, явные смещения, явная ошибка. Буферный пул добавляет вещь, о которой TypeScript-код до сих пор мог не думать: горутины. В Node.js весь твой код крутится в одном потоке, и между двумя строками синхронного кода никто не вклинится. В Go позже, в уроке 11, сервер заведёт горутину на каждое соединение, а движок пустит несколько SELECT параллельно. Все они пойдут за страницами в один пул, к одной таблице кадров и одной стрелке часов. Без защиты это гонка данных, и Go тут честнее многих языков: одновременная запись в map из двух горутин роняет процесс с fatal error: concurrent map writes. Поэтому пул с первого дня живёт под sync.Mutex. Заодно урок покажет вторую сильную сторону Go: маленький интерфейс, объявленный там, где его используют, и подмену диска в тесте без единого фреймворка.

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

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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  ← мы здесь
│  disk.Manager (страницы поверх файла)             │  урок 1
└────────────────────────────────────────────────┘

После этого урока весь движок будет ходить за страницами не к disk.Manager напрямую, а к пулу. Диск остаётся, но прячется за кэшем: к нему обращается только сам пул, когда страницы не оказалось в памяти или когда пора что-то сбросить. Куча из урока 3 и B+Tree из урока 4 получат в конструктор *bufferpool.Pool и про файл не узнают вовсе.

Раскладка пакетов растёт на один каталог:

ourdb/
├── go.mod              module ourdb, go 1.23
├── page/page.go        урок 1: байты страницы
├── disk/disk.go        урок 1: файл как массив страниц
└── bufferpool/
    ├── pool.go                       урок 2: этот урок
    └── lesson02_bufferpool_test.go   тесты урока

Пакет bufferpool импортирует ourdb/page, но не импортирует ourdb/disk. Почему так, разберём через пару разделов, это одно из главных решений порта.

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

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

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

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

Ты можешь спросить: у ОС уже есть страничный кэш, ReadAt второй раз и так прочитает из памяти ядра. Зачем свой? Затем, что кэш ядра не знает того, что знает движок. Он не знает, какую страницу сейчас читает оператор и вытеснять её нельзя. Не знает, какую страницу можно писать на диск только после журнала (урок 7). И каждое обращение к нему это всё равно системный вызов с копированием 8 КБ из ядра в твой срез. Свой пул отдаёт указатель на уже лежащую в памяти страницу, без копии и без перехода в ядро.

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

Прежде чем выбирать жертву, надо понять, какие страницы трогать вообще нельзя. Если оператор сейчас читает кортежи прямо из буфера страницы, а пул в этот момент вытеснит её и положит в кадр другую, оператор будет работать со страницей, которой в пуле уже нет. В Go это даже коварнее, чем в языке с ручной памятью: старый *page.Page не превратится в мусор, сборщик мусора держит буфер живым, пока на него есть указатель. Чтение пройдёт без паники. А вот запись в такую страницу молча пропадёт: пул про этот буфер забыл и на диск его больше не понесёт. Поэтому, пока кто-то работает со страницей, она закреплена.

pin это счётчик, а не замок. Закрепление говорит ровно одно: “эту страницу сейчас используют, не вытесняй”. Несколько читателей могут держать pin на одну страницу одновременно, поэтому это pinCount int, а не bool. Закончив, каждый делает UnpinPage, и когда счётчик падает до нуля, страница снова становится кандидатом на вытеснение. Не путай pin с sync.Mutex и с блокировками транзакций из урока 9: pin не мешает другой горутине читать ту же страницу, он только запрещает пулу её выкинуть. Pin живёт миллисекунды, пока идёт работа с буфером, и к изоляции транзакций отношения не имеет.

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

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

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

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

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

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

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

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

Главное решение порта: мьютекс и маленький интерфейс

В TS-треке BufferPool это класс с полями frames, pageTable, clockHand, который получает в конструктор конкретный DiskManager. В Effect-треке это сервис на слое, где критическую секцию держит семафор на один пермит. У Go-порта свои четыре решения, и каждое вытекает из идиом языка.

Диск за интерфейсом, который объявил сам пул. Пулу нужны от диска четыре метода, и он описывает их у себя: type Disk interface { ReadPage; WritePage; AllocatePage; PageCount }. *disk.Manager подходит под него без единого слова implements, потому что в Go интерфейс выполняется неявно: есть методы с нужными подписями, значит тип подходит. Тест подсовывает обёртку, которая считает обращения. Это классическое правило Go “принимай интерфейсы, возвращай структуры”, и оно же убирает импорт ourdb/disk из bufferpool.
Состояние под sync.Mutex, а не sync.RWMutex. Каждый публичный метод начинает с bp.mu.Lock() и defer bp.mu.Unlock(). Читающего режима нет, потому что у пула нет чистых чтений: даже попадание пишет (pinCount++, refBit = true, Hits++). А промах может вытеснить жертву и записать её на диск, всё под тем же мьютексом.
Две разные беды, два разных механизма. “Все кадры заняты” это нормальная ситуация, на которую вызывающий может ответить, поэтому это значение ошибки ErrExhausted. “Сняли pin, которого не было” это баг в вызывающем коде, и его не ловят, его чинят. Поэтому UnpinPage в этом случае паникует, ровно как sync.Mutex.Unlock на незахваченном мьютексе.
Нет withPin. Effect-порт прятал снятие pin в финалайзер scope. В Go эту работу делает defer на стороне вызывающего: p, err := pool.FetchPage(id), проверка ошибки, defer pool.UnpinPage(id, false). defer срабатывает на любом return и при панике, а значит снятие pin не потеряется на ранней ветке.

Разберём их по очереди, начиная с интерфейса.

Интерфейс Disk: что пулу нужно от диска

// bufferpool/pool.go
// Package bufferpool это кэш страниц между движком и диском (урок 2). Пул фиксированного
// размера, вытеснение по clock (second-chance), pin/unpin, флаг dirty и отложенный сброс.
// Pin это не блокировка, а защита страницы от вытеснения, пока ей кто-то пользуется.
//
// Пул защищён своим sync.Mutex: под RLock движка несколько SELECT-ов из разных горутин
// закрепляют страницы одновременно, и таблица кадров, ref-биты и счётчики должны это пережить.
package bufferpool

import (
	"errors"
	"fmt"
	"sync"

	"ourdb/page"
)

// Disk это то, что пулу нужно от диска. *disk.Manager подходит как есть, а тесты подставляют
// обёртку, считающую обращения.
type Disk interface {
	ReadPage(id uint32) (*page.Page, error)
	WritePage(id uint32, p *page.Page) error
	AllocatePage() (uint32, error)
	PageCount() (uint32, error)
}

Сравни с тем, как это выглядит в языках с явным implements. Там сначала автор disk.Manager должен был бы заранее объявить интерфейс, потом пул сослался бы на него, и оба пакета оказались бы связаны общим определением. В Go интерфейс принадлежит потребителю. Автор disk ничего не знает про пул и не должен: он написал структуру с методами. Пул сам решает, какое подмножество этих методов ему нужно, и описывает его у себя. Если ты подзабыл, как работает неявное выполнение интерфейса, загляни в урок про интерфейсы.

Что это даёт на практике.

Интерфейс узкий. У disk.Manager есть ещё Sync и Close, но пулу они не нужны, и в интерфейс они не попали. Чем меньше методов, тем проще подменить. Роб Пайк формулирует это как “чем больше интерфейс, тем слабее абстракция”.
Тест подменяет диск встраиванием. Обёртка в тестах встраивает *disk.Manager и переопределяет только два метода, остальные два достаются ей даром. Это увидим в разделе про тесты.
Граф импортов чище. bufferpool не импортирует disk. Сборщик программы (движок в уроке 6) импортирует оба и соединяет их одной строкой bufferpool.New(m, size).

Если хочешь, чтобы компилятор упал сразу, когда disk.Manager перестанет подходить под Disk (скажем, кто-то сменит подпись PageCount), в Go есть идиома проверки на этапе компиляции: присвоить (*disk.Manager)(nil) переменной _ типа bufferpool.Disk в пакете, который импортирует оба. В эталоне такой строки нет, её заменяют тесты: они передают настоящий *disk.Manager в bufferpool.New, и несовпадение подписи не скомпилируется.

Кадр, счётчики и сам пул

Теперь данные. Кадр это слот пула: одна страница плюс метаданные закрепления и вытеснения. Счётчики пригодятся для hit rate. Сторожевая ошибка отвечает на вопрос “почему не дали страницу”.

// Stats это счётчики пула.
type Stats struct {
	Hits, Misses, Evictions int
}

// ErrExhausted значит, что жертвы для вытеснения нет.
var ErrExhausted = errors.New("buffer pool exhausted: all frames are pinned or hold uncommitted (no-steal) pages")

type frame struct {
	pageID   uint32
	page     *page.Page
	pinCount int
	dirty    bool
	refBit   bool
}

Пять полей кадра это вся механика урока. pageID и page это что лежит в кадре. pinCount это защита от вытеснения, dirty это надо ли писать перед вытеснением, refBit это второй шанс для clock. Тип frame со строчной буквы, значит он не экспортируется: снаружи пакета про кадры знать незачем, и компилятор не даст их потрогать.

Stats экспортирован и состоит только из int. Это делает его сравнимым: тест проверит счётчики одной строкой s != (bufferpool.Stats{Hits: 1, Misses: 1}), без поэлементного сравнения и без reflect.DeepEqual. И ещё одно свойство даром: Stats() вернёт структуру по значению, то есть копию. В TS-треке ради этого писали { ...counters }, здесь копирование это просто семантика присваивания структуры (подробнее в уроке про значимые и ссылочные типы).

ErrExhausted это сторожевая ошибка на уровне пакета, как io.EOF. Вызывающий проверяет её через errors.Is(err, bufferpool.ErrExhausted) и решает, что делать: подождать, увеличить пул, отказать запросу. Полей ей не нужно, вся информация в самом факте. Хвост сообщения про no-steal станет правдой в уроке 7, когда пул научится отказываться вытеснять страницы незафиксированных транзакций. Сейчас причина одна: все кадры запинены. Текст оставляем как в эталоне, чтобы тесты всех уроков сверяли одну строку. Как устроены errors.Is и сторожевые значения, разобрано в уроке про ошибки.

Сам пул:

// Pool это буферный пул над одним файлом.
type Pool struct {
	mu     sync.Mutex
	disk   Disk
	size   int
	frames []*frame
	table  map[uint32]int // pageID -> индекс кадра
	hand   int
	stats  Stats
}

// New создаёт пул на size кадров. size < 1 это ошибка программиста.
func New(disk Disk, size int) *Pool {
	if size < 1 {
		panic(fmt.Sprintf("poolSize must be >= 1, got %d", size))
	}
	return &Pool{disk: disk, size: size, table: make(map[uint32]int)}
}

Листинг сокращён на одно поле: в эталоне у Pool есть ещё hooks FlushHooks и метод SetFlushHooks, через них в уроке 7 журнал встанет в путь сброса страницы. Пока их нет, и код ниже это учитывает.

Разберём поля.

mu sync.Mutex стоит первым и без указателя. Нулевое значение sync.Mutex это открытый мьютекс, инициализировать его не нужно. Обратная сторона: мьютекс нельзя копировать после первого использования, копия получит своё, отдельное состояние замка. Поэтому New возвращает *Pool, все методы объявлены на указателе, а go vet с анализатором copylocks ругается, если структуру с мьютексом передают по значению.
frames []*frame это срез указателей на кадры. Он растёт лениво через append, пока не дорастёт до size. Указатели, а не значения, затем, чтобы f := bp.frames[i] давал доступ к самому кадру, а не к его копии: правка f.refBit = false должна менять кадр в пуле.
table map[uint32]int отвечает на вопрос “лежит ли страница N в пуле и в каком кадре” за O(1). Именно эта map уронила бы процесс при одновременной записи из двух горутин.
hand int это позиция стрелки часов. Она не сбрасывается между поисками жертвы: следующий поиск начинается там, где закончился предыдущий.
stats Stats это счётчики попаданий, промахов и вытеснений.

size < 1 это ошибка программиста, а не сбой окружения: пул на ноль кадров бессмыслен, и чинить надо вызов. Поэтому New паникует, а не возвращает error. Тут Go-порт совпадает с Effect-портом по смыслу: там это был Effect.die, дефект вне канала ошибок. Правило одно и то же: ошибка как значение для того, на что вызывающий может ответить, паника для нарушенного предусловия.

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

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

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

войти