Средний

14 мин

8.9K

Введение: Это было не так случайно, почти

Я хотела разобраться, почему LSM‑движки такие быстрые. Мои попытки получить циферки «получше» были слишком наивными. С каждой тысячей записей читать становилось всё тяжелее ждать когда же тест закончится.

И тут возможно проблема в том что я не знала многих вещей, возможно, потому что я не думала даже о том, что данные должны быть каким-то способом организованы. Не в свою защиту но бывшему Беку на фастапи это не пригождалось. Правда, я потом подумала о слишком многом.

Если вы писали свое хранилище — даже простую очередь или кэш — вы сталкивались с тем же. Мой опыт поможет не повторять мои ошибки. В статье расскажу: из каких частей состоит мой LSM‑движок и чьи решения я подсмотрела для своего «лего» 0

Оглавление

• Вступление: хотела пополнить резюме, а написала базу данных

• Архитектура ScoriaDB: как я собирала конструктор

• Что пошло не так: реальные проблемы и их решения

• Что уже работает, а что ещё нет

• Что я вынесла из этого проекта

• Попробовать у себя

• Демонстрация CLI

• Документация

• Заключение

Архитектура ScoriaDB: как я собирала конструктор

Я не изобретала велосипед это по сути конструктор, содержащий в себе множество готовых решений. Посмотрев, как устроены LevelDB, RocksDB, BadgerDB, TiKV, я взяла у них некоторые идеи. Получился гибрид.

MemTable: почему всё‑таки B‑tree, а не skip list (и когда это станет проблемой)

Мне нужна была отсортированная in‑memory структура. Для чего? Чтобы быстро делать скан по префиксу и потом сбрасывать эти отсортированные данные в SSTable (на диск).

Вот как я сравнивала варианты:

• Хеш‑мапа? нет, она не сохраняет порядок ключей, скан невозможен.

• sync.Map? Тоже нет, не упорядочена, под write‑heavy нагрузкой меня лично не устроили цифры.

• Skip list — Хм, это золотой стандарт LSM (LevelDB, RocksDB, BadgerDB), lock‑free или хотя бы с минимальными блокировками. Но корректная реализация конкурентного skiplist в Go — задача, которая может затянуться и отвлечь от реализации mvp.

• B‑tree — взяла github.com/google/btree. Стабильный, есть copy‑on‑write, быстро и просто использовать.

Поясню еще один момент, глобальный мьютекс на всю MemTable (реализация B‑tree) означает, что при интенсивной записи все горутины выстраиваются в очередь. Для первого релиза я осознанно пошла на это, выиграв время для реализации других частей. В планах на v0.3.0 — замена на lock‑free skip list с собственным управлением памятью. Это будет необходимо, чтобы база держала конкурентную нагрузку.

SSTable и Bloom‑фильтр

Когда MemTable переполняется, она сбрасывает все в Sstable. Ниже его структура:

┌─────────────┐
│   Header    │  ← magic, версия, контрольная сумма заголовка
├─────────────┤
│ Block index │  ← массив «последний ключ блока → смещение»
├─────────────┤
│Bloom filter │
├─────────────┤
│  Block 1    │  ← данные + CRC32 блока
│  Block 2    │
│  ...        │
└─────────────┘

• Блочный индекс — массив, который для каждого блока SSTable хранит его последний ключ и смещение в файле. Позволяет быстро найти нужный блок бинарным поиском, не читая весь файл.

• Префиксное сжатие — способ экономить место в SSTable: если ключи имеют общий префикс (например, user:100, user:101), то общая часть хранится один раз, а различающиеся суффиксы — отдельно.

• Bloom‑фильтр — вероятностная структура, которая быстро говорит «ключа точно нет», отсекая лишние чтения с диска. Ложноположительные срабатывания возможны, но они лишь приводят к холостому поиску в блоке, не нарушая корректности.

• Контрольные суммы — каждый блок снабжён CRC32. При чтении блока я проверяю сумму, чтобы обнаружить битые данные на диске. Без этого можно было бы молча получить мусор, если файл повреждён.

