6 октября 2026Команда Сарнас

Что внутри bbolt: как устроено самое простое KV-хранилище

Устройство bbolt разбирается на уровне отдельных страниц и метаданных: как хранилище определяет размер страницы при открытии, зачем держит две мета-страницы и почему блокирует файл. Особенно полезно тем, кто хочет понять, как надёжность и восстановление после сбоев обеспечиваются на уровне формата файла, а не API.

bbolt — встраиваемое хранилище «ключ-значение», которое целиком живёт в одном файле. За простым API прячется несколько слоёв механики: при открытии файла нужно выбрать размер страницы, проверить целостность метаданных и взять блокировку; при записи — не перезаписывать старые страницы на месте, а строить новые; при коммите — записывать данные и метаданные в две фазы, чтобы пережить сбой. Ниже разобрано, что именно происходит в каждом из этих мест.

Что делает Open при старте

Размер страницы определяется в несколько шагов. Если options.PageSize не задан (равен нулю), берётся common.DefaultPageSize. Если файл уже существует и непустой, размер страницы пытаются выяснить из мета-страниц. Для этого перебираются возможные размеры от 1KB до 16MB — это 1024 << i для i от 0 до 14. Для каждого варианта читается блок 0x1000 байт по соответствующему смещению, и размер принимается только если прочитанная мета-страница проходит проверку целостности. Так хранилище узнаёт свой размер страницы, не полагаясь на внешнюю конфигурацию.

После отображения файла в память сохраняются ссылки на обе мета-страницы. Затем обе проверяются на целостность, и ошибка возвращается только если невалидны обе сразу:

err0 := db.meta0.Validate()
err1 := db.meta1.Validate()
if err0 != nil && err1 != nil {
	return err0
}

Смысл в том, что при повреждении одной мета-страницы можно восстановиться по второй.

Блокировка файла

При открытии bbolt берёт файловую блокировку , чтобы два процесса не писали мета-страницы и список свободных страниц раздельно — иначе база повредилась бы. Режим блокировки зависит от режима открытия: обычное (не read-only) открытие блокирует файл эксклюзивно, а при options.ReadOnly берётся разделяемая блокировка .

Если файл уже занят, Open не завершается сразу, а ждёт освобождения. При заданном Options.Timeout ожидание ограничено этим таймаутом, и по его истечении Open возвращает ошибку блокировки. Без таймаута ожидание может быть бесконечным: открытие уже открытой базы зависает, пока другой процесс её не закроет. При неудачной блокировке Open закрывает уже открытый файл и возвращает ошибку.

Формат файла: страницы и метаданные

Страница описывается структурой Page с полями id, flags, count и overflow. id — номер страницы в файле, flags — тип страницы, count — число элементов на странице, overflow — сколько дополнительных страниц занимает эта страница. Типы страниц заданы флагами: BranchPageFlag, LeafPageFlag, MetaPageFlag, FreelistPageFlag.

Проверки типа страницы используют строгое равенство: каждая из проверок — листовая, мета, свободная, ветвление — срабатывает только если flags в точности равен соответствующей константе. То есть допустим ровно один установленный флаг. Общая проверка валидности объединяет эти четыре проверки через логическое ИЛИ. FastCheck(id) — это быстрая внутренняя проверка целостности страницы: она немедленно останавливает работу с паникой, если номер страницы не совпадает с ожидаемым или если флаги не соответствуют ни одному допустимому типу. Паника, а не возврат ошибки, выбрана потому, что такое несоответствие означает повреждение внутренних структур, а не ожидаемую ошибку времени выполнения.

Две мета-страницы нужны для восстановления при повреждении одной из них. Актуальная версия выбирается по большему txid: при инициализации meta0 получает txid 0, meta1 — txid 1, а при копировании базы meta1 записывается с пониженным txid. Целостность проверяет Validate, вызываемый для каждой мета-страницы при открытии. При инициализации в мета-страницу записываются magic, version, pageSize, freelist, root bucket, pgid, txid и контрольная сумма.

Leaf- и branch-страницы

На leaf-странице каждый элемент описывается структурой leafPageElement с полями flags, pos, ksize, vsize. Key() возвращает срез байтов ключа по смещению pos длиной ksize, а Value() — срез значения сразу после ключа длиной vsize.

branch-страницы используют branchPageElement с полями pos, ksize, pgid. Key() возвращает ключ, а Pgid() — идентификатор дочерней страницы. Branch-элемент хранит только ключ и pgid, без значения, потому что его назначение — направлять поиск к дочерним страницам, а не хранить данные.

