Своя СУБД на Go · урок 8: транзакции, откат и видимость

Кому это. В прошлом уроке у движка появился журнал. INSERT и CREATE переживают падение: engine.Open проигрывает wal.log и догоняет потерянное. Но мы честно оставили дыру: настоящих транзакций нет, ROLLBACK движок не знает, а DELETE стирает слот и падение не переживает.

Зачем. Сегодня закрываем дыру целиком. Появятся BEGIN, COMMIT и ROLLBACK, и каждая транзакция станет атомарной: всё или ничего. Чтобы это заработало и чтобы починить удаление, кортеж научится версиям. Это MVCC, модель, на которой стоит Postgres. Со стороны Go урок про пакет txn и про то, как разложить ответственность без циклов импорта: менеджер транзакций не знает про каталог и откатывает изменения через функцию-колбэк, а пакет dberr из урока 6 впервые окупает свою отдельность.

Важно про объём. Это самый плотный урок воркшопа: транзакции, версии, видимость, откат и восстановление сходятся вместе. Но почти всё опирается на готовое: журнал из прошлого урока, исполнитель из шестого. Сессионная транзакция SQL одна на движок, но появятся и программные хэндлы db.Begin(), и открыть их можно несколько. Снимки у них заработают честно, а вот запись между ними пока ничем не защищена: блокировки, конфликты и дедлоки это следующий урок. Движок по-прежнему однопоточный, горутины придут в уроке 11.

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

wire/              протокол и TCP-сервер                   урок 11
engine/            каталог, binder, планировщик, Volcano   урок 6
sql/               лексер, парсер, AST                     урок 5
vacuum/            сборка мёртвых версий                   урок 10
lock/              блокировки, граф ожидания               урок 9
txn/               xid, снимки, undo-log                   урок 8  ← мы здесь
dberr/             ошибки движка с кодом                   урок 6
wal/, recovery/    журнал и redo-проход                    урок 7
btree/             B+Tree индекс                           урок 4
heap/, tuple/      куча и кортеж                           урок 3
bufferpool/        кэш страниц, вытеснение clock           урок 2
page/, disk/       страница и файл                         урок 1

Новый пакет один, txn: он выдаёт xid, ведёт статусы транзакций, цепочку записей журнала и undo-log, а ещё решает видимость версий по снимку. Он пронизывает исполнитель: каждый скан теперь фильтрует версии по видимости, а удаление и обновление пишут версии вместо стирания.

Идея версий

Главная мысль урока в одном абзаце. У кортежа из урока 3 уже есть два поля заголовка, которые до сих пор ничего не значили. Xmin это xid транзакции, создавшей версию. Xmax это xid транзакции, удалившей версию, или 0, если версия жива. Удаление больше не стирает слот: оно ставит Xmax. Обновление это удаление старой версии плюс вставка новой. А видна ли строка конкретной транзакции, решает функция видимости по Xmin, Xmax и статусам их транзакций. Так удаление становится обычной журналируемой пометкой, которую можно проиграть при восстановлении и откатить при ROLLBACK.

Версии в странице: SetXmax

Сначала научим страницу писать xmax кортежа на месте. Добавь в page/page.go:

func (p *Page) SetXmax(slot int, xmax uint32) {
	le.PutUint32(p[p.Slot(slot)+tupleXmaxOffset:], xmax)
}

// Xmax читает xmax кортежа в слоте.
func (p *Page) Xmax(slot int) uint32 { return le.Uint32(p[p.Slot(slot)+tupleXmaxOffset:]) }

SetXmax не трогает сам слот, только заголовок кортежа по его смещению. Слот остаётся живым, seq scan кортеж увидит, а показывать ли его, решит видимость. Это принципиальное отличие от DeleteSlot из урока 3: тот зануляет слот (физическое стирание), а SetXmax оставляет версию на месте, лишь помечая её удалённой.

Видимость: снимок и правило

Теперь сердце MVCC. Заведи пакет txn и файл txn/snapshot.go. Начнём с реестра статусов транзакций.

