Своя СУБД на Go · урок 7: журнал упреждающей записи и восстановление
Кому это. К этому уроку у тебя собран целый движок на Go. В уроке 6 появилась верхняя половина: каталог, binder, планировщик и исполнитель по модели Volcano. CREATE TABLE, INSERT, SELECT ... WHERE и EXPLAIN уже бегут через engine.Database. Но у движка есть дыра, и ты её, наверное, уже почувствовал.
Зачем именно Go. Убей процесс посреди работы и перезапусти. Что осталось на диске? Часть данных лежит только в буферном пуле, в памяти, и при падении испаряется. Сегодня закрываем половину этой дыры через журнал упреждающей записи и фазу восстановления. В Go это урок про стандартную библиотеку: формат записи собирается через encoding/binary, контрольная сумма считается hash/crc32, файл пишется по смещению через os.File.WriteAt и сбрасывается на диск через File.Sync. Сторонних модулей нет ни одного. А ещё у журнала появляется свой sync.Mutex, хотя движок пока однопоточный: в уроке 11 соединения разойдутся по горутинам, чтения пойдут параллельно, и журнал должен быть к этому готов уже сейчас, как пул из урока 2.
Важно про объём. Это первый из двух уроков про долговечность. Сегодня механика журнала и восстановления на самом простом пути: одиночная вставка в режиме autocommit. Транзакций, отката и удаления через версии ещё нет, это следующий урок. Исполнитель из урока 6 сегодня не меняется: вся работа в двух новых пакетах, wal и recovery, и в проводке журнала к куче и буферному пулу.
Где мы в движке
wire/ протокол и TCP-сервер урок 11
engine/ каталог, binder, планировщик, Volcano урок 6
sql/ лексер, парсер, AST урок 5
vacuum/ сборка мёртвых версий урок 10
lock/ блокировки, граф ожидания урок 9
txn/ xid, снимки, undo-log урок 8
wal/, recovery/ журнал и redo-проход урок 7 ← мы здесь
btree/ B+Tree индекс урок 4
heap/, tuple/ куча и кортеж урок 3
bufferpool/ кэш страниц, вытеснение clock урок 2
page/, disk/ страница и файл урок 1Пакеты повторяют модули TS-эталона, по пакету на урок. WAL это поперечный слой: он не лежит между двумя другими, он висит сбоку и страхует все изменения страниц. Сегодня проведём его к двум местам: к куче (вставка дописывает запись в журнал) и к буферному пулу (страница не уходит на диск раньше своей журнальной записи). А engine.Open получит фазу восстановления.
Что теряется при падении
Вспомни путь вставки. INSERT зовёт heap.File.Insert, та кладёт кортеж в страницу буферного пула и снимает pin с флагом dirty. Грязная страница на диск не идёт сразу: пул сбрасывает её лениво, при вытеснении или при FlushAll. Это правильно для скорости, но смертельно для долговечности: между вставкой и сбросом страница живёт только в памяти. Процесс убили, и кортеж исчез, хотя клиенту мы уже ответили INSERT 0 1.
Решение в журнале. Идея write-ahead такая: перед тем как менять данные, опиши изменение маленькой записью в отдельном журнале и форсни журнал на диск. Журнал пишется только в конец, это дёшево, а страницы данных пусть сбрасываются лениво, как раньше. Если упали, при старте читаем журнал и заново применяем (redo) всё, что журнал успел зафиксировать, а данные не успели.
Формат записи
Запись журнала это самоописывающий блок: заголовок фиксированной формы, payload переменной длины и контрольная сумма в хвосте. Формат общий для всех портов и описан в examples/our-db/SPEC.md, поэтому байты, которые пишет Go, читает TS, и наоборот. Заведи пакет wal и файл wal/record.go.
package wal
import (
"encoding/binary"
"hash/crc32"
"ourdb/page"
)
// Коды типа записи зафиксированы навсегда (SPEC.md): 6 это снятый физический DELETE,
// номер не переиспользуется, чтобы CHECKPOINT и SET_XMAX не сдвигались.
const (
TypeBegin uint16 = 1
TypeCommit uint16 = 2
TypeAbort uint16 = 3
TypeCreate uint16 = 4
TypeInsert uint16 = 5
TypeCheckpoint uint16 = 7
TypeSetXmax uint16 = 8
)
// HeaderSize это lsn u64, prev_lsn u64, xid u32, type u16, length u32.
const HeaderSize = 26
const crcSize = 4
var le = binary.LittleEndian
// Record это одна запись журнала.
type Record struct {
LSN uint64
PrevLSN uint64
Xid uint32
Type uint16
Payload []byte
}
// Encode пишет запись с CRC-32 IEEE (как zlib.crc32) по байтам от lsn до конца payload.
func (r Record) Encode() []byte {
out := make([]byte, HeaderSize, HeaderSize+len(r.Payload)+crcSize)
le.PutUint64(out[0:], r.LSN)
le.PutUint64(out[8:], r.PrevLSN)
le.PutUint32(out[16:], r.Xid)
le.PutUint16(out[20:], r.Type)
le.PutUint32(out[22:], uint32(len(r.Payload)))
out = append(out, r.Payload...)
return le.AppendUint32(out, crc32.ChecksumIEEE(out))
}LSN это номер записи, монотонный. PrevLSN пригодится в следующем уроке для цепочки записей одной транзакции. Xid это номер транзакции. Типов сразу полный набор, включая те, что заработают позже: формат байтов это контракт, и менять его задним числом дороже. Числа little-endian, как и вся раскладка страницы из урока 1.
Посмотри на Encode глазами Go. make([]byte, HeaderSize, HeaderSize+len(r.Payload)+crcSize) сразу резервирует ёмкость под всю запись, поэтому оба append дальше не перевыделяют память. le.AppendUint32 (появился в Go 1.19) дописывает число в конец среза и возвращает новый срез: удобнее, чем завести четыре байта и звать PutUint32. Метод висит на значении Record, а не на указателе: запись маленькая, неизменяемая, и Record{...}.Encode() читается как выражение.
Контрольная сумма это CRC32 по всему телу от lsn до конца payload. crc32.ChecksumIEEE считает тот же полином IEEE, что zlib.crc32 у TS-эталона. Это не мелочь: если бы Go взял полином Castagnoli (crc32.MakeTable(crc32.Castagnoli), он быстрее на современных процессорах), журналы двух портов перестали бы читаться друг другом, и общий корпус examples/our-db/golden упал бы на первой записи.
Decode: до первой рваной записи
Разбор идёт по буферу и останавливается на первой записи, которой нельзя верить. Положи рядом, в тот же record.go.
// Decode разбирает все целые записи и останавливается на первой оборванной или повреждённой
// (писатель один и последовательный, поэтому рваная запись всегда последняя). validEnd это
// смещение сразу за последней целой записью: туда пойдут будущие дозаписи.
func Decode(buf []byte) (records []Record, validEnd int) {
off := 0
for off+HeaderSize <= len(buf) {
length := int(le.Uint32(buf[off+22:]))
if length > page.Size {
break
}
bodyEnd := off + HeaderSize + length
if bodyEnd+crcSize > len(buf) || crc32.ChecksumIEEE(buf[off:bodyEnd]) != le.Uint32(buf[bodyEnd:]) {
break
}
records = append(records, Record{
LSN: le.Uint64(buf[off:]),
PrevLSN: le.Uint64(buf[off+8:]),
Xid: le.Uint32(buf[off+16:]),
Type: le.Uint16(buf[off+20:]),
Payload: append([]byte(nil), buf[off+HeaderSize:bodyEnd]...),
})
off = bodyEnd + crcSize
}
return records, off
}Три причины остановиться: длина больше страницы (мусор вместо заголовка), запись не помещается до конца буфера (процесс убили посреди записи), CRC не сошёлся. Писатель у журнала один и пишет только в конец, поэтому испорченной может быть лишь последняя запись, и всё, что до неё, честно целое.
Две детали, которые в Go легко пропустить. Первая: порядок проверок защищает от паники. Go проверяет границы каждого среза, и buf[bodyEnd:] за концом буфера уронил бы процесс, поэтому сначала сравниваем bodyEnd+crcSize > len(buf), и только потом читаем CRC. Оператор || вычисляется лениво, второе условие до чтения за границей не доходит. Вторая: append([]byte(nil), ...) копирует payload. Без копии каждая запись держала бы срез поверх общего буфера всего файла: сборщик мусора не освободил бы буфер, пока жива хоть одна запись, а любая правка буфера тихо поменяла бы payload. Именованные результаты (records []Record, validEnd int) тут работают как документация: по подписи видно, что второе число это граница целого журнала.
Payload: что несёт запись
Сегодня нужны три payload: для CREATE (DDL проигрывается при старте, чтобы пересобрать каталог), для INSERT (образ кортежа плюс его адрес) и для SET_XMAX. Последний заработает только в следующем уроке, вместе с MVCC-удалением, но формат фиксируем сразу. Положи в wal/payload.go; payload Checkpoint придёт вместе с ротацией журнала.
package wal
import (
"errors"
"fmt"
)
var errShortPayload = errors.New("wal: payload короче, чем требует тип записи")
// Insert это payload INSERT: relation_id u32, page_id u32, slot u16, образ кортежа.
type Insert struct {
RelationID uint32
PageID uint32
Slot uint16
Image []byte
}
func (p Insert) Encode() []byte {
out := make([]byte, 0, 10+len(p.Image))
out = le.AppendUint32(le.AppendUint32(out, p.RelationID), p.PageID)
return append(le.AppendUint16(out, p.Slot), p.Image...)
}
func DecodeInsert(b []byte) (Insert, error) {
if len(b) < 10 {
return Insert{}, errShortPayload
}
return Insert{le.Uint32(b), le.Uint32(b[4:]), le.Uint16(b[8:]), append([]byte(nil), b[10:]...)}, nil
}
// SetXmax это payload SET_XMAX: relation_id u32, page_id u32, slot u16, xmax u32.
type SetXmax struct {
RelationID uint32
PageID uint32
Slot uint16
Xmax uint32
}
func (p SetXmax) Encode() []byte {
out := le.AppendUint32(le.AppendUint32(make([]byte, 0, 14), p.RelationID), p.PageID)
return le.AppendUint32(le.AppendUint16(out, p.Slot), p.Xmax)
}
func DecodeSetXmax(b []byte) (SetXmax, error) {
if len(b) < 14 {
return SetXmax{}, errShortPayload
}
return SetXmax{le.Uint32(b), le.Uint32(b[4:]), le.Uint16(b[8:]), le.Uint32(b[10:])}, nil
}
// Create это payload CREATE: relation_id u32 и текст DDL (UTF-8) до конца payload.
type Create struct {
RelationID uint32 `json:"relationId"`
SQL string `json:"sql"`
}
func (p Create) Encode() []byte { return append(le.AppendUint32(nil, p.RelationID), p.SQL...) }
func DecodeCreate(b []byte) (Create, error) {
if len(b) < 4 {
return Create{}, errShortPayload
}
return Create{le.Uint32(b), string(b[4:])}, nil
}CREATE несёт id отношения и канонический DDL (тот, что печатает принтер из урока 5). INSERT несёт id, адрес (PageID, Slot) и сам сериализованный кортеж. SET_XMAX несёт адрес версии и номер удалившей транзакции. Образ кортежа это физическое логирование: redo просто положит байты обратно.
Почему DecodeInsert возвращает ошибку, а не доверяет длине? В TS чтение за концом Buffer даёт undefined или исключение, в Go это паника index out of range. Payload мы читаем из файла, который мог пережить что угодно, поэтому каждый декодер сначала сверяет длину и отдаёт errShortPayload. Тест урока это и проверяет на DecodeSetXmax: короткий payload это ошибка, а не упавший процесс. Сентинел-ошибка через errors.New на уровне пакета это обычная идиома Go, как io.EOF.
Строка append(le.AppendUint32(nil, p.RelationID), p.SQL...) показывает ещё одну мелочь: к срезу байт можно дописать строку через ... без явного []byte(p.SQL). Это частный случай, записанный прямо в спецификации языка, и промежуточный []byte не создаётся.
wal.Manager: файл, буфер и мьютекс
Журнал владеет файлом. Записи копятся в памяти и попадают на диск при фиксации или когда правило write-ahead требует сбросить журнал перед записью грязной страницы. Положи в wal/wal.go. Методы Checkpoint (ротация журнала) и CurrentLSN живут тут же, но понадобятся только в следующем уроке.
// Package wal это журнал упреждающей записи (урок 7, SPEC.md, раздел "Запись WAL"). Записи
// переменной длины с самоописывающим заголовком и CRC32, числа little-endian. Один журнал на
// базу, общий для всех таблиц (записи несут relationId). Записи копятся в памяти и попадают
// на диск при commit (fsync) или когда write-ahead требует сбросить журнал перед записью
// грязной страницы.
//
// Manager под своим sync.Mutex: под RLock движка вытеснение страницы в одной горутине-читателе
// может сбрасывать журнал, пока другая делает то же самое.
package wal
import (
"io"
"os"
"sync"
)
// Manager владеет файлом журнала.
type Manager struct {
mu sync.Mutex
f *os.File
offset int64
nextLSN uint64
flushed uint64
pending []byte
}
// Open открывает журнал и продолжает нумерацию после существующих записей. Рваный хвост
// перезапишется следующей дозаписью.
func Open(path string) (*Manager, error) {
f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE, 0o644)
if err != nil {
return nil, err
}
data, err := io.ReadAll(f)
if err != nil {
f.Close()
return nil, err
}
records, end := Decode(data)
var last uint64
if len(records) > 0 {
last = records[len(records)-1].LSN
}
return &Manager{f: f, offset: int64(end), nextLSN: last + 1, flushed: last}, nil
}
// ReadAll читает все целые записи (для recovery).
func (m *Manager) ReadAll() ([]Record, error) {
m.mu.Lock()
defer m.mu.Unlock()
data, err := io.ReadAll(io.NewSectionReader(m.f, 0, 1<<62))
if err != nil {
return nil, err
}
records, _ := Decode(data)
return records, nil
}
// Append дописывает запись в память и возвращает её lsn. На диск она пока не идёт.
func (m *Manager) Append(xid uint32, typ uint16, payload []byte, prevLSN uint64) uint64 {
m.mu.Lock()
defer m.mu.Unlock()
lsn := m.nextLSN
m.nextLSN++
m.pending = append(m.pending, Record{LSN: lsn, PrevLSN: prevLSN, Xid: xid, Type: typ, Payload: payload}.Encode()...)
return lsn
}
// Flush пишет накопленные записи и делает fsync.
func (m *Manager) Flush() error {
m.mu.Lock()
defer m.mu.Unlock()
return m.flushLocked()
}
func (m *Manager) flushLocked() error {
if len(m.pending) > 0 {
if _, err := m.f.WriteAt(m.pending, m.offset); err != nil {
return err
}
m.offset += int64(len(m.pending))
m.pending = m.pending[:0]
}
if err := m.f.Sync(); err != nil {
return err
}
m.flushed = m.nextLSN - 1
return nil
}
// FlushUpTo это правило write-ahead: журнал durable хотя бы до lsn.
func (m *Manager) FlushUpTo(lsn uint64) error {
m.mu.Lock()
defer m.mu.Unlock()
if m.flushed >= lsn {
return nil
}
return m.flushLocked()
}
// Close закрывает файл журнала.
func (m *Manager) Close() error { return m.f.Close() }Разберём по полям. offset это место следующей записи в файле, nextLSN это следующий номер, flushed это последний lsn, который точно на диске, pending это закодированные, но ещё не записанные байты. Open читает файл целиком, берёт validEnd из Decode и продолжает нумерацию с последней целой записи: журнал переживает перезапуски, номера не сбрасываются.
Почему файл открыт без O_APPEND, а пишется через WriteAt(m.pending, m.offset)? Из-за рваного хвоста. Если процесс убили посреди записи, в конце файла лежит огрызок. Decode его отбросил, и offset указывает на начало огрызка: следующая дозапись честно затрёт мусор. С O_APPEND ядро писало бы всегда в конец файла, за огрызок, и при следующем чтении Decode остановился бы на огрызке, потеряв всё, что за ним. К тому же Go это прямо запрещает: WriteAt у файла, открытого с O_APPEND, возвращает ошибку.
ReadAll читает через io.NewSectionReader(m.f, 0, 1<<62). Это читатель поверх ReadAt с нуля: он не зависит от текущей позиции файла, которую сдвинул io.ReadAll в Open. Граница 1<<62 значит “до конца, сколько бы ни было”. File.Sync это fsync: пока он не вернулся, данные могут лежать в кэше ядра и пропасть вместе с питанием.
Теперь мьютекс. Сегодня движок зовёт журнал из одной горутины, и sync.Mutex кажется лишним. Но смотри на комментарий пакета. В уроке 11 каждое соединение получит свою горутину, а движок встанет под sync.RWMutex и пустит SELECT параллельно под разделяемым RLock. Чтение тоже может вытеснить грязную страницу, а вытеснение по правилу write-ahead зовёт FlushUpTo. Ровно по той же причине свой мьютекс с урока 2 держит пул. Две горутины-читателя одновременно сбрасывают журнал, и без мьютекса они записали бы один pending дважды или потеряли offset. Поэтому журнал сам защищает своё состояние, не надеясь на лок движка. Публичные методы берут m.mu и отпускают его через defer, а flushLocked по соглашению Go (суффикс Locked) зовут только с уже взятым мьютексом: так FlushUpTo проверяет flushed и сбрасывает журнал под одним захватом, без окна между проверкой и записью.
Куча журналирует вставку
Куча должна описывать каждую вставку в журнале. Контракт для этого ты завёл ещё в уроке 3, когда в heap.New передавался nil: узкий интерфейс прямо в пакете heap, рядом с его потребителем. Сегодня он оживает.
// Journal это канал логирования для кучи (урок 7): мутация передаёт свой xid и получает
// lsn для штампа page.lsn. Реализует txn.Manager.
type Journal interface {
LogInsert(xid, relationID, pageID uint32, slot uint16, image []byte) (uint64, error)
}Второй метод, LogSetXmax, добавится в уроке 8 вместе с MVCC-удалением. Это классическая идиома Go: интерфейс объявляет тот, кто им пользуется, а реализация подходит к нему неявно, без слова implements. Куче нужна способность “записать вставку и получить lsn”, а кто это делает, ей всё равно. В финальном движке интерфейс реализует txn.Manager из следующего урока, с цепочкой записей и откатом. На этапе 7 хватит минимальной реализации autocommitJournal, которая дописывает INSERT-запись с prev_lsn = 0; она живёт в engine, и мы увидим её ниже.
heap.New(pool, schema, journal, relationID) с урока 3 принимает журнал и номер таблицы. До сих пор каталог передавал nil и 0, и куча пропускала ветку журнала; теперь каталог передаёт настоящий журнал и RelationID таблицы. Без журнала куча ведёт себя по-старому, и старые тесты не ломаются. Вся логика сидит в одном месте, где вставка завершается:
func (h *File) finishInsert(p *page.Page, pageID uint32, slot int, data []byte, xid uint32) (Rid, error) {
defer h.pool.UnpinPage(pageID, true)
rid := Rid{PageID: pageID, Slot: uint16(slot)}
if h.journal != nil {
lsn, err := h.journal.LogInsert(xid, h.relationID, pageID, rid.Slot, data)
if err != nil {
return Rid{}, err
}
p.SetLSN(lsn)
}
return rid, nil
}Порядок такой: кортеж уже лежит в странице (InsertTuple отработал выше), потом журналируем и штампуем page.LSN, и только потом defer снимает pin с флагом dirty. На диск отсюда ничего не уходит, журнал копит запись в pending. Гарантию write-ahead даст буферный пул в момент, когда страница реально пойдёт на диск. defer в первой строке гарантирует, что pin снимется на любом выходе, включая ошибку журнала: в Go это замена try/finally.
Страница помнит свой redo: InsertTupleAt
При восстановлении redo обязан положить кортеж ровно в тот слот, что записан в журнале, а не “куда влезет”. InsertTuple из урока 1 сам выбирает следующий слот, а redo нужен адресный вариант. Добавь в page/page.go.
func (p *Page) InsertTupleAt(slot int, data []byte) {
off := p.Upper() - len(data)
copy(p[off:], data)
p.SetUpper(off)
p.SetSlot(slot, off)
if need := HeaderSize + (slot+1)*SlotSize; need > p.Lower() {
p.SetLower(need)
}
}Номер слота приходит снаружи. Это важно для верности redo: если между двумя вставками в журнале есть пропуск (в следующем уроке так будет с откатанной вставкой), redo обязан сохранить исходные номера слотов, иначе RID сдвинутся, и индекс начнёт врать. InsertTupleAt поднимает lower ровно настолько, чтобы покрыть указанный слот; пропущенные слоты остаются нулевыми, то есть мёртвыми. p[off:] работает потому, что Page в Go это массив [page.Size]byte, и срез от него указывает прямо в байты страницы, без копирования.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.