Своя СУБД на Go · урок 10: vacuum, заморозка и сборка мёртвых версий

Кому это. В уроке 8 удаление стало MVCC-пометкой, а в уроке 9 транзакции начали конкурировать. Движок честно версионирует строки: DELETE ставит Xmax (слот остаётся живым), UPDATE это пометка старой версии плюс вставка новой. У этой схемы есть цена, которую мы пока не платили: мёртвые версии копятся на страницах, и таблица распухает.

Зачем. Сегодня пишем vacuum: проход по куче, который находит мёртвые версии, уплотняет страницу, чистит индекс и замораживает очень старые живые версии. Со стороны Go урок короткий, но в нём сидит одна из самых известных ловушек языка: когда именно defer вычисляет аргументы. Ещё увидим структуру как набор параметров прохода, перечисление вердиктов на iota и колбэк, через который движок чистит индекс.

Важно про объём. Vacuum опирается на всё, что уже построено: версии и видимость из урока 8, снимки из урока 9, слоты страницы из урока 1. Новый пакет один, vacuum, остальное небольшие добавки: бит Frozen в кортеже, одна проверка в видимости, метод горизонта в менеджере транзакций, примитив переписи страницы и метод Database.Vacuum. Как и checkpoint, наш vacuum требует, чтобы открытых транзакций не было. Конкурентный vacuum вынесен в упражнение.

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

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

Vacuum читает кучу через буферный пул, решает судьбу каждой версии по горизонту и переписывает страницу примитивом из page. Пакет не знает ни про каталог, ни про индекс: всё, что ему нужно от движка, приходит полями структуры.

Идея vacuum

Главная мысль в трёх определениях.

Мёртвая версия это кортеж, который не виден и уже не станет виден никакому живому снимку. Таких два рода. Вставка откатанной транзакции: её никто не видел и не увидит. И версия, удалённая зафиксированной транзакцией, чьё удаление видят уже все живые снимки.

Горизонт удаляемости это граница, относительно которой считается “давно”. Без открытых транзакций горизонт это следующий xid: всё зафиксированное удаляемо. С открытыми это минимум Xmin их снимков.

Заморозка решает отдельную, коварную проблему. xid у нас uint32, и рано или поздно счётчик переполнится и пойдёт по кругу. Тогда древний Xmin, который был “маленьким и давним”, вдруг окажется больше текущего и выпадет из любого снимка: строка исчезнет. Замороженная версия выведена из этой арифметики навсегда.

Итак, vacuum обходит каждую живую версию и выносит вердикт: удалить, заморозить или оставить.

Бит Frozen в кортеже

Бит заморозки живёт в infomask заголовка кортежа рядом с InfomaskHasNull из урока 3. В tuple/tuple.go:

const (
	// HeaderSize это размер заголовка кортежа до null bitmap.
	HeaderSize = 12
	// InfomaskHasNull значит, что null bitmap значим.
	InfomaskHasNull = 0x0001
	// InfomaskXminFrozen ставит vacuum (урок 10): xmin такой версии виден всегда.
	InfomaskXminFrozen = 0x0002
)

// Tuple это версия строки: значения плюс заголовок MVCC.
type Tuple struct {
	Values []Value
	Xmin   uint32
	Xmax   uint32
	// Frozen поднимает vacuum: версия видна по xmin всегда.
	Frozen bool
}

// Freeze возвращает замороженную копию версии.
func (t Tuple) Freeze() Tuple {
	t.Frozen = true
	return t
}

Freeze написан на получателе-значении: t внутри метода это копия, метод меняет копию и возвращает её. Исходная версия не трогается, поэтому вызов читается как чистое преобразование: t = t.Freeze(). Копия дешёвая: Values это срез, и копируется только его заголовок, а не значения. Serialize подмешивает бит в infomask (if t.Frozen { infomask |= InfomaskXminFrozen }), а Deserialize читает его обратно (t.Frozen = infomask&InfomaskXminFrozen != 0).

Бит занимает место, которое в infomask уже было зарезервировано. Формат страницы не меняется, только смысл одного флага: замороженная версия занимает столько же байт, а старые файлы, где бит не выставлен, читаются как Frozen: false. Байтовый контракт с TS-портом цел.

Видимость замороженной версии

Замороженный кортеж виден всегда. Это ровно та проверка, которую мы пометили в уроке 8. Финальный txn.IsVisible:

// IsVisible решает, видна ли версия транзакции self под её снимком. Свои записи (xmin или
// xmax == self) видны сразу; замороженный xmin виден всегда (урок 10).
func IsVisible(t tuple.Tuple, snap Snapshot, self uint32, status *CommitStatus) bool {
	if !t.Frozen && 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)
}

Бит влияет только на видимость создателя, удаление проверяется как прежде. Замороженная, но потом удалённая версия по-прежнему скрывается своим Xmax. Заморозка это “вставка видна вечно”, а не “версия бессмертна”.

Горизонт удаляемости

Горизонт считает менеджер транзакций. Xmin снимка мы завели в уроке 8 как раз “для vacuum”. Добавь в txn/manager.go:

// VacuumHorizon это наименьший xid, ещё релевантный живому снимку (RecentGlobalXmin, урок 10).
func (m *Manager) VacuumHorizon() uint32 {
	horizon := m.nextXid
	for _, a := range m.active {
		horizon = min(horizon, a.snapshot.Xmin)
	}
	return horizon
}

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

Перепись страницы

Куча хранит только смещение слота, не длину кортежа. Поэтому “прочитать версии, решить судьбу, переупаковать” будет жить в vacuum, а page получит лишь примитив переписи. В page/page.go:

type Live struct {
	Slot int
	Data []byte
}

// VacuumRewrite переписывает область данных из живых кортежей (vacuum, урок 10). Массив
// слотов сохраняет длину slotCount: живой кортеж остаётся в своём слоте (RID стабилен),
// мёртвый слот становится DeadSlot. Длины кортежей знает только vacuum, он их и передаёт;
// Data обязаны быть отдельными буферами, а не срезами этой же страницы.
func (p *Page) VacuumRewrite(slotCount int, live []Live) {
	p.SetLower(HeaderSize + slotCount*SlotSize)
	p.SetUpper(Size)
	for slot := 0; slot < slotCount; slot++ {
		p.SetSlot(slot, DeadSlot)
	}
	for _, t := range live {
		off := p.Upper() - len(t.Data)
		copy(p[off:], t.Data)
		p.SetUpper(off)
		p.SetSlot(t.Slot, off)
	}
}

Ключевой инвариант: номер слота живого кортежа сохраняется. RID это пара (PageID, Slot), индекс хранит ключ -> RID, и переназначь vacuum слоты, все указатели индекса протухли бы разом. Поэтому массив слотов остаётся той же длины, живые кортежи возвращаются в свои слоты, а мёртвые слоты становятся DeadSlot и больше не переиспользуются (InsertTuple всегда дописывает слот в конец). Переупаковываются только данные: upper поднимается к концу страницы, и всё свободное место собирается в одну дыру между lower и upper.

Последняя строка комментария к функции стоит отдельного внимания, это чисто гошная ловушка. t.Data это срез. Если бы vacuum передал срез этой же страницы (p[off:off+n]), VacuumRewrite сначала затёр бы данные страницы, а потом скопировал бы из уже затёртого места. В TS Buffer.subarray устроен так же, но там vacuum создаёт новые буферы сериализацией, и вопрос не встаёт. Наш vacuum делает то же самое: каждый Data получен из t.Serialize, это свежий буфер.