// Package txn это MVCC (урок 8): снимки, видимость версий, реестр статусов транзакций и
// менеджер транзакций с цепочкой prev_lsn, undo-log и границами no-steal и vacuum.
//
// xid это монотонный счётчик; 0 это сентинел (DDL и "нет писателя"), никогда не живая
// транзакция, поэтому xmax == 0 значит "не удалена".
package txn

import "ourdb/tuple"

// State это статус транзакции.
type State uint8

const (
	Aborted State = iota // незнакомый xid тоже считается откатанным
	InProgress
	Committed
)

// CommitStatus это реестр статусов. Явная запись приоритетна, а ниже floor (водяной знак
// последнего checkpoint) любой xid считается зафиксированным: к checkpoint открытых
// транзакций нет, а откатанные не оставляют следов на диске (аналог обрезания CLOG).
type CommitStatus struct {
	states map[uint32]State
	floor  uint32
}

// NewCommitStatus создаёт реестр с явными статусами.
func NewCommitStatus(states map[uint32]State) *CommitStatus {
	s := &CommitStatus{states: make(map[uint32]State, len(states))}
	for xid, st := range states {
		s.states[xid] = st
	}
	return s
}

// Get это статус транзакции.
func (s *CommitStatus) Get(xid uint32) State {
	if st, ok := s.states[xid]; ok {
		return st
	}
	if xid != 0 && xid < s.floor {
		return Committed
	}
	return Aborted
}

// Set ставит явный статус.
func (s *CommitStatus) Set(xid uint32, st State) { s.states[xid] = st }

// RaiseFloorTo поднимает floor: xid ниже считаются committed.
func (s *CommitStatus) RaiseFloorTo(watermark uint32) { s.floor = max(s.floor, watermark) }

// Absorb перенимает floor и явные статусы другого реестра (после recovery).
func (s *CommitStatus) Absorb(other *CommitStatus) {
	s.RaiseFloorTo(other.floor)
	for xid, st := range other.states {
		s.states[xid] = st
	}
}

CommitStatus отвечает на вопрос “зафиксирована ли транзакция xid”. Обычно по явной записи, а незнакомый xid считается откатанным: если мы ничего не знаем о транзакции, значит, она не дошла до COMMIT. Посмотри, как это легло на iota: Aborted стоит первым и получает 0, то есть нулевое значение State это ровно консервативный ответ. Ошибись где-то с инициализацией, и движок скорее спрячет строку, чем покажет незафиксированную.

Тонкость это floor. После checkpoint старые commit-записи журнала усекаются, и любой xid ниже водяного знака считается зафиксированным без явной записи. Это спасает реестр от бесконечного роста, как обрезание CLOG в Postgres. NewCommitStatus копирует переданную карту, а не берёт её себе: снаружи могут дальше её менять, а реестр должен быть единственным владельцем своих данных. max здесь встроенная функция Go 1.21, без math.Max и преобразований во float64.

Дальше снимок и видимость, в том же файле.

// Snapshot это снимок транзакции на момент begin.
type Snapshot struct {
	// Xmin это самый старый активный xid (для горизонта vacuum).
	Xmin uint32
	// Xmax это верхняя граница, эксклюзивно: xid >= Xmax ещё не начинались.
	Xmax uint32
	// Active это открытые транзакции на момент снимка, кроме самой себя.
	Active map[uint32]bool
}

// CommittedAsOf сообщает, зафиксирована ли x к моменту снимка.
func CommittedAsOf(x uint32, snap Snapshot, status *CommitStatus) bool {
	return x != 0 && status.Get(x) == Committed && x < snap.Xmax && !snap.Active[x]
}

// IsVisible решает, видна ли версия транзакции self под её снимком. Свои записи (xmin или
// xmax == self) видны сразу.
func IsVisible(t tuple.Tuple, snap Snapshot, self uint32, status *CommitStatus) bool {
	if t.Xmin != self && !CommittedAsOf(t.Xmin, snap, status) {
		return false
	}
	if t.Xmax == 0 {
		return true
	}
	return t.Xmax != self && !CommittedAsOf(t.Xmax, snap, status)
}

