Радикальная идея: писать только в конец

Обычная файловая система пишет данные на место (in-place): у файла есть свои блоки на диске, и когда ты меняешь байты в середине, ФС перезаписывает именно те блоки, где они лежат. Заодно надо обновить и метаданные — например, отметку «файл изменён» в его inode (это структура с информацией о файле: размер, права, указатели на блоки данных; разбирали в главе про реализацию ФС). Получается, что одно маленькое изменение порождает несколько записей в разные места диска: сюда блок данных, туда inode, ещё в третье место — битовую карту занятости.

Log-structured File System (LFS, «лог-структурированная ФС») предлагает поступить наоборот. Никаких перезаписей на месте вообще. Любое изменение — это дозапись в конец одного растущего лога. Лог тут — журнал в буквальном смысле: бесконечная лента, куда новые записи добавляются только в хвост, как строчки в дневник.

Бытовая аналогия. Представь бухгалтерскую книгу. Можно вести её так: нашёл нужную строку, стёр ластиком старую сумму, вписал новую (in-place). А можно так: никогда ничего не стираешь, а просто дописываешь снизу новую строку «по счёту №5 теперь такая-то сумма». Актуальное значение — это всегда последняя запись про данный счёт. Вторая модель и есть лог.

   ЗАПИСЬ НА МЕСТО (in-place):                ЗАПИСЬ В ЛОГ (append-only):
 
   меняем блок B17 файла foo                  меняем блок B17 файла foo
        │                                          │
   ┌────▼─────────────────────┐              ┌─────▼──────────────────────────┐
   │ ...│B17(старое→новое)│... │              │ старое │...│ [B17 новое] ◄─ хвост│
   └──────────────────────────┘              └────────────────────────────────┘
   позиционируем головку точно                всегда пишем в КОНЕЦ, подряд,
   на B17 → случайная запись                   большими пачками → последовательно

Что нарисовано: слева головка диска (или контроллер) каждый раз прыгает на точный адрес старого блока — это случайная запись (random write). Справа все записи сыплются подряд в один растущий конец — последовательная запись (sequential write).

Почему «в конец» — это быстро

Главный аргумент LFS — про производительность записи, и он живёт до сих пор.

На HDD (жёсткий диск с вращающимися пластинами; см. главу про HDD) самое дорогое — это seek, перемещение головки на нужную дорожку, и ожидание поворота пластины. Случайные записи в разные места = постоянные seek'и, диск тратит время на механику, а не на данные. Последовательная же запись идёт одним потоком без seek'ов и выжимает из диска максимум.

На SSD (твердотельный накопитель; см. главу про SSD) пластин нет, но есть своя беда: ячейки нельзя перезаписать «поверх». Чтобы записать в уже занятую страницу, надо сначала стереть весь блок (а блок — это много страниц). Мелкие случайные записи провоцируют write amplification (усиление записи) — контроллер внутри перетасовывает данные, изнашивая ячейки. Последовательная запись большими кусками ложится ровно и щадит флеш.

   почему последовательная запись выигрывает:
 
   HDD:  random  →  seek seek seek seek  (головка скачет, механика тормозит)
         seq     →  ───────────────────► (один проход, без скачков)  БЫСТРО
 
   SSD:  random  →  стереть блок → записать → износ ячеек (write amplification)
         seq     →  заполняем блоки целиком, ровно            ЩАДЯЩЕ

Что нарисовано: и на магнитном диске, и на флеше последовательная запись принципиально дешевле случайной. LFS превращает все записи в последовательные — в этом её суть.

LFS ещё и копит изменения в памяти, собирая их в большой сегмент (segment) — непрерывный кусок лога (например, несколько мегабайт), — и пишет его на диск целиком одной операцией. Это та же идея, что батчинг записей в журнале (см. главу про журналирование): много мелких изменений → одна крупная последовательная запись.

А как теперь найти данные? imap

Тут всплывает проблема. Если inode каждый раз переписывается в новое место хвоста лога, то как его найти? В обычной ФС inode номер N лежит по фиксированному адресу (массив inode). В LFS inode «гуляет» по логу.

Решение — inode map (imap), карта inode: таблица, которая отображает «номер inode → текущий адрес inode в логе». Когда inode перезаписывается в новое место, обновляется и его запись в imap. Сама imap тоже пишется в лог (по кусочкам), а чтобы её саму найти, есть одно фиксированное место на диске — checkpoint region (контрольная область), которое периодически указывает на актуальные куски imap.

   ЦЕПОЧКА ПОИСКА БЛОКА ФАЙЛА в LFS:
 
   [фикс. место]      [в логе]              [в логе]            [в логе]
   checkpoint  ───►   imap  ───►  inode #N  ───►  блок данных D
    region            (№N→адрес) (адреса блоков)  (то, что читаем)
 
   читаем файл #N:
     1) checkpoint → находим актуальные куски imap
     2) imap[N]    → адрес inode #N в логе
     3) inode #N   → адреса блоков данных
     4) блок D     → собственно данные