WriteBatch: атомарные группы операций

Идея из RocksDB. Если нужно записать несколько ключей атомарно — либо все, либо ничего. В ScoriaDB WriteBatch сериализуется в один буфер и пишется в WAL одной записью. При восстановлении применяется всё до маркера конца. Если обнаружен обрыв — операции батча не применяются.

WiscKey и Value Log: большие значения без амплификации записи

Классический LSM страдает амплификацией записи : значение в 1 МБ копируется при каждом компакшене. Десять раз и уже 10 МБ записи, а двадцать — 20 МБ. У Badger я подсмотрела реализацию Value Log (WiscKey‑стиль). Значения >64 байт выносятся в отдельный файл, а в LSM‑дереве хранятся только указатели.

CRC32 значения хранится отдельно — в заголовке записи VLog. Так что по указателю я могу быстро найти значение, проверить его целостность и прочитать.

mmap и почему zero‑copy в Go — не то, чем кажется

Я использую mmap для отображения файла VLog в память. Какие проблемы возникают:

• После syscall.Munmap (например, при закрытии БД) слайсы, которые ссылаются на этот регион, становятся висячими указателями, то есть любое обращение к ним вызывает SIGSEGV.

• Без контроля времени жизни таких слайсов легко получить аварию: горутина читает по старому слайсу, пока основной поток закрыл файл и сделал Munmap.

Текущая реализация копирует данные из mmap‑области в новую кучу, думаю это безопасно и одно лишнее копирование не сыграет. Настоящий zero‑copy требовал бы системы подсчёта ссылок на регионы mmap и гарантии, что никто не держит слайс после закрытия VLog. Пока это остаётся в планах на v0.3.0.

MVCC и инвертированная метка

MVCC (Multi‑Version Concurrency Control) даёт каждой записи версию с временной меткой commitTS. Транзакция получает startTS и видит только версии с commitTS <= startTS. Главное: писатели никогда не блокируют читателей. Если транзакция обнаруживает конфликт (кто‑то записал ключ после её начала), она возвращает ошибку, и вызов должен повторить транзакцию — обычно в цикле с несколькими попытками.

Инвертированная метка — трюк, который я подсмотрела в TiKV. Обычно timestamp растёт, и новые записи лежат в конце дерева. Причем хранится не сам timestamp, а его побитовое отрицание (^uint64(now) в Go — это инвертирование всех битов). Благодаря этому свежие записи (с большим commitTS) оказываются в начале итератора. Итератор по умолчанию идёт от новых к старым.

Column Families: зачем они нужны на самом деле

Идея из Bigtable и Cassandra. Независимые LSM‑деревья внутри одной базы. У каждого CF свои настройки: размер MemTable, политика компакшена, а в будущем — TTL.

Реализовано виде map[string]*Engine и общего WAL для атомарности между CF. Без общего WAL при сбое часть CF могла остаться в обновлённом состоянии, а другая — нет. Это была одна из первых грубых ошибок, которую я нашла вообще аж при разработке анализатора логов на этой бд.

Leveled Compaction: классика

Классическая схема из LevelDB: уровни L0 → L1 → L2 → L3. На L0 файлы могут пересекаться по ключам, на L1 и ниже — нет.

Сначала была заглушка, потом я сделала multi‑way merge с min‑heap. В планах — добавлять ограничение размеров уровней, чтобы избежать write stall, когда входящая запись опережает компакшн.

Manifest: журнал метаданных

Когда при компакшене создаются и удаляются SSTable, нужно атомарно обновлять список файлов. Просто сканировать папку ненадёжно, потому что можно получить неконсистентное состояние.

Я взяла идею из RocksDB: все изменения состава файлов пишутся в журнал MANIFEST. Сейчас каждая запись — это VersionEdit в JSON (с последующим fsync). Это удобно для отладки, но не для продакшена . В v0.2.0 планирую перейти на компактный бинарный формат и пакетную запись изменений.

Пример записи:

{
  "level": 1,
  "add": ["sstable_000123.sst"],
  "delete": ["sstable_000045.sst"]
}

Fail‑safe VLog: восстановление после повреждения

Если во время записи в Value Log случился сбой, файл может повредиться (magic mismatch — специальная сигнатура в начале). Я сделала как в BadgerDB: при открытии проверяю magic. Если не совпадает — переименовываю в .corrupt, создаю новый, восстанавливаю данные из WAL. Записи с указателями на старый VLog пропускаются (они потеряны), но база остаётся работоспособной.

VFS‑абстракция для тестирования

Чтобы тестировать сбои диска, я абстрагировала все файловые операции через интерфейс VFS:

type VFS interface {
    Open(name string) (File, error)
    Create(name string) (File, error)
    Rename(old, new string) error
    Remove(name string) error
}

В production — DefaultVFS (обёртка над os), в тестах — мок, который эмулирует ошибки записи, задержки или отказы. Правда, здесь есть тонкость: для mmap нужен реальный файловый дескриптор (*os.File), а не абстрактный vfs.File. Поэтому в тестах, где я подменяю файловую систему моком, VLog не сможет использовать mmap — и мой механизм fail‑safe VLog проверить на моках пока не выйдет. Это ограничение я планирую исправить в v0.3.0, например, сделав mmap опциональным или заменив его на pread в тестовом режиме.

Чистый Go без cgo и gRPC как у etcd

RocksDB требует C++ и cgo — сложная сборка, проблемы с кросс‑компиляцией. BadgerDB — чистый Go, но без встроенного сервера.

Я сделала ставку на чистый Go: go build одной командой, никаких внешних зависимостей, работает на всех платформах. А gRPC‑сервер (как в etcd и TiKV) даёт строгую типизацию, HTTP/2 и клиенты на 12+ языках. REST и WebSocket я добавила скорее ради эксперимента; в идеальном мире серверный слой должен быть отдельным процессом или включаться флагом сборки.

Что пошло не так: реальные проблемы и их решения

Ох сколько было часов уже с уставшими, болючими глазами, но со странным чувством, что это нельзя так оставлять, надо доделать, сделать коммит и спать, возможно некоторый перфекционизм здесь тоже сыграл свою роль.

1. WAL без синхронизации → данные улетали в буфер, а не на диск

Как было: самый первый WAL писался через f.Write(). Данные уходили в буфер операционной системы и при перезагрузке просто исчезали.

Как обнаружилось: провела стресс‑тест: записала 10 000 ключей, убила процесс через kill -9, перезапустила базу… пусто.

Исправление: добавила f.Sync() после каждой записи батча. Теперь данные действительно сохраняются.

Цена вопроса: замеры на Intel Core i3‑1215U:

Запись замедлилась в 5 раз. Но теперь после kill -9 данные не теряются.

Обратите внимание: это тесты одиночных записей с честным fsync на диск. В синтетическом тесте без реальной синхронизации задержка ~1 мкс — но такие цифры не отражают надёжность.

Что дальше: в v0.2.0 добавлю Group Commit — буферизирую несколько записей и делаю один fsync на группу. Должно стать и быстро, и надёжно.

2. Гонка в генераторе меток (и как её нашёл ‑race)

Как нашла: включила go test -race. Без него я бы искала этот баг неделю.

Исправление (первое):

// Было
func (g *TimestampGenerator) Next() uint64 {
    g.lastTS++
    return g.lastTS
}

// Стало
func (g *TimestampGenerator) Next() uint64 {
    return atomic.AddUint64(&g.lastTS, 1)
}

Но этого оказалось мало. При перезапуске базы счётчик lastTS сбрасывался в 1, и новые транзакции могли получить метки, которые уже были меньше уже записанных в SSTable. Это ломало изоляцию снапшотов между запусками.

Окончательное исправление: теперь я сохраняю последнее выданное значение в Manifest (отдельной записью), а при открытии базы загружаю его и продолжаю инкремент. Метки уникальны даже между сессиями.