Снимок это три поля: Xmin (самый старый активный xid, пригодится vacuum в уроке 10), Xmax (граница: xid не меньше неё на момент снимка ещё не начинались) и Active (открытые транзакции, кроме самой себя). Active наполняется, как только открыто больше одной транзакции: capture ниже собирает в него все открытые, кроме самой себя. На этом в следующем уроке встанет изоляция снимков вместе с тестами на неё.

IsVisible стоит прочитать медленно (в уроке 10 vacuum добавит в первое условие проверку замороженной версии). Версия видна, если выполнены два условия. Первое: виден создатель, то есть либо это моя вставка (t.Xmin == self), либо создатель зафиксировался к моему снимку. Второе: версия не удалена видимым образом. Xmax == 0 значит жива; иначе она удалена, если удаливший это я сам или он зафиксировался к снимку. CommittedAsOf собирает три условия: статус Committed, транзакция началась до снимка (x < snap.Xmax) и не была активной на его момент.

Ещё одна гошная деталь: !snap.Active[x] работает даже тогда, когда Active равен nil. Чтение из nil-карты в Go не паникует, а возвращает нулевое значение, то есть false. Поэтому тесты собирают снимок как txn.Snapshot{Xmin: 10, Xmax: 10}, не заводя пустую карту. Паникует только запись в nil-карту.

Покрути это вживую. Виджет показывает одну транзакцию на таймлайне: BEGIN, INSERT, DELETE (ставит xmax) и три исхода: COMMIT, ROLLBACK, падение. Видно, как xmin, xmax и статус транзакции вместе решают, видна ли строка.

dberr окупает отдельность

Менеджеру транзакций нужно вернуть ошибку “нет открытой транзакции” с кодом 42000. В уроке 6 мы положили ошибки движка в отдельный пакет-лист dberr и обещали, что это пригодится. Сегодня видно зачем: txn сам создаёт dberr.New(dberr.Engine, ...), а engine импортирует txn. Живи ошибки в engine, txn пришлось бы импортировать engine обратно, и Go не собрал бы такой цикл. У TS-эталона это классы EngineError, UniquenessError в engine/errors.ts, и циклы импорта там не мешают.

Сам пакет сегодня не меняется. Вызывающий по-прежнему узнаёт класс через dberr.CodeOf(err), который ищет *dberr.Error через errors.As и находит код даже внутри обёрток fmt.Errorf("...: %w", err) и склеек errors.Join. Коды для конфликтов и дедлоков понадобятся в следующем уроке: их вернёт пакет lock, второй после txn пользователь dberr.

Менеджер транзакций

Теперь тот, кто выдаёт xid, ведёт статусы, цепочку записей журнала и undo-log. Сначала контракт журналирования: у heap.Journal из прошлого урока появляется второй метод.

// Journal это канал логирования для кучи (урок 7): мутация передаёт свой xid и получает
// lsn для штампа page.lsn. Реализует txn.Manager.
type Journal interface {
	LogInsert(xid, relationID, pageID uint32, slot uint16, image []byte) (uint64, error)
	LogSetXmax(xid, relationID, pageID uint32, slot uint16, xmax uint32) (uint64, error)
}

Реализует его txn.Manager. Положи в txn/manager.go (ниже без VacuumHorizon, он придёт в уроке 10).

// UndoKind это вид отката.
type UndoKind uint8

const (
	// UndoInsert помечает слот вставки мёртвым.
	UndoInsert UndoKind = iota
	// UndoSetXmax возвращает xmax версии в 0 (версия снова жива).
	UndoSetXmax
)

// UndoEntry это запись undo-log.
type UndoEntry struct {
	Kind       UndoKind
	RelationID uint32
	PageID     uint32
	Slot       uint16
}

type active struct {
	beginLSN uint64
	prevLSN  uint64
	snapshot Snapshot
	undo     []UndoEntry
}

