← назад к разделу

Вы не будете писать собственную СУБД. Но выбирать между PostgreSQL и Cassandra, настраивать ClickHouse, объяснять, почему индекс замедлил запись, — будете. Для всего этого нужно примерное понимание, что база делает на диске. Внутри почти любой СУБД — один из двух движков хранения: B-дерево или LSM-дерево. Разберём оба с нуля.

Самая простая БД в мире

Классический пример из первой части книги Клеппмана — «база данных» из двух функций Bash:

db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }

db_set дописывает пару «ключ,значение» в конец файла; db_get ищет последнее вхождение ключа. Запись здесь на удивление хороша: дописывание в конец файла — самая дешёвая дисковая операция, и настоящие базы используют тот же приём под именем журнал (log): последовательность записей, только для дописывания. А вот чтение ужасно: O(n), вся база просматривается целиком.

Чтобы читать быстро, нужен индекс — дополнительная структура рядом с данными. И сразу главный размен всего этого мира: индекс ускоряет чтение, но замедляет запись — его приходится обновлять при каждой вставке. Поэтому базы не индексируют всё подряд, а просят разработчика выбирать индексы под запросы.

Шаг первый: хеш-индекс

Простейший индекс к журналу — hash map в памяти: ключ → смещение в файле, где лежит последнее значение. Запись остаётся дописыванием (плюс обновление карты), чтение — один прыжок по смещению. Чтобы файл не рос бесконечно, журнал режут на сегменты и в фоне выполняют уплотнение (compaction): выбрасывают устаревшие версии ключей, сливают сегменты.

Так работает реальный движок Bitcask. Ограничения: все ключи обязаны помещаться в память, а запросы по диапазону («все ключи от А до Б») безнадёжны — хеш ничего не знает о порядке.

LSM-дерево: сортированные сегменты

Оба ограничения снимает одна идея: хранить сегменты отсортированными по ключу. Такой файл называется SSTable (sorted string table). Схема работы движка:

  1. Запись попадает в MemTable — сбалансированное дерево в памяти (плюс короткий журнал на диске — страховка от потери при сбое).
  2. Когда MemTable вырастает до нескольких мегабайт, она сбрасывается на диск целиком как новая SSTable — это опять последовательная запись.
  3. Чтение ищет ключ в MemTable, затем в самой свежей SSTable, затем в предыдущей — и так далее.
  4. Фоновый compaction сливает SSTable между собой: слияние отсортированных файлов — это дешёвый mergesort, дубликаты ключей схлопываются до последней версии.

Это и есть LSM-дерево (log-structured merge-tree) — сердце RocksDB и LevelDB, Cassandra и HBase; тот же принцип «отсортированные сегменты + фоновое слияние» лежит в основе словаря термов Lucene (то есть Elasticsearch) и MergeTree в ClickHouse.

Тонкое место — поиск отсутствующего ключа: придётся проверить MemTable и все SSTable до самой старой. Лечится фильтром Блума — компактной вероятностной структурой, которая по ключу отвечает «точно нет» или «возможно есть» и экономит чтения диска.

B-дерево: страницы и WAL

B-дерево — ровесник 1970-х и стандарт де-факто: на нём построены индексы PostgreSQL, MySQL, Oracle и почти всех реляционных баз. Подход противоположный: база разбивается не на сегменты переменного размера, а на страницы фиксированного размера (обычно 4–8 Кбайт), которые читаются и перезаписываются на месте.

Страницы образуют дерево: корень содержит ключи-границы и ссылки на детей, каждый ребёнок отвечает за свой диапазон, в листьях — сами значения. Коэффициент ветвления — сотни ссылок на страницу, поэтому дерево очень плоское: четырёх уровней хватает на сотни гигабайт, поиск — O(log n) с тремя-четырьмя прыжками по диску. Вставка в переполненную страницу расщепляет её на две и обновляет родителя.

Перезапись на месте — операция опасная: сбой в момент расщепления страницы может оставить индекс в разорванном состоянии. Поэтому каждая модификация сначала дописывается в журнал упреждающей записи (write-ahead log, WAL) и только потом применяется к страницам; после сбоя база восстанавливает согласованность по журналу. Знакомая ирония: движок с перезаписью на месте всё равно носит с собой журнал.

Сравнение: за что платим

  • Запись. LSM обычно быстрее: всё пишется последовательно. У B-дерева каждая запись — это WAL плюс страница целиком (даже если поменялись три байта). Мера этой цены — усиление записи (write amplification): сколько байт реально уезжает на диск на один байт полезных данных. Впрочем, у LSM усиление тоже есть — compaction переписывает данные многократно; при больших объёмах записи он конкурирует с ней за пропускную способность диска, и за отставанием compaction нужно следить отдельно.
  • Чтение. B-дерево предсказуемее: ключ живёт ровно в одном месте, путь к нему — фиксированные три-четыре прыжка. В LSM ключ может лежать в нескольких сегментах на разных стадиях уплотнения, и хвостовые задержки (см. перцентили) у него заметно капризнее — фоновый compaction время от времени отъедает диск у запросов.
  • Транзакционность. В B-дереве блокировку диапазона ключей можно привязать прямо к дереву — одна из причин, почему реляционные базы с их изоляцией транзакций стоят на B-деревьях.

Правило из практики: нагрузка «много пишем, читаем недавнее» (события, метрики, лента) — территория LSM; «много читаем по ключам и диапазонам, транзакции» — B-дерева. Но численно это решается только тестом на вашей нагрузке.

Где это применяется

Знание движка превращает «магические» свойства баз в понятные следствия. Почему Cassandra держит огромный поток записи? Последовательные SSTable. Почему в PostgreSQL индексы замедляют вставку? Каждый — ещё одно B-дерево, которое надо обновить. Почему у ClickHouse данные обязаны быть отсортированы по ключу таблицы? MergeTree — родственник LSM, сортировка и есть его индекс. Почему после сбоя PostgreSQL стартует не мгновенно? Прокатывает WAL.

Где спотыкаются начинающие:

  • Сравнивают базы по маркетингу, а не по движку. «NoSQL быстрее» — бессмысленно; быстрее на записи и почему — вот вопрос, и ответ лежит в движке хранения.
  • Забывают, что индекс — не бесплатный. Пять индексов на таблице — пять деревьев, обновляемых на каждую вставку.
  • Не следят за compaction. LSM-база без мониторинга уплотнения тихо копит сегменты, пока не кончится диск или не просядут чтения.
  • Пугаются слова WAL. Это не экзотика, а причина, по которой база переживает выключение питания; на нём же построены репликация и бэкапы.

Что почитать дальше: OLTP и OLAP — как паттерн доступа определяет и движок, и всю архитектуру хранения; типы индексов PostgreSQL — B-дерево со стороны пользователя; моделирование в ClickHouse — MergeTree на практике. Первоисточник — Мартин Клеппман, «Высоконагруженные приложения», глава 3.