Любая база данных в конечном счёте сводится к вопросу: как организовать байты на диске так, чтобы потом быстро их находить и не менее быстро обновлять. Два семейства структур решают эту задачу принципиально по разному. Сбалансированные деревья BTree десятилетиями служат основой реляционных систем и держат данные упорядоченными прямо на месте. Журнальные LSM Tree пришли из мира больших распределённых хранилищ и построены вокруг последовательной записи с последующей периодической сборкой. Понимание их различий объясняет, почему одна и та же нагрузка летает в одном движке и ползёт в другом, и позволяет выбирать хранилище осознанно, а не по моде.
Устройство BTree и цена обновления на месте
BTree это широкое сбалансированное дерево, где каждая страница диска соответствует узлу, содержащему десятки ключей и указателей. Поиск ключа это спуск от корня к листу за три четыре перехода, и каждый переход читает одну страницу. При миллионе записей нужны буквально единицы обращений к диску, если верхние уровни закэшированы в оперативной памяти. Листья дерева хранят ключи в порядке, что делает диапазонные запросы дешёвыми: нашёл левую границу и читаешь подряд.
Запись в BTree означает изменение на месте. Найденная страница листа модифицируется, сброшена на диск при вытеснении, иногда расщепляется, и расщепление может каскадом двинуться вверх. Это порождает случайные записи по диску, которые на магнитных носителях жутко дороги, а на твердотельных просто отъедают ресурс и полосу записи. Усиливает эффект фактор обновления: каждая маленькая правка строки превращается в перезапись восьмикилобайтной страницы.
Поверх этого BTree требует защиты от частичной записи. Известные механизмы двойной записи, контрольные суммы страниц и журналирование гарантируют, что после сбоя страница восстановится, но все они увеличивают объём физической записи. Отдельного разговора стоит кластеризация по первичному ключу. Когда строки таблицы физически упорядочены по ключу, диапазонный запрос читается непрерывной полосой страниц, и стоимость чтения миллиона последовательных идентификаторов оказывается близка к стоимости простого линейного сканирования. Разрушает эту красоту фрагментация: после месяцев вставок и удалений физический порядок перестаёт совпадать с логическим, и чтение превращается в прыжки по диску. Периодическая реорганизация таблиц существует именно чтобы возвращать совпадение порядков.
Итоговая арифметика такова: чтение в дереве дешёвое и предсказуемое, обновление на месте дорогое и фоново шумное.
Устройство LSM Tree и цена чтения через уровни
LSM Tree стартует с противоположной посылки: писать быстро и только последовательно. Свежее обновление сначала попадает в журнал на диске для надёжности, затем в таблицу в памяти, memtable, обычно упорядоченную структуру вроде скип листа. Заполненная memtable замораживается и сливается на диск цельным отсортированным файлом, SSTable. Такие файлы образуют уровни, и периодический процесс уплотнения, compaction, склеивает перекрывающиеся файлы нижних уровней в более крупные, выбрасывая устаревшие версии и удалённые записи.
Запись здесь почти всегда последовательная: дописывание журнала, большие файлы уровней, линейное слияние. Диск любит такой паттерн, и пропускная способность записи получается в разы выше, чем у дерева, обновляющегося на месте под случайным трафиком. Именно поэтому LSM стал фундаментом систем, принимающих потоковые вставки в гигантских объёмах.
Плата за это лежит в чтении. Ключ может находиться в свежей memtable, в любом из недавних файлов верхнего уровня или глубоко внизу, и движок проверяет кандидатов от свежих к старым, пока не найдёт актуальную версию. Частично проверки отсекаются фильтрами Блума, частично итоговыми индексами внутри файлов, но физика остаётся: чтение в LSM дороже и менее предсказуемо, особенно без настроенного уплотнения.
Ещё одна издержка это усиление записи. Одно логическое изменение живёт в нескольких версиях на разных уровнях, пока compaction не вычистит старьё, и при уровневом уплотнении физическая запись на единицу логической обычно выше логической на порядок, примерно в 10–30 раз. Сравнение с BTree зависит от нагрузки: дерево переписывает страницу целиком (4–16 КБ) ради нескольких изменённых байт и дублирует запись в журнал, поэтому на потоке мелких случайных записей его усиление может быть не ниже, чем у LSM, а на крупных последовательных записях преимущество LSM пропадает. На ограниченных по ресурсу записи накопителях это сокращает их жизнь, что учитывается в серверных сценариях.
Сравнение поведения под типовыми нагрузками
Чтение точек по ключу это территория дерева. Два три чтения страниц на хорошо прогретом кэше обычно быстрее, чем обход уровней LSM даже с фильтрами. Диапазонные сканирования тоже выигрывают у дерева, потому что данные физически отсортированы и смежны. Аналитические сканирования больших диапазонов ведут себя прилично в обеих структурах, когда файлы LSM уже уплотнены, но в смеси со свежей записью LSM страдает от чтения перекрывающихся файлов.
Запись разворачивает рейтинг. Интенсивные вставки и обновления под случайными ключами заставляют BTree гонять случайные записи и расщепления, тогда как LSM принимает их последовательным потоком. На высоких темпах записи разрыв достигает порядка величины, особенно когда помимо индекса обновляются несколько вторичных структур.
Смешанная нагрузка проявляет скрытые эффекты. Уплотнение в LSM конкурирует с запросами за диск, и настройка его агрессивности становится самостоятельной задачей: слишком вялое уплотнение пускает уровни вразнос и убивает чтение, слишком энергичное отнимает полосу у записи. В BTree фоновая работа это очистка и контрольные точки журнала, и её влияние понятнее и стабильнее. Дополнительный фактор смешанных нагрузок это блокировки: обновления дерева захватывают страницы и могут задерживать читателей, тогда как чтение в LSM не конфликтует с записью, поскольку читает иммутабельные файлы. Поведение под конкурентной нагрузкой различается системно, и бенчмарк обязан включать параллельность, чтобы показать это различие.
Память тоже распределяется по разному. Дерево тратит кэш на горячие внутренние страницы и листья, LSM на memtable, фильтры Блума и блочный кэш файлов. На дефиците оперативной памяти обе структуры деградируют, но по разным механизмам, и конфигурацию приходится выверять под реальный профиль.
Измерение и диагностика каждой структуры
Для BTree полезные метрики включают глубину дерева, заполненность страниц, частоту расщеплений и объём журнальной записи на транзакцию. Рост глубины означает увеличение стоимости точечного поиска, акапнивание мусора в страницах после массовых удалений требует реорганизации. Профилировщик ввода вывода показывает долю случайных записей и их темп.
Для LSM главные индикаторы это размер и возраст файлов по уровням, число файлов, участвующих в проверке чтения, скорость и отставание compaction, а также текущее усиление записи. Каждая из этих цифр легко читается из статистики движка, и по их совокупности строится операционная политика: когда уплотнять, сколько потоков отвести, какой стиль уплотнения выбрать, уровневый или универсальный.
Бенчмарки следует гонять на нагрузке, похожей на продакшн, и с прогретым состоянием. Холодный прогон LSM без накопленных файлов покажет нереалистично хорошее чтение, а горячий прогон дерева без фоновой записи не покажет конкуренцию за полосу. Честное сравнение требует часов замешанного трафика с периодами простоя и всплесков.
Диагностическая последовательность при выборе структуры выглядит так:
- Описать профиль нагрузки в терминах соотношения чтений и записей, доли диапазонных запросов и темпа обновлений;
- Оценить жизненный цикл данных: частые удаления и перезаписи сильно давят LSM уплотнением, стабильные данные нет;
- Прогнать репрезентативный бенчмарк на обоих движках с одинаковыми ресурсами памяти и диска;
- Измерить не только средние, но и хвостовые задержки, потому что фоновая работа структур видна именно там.
Гибридные инженерные решения и эволюция структур
Практика породила много мутаций вокруг обеих идей. В мире деревьев появились буферные деревья, где изменения верхних узлов накапливаются и спускаются вниз пачками, превращая случайные записи в более упорядоченные. В мире журнальных структур различают стратегии уплотнения: уровневая держит мало перекрытий и быстрое чтение ценой высокого усиления записи, универсальная формирует редкие большие слияния и экономит запись ценой всплесков задержки чтения в периоды слияния.
Индексы второго уровня тоже эволюционировали. В деревах их роль играют отдельные деревья, в журнальных хранилищах вторичный индекс это обычно соседний LSM со ссылками на основные ключи, и согласованность между ними обеспечивается всё тем же журналом. Учёт этих деталей важен при оценке стоимости транзакции с несколькими полями поиска.
Кэширование стало скорее общей дисциплиной, чем отличием. Оба мира выжимают всё из оперативной памяти, и промах кэша одинаково болезнен в обеих структурах. Отличие в стратегии: дерево стремится держать горячие страницы, журнальная система агрессивнее инвестирует в фильтры Блума на файлы, чтобы не трогать диск впустую на промахах ключа.
Отдельной ветвью идут адаптивные структуры с обученными индексами, которые заменяют дерево поиском по предсказанной позиции. Для практикантов важно другое: фундаментальный закон о разнице паттернов чтения и записи остаётся в силе независимо от орнаментов, и именно он режет правильный выбор в вопросе движка хранения.
Выбор структуры влияет и на экономику хранения. Журнальные системы агрессивно сжимают иммутабельные файлы, потому что компрессия решается раз на всю жизнь блока, и объёмы на диске у них обычно меньше. Дерево сжимает страницы с осторожностью, потому что обновление на месте под лёгкой компрессией дороже, а выравнивание сложнее. На больших архивах различие в плотности хранения само по себе способно перевесить остальные доводы, и его обязательно включают в расчёт стоимости владения.
Практические рекомендации по выбору движка
Реляционные системы общего назначения, где важны транзакции, вторичные индексы и отзывчивое чтение, исторически и обоснованно строятся на BTree. Дерево даёт широкий набор возможностей доступа и понятную административную модель, и большинство бизнес приложений живёт именно на нём.
Журнальные подходы выбирают там, где запись доминирует и важна пропускная способность вставок: ленты событий, метрики, логи, каталоги с постоянными обновлениями. Хранилища семейства LSM принимают потоки, которые задушили бы дерево фоновой записью, и отвечают на точечные запросы через фильтры и кэши чуть дороже, но стабильно.
Граница между мирами давно размыта. Современные реляционные движки включают журнальные структуры для отдельных таблиц, а LSM хранилища обзаводятся транзакциями и вторичными индексами. На этапе выбора полезны не ярлыки SQL или NoSQL, а конкретные характеристики: тип доминирующей операции, объём рабочего множества, калькуляция усиления записи, требования к задержке хвостов.
Проверочный совет перед коммитом архитектуры таков: собрать профиль реальных запросов за неделю, посчитать соотношения и прогнать упрощённый стенд на обоих семействах. День измерений экономит годы миграций, и это наблюдение старо как само искусство проектирования хранилищ.
Как и всякая фундаментальная развилка инженерии, выбор между BTree и LSM сводится к уважению физики устройства. Последовательная запись и упорядоченное чтение это дары, которые нельзя получить одновременно бесплатно, и хорошая команда просто решает, за что именно она готова платить в своей системе.
История этого противостояния не закончена: границы между семействами продолжают размываться, а новые накопители смещают точку равновесия к последовательным паттернам. Команды, которые отслеживают эту динамику и периодически пересматривают выбор движка под изменившуюся нагрузку, удерживают свои системы быстрыми долгие годы эксплуатации без героических переписываний.