--- title: "Log-structured FS и мост к LSM-деревьям" description: "Обычная файловая система обновляет данные на месте (in-place): у блока файла есть постоянный адрес на диске, и изменение перезаписывает именно его. Одно маленькое изменение при…" canonical: https://graphlms.ru/os/book/lfs course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Log-structured FS и мост к LSM-деревьям > Источник: https://graphlms.ru/os/book/lfs — курс «Операционные системы», GraphLMS. ## Идея: писать только в конец Обычная файловая система обновляет данные **на месте** (in-place): у блока файла есть постоянный адрес на диске, и изменение перезаписывает именно его. Одно маленькое изменение при этом порождает записи в разные места: блок данных, inode, битмап (см. [устройство ФС](/os/book/fs-implementation)). Для [жёсткого диска](/os/book/hdd) каждое такое место — отдельный seek. В 1991 году Мендель Розенблюм и Джон Оустерхаут предложили **log-structured file system** (LFS): никогда ничего не перезаписывать. Любое изменение — данные, inode, служебные структуры — дописывается в конец одного растущего **лога**. Лог здесь в буквальном смысле: лента, куда записи добавляются только в хвост. Аналогия — бухгалтерская книга, в которой ничего не стирают. Изменился остаток на счёте — внизу дописывается новая строка «счёт № 5: такая-то сумма». Актуальное значение — последняя строка про этот счёт. ```text на месте (in-place): в лог (append-only): изменить блок B17 файла foo изменить блок B17 файла foo ┌────┬───────┬────┐ ┌──────┬─────┬────────────┐ │ ...│ B17 → │... │ │старое│ ... │ B17 новый ◄─ хвост └────┴───────┴────┘ └──────┴─────┴────────────┘ идём туда, где лежал B17 пишем в конец, подряд → случайная запись → последовательная запись ``` ## Зачем это нужно Авторы LFS исходили из двух наблюдений. Памяти становится всё больше, поэтому чтения всё чаще обслуживает кэш, и производительность определяется записью. А запись на HDD быстра только последовательная: случайная в сотни раз медленнее из-за seek и вращения. LFS превращает любую запись в последовательную. Изменения копятся в памяти, пока не наберётся **сегмент** — непрерывный кусок лога в несколько мегабайт, — и сегмент пишется одной большой операцией. Сотни мелких изменений разных файлов превращаются в одну последовательную запись на полной скорости диска. На [SSD](/os/book/ssd) seek нет, но последовательная запись крупными кусками тоже выгоднее: она заполняет блоки флеша целиком и меньше нагружает сборку мусора контроллера. Более того, FTL внутри SSD сам устроен как лог-структурированная система: та же запись в чистое место и та же уборка мусора, только на уровне контроллера. ## Как найти inode: imap В обычной ФС inode номер N лежит по вычисляемому адресу в таблице inode. В LFS inode тоже дописывается в лог при каждом изменении, значит, его адрес всё время меняется. Как его найти? Через ещё один уровень косвенности — **карту inode** (inode map, imap): таблицу «номер inode → текущий адрес inode в логе». При записи нового inode обновляется и его элемент в imap. Сама imap тоже пишется в лог, кусками, рядом с изменёнными inode. А чтобы найти куски imap, есть одно место на диске с фиксированным адресом — **checkpoint region** (CR). LFS периодически (например, раз в 30 секунд) записывает в CR адреса актуальных кусков imap. ```text поиск блока файла с номером inode N: [фиксированный адрес] [в логе] [в логе] [в логе] checkpoint region ───► кусок imap ───► inode N ───► блок данных (N → адрес) (адреса блоков) ``` Только одно звено живёт по фиксированному адресу, остальные «плавают» по логу. На практике imap целиком держат в памяти (читают при монтировании), поэтому лишних чтений при обычной работе нет. На самом деле CR в LFS две, в разных концах диска, и обновляют их по очереди: если сбой случится во время записи одной, вторая останется целой. Логически же точка входа одна. ## Мусор и его уборка Раз ничего не перезаписывается, старые версии остаются в логе. Блок изменили десять раз — в логе девять мёртвых копий и одна живая. Рано или поздно место кончится. Поэтому LFS постоянно в фоне убирает мусор — это **segment cleaning** (очистка сегментов). Очиститель берёт несколько старых сегментов, определяет, какие блоки в них ещё **живые**, переписывает живые плотно в новый сегмент в хвосте лога, а старые сегменты помечает свободными. ```text до (Ж — живой блок, x — мёртвый): ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ Ж x x Ж x Ж │ │ x Ж x x Ж x │ │ Ж x Ж x x x │ └─────────────┘ └─────────────┘ └─────────────┘ сегмент 1 сегмент 2 сегмент 3 после: живые переписаны в новый сегмент в хвосте лога ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ свободен │ │ свободен │ │ свободен │ │ Ж Ж Ж Ж Ж Ж Ж│ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘ ``` Как понять, жив ли блок? В начале каждого сегмента LFS хранит **сводку сегмента** (segment summary): для каждого блока — номер inode и номер блока в файле. Очиститель берёт блок, находит через imap актуальный inode и смотрит: указывает ли inode на этот адрес? Если да — блок живой. Если inode указывает уже куда-то ещё — блок перезаписан, это мусор. Цена уборки — дополнительная запись: живые блоки копируются повторно. Если очищать сегмент, в котором 90% блоков живые, нужно переписать 90% сегмента ради 10% свободного места. Поэтому очиститель предпочитает сегменты, где живых мало, и производительность LFS сильно падает, когда диск почти заполнен — ровно та же закономерность, что у сборки мусора в SSD. Компромисс LFS в одной фразе: дешёвая запись сейчас, отложенная работа по уборке потом. ## Восстановление после сбоя Лог упрощает восстановление. При монтировании LFS читает последнюю целую checkpoint region — это согласованная точка. Затем проходит по сегментам, записанным после неё (**roll-forward**), и подхватывает из них inode и изменения, которые успели лечь целиком. Писать «на места» не нужно, потому что постоянных мест нет: лог и есть данные. ```text журналируемая ФС LFS ┌──────────┐ ┌──────────────┐ ┌────────────────────────────┐ │ журнал │──►│ основные места│ │ лог = вся файловая система │ │ (по кругу)│ │ (постоянные) │ │ (хвост растёт вправо ►) │ └──────────┘ └──────────────┘ └────────────────────────────┘ журнал — страховка, данные лог — единственное хранилище потом переносятся на места ``` Как и везде, долговечность конкретной записи даёт только сброс на носитель: запись в лог тоже сначала копится в памяти, и без `fsync` (см. [fsync и durability](/os/book/fsync-durability)) последние изменения пропадут при сбое питания. Чистая LFS в мейнстрим не вышла: накладные расходы на уборку оказались слишком заметными для файловых систем общего назначения. Но её идеи живут. **F2FS** (flash-friendly file system), которую используют многие Android-устройства, — лог-структурированная файловая система для флеша. Copy-on-write ФС вроде ZFS и btrfs (см. [журналирование](/os/book/journaling)) тоже никогда не пишут на место. А самое важное для бэкенда наследие — LSM-деревья. ## Мини-модель на Go Соберём игрушечное хранилище «ключ-значение» на этой идее: запись только в конец, индекс «ключ → позиция последней версии» (аналог imap) и уборка мусора. ```go play package main import "fmt" type record struct { key, value string } // LogKV — хранилище «ключ-значение», которое только дописывает в конец лога. type LogKV struct { log []record // «диск»: записи только добавляются index map[string]int // ключ → позиция последней версии (аналог imap) } func NewLogKV() *LogKV { return &LogKV{index: map[string]int{}} } func (kv *LogKV) Put(key, value string) { kv.log = append(kv.log, record{key, value}) // всегда в конец kv.index[key] = len(kv.log) - 1 // старая версия стала мёртвой } func (kv *LogKV) Get(key string) (string, bool) { pos, ok := kv.index[key] if !ok { return "", false } return kv.log[pos].value, true } // Compact переписывает только живые записи в новый лог (segment cleaning). func (kv *LogKV) Compact() { var fresh []record newIndex := map[string]int{} for pos, r := range kv.log { if kv.index[r.key] == pos { // запись живая, если индекс указывает на неё fresh = append(fresh, r) newIndex[r.key] = len(fresh) - 1 } } kv.log, kv.index = fresh, newIndex } func main() { kv := NewLogKV() kv.Put("user:1", "Аня") kv.Put("user:2", "Боря") kv.Put("user:1", "Аня Петрова") // обновление = новая запись в конце kv.Put("user:2", "Борис") kv.Put("user:1", "Анна Петрова") v, _ := kv.Get("user:1") fmt.Println("user:1 =", v) fmt.Println("записей в логе:", len(kv.log), "живых ключей:", len(kv.index)) kv.Compact() v, _ = kv.Get("user:2") fmt.Println("после компакции записей:", len(kv.log), "user:2 =", v) } ``` ```text user:1 = Анна Петрова записей в логе: 5 живых ключей: 2 после компакции записей: 2 user:2 = Борис ``` Пять записей, из них живых две. Компакция определяет живые записи так же, как очиститель LFS: запись жива, если индекс указывает на неё. Почти в таком виде устроен движок Bitcask (хранилище в базе Riak): файлы-логи на диске, хеш-таблица «ключ → позиция» в памяти, периодическое слияние файлов. ## LSM-дерево: LFS для баз данных Индекс в памяти, как в примере, хорош, пока все ключи помещаются в RAM. Если ключей миллиарды, нужен другой подход. Им стало **LSM-дерево** (log-structured merge tree). На нём построены RocksDB, LevelDB, Pebble (движок CockroachDB), Cassandra, ScyllaDB; похожие идеи — в движке MergeTree у ClickHouse. Путь записи в LSM: 1. Запись дописывается в **WAL** на диске — только ради восстановления после сбоя, тот же журнал, что в [главе про fsync](/os/book/fsync-durability). 2. Запись попадает в **memtable** — отсортированную структуру в памяти (обычно skip list или дерево). 3. Когда memtable вырастает до порога (десятки мегабайт), её целиком записывают на диск одним последовательным файлом — **SSTable** (sorted string table): неизменяемый файл, где пары «ключ-значение» отсортированы по ключу. 4. SSTable копятся, в них лежат устаревшие версии ключей и метки удаления. Фоновая **компакция** (compaction) сливает несколько SSTable в новые, выбрасывая мёртвые версии. Это segment cleaning из LFS, только над парами ключ-значение. ```text write(key, val) │ ├──► WAL на диске (последовательно, для восстановления) ▼ ┌──────────┐ │ memtable │ в памяти, отсортирована └────┬─────┘ │ заполнилась → сброс одним последовательным файлом ▼ L0: [SSTable] [SSTable] [SSTable] неизменяемые, отсортированные │ компакция: слияние, выброс мёртвых версий ▼ L1: [ SSTable побольше, без дублей ] │ компакция ▼ L2: [ ещё больше ... ] ``` Соответствие с LFS: | LFS | LSM-дерево | |---|---| | запись сегментом в конец лога | сброс memtable в новый SSTable | | мёртвые версии блоков | устаревшие версии ключей и метки удаления | | segment cleaning | компакция | | imap: где сейчас лежит inode | индексы SSTable и манифест (какие файлы актуальны) | Чтение в LSM дороже записи: ключ может лежать в memtable или в любом из SSTable, и проверять приходится несколько мест, от новых к старым. Чтобы не открывать каждый файл, у каждого SSTable есть **фильтр Блума** (Bloom filter) — компактная вероятностная структура, которая умеет отвечать «ключа здесь точно нет» или «ключ, возможно, есть». Ответ «точно нет» позволяет пропустить файл без чтения с диска. ## LSM или B-дерево Классическая альтернатива — **B-дерево** (B-tree): сбалансированное дерево страниц, которое обновляется на месте. На нём построены индексы PostgreSQL, InnoDB в MySQL, BoltDB/bbolt в Go. Это та самая модель «на месте», с которой начиналась глава. | | LSM-дерево | B-дерево | |---|---|---| | Запись | в память и последовательно в лог, дёшево | найти страницу и переписать её, случайная запись | | Чтение | проверить memtable и несколько SSTable (помогают фильтры Блума) | спуститься по дереву к одной странице | | Фоновая работа | компакция, отъедает диск и CPU | почти нет | | Лишнее место | старые версии до компакции | полупустые страницы | | Хорош для | потоков записи: логи, метрики, события | смешанной нагрузки с большим числом чтений | Обе структуры переписывают данные больше одного раза. B-дерево меняет страницу целиком ради одной строки, LSM переписывает данные при каждой компакции, и суммарно один байт может быть записан на диск десятки раз. Какая из схем выигрывает, зависит от нагрузки, поэтому выбор движка начинается с вопроса: чего у вас больше, записей или чтений, и насколько важна задержка чтения. > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/lfs ## Частые ошибки - Думать, что лог-структурированная запись бесплатна: уборка мусора переписывает живые данные, и на заполненном диске это дорого. - Удалять ключ в LSM-подобном хранилище только из индекса в памяти. - Выбирать движок (LSM или B-дерево) без оценки соотношения записей и чтений. - Считать, что лог отменяет `fsync`: последние изменения в памяти всё равно пропадут при сбое. ## Проверьте себя 1. Зачем LFS нужна imap и где лежит точка входа в неё? 2. Как очиститель понимает, что блок в сегменте ещё живой? 3. Зачем у SSTable фильтр Блума? 4. Добавьте в `LogKV` из главы метод `Delete(key)`. Почему недостаточно удалить ключ из `index`, если после перезапуска индекс будет восстанавливаться чтением лога, и что для этого делают LSM-движки? Ответы. (1) inode всё время переезжает в хвост лога, imap хранит его текущий адрес; адреса кусков imap записаны в checkpoint region по фиксированному адресу. (2) По сводке сегмента находит inode и номер блока, через imap берёт актуальный inode и проверяет, указывает ли он на этот адрес. (3) Чтобы не читать файлы, где ключа точно нет. (4) При восстановлении из лога найдётся последняя запись ключа со старым значением, и удалённый ключ «воскреснет». Удаление тоже нужно записать в лог — специальной записью-надгробием (tombstone). LSM-движки так и делают, а сами надгробия выбрасывают при компакции, когда старых версий ключа ниже уже не осталось. ## Что спрашивают на собесе - **В чём идея LFS?** Ничего не перезаписывать на месте; все изменения дописываются в конец лога крупными сегментами, поэтому любая запись последовательная. - **Как найти inode, если он всё время переезжает?** Через imap («номер inode → адрес»), куски которой тоже в логе; точка входа — checkpoint region по фиксированному адресу. imap держат в памяти. - **Что такое segment cleaning?** Сборка мусора: живые блоки из полупустых сегментов переписываются плотно, сегменты освобождаются. Чем полнее диск, тем дороже. - **Чем LFS отличается от журналируемой ФС?** В журналируемой ФС журнал — временная страховка, данные живут на постоянных местах. В LFS лог и есть хранилище. - **Как LFS связана с LSM?** Запись в конец, неизменяемые сегменты (SSTable), компакция = segment cleaning. - **Зачем в LSM фильтр Блума?** Чтобы не читать SSTable, где ключа точно нет. - **LSM или B-дерево?** LSM дешевле на запись и платит чтением и фоновой компакцией; B-дерево быстрее читает и пишет случайно на место. ## Вопросы для самопроверки **Квиз «Log-structured FS и LSM»** 1. В чём ключевая идея log-structured файловой системы? - Каждый файл хранится в отдельном журнале для надёжности - Данные шифруются перед записью на диск - Метаданные пишутся на месте, а данные — в лог - Все изменения пишутся только дозаписью в конец одного растущего лога, без перезаписи на месте (верно) - Пояснение: LFS вообще не перезаписывает блоки на месте: любое изменение — это append в хвост лога. Так все записи становятся последовательными, что быстро на HDD и щадяще для SSD. 2. Зачем в LFS нужна imap (inode map)? - Чтобы считать свободное место на диске - Чтобы находить текущий адрес inode в логе, ведь inode при каждом изменении переезжает в новое место (верно) - Чтобы хранить права доступа к файлам - Чтобы кэшировать содержимое файлов в памяти - Пояснение: Поскольку inode переписывается в хвост лога и его адрес постоянно меняется, imap отображает стабильный номер inode на его плавающий адрес. Корень imap закреплён в checkpoint region. 3. Что делает segment cleaning в LFS? - Шифрует старые сегменты - Сжимает данные алгоритмом компрессии - Собирает живые блоки из частично занятых сегментов в новый плотный сегмент и освобождает старые (верно) - Переносит данные с SSD на HDD - Пояснение: Старые версии блоков копятся мёртвым грузом. Segment cleaning (сборка мусора) переписывает живые блоки плотно, освобождая сегменты под новую запись. В LSM это называется компакцией. 4. Какие соответствия между LFS и LSM-tree верны? - мёртвые старые блоки ↔ устаревшие версии ключей в SSTable (верно) - последовательная запись лога ↔ flush memtable одним куском (верно) - imap ↔ bloom-фильтр - segment cleaning ↔ compaction (верно) - Пояснение: Компакция — это segment cleaning над парами ключ-значение; flush memtable — последовательная запись сегмента; устаревшие версии ключей соответствуют мёртвым блокам. Imap — это карта адресов, а не bloom-фильтр (тот ускоряет проверку отсутствия ключа). 5. Что верно про сравнение LSM-tree и B-tree? - LSM оптимизирован под чтение, B-tree — под запись - Оба пишут строго на месте - B-tree использует append-only лог, а LSM — записи на месте - LSM оптимизирован под запись (последовательная в лог), B-tree — под чтение (in-place, спуск к одной странице) (верно) - Пояснение: LSM write-optimized: дешёвая последовательная запись, но чтение дороже (ключ ищется в нескольких SSTable). B-tree read-optimized: in-place обновления (случайная запись), зато чтение — быстрый спуск к одной странице. 6. После перезагрузки LFS надо найти любой файл, хотя почти все структуры «плавают» по логу. С чего она начинает? - С checkpoint region, которая лежит по фиксированному адресу и указывает на актуальные куски imap (верно) - С суперблока, где записаны адреса всех inode - С полного чтения лога с самого начала - С корневого каталога, адрес которого известен заранее - Пояснение: Нужна хотя бы одна точка опоры с неизменным адресом. В LFS это checkpoint region: логически она одна, а физически её держат в двух копиях и обновляют по очереди, чтобы сбой посреди записи не оставил диск без валидной точки опоры. Регион указывает на свежие куски imap, imap по номеру inode даёт его текущий адрес в логе, а inode ведёт к блокам данных.