Бонус: я добавила кэш последних версий(lastCommitCache), чтобы проверять конфликты за O(1) без полного сканирования LSM.

3. Value Log без CRC32 → мусор вместо значений

Я писала в VLog и магическое число, и CRC32 каждого значения. Но при чтении проверяла только магическое число, а CRC32 нет.

Как обнаружилось: после очередного краша VLog повредился (магическое число не совпало). Движок создал новый пустой файл, а старые указатели из WAL вели в пустоту. База молча возвращала мусор вместо значений.

Исправление:

• При открытии проверяю магическое число. Если не совпадает — переименовываю файл в .corrupt, создаю новый, восстанавливаю данные из WAL.

• В методе Get перед возвратом значения сверяю CRC32 блока с записанным.

4. Компакшн, который убивал снапшоты

Изначально он оставлял только самую новую версию каждого ключа, а все старые удалялись без разбора.

В процессе разработки транзакций появились долгие транзакции. Они смотрели на свой startTS, пытались найти нужную версию, а их нет! Потому что компакшн решил, что ее надо убрать.

Решение: добавила глобальный минимум активных снапшотов (minActiveSnapshotTS), атомарную переменную. В компакшене перед удалением версии теперь проверяется: если commitTS этой версии больше, чем minActiveSnapshotTS, то оставляем версию.

5. WriteBatch терял атомарность

Раньше: каждая операция из батча писалась в WAL отдельной записью, тем самым пытаясь экономить на сериализации (и как оказалось неизвестсно зачем)

Как проявилось: тесты на восстановление после сбоя показали, что если процесс умирал после записи 3 операций из 10, при повторном запуске применялись только эти 3.

Теперь: сериализую весь WriteBatch в один буфер, записываю одной записью в WAL с маркерами начала и конца. При восстановлении: если есть маркер конца — применяю всё; если нет — отбрасываю целиком.

6. Column Families теряли атомарность между CF

Как было: у каждого CF был свой WAL. Мне казалось, так проще и изолированнее

К чему привело: когда батч обновлял два CF, произошёл сбой, после того, как WAL первого CF записался (и даже, возможно, выполнил fsync), но до того, как второй CF начал свою запись. В итоге первый CF сохранил изменения, а второй — нет. Атомарность между CF была потеряна.

Исправление: сделала общий WAL для всех CF. WriteBatch сериализуется в одну запись с идентификаторами CF. При восстановлении теперь читается только один поток и точно известно, куда применять каждую операцию.

7. ScanCF возвращал пустой итератор вместо ошибки

Что было до: в публичном API ScanCF я возвращала пустой итератор, если запрошенный Column Family не существовал.

Как выяснилось на практике: в демо‑проекте Scorix (анализатор логов) импортёр забыл создать CF raw. ScanCF молча возвращал пустой результат. Пользователь видел «No logs found» и не понимал, почему.

Исправление: создала errorIterator, который при первом вызове Next() или Err() возвращает ошибку CF not found. Сигнатура метода не изменилась, но пользователь наконец видит причину.

8. Manifest без fsync → база забывала свежие SSTable

Что было: VersionEdit писался в JSON‑файл, но не вызывал fsync. Всё работало…

К чему привело: после сбоя база не видела SSTable, созданные во время последнего компакшена. Файлы на диске лежали, а метаданные о них как след простыл.

Исправление: добавила f.Sync() после каждой записи в Manifest.

И ещё один fsync, замедляющий компакшн.

9. SSTable не проверял CRC блоков

Исходная наивность: я проверял только заголовок SSTable, считая, что если заголовок цел — то и всё остальное в порядке.

Как проявилось: в тестах с повреждённым файлом (симуляция битого диска) база продолжала читать блоки и возвращала мусор.

Исправление: добавила CRC32 на каждый блок SSTable. При чтении блока проверяю контрольную сумму. Если не сошлась — блок считается повреждённым.

Что уже работает, а что ещё нет

Стабильно работает (v0.1.0)

Что пока на костылях или в планах

• MemTable: B‑tree с глобальным мьютексом → замена на lock‑free skip list (v0.3.0).

