Раздел 10 · Databases

Своя СУБД на Go · урок 1: страницы и свой файловый слой

senior~90 мин

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

Своя СУБД на Go · урок 1: страницы и свой файловый слой

Кому это. Ты пишешь на Go: знаешь, чем массив отличается от среза, возвращал error вторым значением и запускал go test. Теперь мы возьмём этот язык и построим им что-то весомое: маленькую честную реляционную СУБД снизу вверх. Это тот же воркшоп ourdb, что и в TS-треке и в Effect-треке, но переложенный на Go. Если ты прошёл одну из тех версий, этот урок покажет ту же механику под другим углом: где у TypeScript был DataView над Buffer, у нас будет массив байтов и encoding/binary, а где было исключение, будет значение error, которое функция честно возвращает.

Зачем именно Go. Движок базы весь состоит из байтов с точной раскладкой и из операций, которые могут сбоить. Go закрывает обе стороны без сторонних модулей. Размер страницы можно зашить прямо в тип: [8192]byte это другой тип, чем [4096]byte, и страницу неправильного размера просто не собрать. 64-битный LSN это родной uint64, а не bigint. Числа в заданном порядке байтов пишет стандартный encoding/binary. Ошибка ввода-вывода видна в подписи каждой функции, которая трогает диск, и её не проглотить молча. А дальше, когда в уроке 2 появятся параллельные читатели, у нас под рукой будут sync.Mutex, горутины и детектор гонок. Этот урок закладывает первый камень: страницу как массив байтов и файл как массив страниц.

Важно про код. Ты пишешь свою реализацию с нуля, в своём репозитории. Готовых примеров под рукой нет, поэтому каждый кусок кода приведён целиком и разобран построчно. Читай, печатай руками, запускай тесты. Понадобится Go 1.23 или новее и модуль без единой зависимости: только стандартная библиотека.

Что мы строим за одиннадцать уроков

ourdb это однонодовая дисковая реляционная СУБД в духе Postgres, урезанная до обучаемого ядра. На входе SQL, на выходе строки. Внутри полный путь запроса: разбор, планирование, исполнение поверх страничного хранилища с индексами, транзакциями и MVCC. Слои снизу вверх, и справа номер урока, который этот слой добавляет:

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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  ← мы здесь
└────────────────────────────────────────────────┘

В Go каждый слой это свой пакет: page, disk, bufferpool, heap, btree, sql, engine и дальше. Пакет импортирует только тех, кто ниже, и компилятор запрещает циклы импорта, поэтому слоистость тут не договорённость, а правило сборки. Мы стоим в самом низу. Без прочного нижнего слоя весь движок повиснет в воздухе, поэтому начинаем с фундамента: как уложить байты на диск так, чтобы их потом можно было адресовать, читать и менять.

Зачем базе своя файловая раскладка

Первый вопрос: у нас уже есть файловая система. Можно открыть файл, дописать в конец строку, прочитать назад. Зачем городить ещё один слой адресации поверх файла?

Причин четыре, и все про контроль.

  • Фиксированный размер блока даёт предсказуемый ввод-вывод. Диск и ОС всё равно работают блоками. Если наш минимальный кусок данных это страница фиксированного размера, то чтение и запись это всегда ровно один блок по известному смещению. Никаких частичных чтений на полстроки.
  • Адресация по номеру страницы стабильна. Кортеж адресуется парой RID вида (номер страницы, номер слота). Пока кортеж жив, его адрес не меняется, и на него можно ссылаться из индекса. Если бы мы дописывали строки в файл как попало, любой сдвиг ломал бы все ссылки.
  • Кэширование становится возможным. В уроке 2 мы поставим между движком и диском буферный пул: страница один раз прочитана, дальше живёт в памяти. Кэшировать имеет смысл единицы фиксированного размера, а не строки произвольной длины.
  • Журнал и восстановление опираются на страницы. WAL в уроке 7 будет писать “страница номер N изменилась так-то”. Без понятия страницы нечего журналировать.

Поэтому почти каждая СУБД строит поверх сырого файла свою адресацию страницами. Это и есть та самая “своя ФС”: мы не доверяем файловой системе ОС вопрос раскладки данных, а берём его на себя. Наш самый нижний слой называется disk.Manager, и его работа ровно одна: представить один файл как массив страниц фиксированного размера с операциями “прочитай страницу N”, “запиши страницу N”, “выдели новую страницу”.

Страница: контракт байтов

