Log-structured FS и мост к LSM-деревьям

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

Обычная файловая система обновляет данные на месте (in-place): у блока файла есть постоянный адрес на диске, и изменение перезаписывает именно его. Одно маленькое изменение при этом порождает записи в разные места: блок данных, inode, битмап (см. устройство ФС). Для жёсткого диска каждое такое место — отдельный seek.

В 1991 году Мендель Розенблюм и Джон Оустерхаут предложили log-structured file system (LFS): никогда ничего не перезаписывать. Любое изменение — данные, inode, служебные структуры — дописывается в конец одного растущего лога. Лог здесь в буквальном смысле: лента, куда записи добавляются только в хвост.

Аналогия — бухгалтерская книга, в которой ничего не стирают. Изменился остаток на счёте — внизу дописывается новая строка «счёт № 5: такая-то сумма». Актуальное значение — последняя строка про этот счёт.

   на месте (in-place):                    в лог (append-only):
 
   изменить блок B17 файла foo             изменить блок B17 файла foo
   ┌────┬───────┬────┐                     ┌──────┬─────┬────────────┐
   │ ...│ B17 → │... │                     │старое│ ... │ B17 новый ◄─ хвост
   └────┴───────┴────┘                     └──────┴─────┴────────────┘
   идём туда, где лежал B17                 пишем в конец, подряд
   → случайная запись                       → последовательная запись

Зачем это нужно

Авторы LFS исходили из двух наблюдений. Памяти становится всё больше, поэтому чтения всё чаще обслуживает кэш, и производительность определяется записью. А запись на HDD быстра только последовательная: случайная в сотни раз медленнее из-за seek и вращения.

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

На 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.

   поиск блока файла с номером inode N:
 
   [фиксированный адрес]    [в логе]          [в логе]        [в логе]
   checkpoint region  ───►  кусок imap  ───►  inode N  ───►  блок данных
                            (N → адрес)       (адреса блоков)

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

Мусор и его уборка

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

Поэтому LFS постоянно в фоне убирает мусор — это segment cleaning (очистка сегментов). Очиститель берёт несколько старых сегментов, определяет, какие блоки в них ещё живые, переписывает живые плотно в новый сегмент в хвосте лога, а старые сегменты помечает свободными.

   до (Ж — живой блок, 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 и изменения, которые успели лечь целиком. Писать «на места» не нужно, потому что постоянных мест нет: лог и есть данные.

   журналируемая ФС                     LFS
   ┌──────────┐   ┌──────────────┐      ┌────────────────────────────┐
   │ журнал   │──►│ основные места│      │ лог = вся файловая система │
   │ (по кругу)│   │ (постоянные)  │      │ (хвост растёт вправо ►)    │
   └──────────┘   └──────────────┘      └────────────────────────────┘
   журнал — страховка, данные           лог — единственное хранилище
   потом переносятся на места

Как и везде, долговечность конкретной записи даёт только сброс на носитель: запись в лог тоже сначала копится в памяти, и без fsync (см. fsync и durability) последние изменения пропадут при сбое питания.

Чистая LFS в мейнстрим не вышла: накладные расходы на уборку оказались слишком заметными для файловых систем общего назначения. Но её идеи живут. F2FS (flash-friendly file system), которую используют многие Android-устройства, — лог-структурированная файловая система для флеша. Copy-on-write ФС вроде ZFS и btrfs (см. журналирование) тоже никогда не пишут на место. А самое важное для бэкенда наследие — LSM-деревья.

Мини-модель на Go

Соберём игрушечное хранилище «ключ-значение» на этой идее: запись только в конец, индекс «ключ → позиция последней версии» (аналог imap) и уборка мусора.

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)
}

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.
2. Запись попадает в memtable — отсортированную структуру в памяти (обычно skip list или дерево).
3. Когда memtable вырастает до порога (десятки мегабайт), её целиком записывают на диск одним последовательным файлом — SSTable (sorted string table): неизменяемый файл, где пары «ключ-значение» отсортированы по ключу.
4. SSTable копятся, в них лежат устаревшие версии ключей и метки удаления. Фоновая компакция (compaction) сливает несколько SSTable в новые, выбрасывая мёртвые версии. Это segment cleaning из LFS, только над парами ключ-значение.

   write(key, val)
        │
        ├──► WAL на диске (последовательно, для восстановления)
        ▼
   ┌──────────┐
   │ memtable │  в памяти, отсортирована
   └────┬─────┘
        │ заполнилась → сброс одним последовательным файлом
        ▼
   L0:  [SSTable] [SSTable] [SSTable]     неизменяемые, отсортированные
        │ компакция: слияние, выброс мёртвых версий
        ▼
   L1:  [ SSTable побольше, без дублей ]
        │ компакция
        ▼
   L2:  [      ещё больше ...           ]