• WAL: Group Commit (v0.2.0).

• Manifest: бинарный формат (v0.2.0).

• Value Log GC: ручной режим есть (scoria gc), автоматический (битовая карта, инкрементальный) → v0.3.0.

• Ограничение размеров уровней в компакшене → v0.3.0.

• TTL для записей → v0.2.0.

• Raft, шардирование, распределённые транзакции, Sorted Sets, JSON‑документы → после v1.0 (без точных дат).

Что я вынесла из этого проекта

1. Не нужно боятся переписывать. Три переписывания компакшена, два — WAL, один серьёзный рефакторинг MVCC. Мне становилось страшно, что останется какая‑то глубокая ошибка после этих изменений, ведь до этого я максимально старалась избежать того чтобы пришлось прям кардинально что‑то менять.

2. Тесты с -race — с первого дня. Гонку в генераторе меток я нашла бы за день, а не за неделю, если бы включила -race раньше. В моём CI это стало обязательно, до недавних пор я об этом не думала.

3. fsync — правда полезная штука. Запись замедлилась в 5 раз (всего лишь), но теперь после kill -9 данные сохраняются. Позже Group Commit амортизирует все затраты, сохраняя надежность.

4. LSM — это намного сложнее, чем просто скинуть на диск. Bloom‑фильтр отсекает лишние чтения. Блочный индекс и CRC блоков — ещё пара мелочей, но без них данные либо теряются, либо ищутся вечность. Префиксное сжатие экономит память. Value log в помощь LSM. В сумме эти мелочи и делают базу данных быстрой и надёжной.

5. Самое сложное — заставить всё работать вместе. MemTable работает, SSTable работает, WAL работает. Каждый по отдельности — отлично. Но когда они начинают взаимодействовать при компакшне и восстановлении, вылезают такие грабли, о которых ты и не догадывалась. Интеграционные и стресс‑тесты — вот где настоящая боль и настоящие открытия.

Попробовать у себя

ScoriaDB открыта под лицензией Apache 2.0.

# Клонировать
git clone https://github.com/f4ga/ScoriaDB.git
cd ScoriaDB

# Быстрый старт через Docker
docker compose -f deployments/docker-compose.yml up --build
# Сервер на :50051 (gRPC) и :8080 (HTTP)
# Логин/пароль при первом запуске: admin/admin

# Или собрать вручную
go build -o scoria-server ./cmd/server
go build -o scoria-cli ./cmd/cli
./scoria-server &
TOKEN=$(./scoria-cli admin auth admin admin)
./scoria-cli --token "$TOKEN" set hello world
./scoria-cli --token "$TOKEN" get hello

# Запустить все тесты (обязательно с -race!)
go test -race ./...

Демонстрация CLI <3

Документация

Полная документация ScoriaDB доступна в папке [docs/] репозитория на GitHub c подробным описанием всех команд CLI, Column Families, транзакций, админ прав и примеров интеграции. Спойлер: В клишке намного больше команд чем на скрине, достаточно вызывать команду help или почитать документацию на GitHub Pages.

Заключение

ScoriaDB начиналась как строчка в резюме, а стала для меня причиной написать об этом свою статью. Сейчас это рабочий LSM-движок с MVCC, транзакциями, Column Families и собственным Value Log — всё на чистом Go, без внешних зависимостей, с gRPC‑сервером и CLI из коробки. Он не заменит Redis в специфичных для него вещах, но для embedded‑сценариев, локального хранения, анализа логов или учебных проектов, уже сейчас, более чем готов.

Пока я собирала материал для статьи, в голову пришло ещё несколько идей, и между делом появились новые коммиты, исправления и даже фичи. Проект живёт, родмара расписана на несколько версий, кстати, issues открыты, жду ваших предложений!

Исходники на GitHub

Я прочитаю все комментарии, хотелось бы услышать есть ли у кого-то опыт написания хранилищ :3

А вы когда‑нибудь начинали проект чисто для резюме, а получалось что‑то большее? Писали ли документацию ?