Bucket как корень дерева

bucket — это коллекция пар ключ-значение внутри базы. newBucket привязывает bucket к транзакции и задаёт FillPercent по умолчанию, а для записываемой транзакции ещё и инициализирует кэши подбакетов и узлов.

Вложенный bucket создаётся через CreateBucket: он клонирует ключ, ищет позицию курсором, проверяет отсутствие существующего ключа и вставляет пустой inline-bucket с флагом BucketLeafFlag. openBucket переинтерпретирует значение подбакета из родителя в Bucket: при выравнивании и записываемой транзакции копирует InBucket, иначе указывает прямо на mmap; если RootPage() == 0, сохраняет ссылку на inline-страницу.

Вложенный bucket отличается от обычного ключа тем, что его значение помечено флагом BucketLeafFlag: обращение к ключу как к bucket не даёт результата, если флаг не установлен, а удаление такого ключа как bucket завершается ошибкой ErrIncompatibleValue. Подбакеты не допускаются на inline-бакетах, поэтому после вставки b.page = nil, и бакет далее трактуется как обычный не-inline.

Sequence: автоинкремент внутри bucket

NextSequence возвращает автоинкрементное целое для bucket. Сначала проверяется, что транзакция открыта (иначе ErrTxClosed) и доступна для записи (иначе ErrTxNotWritable), затем при необходимости материализуется корневой узел, счётчик увеличивается и возвращается его текущее значение. SetSequence устанавливает счётчик с теми же проверками и тоже материализует корневой узел, чтобы bucket был сохранён при коммите. Sequence просто читает текущее значение без инкремента.

Счётчик хранится в самом bucket, а не отдельным ключом: NextSequence/SetSequence работают через IncSequence()/SetInSequence() и материализацию корневого узла — значение живёт в структуре bucket и сохраняется вместе с ним при коммите.

Транзакции: View, Update и Batch

DB.Begin(writable) при writable=true вызывает beginRWTx, а при false — beginTx. Read-only транзакция берёт metalock и read-lock на mmap, создаёт Tx и, если freelist доступен, добавляет её txid через AddReadonlyTXID. Freelist хранит txid активных читателей, чтобы не переиспользовать страницы, которые ещё нужны этим транзакциям. Write-транзакция сначала проверяет, что база не открыта только для чтения, затем берёт rwlock — «This enforces only one writer transaction at a time» — и только потом metalock.

Учёт read-only транзакций ведётся парно: AddReadonlyTXID при старте и RemoveReadonlyTXID при завершении. Писатель только один, потому что beginRWTx удерживает rwlock до закрытия транзакции, а при закрытии write-транзакции сбрасывается db.rwtx и освобождается rwlock.

DB.Batch склеивает конкурентные вызовы в один batch, если уже есть текущий batch и число накопленных в нём вызовов меньше db.MaxBatchSize. Иначе создаётся новый batch с таймером на db.MaxBatchDelay. Когда размер достигает db.MaxBatchSize, batch запускается немедленно. Внутри вызовы выполняются в одной транзакции Update, и если safelyCall для какого-то вызова вернул ошибку, запоминается индекс упавшего вызова и транзакция завершается ошибкой. Упавший вызов удаляется из очереди заменой на последний элемент и обрезанием среза, его отправителю посылается trySolo, после чего цикл повторяется с остальными вызовами. Получив trySolo, DB.Batch перезапускает функцию отдельно через db.Update(fn). safelyCall вызывает fn(tx) под defer с recover(), превращая панику в ошибку.

Почему байты из Get/Cursor живут только внутри транзакции

Байты, возвращаемые из Bucket.Get/Cursor, могут указывать прямо на mmap-область, поэтому они действительны только пока транзакция жива и mmap не пересоздан. При открытии вложенного bucket в read-only транзакции код прямо указывает на mmap-запись. Если адрес не выровнен, значение копируется через cloneBytes, потому что невыровненный доступ требует копии.

dereference нужен, чтобы убрать все ссылки на старый mmap перед его освобождением. Перед повторным mmap вызывается db.rwtx.root.dereference(), затем db.munmap(), а munmap через defer вызывает invalidate(), обнуляя dataref/data/datasz и meta0/meta1. При rollback write-транзакции tx.close() очищает ссылки транзакции.

Запись: Put, split и подъём до корня