// Manager выдаёт xid, берёт снимок при Begin (snapshot isolation), ведёт prev_lsn, undo-log и
// общий CommitStatus. Реализует heap.Journal. Синхронизацию держит движок: мутации идут под
// его эксклюзивным локом, чтения (снимки, границы) под разделяемым.
type Manager struct {
	wal     *wal.Manager
	nextXid uint32
	active  map[uint32]*active
	status  *CommitStatus
}

// NewManager создаёт менеджер над журналом.
func NewManager(w *wal.Manager) *Manager {
	return &Manager{wal: w, nextXid: 1, active: map[uint32]*active{}, status: NewCommitStatus(nil)}
}

// Begin открывает транзакцию.
func (m *Manager) Begin() uint32 {
	xid := m.nextXid
	m.nextXid++
	lsn := m.wal.Append(xid, wal.TypeBegin, nil, 0)
	m.active[xid] = &active{beginLSN: lsn, prevLSN: lsn, snapshot: m.capture(xid)}
	m.status.Set(xid, InProgress)
	return xid
}

// Commit пишет COMMIT и форсирует журнал (durability).
func (m *Manager) Commit(xid uint32) error {
	a, err := m.require(xid)
	if err != nil {
		return err
	}
	m.wal.Append(xid, wal.TypeCommit, nil, a.prevLSN)
	if err := m.wal.Flush(); err != nil {
		return err
	}
	m.status.Set(xid, Committed)
	delete(m.active, xid)
	return nil
}

// Abort применяет undo-log в обратном порядке и помечает транзакцию aborted.
func (m *Manager) Abort(xid uint32, undo func(UndoEntry) error) error {
	a, err := m.require(xid)
	if err != nil {
		return err
	}
	for i := len(a.undo) - 1; i >= 0; i-- {
		if err := undo(a.undo[i]); err != nil {
			return err
		}
	}
	m.wal.Append(xid, wal.TypeAbort, nil, a.prevLSN)
	m.status.Set(xid, Aborted)
	delete(m.active, xid)
	return nil
}

// LogInsert журналирует вставку (heap.Journal).
func (m *Manager) LogInsert(xid, relationID, pageID uint32, slot uint16, image []byte) (uint64, error) {
	payload := wal.Insert{RelationID: relationID, PageID: pageID, Slot: slot, Image: image}.Encode()
	return m.log(xid, wal.TypeInsert, payload, UndoEntry{UndoInsert, relationID, pageID, slot})
}

// LogSetXmax журналирует MVCC-удаление (heap.Journal).
func (m *Manager) LogSetXmax(xid, relationID, pageID uint32, slot uint16, xmax uint32) (uint64, error) {
	payload := wal.SetXmax{RelationID: relationID, PageID: pageID, Slot: slot, Xmax: xmax}.Encode()
	return m.log(xid, wal.TypeSetXmax, payload, UndoEntry{UndoSetXmax, relationID, pageID, slot})
}

func (m *Manager) log(xid uint32, typ uint16, payload []byte, undo UndoEntry) (uint64, error) {
	a, err := m.require(xid)
	if err != nil {
		return 0, err
	}
	a.prevLSN = m.wal.Append(xid, typ, payload, a.prevLSN)
	a.undo = append(a.undo, undo)
	return a.prevLSN, nil
}

// FlushableLSN это граница no-steal: минимум (beginLSN - 1) по открытым транзакциям, иначе
// текущий максимум. Страница с lsn выше тронута незафиксированной транзакцией.
func (m *Manager) FlushableLSN() uint64 {
	if len(m.active) == 0 {
		return m.wal.CurrentLSN()
	}
	var limit uint64 = 1<<64 - 1
	for _, a := range m.active {
		limit = min(limit, a.beginLSN-1)
	}
	return limit
}