Соответствие с LFS:

Чтение в LSM дороже записи: ключ может лежать в memtable или в любом из SSTable, и проверять приходится несколько мест, от новых к старым. Чтобы не открывать каждый файл, у каждого SSTable есть фильтр Блума (Bloom filter) — компактная вероятностная структура, которая умеет отвечать «ключа здесь точно нет» или «ключ, возможно, есть». Ответ «точно нет» позволяет пропустить файл без чтения с диска.

LSM или B-дерево

Классическая альтернатива — B-дерево (B-tree): сбалансированное дерево страниц, которое обновляется на месте. На нём построены индексы PostgreSQL, InnoDB в MySQL, BoltDB/bbolt в Go. Это та самая модель «на месте», с которой начиналась глава.

Обе структуры переписывают данные больше одного раза. B-дерево меняет страницу целиком ради одной строки, LSM переписывает данные при каждой компакции, и суммарно один байт может быть записан на диск десятки раз. Какая из схем выигрывает, зависит от нагрузки, поэтому выбор движка начинается с вопроса: чего у вас больше, записей или чтений, и насколько важна задержка чтения.

Частые ошибки

• Думать, что лог-структурированная запись бесплатна: уборка мусора переписывает живые данные, и на заполненном диске это дорого.
• Удалять ключ в LSM-подобном хранилище только из индекса в памяти.
• Выбирать движок (LSM или B-дерево) без оценки соотношения записей и чтений.
• Считать, что лог отменяет fsync: последние изменения в памяти всё равно пропадут при сбое.

Проверьте себя

1. Зачем LFS нужна imap и где лежит точка входа в неё?
2. Как очиститель понимает, что блок в сегменте ещё живой?
3. Зачем у SSTable фильтр Блума?
4. Добавьте в LogKV из главы метод Delete(key). Почему недостаточно удалить ключ из index, если после перезапуска индекс будет восстанавливаться чтением лога, и что для этого делают LSM-движки?

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

• В чём идея LFS? Ничего не перезаписывать на месте; все изменения дописываются в конец лога крупными сегментами, поэтому любая запись последовательная.
• Как найти inode, если он всё время переезжает? Через imap («номер inode → адрес»), куски которой тоже в логе; точка входа — checkpoint region по фиксированному адресу. imap держат в памяти.
• Что такое segment cleaning? Сборка мусора: живые блоки из полупустых сегментов переписываются плотно, сегменты освобождаются. Чем полнее диск, тем дороже.
• Чем LFS отличается от журналируемой ФС? В журналируемой ФС журнал — временная страховка, данные живут на постоянных местах. В LFS лог и есть хранилище.
• Как LFS связана с LSM? Запись в конец, неизменяемые сегменты (SSTable), компакция = segment cleaning.
• Зачем в LSM фильтр Блума? Чтобы не читать SSTable, где ключа точно нет.
• LSM или B-дерево? LSM дешевле на запись и платит чтением и фоновой компакцией; B-дерево быстрее читает и пишет случайно на место.