Прежде чем писать код, договоримся о формате. Это важнее, чем кажется: реализации ourdb на разных языках читают файлы друг друга, а значит формат страницы зафиксирован раз и одинаков для всех. Go-порт проходит общий корпус эталонных файлов в обе стороны: читает то, что записал TS, и пишет то, что TS прочитает. Числа на диске мы пишем little-endian, родным порядком для x86 и ARM.

Почему 8192 и почему фиксированный размер

Размер страницы 8192 байта, фиксированный, как у Postgres. Почему именно столько?

Это компромисс. Слишком маленькая страница (скажем, 512 байт) означает, что под крупную строку нужно много страниц, и накладные расходы на заголовки растут. Слишком большая (64 КБ) означает, что ради одной короткой строки мы тянем с диска и держим в кэше много лишнего. 8 КБ исторически хорошо ложатся на размер блока файловых систем и на страницы памяти, поэтому это разумное значение по умолчанию. Для нас важнее другое: размер фиксированный. Страница с номером N всегда лежит по смещению N * 8192. Зная номер, мы за одно умножение получаем место на диске.

Анатомия slotted page

Внутри страницы мы используем раскладку slotted page, ту же, что в Postgres. Идея в том, чтобы развести две вещи, которые тянут в разные стороны: указатели фиксированного размера и данные переменной длины.

Заголовок страницы лежит в первых 16 байтах:

смещение  размер  поле     тип    смысл
0         8       lsn      u64    LSN последней записи WAL, изменившей страницу (урок 7)
8         2       lower    u16    конец массива слотов (растёт вправо, к большим смещениям)
10        2       upper    u16    начало области данных (растёт влево, к меньшим смещениям)
12        2       special  u16    начало special-области (метаданные узла B+Tree, урок 4)
14        2       flags    u16    тип и флаги страницы
16        ...     slots[]         массив слотов: на слот u16 со смещением кортежа
...                                свободное место между lower и upper
upper     ...     tuples[]        кортежи растут от конца страницы к началу

Картинка целиком выглядит так. Слева заголовок, дальше массив слотов растёт вправо, кортежи растут влево от конца страницы, посередине свободное место:

0        16        lower                upper                  8192
│ header │ slot0 slot1 slot2 ->    ←  tuple2 tuple1 tuple0 │
│ 16 B   │ растут вправо    free   растут влево            │
                         space = upper - lower

Ключевая величина это свободное место, и оно ровно upper - lower. Вставка нового кортежа делает два движения навстречу: кладёт данные кортежа у upper (сдвигая upper влево, к меньшим смещениям) и добавляет слот у lower (сдвигая lower вправо). Когда lower догоняет upper, свободного места не осталось.

Зачем такая раздвоенность? Слот это маленький указатель фиксированного размера (2 байта). Кортеж это данные переменной длины. Если хранить их вперемешку, удаление кортежа в середине двигало бы всё, что за ним, и ломало бы RID соседей. А так слот всегда на своём месте по своему номеру, кортеж лежит где угодно в области данных, и удаление просто помечает слот, не трогая остальные. Физически место мёртвого кортежа вернёт vacuum в уроке 10.

Поиграй с этим вживую. Кнопка INSERT кладёт кортеж, клик по слоту помечает его мёртвым, VACUUM уплотняет страницу. Смотри за тремя числами внизу: lower, upper и свободным местом. Обрати внимание на главный сюрприз: удаление кортежа не возвращает свободное место сразу.

Если ты повозился с виджетом, ты заметил две вещи, которые и есть мораль урока про страницу. Первая: DELETE двигает не данные, а только статус слота, поэтому свободное место не растёт. Вторая: VACUUM возвращает место, двигая upper вверх, но lower оставляет на месте. Номера живых слотов сохраняются, а значит RID остаётся стабильным и индекс не протухает. Запомни это, в уроке 10 мы это запрограммируем.

Модуль и раскладка пакетов

Прежде чем писать страницу, заведи модуль. Имя модуля ourdb, поэтому пакеты импортируются как "ourdb/page", "ourdb/disk" и так далее:

mkdir ourdb && cd ourdb
go mod init ourdb

go.mod получится из двух строк. Зависимостей нет и не будет до самого конца воркшопа:

module ourdb

go 1.23

К концу урока дерево проекта выглядит так:

ourdb/
├── go.mod
├── page/
│   ├── page.go                  страница: чистые байты, без ввода-вывода
│   └── lesson01_pages_test.go
├── disk/
│   ├── disk.go                  файл как массив страниц
│   └── lesson01_pages_test.go
└── internal/
    └── must/
        └── must.go              помощник тестов