Put сначала проверяет, что транзакция открыта и доступна для записи, а ключ не пустой и не слишком большой, иначе возвращает ErrTxClosed, ErrTxNotWritable, ErrKeyRequired, ErrKeyTooLarge или ErrValueTooLarge. Затем ключ копируется в newKey, чтобы избежать утечки, и курсор перемещается в позицию для вставки. Если по этому ключу уже есть значение с флагом BucketLeafFlag, возвращается ErrIncompatibleValue. После этого пара ключ-значение вставляется или перезаписывается в текущем узле.

При разбиении узла вызывается n.split(uintptr(tx.db.pageSize)), который делит узел на несколько узлов. Если у узла нет родителя, создаётся новый родительский узел, а новый узел добавляется в parent.children. Изменения поднимаются до корня: после разбиения каждый узел записывается на страницу, и если у узла есть родитель, в него вставляется ключ с pgid узла. Если корневой узел разбился и создал нового родителя, вызывается n.parent.spill(), чтобы записать и его.

Spill: грязные узлы превращаются в новые страницы

spill записывает все узлы бакета в грязные страницы. Сначала рекурсивно обрабатываются дочерние бакеты: если дочерний bucket можно встроить (inlineable), его страницы освобождаются и он записывается в родительский узел как значение; иначе рекурсивно вызывается spill и в родителе сохраняется указатель на страницу. Затем, если у бакета есть материализованный корневой узел, вызывается spill для корневого узла, после чего корневой узел заменяется на результат root(). Новый корневой узел получает pgid, который проверяется на непревышение верхней границы, и этот pgid записывается в bucket через SetRootPage.

Старые страницы не перезаписываются на месте: при разбиении узлов старые страницы освобождаются (node.free()), а для узла выделяются новые страницы через tx.allocate, и только после этого узел записывается в новую страницу.

Rebalance и DefaultFillPercent

rebalance запускается при коммите транзакции: Commit вызывает tx.root.rebalance(), который рекурсивно обходит все узлы бакета и вызывает n.rebalance() для каждого, а затем рекурсивно для дочерних бакетов. Узел обрабатывается только если он помечен как unbalanced; при этом флаг сбрасывается и увеличивается счётчик статистики.

Порог вычисляется так:

threshold = int(float64(pageSize)*FillPercent) / 2

При DefaultFillPercent = 0.5 это 25% от размера страницы. Если размер узла больше порога и ключей больше minKeys(), узел не трогают. Иначе он объединяется с соседом: при индексе 0 берётся правый сосед, иначе левый, inodes правого переносятся в левый, правый удаляется из родителя и освобождается, после чего родитель рекурсивно rebalance-ится. Для корневого узла особый случай: если это branch с одним ключом, его единственный ребёнок поднимается на место корня, что уменьшает глубину дерева. Порог именно такой, потому что DefaultFillPercent = 0.5, а делитель 2 даёт 25% — узлы, заполненные менее чем на четверть страницы, считаются кандидатами на слияние.

Freelist и рост файла

Файл bbolt не уменьшается после удаления данных, потому что удалённые страницы не возвращаются операционной системе: они лишь помечаются свободными для повторного использования внутри базы. Страницы освобождаются только когда их перестают использовать все активные транзакции, а сам файл остаётся прежнего размера. Долго живущая read-транзакция может заставить базу быстро расти.

Компактную копию создаёт Tx.WriteTo: он формирует новый файл, записывая только актуальные данные. Сначала генерируются и пишутся две мета-страницы — мета 0 с текущим txid и мета 1 с уменьшенным txid. Затем копируются только страницы данных, начиная со смещения после двух мета-страниц (dataOffset := int64(tx.db.pageSize * 2)), через SectionReader, чтобы не менять смещение исходного файла. Tx.CopyFile — обёртка: открывает файл по пути и вызывает WriteTo. Compact(dst, src *DB, txMaxSize int64) переносит данные из src в dst с ограничением размера транзакции txMaxSize.

Коммит: две фазы записи

Tx.Commit сначала перебалансирует узлы после удалений (tx.root.rebalance()), затем переносит данные на грязные страницы (tx.root.spill()), после чего освобождает старый корневой bucket и старый freelist, при необходимости записывает новый freelist или помечает его отсутствующим (SetFreelist(PgidNoFreelist)), и при росте pgid увеличивает файл. Далее вызывается tx.write(), которая пишет грязные страницы на диск; при StrictMode выполняется проверка целостности, и только затем tx.writeMeta() записывает новую мета-страницу с увеличенным txid.

