Объясните, за счёт какого механизма LSM-дерево часто эффективнее B-дерева при высокой доле последовательных вставок?
LSM-дерево ускоряет последовательные вставки, потому что сначала записывает изменения в последовательные структуры, а не выполняет множество случайных обновлений страниц на месте. Данные периодически объединяются в отсортированные файлы во время компакции. Компромисс — более сложное чтение, дополнительная запись при компакции и необходимость контролировать её влияние на задержки.
Классические B-деревья хорошо подходят для систем, где записи и чтения должны быстро находить и изменять данные в одном отсортированном индексе. Однако случайные обновления страниц становятся дорогими на дисках и в распределённых хранилищах, особенно при высокой интенсивности вставок.
LSM-деревья появились как подход для сценариев с большим потоком записей. Их исходная идея — заменить множество мелких случайных изменений последовательной записью и отложенным слиянием данных.
При вставке в B-дерево системе может потребоваться найти нужную страницу, изменить её, поддержать сортировку ключей и иногда разделить переполненную страницу. При высокой конкуренции это приводит к случайному вводу-выводу, блокировкам или конфликтам доступа к горячим страницам.
LSM-модель принимает другой компромисс: свежие записи временно находятся в памяти и журнале, а затем сбрасываются в неизменяемые отсортированные файлы. Поэтому чтение может потребовать проверки нескольких уровней данных, а удаление часто представляется специальной меткой, а не немедленным физическим удалением.
Запись обычно сначала попадает в структуру в памяти, например в memtable, и в журнал предзаписи для восстановления после сбоя. Когда memtable достигает заданного размера, она сбрасывается на диск как отсортированный неизменяемый файл, часто называемый SSTable.
Новые SSTable периодически объединяются в процессе компакции. Во время слияния система сортирует ключи, оставляет актуальное значение, удаляет перекрытые версии и может физически исключать устаревшие записи и tombstone — маркеры удаления, если это безопасно.
Преимущество записи возникает из-за последовательного характера сброса и компакции. Система не обязана сразу изменять множество случайно расположенных дисковых страниц, поэтому достигает высокой пропускной способности вставок.
Чтение устроено сложнее: сначала проверяются наиболее свежие данные в памяти, затем несколько наборов SSTable. Для ускорения применяют фильтры Блума, индексы диапазонов и кэширование. При этом фильтр Блума может подтвердить, что ключа точно нет, но не может гарантировать его наличие без чтения соответствующего файла.
Главное ограничение — стоимость компакции. Одни и те же данные могут несколько раз прочитываться и записываться при слиянии уровней. Это создаёт write amplification, потребляет ресурсы диска и процессора и может вызывать всплески задержек.
Кроме того, LSM не всегда лучше B-дерева. При преимущественно точечных чтениях, частых обновлениях небольшого числа записей или строгих требованиях к предсказуемой задержке B-дерево может быть проще и эффективнее. Выбор зависит от соотношения записей и чтений, размера данных, характера ключей, требований к диапазонным запросам и допустимой задержки компакции.
Сервис телеметрии принимает миллионы измерений в минуту. Записи в основном добавляются последовательно по времени, а чтения выполняются по идентификатору устройства и диапазону временных меток.
Вариант с B-деревом обеспечивает понятное поведение чтения и удобные диапазонные запросы, но при большом потоке вставок создаёт значительный объём случайных обновлений и конкуренцию за страницы индекса. Его преимущество — более непосредственная актуальность данных на месте и отсутствие отдельного крупного этапа компакции.
Вариант с LSM хорошо использует последовательную запись и масштабируется по потоку вставок. Его недостатки — необходимость настройки компакции, возможное увеличение задержек чтения при большом числе уровней и дополнительная нагрузка на хранилище.
Разумным выбором будет LSM-хранилище при условии, что команда заранее задаст политики компакции, ограничит число фоновых операций и проверит влияние write amplification на диски. Для результата важно измерять не только среднюю пропускную способность, но и хвостовые задержки чтения и записи во время компакции.
Вопрос: Почему простое последовательное чтение всех SSTable не является достаточным объяснением эффективности LSM?
Ответ: Потому что выигрыш касается прежде всего записи, а чтение всех файлов было бы слишком дорогим. На практике используются разреженные индексы, фильтры Блума, кэши и компакция. Они сокращают число файлов и диапазонов, которые нужно проверять, но не устраняют стоимость чтения полностью.
Вопрос: Что произойдёт, если компакция не успевает за скоростью поступления данных?
Ответ: Будет расти число непересечённых или слабо объединённых файлов. Чтения начнут проверять больше структур, увеличатся write amplification и потребление дискового пространства, а очередь фоновых операций может привести к росту задержек. Система обычно требует ограничения скорости записи, выделения ресурсов компакции или изменения политики уровней.
Вопрос: Почему tombstone нельзя сразу удалить во время ближайшей компакции?
Ответ: Старое значение удалённого ключа может ещё находиться в другом файле или на реплике, которая участвует в чтении. Если преждевременно удалить tombstone, старое значение может снова стать видимым. Удаление маркера безопасно только после выполнения условий, гарантирующих, что более старые версии больше не могут повлиять на результат чтения.