Почему page и disk это два пакета, а не один? Потому что у них разная природа. Страница это арифметика над байтами в памяти: у неё нет ни файла, ни системных вызовов, ни ошибок окружения. Диск это ввод-вывод, и почти каждая его операция может сбоить. Разведя их по пакетам, мы получаем страницу, которую тестируют без единого файла, и слой диска, в котором сосредоточена вся работа с ОС. Каталог internal Go трактует особо: пакет из internal/must могут импортировать только пакеты внутри ourdb. Это помощник для тестов, наружу ему незачем.

Пакет page: страница как массив байтов

Вот первое важное решение порта. Страница это буфер ровно 8192 байта с типизированным доступом к заголовку и слотам. Она не делает ввода-вывода (читать и писать её на диск это дело пакета disk) и не держит ресурсов. Ни одна её операция не может сбоить из-за внешнего мира, поэтому ни одна не возвращает error. Это общий принцип всего воркшопа: ошибка появляется в подписи ровно там, где есть окружение, которое может подвести. Чистое ядро остаётся чистым.

Константы: один раз и навсегда

Сначала размеры и смещения. Когда у тебя несколько реализаций на разных языках, единственный способ их синхронизировать это держать раскладку в одном месте на каждую. В Go это блок констант в начале page.go:

// Package page это страница (урок 1): буфер PAGE_SIZE байт с типизированным доступом к
// заголовку slotted page и слотам. Чистые операции над байтами без ввода-вывода: читать и
// писать страницу на диск это дело пакета disk. Числа на диске little-endian (SPEC.md).
package page

import "encoding/binary"

const (
	// Size это размер страницы в байтах, фиксированный, как у Postgres.
	Size = 8192
	// HeaderSize это размер заголовка slotted page до массива слотов.
	HeaderSize = 16
	// SlotSize это размер слота: u16 со смещением кортежа внутри страницы.
	SlotSize = 2
	// DeadSlot это сентинел мёртвого слота: живой кортеж всегда лежит не ниже HeaderSize.
	DeadSlot = 0
)

// Смещения полей заголовка (SPEC.md, раздел "Страница").
const (
	offLSN     = 0
	offLower   = 8
	offUpper   = 10
	offSpecial = 12
	offFlags   = 14
)

Здесь три детали, и все про Go.

Регистр первой буквы решает видимость. Size, HeaderSize, SlotSize, DeadSlot начинаются с заглавной, поэтому видны снаружи как page.Size. Смещения offLower и компания со строчной, это кухня пакета: остальной движок не должен знать, что lower лежит на восьмом байте, ему хватит метода Lower(). Отдельного слова export или private в Go нет, его роль играет первая буква.

Константы нетипизированные. Size = 8192 без указания типа это нетипизированная константа. Она подстраивается под выражение: в int64(id) * page.Size ведёт себя как int64, в info.Size() / page.Size тоже как int64, в p.SetUpper(page.Size) как int. Будь она int, слою диска пришлось бы писать приведения на каждом шагу. Заодно компилятор проверит, что значение влезает в тип назначения: uint16(Size) соберётся, а uint8(Size) нет.

Сентинел вместо флага. Посмотри на DeadSlot = 0. Слот хранит смещение кортежа внутри страницы. Живой кортеж не может лежать в первых 16 байтах, там заголовок, значит его смещение всегда не меньше HeaderSize. Поэтому ноль в слоте мы используем как метку “слот мёртв”, не заводя отдельный бит. Удаление это запись нуля в слот.

В эталоне в этом же блоке есть ещё смещение xmax в заголовке кортежа. Оно понадобится в уроке 8, когда удаление станет версионным, поэтому сейчас мы его пропускаем.

Тип Page: массив, а не обёртка

Теперь сам тип. В TypeScript страница была классом вокруг Buffer, а размер буфера проверялся в рантайме: Page.from бросал RangeError на буфере не той длины. В Go размер можно записать прямо в тип:

var le = binary.LittleEndian

// Page это сырые байты одной страницы. Диск пишет и читает её целиком.
type Page [Size]byte

// New возвращает свежую страницу: lsn = 0, lower = 16, upper = special = 8192, flags = 0.
func New() *Page {
	p := new(Page)
	p.SetLower(HeaderSize)
	p.SetUpper(Size)
	p.SetSpecial(Size)
	return p
}

type Page [Size]byte объявляет новый тип поверх массива из 8192 байт. Длина массива это часть его типа: [8192]byte и [4096]byte такие же разные типы, как int и string. Значит, страницу неправильного размера в Go не собрать вообще, проверять нечего. Это и есть главный выигрыш порта на нижнем слое: инвариант, который в TS охранял рантайм, здесь охраняет компилятор.