// capture берёт снимок: активны все открытые кроме самой себя, Xmax это self.
func (m *Manager) capture(self uint32) Snapshot {
	snap := Snapshot{Xmin: self, Xmax: self, Active: make(map[uint32]bool, len(m.active))}
	for xid := range m.active {
		if xid != self {
			snap.Active[xid] = true
			snap.Xmin = min(snap.Xmin, xid)
		}
	}
	return snap
}

func (m *Manager) require(xid uint32) (*active, error) {
	if a := m.active[xid]; a != nil {
		return a, nil
	}
	return nil, dberr.New(dberr.Engine, "нет открытой транзакции %d", xid)
}

Кода много, но он распадается на ясные части. Begin выдаёт xid, пишет в журнал BEGIN, снимает снимок и заводит запись об активной транзакции с пустым undo-log. Commit пишет COMMIT и форсит журнал: вот она, долговечность фиксации. Abort идёт по undo-log с конца, отменяя каждую запись, пишет ABORT и помечает транзакцию откатанной. ABORT форсить не нужно: если упасть до его записи, транзакция всё равно без COMMIT, и восстановление её пропустит.

LogInsert и LogSetXmax это реализация heap.Journal. Каждый дописывает запись, продлевает цепочку prev_lsn и кладёт запись в undo-log, чтобы при откате знать, что отменять. FlushableLSN это граница no-steal, к ней вернёмся в Database. var limit uint64 = 1<<64 - 1 это максимум uint64: константное выражение вычисляется компилятором без переполнения, потому что нетипизированные константы в Go имеют произвольную точность.

Обрати внимание на три решения, характерные для Go.

Откат через функцию. Abort(xid, undo func(UndoEntry) error) не знает ни про каталог, ни про кучу: он знает только порядок отката. Как именно вернуть слот или xmax, решает вызывающий, передавая функцию. Пакет txn при этом не импортирует engine, и цикла снова нет.

Указатели в карте. active map[uint32]*active хранит указатели. log меняет a.prevLSN и a.undo прямо через указатель, полученный из require. Храни карта значения active, изменение ушло бы в копию, и пришлось бы писать её обратно в карту после каждой записи.

Синхронизации нет. У txn.Manager нет мьютекса, и комментарий объясняет почему: синхронизацию держит движок. Сегодня он однопоточный, а в уроке 11 встанет под sync.RWMutex, и тогда все мутации (begin, commit, журналирование) пойдут под эксклюзивным локом, а чтения (снимки, границы) под разделяемым. Мьютекс у журнала и пула есть, потому что их состояние будут менять и читатели (вытеснение). Состояние менеджера транзакций читатели только читают.

MVCC-удаление в куче

Теперь куча умеет удалять через версию. Добавь в heap/heap.go рядом с Insert:

func (h *File) MarkDeleted(rid Rid, xid uint32) error {
	p, err := h.pool.FetchPage(rid.PageID)
	if err != nil {
		return err
	}
	slot := int(rid.Slot)
	// на мёртвом слоте SetXmax записал бы xmax по смещению 0, то есть в lsn страницы
	if slot >= p.SlotCount() || !p.IsSlotLive(slot) {
		h.pool.UnpinPage(rid.PageID, false)
		return fmt.Errorf("markDeleted: слот %d:%d уже мёртв", rid.PageID, rid.Slot)
	}
	defer h.pool.UnpinPage(rid.PageID, true)
	p.SetXmax(slot, xid)
	if h.journal != nil {
		lsn, err := h.journal.LogSetXmax(xid, h.relationID, rid.PageID, rid.Slot, xid)
		if err != nil {
			return err
		}
		p.SetLSN(lsn)
	}
	return nil
}

Симметрично finishInsert из прошлого урока: меняем кортеж на странице, журналируем, штампуем page.LSN. Гард на мёртвый слот спасает от тихой порчи: смещение мёртвого слота 0, и SetXmax записал бы xmax прямо в заголовок страницы, поверх её lsn. Заметь асимметрию pin: на ветке ошибки страница отпускается чистой явным вызовом, а дальше defer отпустит её грязной. DeleteTuple из урока 3 остаётся физическим примитивом, но движок его больше не зовёт.