Что нарисовано: чтение в LFS — это короткая цепочка указателей. Только одно звено (checkpoint region) живёт по фиксированному адресу; всё остальное «плавает» в логе, а imap связывает стабильные номера inode с их плавающими адресами. На практике imap держат в памяти, поэтому лишних чтений с диска нет.

Старые версии и segment cleaning

Раз мы никогда не перезаписываем на месте, а только дописываем — старые версии блоков остаются лежать в логе мёртвым грузом. Изменил блок десять раз — в логе девять устаревших копий и одна живая. Рано или поздно диск забьётся мусором.

Значит, нужна уборка. В LFS она называется segment cleaning (чистка сегментов) — это, по сути, сборка мусора (garbage collection). Работает так: берём несколько старых сегментов, смотрим, какие блоки в них живые (на них всё ещё указывает актуальный inode), а какие мёртвые (перекрыты более новой версией). Живые блоки переписываем в новый сегмент в хвосте лога, а освободившиеся старые сегменты помечаем как свободные — туда можно писать заново.

   SEGMENT CLEANING (уплотнение):
 
   ДО — три полузанятых сегмента (Ж=живой блок, ✗=мёртвый):
 
   ┌───────────────┐ ┌───────────────┐ ┌───────────────┐
   │ Ж ✗ ✗ Ж ✗ Ж  │ │ ✗ Ж ✗ ✗ Ж ✗  │ │ Ж ✗ Ж ✗ ✗ ✗  │
   └───────────────┘ └───────────────┘ └───────────────┘
        сегмент 1         сегмент 2         сегмент 3
 
   читаем живые (Ж), складываем плотно в новый сегмент в хвосте:
 
   ПОСЛЕ:
   ┌───────────────┐ ┌───────────────┐ ┌───────────────┐
   │ свободен      │ │ свободен      │ │ Ж Ж Ж Ж Ж Ж  │ ◄─ новый, плотный
   └───────────────┘ └───────────────┘ └───────────────┘
   сегменты 1 и 2 теперь свободны → снова доступны под запись

Что нарисовано: разрозненные живые блоки из трёх дырявых сегментов собрали в один плотный, а освобождённые сегменты вернули в оборот. Это ровно то, что делает дефрагментация, но как фоновый непрерывный процесс. Как определить, жив ли блок? В заголовке сегмента LFS хранит, какому inode и какому смещению принадлежит каждый блок; сверяемся с актуальным inode через imap — совпал адрес, значит блок живой.

Цена уборки — дополнительная запись (живые блоки копируются повторно). Это плата за то, что основная запись всегда последовательная. Запомни компромисс: дешёвая запись сейчас → отложенная работа по уборке потом.

Где здесь надёжность: связь с journaling и fsync

LFS и журналируемые ФС — близкие родственники, но не одно и то же.

В журналируемой ФС (см. журналирование) лог — это временный буфер: сначала пишем намерение в журнал, потом применяем изменения на их постоянные места (checkpoint), журнал переиспользуется по кругу. То есть данные в итоге живут на месте, журнал — лишь страховка от падения посреди записи.

В LFS лог — это и есть сама файловая система. Постоянного «места» у блоков нет, весь диск — один большой лог.

   JOURNALING FS                         LOG-STRUCTURED FS
   ┌──────────┐   ┌──────────────┐       ┌────────────────────────────┐
   │ ЖУРНАЛ   │──►│ ОСНОВНОЕ МЕСТО│       │   ЛОГ = ВСЯ ФС (хвост ►)    │
   │(временно)│   │ (постоянно)   │       │   данные живут прямо в логе │
   └──────────┘   └──────────────┘       └────────────────────────────┘
   лог — страховка, потом сброс           лог — конечное хранилище

Что нарисовано: в journaling лог отдельно от данных и недолговечен; в LFS лог и есть хранилище. Восстановление после сбоя в LFS опирается на checkpoint region (последняя согласованная точка) плюс «проигрывание» (roll-forward) сегментов, записанных после неё.

При этом обе системы упираются в одну и ту же физику долговечности. Запись «в конец лога» всё равно сначала оседает в кэше диска, и пока не выполнен fsync (см. fsync и долговечность), данные могут потеряться при потере питания. Последовательность лога упрощает порядок, но не отменяет необходимости форсировать сброс на устройство.

Мост к бэкенду: это и есть LSM-tree

Здесь начинается самое важное для собеса. Идея «пиши всё в лог, потом уплотняй» никуда не делась — она переехала в базы данных и называется LSM-tree (Log-Structured Merge tree, лог-структурированное дерево слияния). На ней построены RocksDB, Pebble (движок CockroachDB), LevelDB, Cassandra, ScyllaDB, движки ClickHouse. Если ты работаешь с любым из них — ты работаешь с идеями LFS.

Как устроена запись в LSM:

1. Запись сначала идёт в WAL (Write-Ahead Log, журнал упреждающей записи) — тот самый append-only лог на диске, чисто для надёжности (как journaling).
2. Одновременно запись попадает в memtable — сортированную структуру в оперативной памяти (обычно дерево). Это быстро, пишем в RAM.
3. Когда memtable наполнилась, её сбрасывают (flush) на диск одним последовательным куском — получается SSTable (Sorted String Table), неизменяемый отсортированный файл-сегмент.
4. SSTable'ов со временем накапливается много, в них копятся устаревшие версии ключей. Фоновая компакция (compaction) сливает несколько SSTable в новые, выкидывая мёртвые версии. Это тот же самый segment cleaning из LFS.

   LSM-TREE — путь записи:
 
       write(key,val)
            │
       ┌────▼─────┐   append    ┌──────────────────┐
       │ memtable │◄────────────│ WAL (на диске)   │  ← надёжность
       │  (в RAM, │             └──────────────────┘     при падении
       │сортиров.)│
       └────┬─────┘
            │ заполнилась → flush одним послед. куском
            ▼
   уровень L0:  [SSTable] [SSTable] [SSTable]   (отсортир., неизменяемые)
                     │ compaction (слияние + выброс мёртвых версий)
                     ▼
   уровень L1:  [ SSTable  крупнее, без дублей ]
                     │ compaction
                     ▼
   уровень L2:  [   ещё крупнее ...            ]

Что нарисовано: запись летит в RAM (memtable) и в WAL для страховки; наполнившись, memtable сбрасывается в отсортированный сегмент SSTable; фоновая компакция уплотняет сегменты по уровням, удаляя устаревшие версии ключей. Сравни с предыдущей схемой segment cleaning — это буквально та же механика, только над парами ключ-значение.

Соответствие один в один:

   LFS                         ⇄    LSM-tree
   ─────────────────────────────────────────────────────
   лог сегментов               ⇄    WAL + поток SSTable
   imap (номер→адрес)          ⇄    индексы/манифест SSTable
   segment cleaning            ⇄    compaction
   мёртвые старые версии блоков ⇄    устаревшие версии ключей
   последовательная запись      ⇄    flush memtable одним куском

Write-optimized vs read-optimized: LSM vs B-tree

Классическая альтернатива LSM — B-tree (сбалансированное дерево, на нём построены PostgreSQL, MySQL/InnoDB, многие индексы). B-tree обновляет данные на месте: нашёл нужную страницу-узел, переписал. Это та самая in-place модель, с которой мы начали главу.

Отсюда фундаментальный компромисс, который обожают на собесах:

• LSM = write-optimized. Запись дешёвая (последовательная, в память + лог), но чтение дороже: ключ может лежать в memtable или в любом из множества SSTable, приходится проверять несколько мест (спасают bloom-фильтры и индексы). Плюс read amplification и фоновая нагрузка от компакции.
• B-tree = read-optimized. Чтение дешёвое (спустился по дереву за O(log n) к одной странице), но запись дороже: случайные in-place обновления страниц, write amplification на уровне страниц.

   LSM (write-opt)                      B-TREE (read-opt)
   ───────────────                      ─────────────────
   write: → RAM + лог (послед.)  ДЁШЕВО write: in-place в страницу СЛУЧАЙНО
   read:  ищем в memtable + N     ДОРОЖЕ read:  спуск по дереву к 1   ДЁШЕВО
          SSTable (+bloom-фильтры)              странице

Что нарисовано: две зеркальные стратегии. LSM жертвует скоростью чтения ради дешёвой записи; B-tree — наоборот. Выбор движка под нагрузку — это выбор, чего у тебя больше: записей или чтений.

Что спрашивают на собесе

• В чём радикальная идея LFS? Никаких перезаписей на месте — всё пишется только дозаписью в конец одного растущего лога, что превращает любые записи в последовательные (быстрые и для HDD, и щадящие для SSD).
• Если inode постоянно переезжает в новое место лога, как его найти? Через imap (inode map): таблицу «номер inode → текущий адрес в логе». Её корень закреплён в фиксированной checkpoint region, саму imap обычно держат в памяти.
• Что такое segment cleaning и зачем он нужен? Сборка мусора: старые версии блоков накапливаются мёртвым грузом, поэтому живые блоки из дырявых сегментов переписывают плотно в новый сегмент, а освободившиеся возвращают под запись.
• Чем LFS отличается от журналируемой ФС? В journaling лог — временный буфер, данные потом ложатся на постоянные места (checkpoint). В LFS лог и есть само хранилище, постоянного «места» у блоков нет.
• Как LFS связана с LSM-tree? Это одна идея: WAL + memtable → flush в SSTable ↔ запись в лог; compaction ↔ segment cleaning; устаревшие версии ключей ↔ мёртвые блоки. RocksDB/Cassandra/LevelDB — прямые наследники LFS.
• LSM vs B-tree — когда что? LSM write-optimized (дешёвая последовательная запись, дороже чтение из-за множества SSTable) — под write-heavy нагрузки. B-tree read-optimized (in-place, быстрый спуск к одной странице) — под read-heavy.