У массива в Go семантика значения, и это надо держать в голове. Присваивание q := *p копирует все 8192 байта, передача Page по значению в функцию тоже копирует страницу целиком. Срез устроен иначе: это маленький заголовок (указатель, длина, ёмкость) над чужим массивом, и копируется только заголовок. Подробно разница разобрана в уроке про устройство срезов. Поэтому весь движок передаёт страницу указателем *Page, а New возвращает именно его.

new(Page) выделяет массив и возвращает указатель на него. Все 8192 байта при этом нули: в Go у любой переменной есть нулевое значение, и для массива байтов это сплошные нули. Нам это на руку: lsn и flags у свежей страницы и должны быть нулевыми, поэтому New выставляет только три поля, у которых значение по умолчанию не ноль.

var le = binary.LittleEndian это просто короткое имя. binary.LittleEndian это значение из стандартного пакета encoding/binary, у которого есть методы Uint16, PutUint16, Uint64, PutUint64 и другие. Каждый читает или пишет число в срез байтов в порядке little-endian. Писать сдвиги и маски руками незачем, об этом же говорит и урок про сериализацию.

Заголовок: геттеры и сеттеры поверх encoding/binary

Каждое поле заголовка это пара методов: геттер читает число по константному смещению, сеттер пишет.

func (p *Page) LSN() uint64           { return le.Uint64(p[offLSN:]) }
func (p *Page) SetLSN(v uint64)       { le.PutUint64(p[offLSN:], v) }
func (p *Page) Lower() int            { return int(le.Uint16(p[offLower:])) }
func (p *Page) SetLower(v int)        { le.PutUint16(p[offLower:], uint16(v)) }
func (p *Page) Upper() int            { return int(le.Uint16(p[offUpper:])) }
func (p *Page) SetUpper(v int)        { le.PutUint16(p[offUpper:], uint16(v)) }
func (p *Page) Special() int          { return int(le.Uint16(p[offSpecial:])) }
func (p *Page) SetSpecial(v int)      { le.PutUint16(p[offSpecial:], uint16(v)) }
func (p *Page) Flags() uint16         { return le.Uint16(p[offFlags:]) }
func (p *Page) SetFlags(v uint16)     { le.PutUint16(p[offFlags:], v) }

Десять однострочников, и в каждом есть что разобрать.

p[offLower:] это срез без копии. p здесь указатель на массив, и Go разрешает индексировать и резать его напрямую: p[off:] значит (*p)[off:]. Получается срез, который смотрит в те же байты страницы, начиная со смещения off. Ничего не копируется, le.PutUint16 пишет прямо в страницу. Это аналог DataView из TS-трека, только без отдельного объекта: срез и есть вид на память.

Получатель указательный. У всех методов получатель *Page, а не Page. Будь он значением, каждый вызов копировал бы 8 КБ, а сеттер вдобавок менял бы копию, и запись бесследно пропадала бы. Указательный получатель меняет ту страницу, на которую смотрит вызывающий.

Границы проверяются. le.Uint16 берёт из среза первые два байта, le.Uint64 первые восемь. Если срез короче, Go не прочитает чужую память, как это сделал бы C, а остановит программу паникой “index out of range”. Ошибка в смещении проявится сразу и громко, а не тихой порчей соседних данных.

LSN это честный uint64. В TS-треке lsn был bigint, потому что number теряет точность после 2⁵³. В Go 64-битное беззнаковое целое родное, никаких особых типов не нужно. LSN пока просто лежит в заголовке и ждёт журнала из урока 7.

lower, upper и special наружу отдаются как int. На диске это u16, но внутри программы с ними считают: вычитают, сравнивают с длиной среза, складывают со смещениями. int это тип, в котором Go отдаёт len() и индексирует срезы, поэтому методы переводят u16 в int на чтении и обратно на записи. Приведение uint16(v) при этом молчаливое: значение больше 65535 обрежется по модулю без паники. Нам хватает запаса, страница всего 8192 байта, но это граница, которую надо знать.

Имена без Get. Геттер называется LSN(), а не GetLSN(), сеттер SetLSN(). Так принято в Go и так советует Effective Go: владелец поля и так понятен из получателя, приставка ничего не добавляет.

Зачем заголовок вообще нужен, нельзя ли держать lower и upper в полях структуры рядом с байтами? Нельзя, и это принципиально. Эти числа должны лежать в байтах страницы, потому что именно эти байты уйдут на диск и вернутся при следующем чтении. Поле структуры живёт только в памяти. Истина это массив, а методы лишь типизированный вид на него. Тип-массив делает эту мысль буквальной: кроме байтов, у Page просто нет других полей.

