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

Свою СУБД вы, скорее всего, писать не будете. Но выбирать между 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) — последовательность записей, в которую можно только дописывать.

А вот чтение ужасное. Чтобы найти ключ, db_get просматривает весь файл от начала до конца. Чем больше данных, тем медленнее — это O(n), то есть время растёт линейно с размером базы.

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

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

Самый простой индекс к нашему журналу — держать в памяти таблицу «ключ → в каком месте файла лежит его последнее значение». Тогда запись остаётся дешёвым дописыванием (плюс обновили табличку в памяти), а чтение — это один прыжок сразу в нужное место файла.

Чтобы файл не рос до бесконечности, журнал режут на куски (сегменты) и время от времени в фоне делают уплотнение (compaction): выбрасывают устаревшие версии ключей и сливают сегменты в один поменьше.

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

LSM-дерево: отсортированные куски

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

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

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

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

B-дерево: страницы фиксированного размера и WAL

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

Страницы выстроены в дерево. В корне — ключи-границы и ссылки на «детей»; каждый ребёнок отвечает за свой диапазон ключей; в самом низу, в листьях, лежат сами значения. У каждой страницы сотни ссылок на детей, поэтому дерево получается очень «плоское»: четырёх уровней хватает на сотни гигабайт, а поиск ключа — это всего три-четыре прыжка по диску. Если вставка не влезает в страницу, страницу разбивают на две и правят ссылку у родителя.

Перезапись на месте — штука опасная: если питание вырубится ровно в момент разбиения страницы, индекс может остаться в «разорванном» виде. Поэтому каждое изменение сначала дописывают в журнал упреждающей записи (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 на практике.