Database Internals — выпуск 2

Разговор начинается с ACID, «приевшегося, но родного», и Гриша подхватывает: атомарность — операции транзакции неотделимы, согласованность — инварианты после каждой транзакции, изоляция — конкурентные транзакции не влияют друг на друга, долговечность — данные переживают сбой. Участникам понравилась мысль автора, что ACID во многом маркетинг и многие базы честного ACID не дают; один из ведущих вспоминает шутку Клеппмана про durability — если сгорит дата-центр, копию придётся хранить в космосе, — а Гриша замечает, что уровень проблем, который мы готовы пережить, у всех разный. Дальше автор перечисляет компоненты, без которых транзакций не бывает: менеджер транзакций, менеджер блокировок, менеджер журнала и кэш страниц — Александр советует держать эту четвёрку в голове, тогда глава читается легко. Кэшей много на всех уровнях, и некоторые базы специальным флагом обходят кэш файловой системы, что не нравилось Линусу Торвальдсу, но альтернативы нет. Buffer pool, подчёркивает Гриша, не набор буферов, а очередь страниц, и главный вопрос — кого вытеснять.

Стратегии вытеснения: FIFO, LRU, CLOCK с битом обращения по кругу и двухочередные схемы вроде TinyLFU с пробационной и защищённой зонами, похожие на поколения в JVM; книга рекламирует библиотеку Caffeine, где это реализовано. Александр объясняет, почему простой LRU для баз плох: первыми в кэш попадают верхние страницы дерева, которые нужны всегда, и выкидывать их по возрасту нельзя. Восстановление — алгоритм ARIES 1992 года, который до сих пор используется: страницы сбрасываются на диск с задержкой, а изменения фиксируются в журнале упреждающей записи. Три фазы после сбоя: анализ находит грязные страницы и незавершённые транзакции, redo проигрывает историю до момента краша, undo откатывает незавершённые транзакции, возвращая базу не просто в состояние до падения, а в согласованное состояние, обещанное буквой C. Гриша уточняет, откуда берутся грязные страницы — из очереди страниц, куда попадают все записи, пока менеджер журнала пишет их на диск. Александру нравится, что даже сбой во время восстановления учтён: откатанные транзакции запоминают, чтобы не накатить повторно.

Управление конкурентностью автор делит на оптимистичное — транзакции работают параллельно и перед коммитом проверяют конфликты, проигравшие откатываются, — многоверсионное с timestamp у каждой версии и пессимистичное с блокировками. Гриша проходит аномалии: грязное чтение незакоммиченных данных, неповторяемое чтение одной строки и фантомы — коллега уточняет, что они всплывают при выборке диапазона; уровни изоляции от read uncommitted, самого быстрого, до serializable, самого дорогого, и Александр напоминает, что стандарт SQL зафиксировал те аномалии, что казались важными при его принятии, а их на самом деле больше — snapshot isolation поверх MVCC даёт свою аномалию, названия которой участник не вспомнил. Гриша советует читать документацию своей базы: repeatable read может быть реализован через снапшоты, а может — заглушкой. Оптимистичный подход при агрессивной конкуренции превращается в забег, где один победитель и толпа проигравших, которые повторяют попытку; пессимистичный — двухфазная блокировка с фазой роста и фазой отпускания, shared и exclusive блокировки, и отдельно латчи на физические страницы дерева.

Шестая глава про варианты B-деревьев — самая забористая: Гриша признаётся, что пробегал глазами по словам, думая о своём; Александр читал ещё недописанную книгу по главам на платформе издателя, на шестой главе остановился на год-полтора, а победил уже по русской версии; Вова купил русскую, а потом вернулся к английской, потому что терминология знакомее. Вова даёт обзор: B-дерево оптимизировано для чтения, а запись требует перезаписывать страницы и делить их, поэтому появились варианты. Copy-on-write делает дерево неизменяемым: при записи копируется веточка, переключаются указатели, старый корень освобождается — такое дерево, по словам Вовы, используется в одном протоколе; Гриша замечает, что копирование ради атомарности — вообще популярный приём. Буферизующий вариант копит изменения в памяти и сбрасывает их порциями — так работает один активно используемый движок; Lazy-Adaptive Tree буферизует по поддеревьям; FD-trees — вариант для флеша, где неизменяемые отсортированные ряды упрощают слияния; остальные варианты Вова оставляет за скобками: дальше пришлось бы рассказывать логарифмические ряды.

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

Фильтр Блума позволяет пропускать таблицы, где ключа точно нет: биты по хешам ключа выставлены — ключ, возможно, есть, а вероятность ложного срабатывания зависит от размера фильтра; структуру данных для быстрого поиска — её названия говорящий не вспомнил — Александр увидел в этой книге впервые; дальше выравнивание блоков, Bitcask, WiscKey с индексом поверх сортированного лога, работа с SSD и сборка мусора — глубже, чем нужно, если не пишете свою базу. Итоговая таблица автора сводит структуры по трём ручкам — буферизация, изменяемость, упорядоченность, — и на слуху из них B-деревья да LSM. Один из ведущих сравнивает с Клеппманом: тот ведёт ступеньками от хеш-индекса к SSTable и LSM, и после него кажется, что понимаешь базы; Петров заходит с обратной стороны и оставляет больше вопросов — обе книги стоит перечитывать на разных уровнях. Александр признаётся, что первая часть местами давалась тяжело — в двадцать лет алгоритмы движка зашли бы лучше, — а вторая, про распределённые системы, прочиталась залпом. В следующий раз — распределённые системы, выбор лидера и репликация с гостями: Костя Евтеев из X5, делавший DBaaS в Avito, и Олег Бондарь, который занимается базами данных в Яндексе.