Слоты и свободное место

Число слотов выводится из lower: массив слотов начинается с HeaderSize, каждый слот занимает SlotSize байт, поэтому (lower - HeaderSize) / SlotSize это сколько слотов уже есть.

func (p *Page) Slot(i int) int        { return int(le.Uint16(p[slotOffset(i):])) }
func (p *Page) SetSlot(i, off int)    { le.PutUint16(p[slotOffset(i):], uint16(off)) }
func (p *Page) IsSlotLive(i int) bool { return p.Slot(i) != DeadSlot }

// SlotCount это число слотов (выводится из lower).
func (p *Page) SlotCount() int { return (p.Lower() - HeaderSize) / SlotSize }

// FreeSpace это свободное место между концом слотов и началом данных.
func (p *Page) FreeSpace() int { return p.Upper() - p.Lower() }

func slotOffset(i int) int { return HeaderSize + i*SlotSize }

SlotCount и FreeSpace не хранят ничего своего: они каждый раз пересчитываются из заголовка. Так не бывает рассинхрона между “что мы думаем” и “что в байтах”. slotOffset это обычная функция, а не метод: ей не нужна страница, только номер слота. Строчная буква оставляет её внутри пакета.

Вставка кортежа: ответ через comma-ok

Главный метод. Он кладёт сырые байты кортежа в страницу: данные у upper (сдвигая его влево), слот у lower (сдвигая его вправо). О формате этих байтов страница ничего не знает, для неё кортеж это непрозрачный []byte. Сериализацию кортежа мы напишем в уроке 3.

// InsertTuple кладёт байты кортежа у upper и добавляет слот у lower. Возвращает номер слота
// или false, если места меньше, чем нужно под данные плюс слот. О формате байтов страница не
// знает: это сырой slotted-page контейнер.
func (p *Page) InsertTuple(data []byte) (int, bool) {
	if len(data)+SlotSize > p.FreeSpace() {
		return 0, false
	}
	off := p.Upper() - len(data)
	copy(p[off:], data)
	p.SetUpper(off)
	slot := p.SlotCount()
	p.SetSlot(slot, off)
	p.SetLower(p.Lower() + SlotSize)
	return slot, true
}

// DeleteSlot помечает слот мёртвым. Место не уплотняется, это работа vacuum.
func (p *Page) DeleteSlot(slot int) { p.SetSlot(slot, DeadSlot) }

Разберём InsertTuple по шагам, это смысловой центр всего урока.

  1. Считаем, сколько места нужно: байты кортежа плюс один новый слот (SlotSize). Если это больше свободного места, страница полна, возвращаем 0, false. Вызывающий код (слой кучи в уроке 3) поймёт, что надо взять другую страницу.
  2. Считаем смещение, куда лягут данные: Upper() - len(data).
  3. copy(p[off:], data) копирует байты кортежа в страницу. Встроенный copy копирует столько байт, сколько влезает в меньший из двух срезов, здесь это ровно len(data).
  4. Двигаем upper влево, на новое начало области данных.
  5. Номер нового слота это текущий SlotCount(). Пишем в этот слот смещение кортежа.
  6. Двигаем lower вправо на один слот.

Почему (int, bool), а не (int, error)? Это тот же вопрос, который Effect-трек решал выбором между null и каналом E. “Места не хватило” это не сбой, а ожидаемый ответ, на который у вызывающего есть план: взять другую страницу. Ошибкой в Go принято называть то, что пошло не так. Полная страница это нормальное состояние, такое же, как отсутствие ключа в map. Для таких ответов в Go есть идиома comma-ok: значение плюс флаг. Ты видел её в v, ok := m[key], и здесь она читается так же: slot, ok := p.InsertTuple(data).

DeleteSlot теперь читается тривиально: пишем DeadSlot (то есть 0) в слот. Данные остаются в области данных, upper не двигается, свободное место не растёт. Это ровно то, что ты видел в виджете: удаление логическое, физическое уплотнение откладывается до vacuum. Почему так? Потому что уплотнение дорого, а ещё потому, что в уроке 8 появится MVCC: “удалённый” кортеж может быть ещё виден старой транзакции, и трогать его рано.

В эталонном page.go ты увидишь ещё несколько методов, которых здесь нет: InsertTupleAt для redo-восстановления (урок 7), SetXmax и Xmax для версионного удаления (урок 8), VacuumRewrite и тип Live для уплотнения (урок 10). Каждый появится в своём уроке, когда для него будет причина.

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

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

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

войти