Что такое lsm

LSM обычно означает Log-Structured Merge-tree (лог-структурированное дерево слияния). Это подход к организации индексов и данных, который особенно эффективен для систем с большим объёмом записей.

Ключевые идеи:

• Записи сначала попадают в память (memtable) и в журнал изменений (WAL).
• Когда memtable заполняется, данные сбрасываются на диск в виде отсортированного нереверсивного файла на диске — SSTable.
• Диск организован в уровни (L0, L1, L2 и т. д.). Релизы на разных уровнях с разной степенью перекрытия ключевых диапазонов.
• Периодически выполняется компакция (слияние) файлов между уровнями: удаляются устаревшие версии ключей, создаются новые SSTable с упорядоченным набором ключей.

Преимущества:

• Очень высокая скорость записи: последовательные записи на диск и минимальные случайные операции.
• Эффективно работает на SSD/HDD за счёт последовательного доступа и компактирования.

Недостатки:

• Поиск может требовать проверки нескольких уровней и множества SSTable, что увеличивает чтение и задержки.
• Необходимы механизмы ускорения чтения, например Bloom-фильтры.
• Стоит задача управления компактациями (их частота и способ зависит от стратегии).

Типы компакций:

• Levelled (leveled): уровни не перекрываются по диапазонам ключей, размер уровней растёт, обеспечивает предсказуемые задержки чтения.
• Size-tiered: файлы накапливаются и объединяются чаще, что даёт большую пропускную способность записи, но может ухудшать задержку чтения.

Где применяется:

• LevelDB, RocksDB, Cassandra (в реализации хранения), и другие современные KV-хранилища.

Если нужно, могу привести простую схему работы на примере: как читаются ключи, как работают мемтаблы и SSTable, или объяснить различия между leveled и size-tiered компакциями. Уточните, в каком контексте вы готовитесь к экзамену (интернет-уровень, архитектура БД, примеры задач).