Database Internals — выпуск 1

Алексей представляется: полтора десятка лет в разработке, около девяти в архитектуре, последние пять — в управлении командами, а книгу, по его словам, Александр подкинул такую, что она взорвала мозг. Первая часть — про движки хранения, вторая — про распределённые системы, и первая глава задаёт вопросы на весь разговор: хранить в памяти или на диске, ориентироваться на строки или на колонки, как разложить данные по файлам данных и индексным файлам. Строчные базы — все привычные реляционные: строка целиком лежит в одном большом файле, и без индексов из него ничего не вытащить; колоночные хранят каждую колонку отдельным файлом, что даёт аналитике быстрые агрегаты и отличное сжатие. Отдельно автор предупреждает не путать их с wide-column-хранилищами, где ключ и timestamp сквозные для нескольких разных колонок; Алексей честно признаёт, что пользу такой схемы до конца не понял. Александр напоминает, что Петров — один из мейнтейнеров Cassandra, и во второй части это будет чувствоваться.

Книга разделяет in-memory и дисковые движки: в памяти нет множества проблем, которые появляются, как только данные надо хранить долго, — и отсюда развилка, совмещать ли данные с индексом или разделять их. Кластерные и некластерные индексы — классический вопрос собеседований, а один из ведущих вспоминает, как на Stack Overflow отвечал про кластерный индекс одной базы, хотя спрашивали про другую. Участники вспоминают подрядчика, который при перезапуске толстой базы понавешал индексов: расхлёбывали три месяца, придумывая, что можно сделать без даунтайма. Вторичные индексы часто ссылаются не на данные, а на первичный ключ — многие движки заводят скрытый по умолчанию, если его не объявили, — чтобы удаление и обновление не ломали ссылки. Три ручки, которыми автор описывает любой движок: буферизация, изменяемость и упорядоченность. Чем ближе данные лежат друг к другу, тем меньше движений шпинделя, и на SSD упорядоченность тоже важна; append-only структуры не переписывают старое и упрощают индексы; буферы есть и у ОС, и у самой базы для горячих страниц. Книга свежая: на английском она, по словам участника, появилась около 2020 года, а перевод — в 2021-м или 2022-м.

Вторую главу ведёт один из ведущих: автор начинает с бинарного дерева поиска и его патологии — отсортированный вход вырождает дерево в список с линейным поиском; балансировка ротациями помогает, но для диска бинарное дерево всё равно не годится: прыгать по узлам дорого, нужны широкие и низкие деревья, где узел — целая страница, а большинство запросов — диапазоны — читаются локально. Алексей объясняет, почему это так: память отдаёт данные адресно, диск — блоками; минимальная единица чтения — страница, страницы собираются в блоки, блоки — в ячейки флеш-памяти; запись меньше страницы всё равно занимает страницу, а запись в две с половиной страницы добивается нулями, что влияет на ресурс SSD. Слушатель Андрей в чате уточняет, что упорядоченность важна прежде всего для последовательного чтения диапазонов, и Алексей соглашается, добавляя, что на петабайтных объёмах разница — секунды и минуты.

Ведущий объясняет B-дерево через библиотечный шкаф: полка, ящик, карточка — каждый уровень уточняет, а карточки в ящике уже отсортированы; сверху разделительные ключи, снизу указатели на следующий уровень или на данные. Сложность поиска логарифмическая, и чат тут же поправляет основание логарифма: не два, а фанаут, что Александр называет несущественным для асимптотики. Участникам понравился эпиграф из Винни-Пуха к главе. Сложное начинается на вставке и удалении: если страница переполнена, происходит split, который может подняться до корня и перестроить дерево прямо в момент вставки, а при удалении соседние страницы с суммой элементов меньше порога сливаются с переносом ссылки у родителя. Участники замечают, что механика имплементации нетривиальна, и возвращаются к первой схеме: параллельные вставки удерживают менеджер блокировок и менеджер транзакций.

Третья глава — про то, как всё это лежит в байтах: порядок байтов big- и little-endian, примитивы (float — 23 бита мантиссы, 8 бит экспоненты и знак), строки в стиле Pascal с длиной впереди против строк, которые лежат просто массивом символов, битовые маски и флаги. Записи с полями фиксированного размера просты, а переменные поля рождают slotted pages: указатели в начале страницы, ячейки — с конца, между ними свободное место. Алексей делится инсайтом: недавно он разбирал бинарный протокол Cisco, и он устроен ровно как страницы со слотами — люди, придумавшие его, явно знали, как хранят данные на диске, и книга объяснила, зачем протокол такой сложный. Дальше фрагментация, free list и стратегии first fit и best fit; ячейки в странице лежат неупорядоченно, а порядок задают отсортированные указатели. В реальных системах индекс и данные чаще живут в разных файлах и упираются уже в лимиты файловой системы; в чате напоминают про TOAST в PostgreSQL для больших значений.

Вова добавляет из конца главы версионирование форматов — Cassandra пишет префикс версии в файлы — и контрольные суммы: диски пишут не всегда честно, и он вспоминает историю из одной книги по SRE, которую недавно начал читать и которая бесплатно лежит на сайте: побитые биты там восстанавливали, перебирая их по одному, пока не сойдётся checksum. Четвёртую, самую сложную главу проходят за шесть минут: один из участников нашёл репозиторий, где большая часть главы реализована на Go, и сам за ночь дошёл до сплитов — понял, что это интересно, но книги для собственной реализации мало. Техники: сиблинг-ссылки для обхода диапазонов, high key как крышка поддерева, overflow-страницы для длинных значений, хлебные крошки для обратного пути, фоновая балансировка, right-most append для монотонно растущих ключей, сжатие с непредсказуемым остатком места и вакуум как борьба с энтропией. Ведущие подводят итог: четыре главы за час — слишком быстро, а прошлую книгу, по их словам, записывали полгода; дальше — абстракции хранения, варианты B-деревьев и транзакции. Алексей благодарит: без клуба до этой книги не добрался бы.