Что такое 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 компакциями. Уточните, в каком контексте вы готовитесь к экзамену (интернет-уровень, архитектура БД, примеры задач).