Документация описывает две фазы: сначала грязные страницы и fsync(), затем новая мета-страница и ещё один fsync(). Частично записанные data-страницы игнорируются, так как мета на них не указывает, а частично записанные мета-страницы отбраковываются по контрольной сумме.

NoSync позволяет пропустить автоматическую синхронизацию, и тогда для принудительной записи на диск используется DB.Sync, выполняющий fdatasync() по файловому дескриптору базы. NoSyncReload применяется при rollback: если freelist не был синхронизирован, список свободных страниц восстанавливается сканированием всей базы через freelist.NoSyncReload(tx.db.freepages()), что тяжело при большом размере базы.

Rollback после ошибки fsync

При ошибке записи на диск (например, fsync) Commit вызывает внутренний rollback, который перезагружает список свободных страниц с диска, чтобы откатить изменения в памяти и не оставить неконсистентное состояние. Сначала вызывается tx.db.freelist.Rollback(tx.meta.Txid()) — это отменяет изменения freelist, сделанные в текущей транзакции. Затем, если буфер данных доступен, выбирается способ восстановления: если список свободных страниц не синхронизирован с диском, он полностью перестраивается сканированием всей базы через NoSyncReload; иначе список читается из страницы freelist на диске через Reload.

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

Что показывают Stats

TxStats — это набор счётчиков транзакции, доступных через атомарные геттеры: число выделенных страниц (GetPageCount), всего байт выделено (GetPageAlloc), число созданных курсоров (GetCursorCount), число выделений узлов (GetNodeCount), число разыменований узлов (GetNodeDeref), число ребалансировок (GetRebalance), общее время ребалансировки (GetRebalanceTime), число разделённых узлов (GetSplit), число вытесненных узлов (GetSpill), общее время вытеснения (GetSpillTime), число записей (GetWrite) и общее время записи на диск (GetWriteTime). Геттеры читают значение через atomic.LoadInt64, а инкрементеры — через atomic.AddInt64, возвращая новое значение; для длительностей используются atomicLoadDuration и atomicAddDuration.

Метод add суммирует все счётчики другой TxStats, а Sub возвращает разницу двух наборов через Get-функции, что полезно для получения счётчиков за промежуток между двумя замерами. DB.Stats возвращает копию db.stats под RLock и обновляется только при закрытии транзакции. Bucket.Stats возвращает BucketStats, обходя страницы через forEachPage и накапливая число ключей, страниц-листьев и их использование, число branch-страниц и их использование, глубину дерева и статистику inline-бакетов; BranchAlloc и LeafAlloc вычисляются как произведение числа страниц (с учётом overflow) на размер страницы.

Что из этого следует на практике

Открытие базы — не мгновенная операция. Для существующего файла размер страницы определяется перебором от 1KB до 16MB с чтением блока 0x1000 байт на каждом шаге. Если файл занят другим процессом, Open без Options.Timeout может зависнуть навсегда.
Одна база — один писатель. Эксклюзивная блокировка при обычном открытии и rwlock внутри процесса гарантируют, что записывающая транзакция всегда одна. Read-only транзакции могут работать параллельно, но каждая регистрирует свой txid в freelist.
Байты из Get/Cursor нельзя хранить после закрытия транзакции. Они могут указывать прямо на mmap; после Rollback или пересоздания mmap ссылки становятся недействительными.
Файл не сжимается сам. Удалённые страницы возвращаются в freelist и переиспользуются, но размер файла не уменьшается. Для компактной копии нужны Tx.WriteTo/CopyFile/Compact.
Долгая read-транзакция тормозит освобождение страниц. Пока её txid зарегистрирован в freelist, страницы не могут быть переиспользованы, и база растёт.
Надёжность коммита держится на двух фазах и контрольной сумме мета-страниц. При сбое частично записанные data-страницы игнорируются, а частично записанные мета-страницы отбраковываются по checksum. При NoSync эту гарантию нужно обеспечивать вручную через DB.Sync.
Порог слияния узлов — 25% страницы при DefaultFillPercent = 0.5. Узлы, заполненные меньше чем на четверть, объединяются с соседями, что уменьшает фрагментацию, но добавляет работу при коммите.
Счётчики Stats обновляются только при закрытии транзакции. Чтобы получить статистику за промежуток, нужно снять два замера и вычесть один из другого через Sub.