Как устроена файловая система (vsfs)

Файловая система — структура данных на диске

В прошлой главе мы смотрели на файлы снаружи: open, read, inode, каталоги, дескрипторы. Теперь заглянем внутрь и соберём простую файловую систему. Назовём её vsfs (very simple file system) — это учебная модель из OSTEP. Настоящие ext4 и XFS сложнее, но держатся на тех же идеях, а где они отличаются, скажем отдельно.

Диск для файловой системы — это массив пронумерованных блоков одинакового размера, обычно 4 КБ. Прочитать или записать можно только блок целиком.

   блок:   0     1     2     3     4    ...   N-1
         ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
         │     │     │     │     │     │ ... │     │   по 4 КБ
         └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

Файловая система договаривается, что в каком блоке лежит, и поддерживает этот порядок при каждой операции. По сути это структура данных, только живёт она не в памяти, а на диске, и должна пережить выключение питания.

Раскладка диска

Возьмём крошечный диск на 64 блока. Большую часть отдадим под содержимое файлов — это область данных. Остальное — служебные структуры.

   S — суперблок, i — битмап inode, d — битмап данных,
   I — таблица inode, D — данные
 
   блок:  0    1    2    3 ... 7       8 ................. 63
        ┌────┬────┬────┬───────────┬───────────────────────┐
        │ S  │ i  │ d  │ I I I I I │ D D D D D ... D D D D │
        └────┴────┴────┴───────────┴───────────────────────┘

Суперблок (superblock, блок 0) описывает всю файловую систему: сколько в ней inode и блоков данных, где начинается таблица inode, где область данных, и «магическое число», по которому ядро ОС узнаёт тип ФС. При монтировании ядро первым делом читает суперблок.

Битмапы (bitmap, блоки 1 и 2) — карты занятости: один бит на объект, 1 — занят, 0 — свободен. Битмап inode отмечает занятые inode, битмап данных — занятые блоки данных. Создаём файл — ищем нулевой бит в битмапе inode и ставим его в 1.

Таблица inode (блоки 3–7) — массив структур inode. При размере inode 256 байт в блок помещается 16 штук, в пять блоков — 80. Значит, в нашей ФС может быть не больше 80 файлов и каталогов, даже если место под данные ещё есть. Это реальное ограничение: на ext4 число inode задаётся при создании ФС, и сервер, хранящий миллионы мелких файлов (кэш, очередь писем), может получить ошибку No space left on device при свободных гигабайтах. Проверяется командой df -i.

Область данных (блоки 8–63) — содержимое файлов и каталогов.

Inode

Inode описывает один файл. В нём:

• тип (обычный файл, каталог, symlink);
• размер в байтах;
• владелец (uid, gid) и права;
• времена: последнего доступа (atime), изменения содержимого (mtime), изменения метаданных (ctime);
• число ссылок (сколько имён указывают на inode);
• указатели на блоки данных.

Имени в inode нет — оно в каталоге (см. прошлую главу).

Найти inode по номеру — простая арифметика. Inode номер 20 при 16 inode на блок лежит в блоке 3 + 20 / 16 = 4 со смещением (20 % 16) × 256 = 1024 байта. Ничего искать не надо, поэтому доступ по номеру мгновенный.

   inode (256 байт)
   ┌──────────────────────────────────┐
   │ тип: обычный файл                │
   │ размер: 12 000 байт              │
   │ uid 1000, права rw-r--r--        │
   │ atime, mtime, ctime              │
   │ число ссылок: 1                  │
   │ указатели на блоки:              │
   │   [0] → блок 8                   │
   │   [1] → блок 14                  │
   │   [2] → блок 9                   │
   │   [3..] пусто                    │
   └──────────────────────────────────┘

Файл на 12 000 байт занимает три блока по 4 КБ (последний заполнен частично). Блоки не обязаны идти подряд: 8, 14, 9.

Прямые и косвенные указатели

Сколько указателей поместить в inode? Пусть 12. Каждый прямой указатель (direct pointer) — номер блока данных. При блоке 4 КБ это 12 × 4 КБ = 48 КБ. Для конфига хватит, для лога на гигабайт — нет.

Решение — косвенный указатель (indirect pointer): он указывает не на данные, а на блок, целиком заполненный номерами блоков. При номере блока в 4 байта в блок 4 КБ помещается 4096 / 4 = 1024 номера.

• Одинарный косвенный (single indirect): inode → блок указателей → 1024 блока данных. Ещё 4 МБ.
• Двойной (double indirect): inode → блок указателей → 1024 блока указателей → по 1024 блока данных. 1024² блоков, 4 ГБ.
• Тройной (triple indirect): ещё один уровень, 1024³ блоков, 4 ТБ.

   inode
   ┌──────────────┐
   │ direct[0]    │──────────────────────────────────► [данные]
   │   ...        │
   │ direct[11]   │──────────────────────────────────► [данные]
   │ single       │──► [1024 указателя] ─────────────► [данные] × 1024
   │ double       │──► [1024 указателя] ─► [1024 ук.] ► [данные] × 1024²
   │ triple       │──► ещё один уровень               ► [данные] × 1024³
   └──────────────┘

Получается несбалансированное дерево. Почему так, а не сразу дерево одной глубины? Потому что большинство файлов маленькие: исследования реальных систем раз за разом показывают, что типичный файл — единицы килобайт. Маленькому файлу хватает прямых указателей, и чтение не тратит лишних обращений к диску. Большому файлу придётся прочитать один-два-три блока указателей — но больших файлов мало, и для них это небольшая доля от объёма чтения.

Максимальный размер файла

Любимая задачка на собеседовании. Блок 4096 байт, указатель 4 байта, 12 прямых указателей и по одному косвенному каждого уровня. P = 4096 / 4 = 1024.

   максимум = (12 + P + P² + P³) × размер блока

Посчитаем, сколько даёт каждый уровень:

package main
 
import "fmt"
 
func main() {
	const (
		blockSize = 4096 // байт
		ptrSize   = 4    // байт на номер блока
		direct    = 12
	)
	p := blockSize / ptrSize // указателей в одном косвенном блоке
 
	levels := []struct {
		name   string
		blocks int
	}{
		{"12 прямых", direct},
		{"single indirect", p},
		{"double indirect", p * p},
		{"triple indirect", p * p * p},
	}
 
	total := 0
	for _, l := range levels {
		total += l.blocks
	}
	for _, l := range levels {
		bytes := l.blocks * blockSize
		fmt.Printf("%-16s %13d блоков  %16d байт  %9.5f%%\n",
			l.name, l.blocks, bytes, 100*float64(l.blocks)/float64(total))
	}
	fmt.Printf("максимум: %d байт ≈ %.3f ТиБ\n",
		total*blockSize, float64(total*blockSize)/(1<<40))
}

12 прямых                   12 блоков             49152 байт    0.00000%
single indirect           1024 блоков           4194304 байт    0.00010%
double indirect        1048576 блоков        4294967296 байт    0.09756%
triple indirect     1073741824 блоков     4398046511104 байт   99.90234%
максимум: 4402345721856 байт ≈ 4.004 ТиБ

Тройная косвенность даёт 99,9% максимального размера, прямые указатели — ничтожную долю. Но именно прямые указатели обслуживают почти все реальные файлы. Если удвоить блок до 8 КБ, P станет 2048, и максимум вырастет примерно в 16 раз: P входит в третьей степени, плюс сам блок вдвое больше.

Это теоретический предел структуры указателей. У реальных файловых систем бывают и другие ограничения: например, ext3 с блоком 4 КБ не позволяет файл больше 2 ТиБ из-за разрядности счётчика блоков в inode. Обобщённую функцию для любых параметров вы напишете в задаче «Максимальный размер файла по inode».

Как это сделано в ext4 и XFS: экстенты

Указатель на каждый блок — расточительная схема для больших файлов. Файл на 1 ГБ занимает 262 144 блока, значит, нужно хранить 262 144 номера, то есть около 1 МБ указателей, и при чтении проходить по косвенным блокам.

Современные ФС описывают файл экстентами (extent): «начиная с логического блока L, лежат B блоков подряд, с физического блока P». Если файл записан на диск одним непрерывным куском, его описывает один экстент. В ext4 один экстент покрывает до 32 768 блоков (128 МБ при блоке 4 КБ), в самом inode помещаются четыре экстента, а при большем числе они складываются в небольшое дерево. XFS устроена похоже, только деревья там B+-деревья.

   блок-указатели:  [1000][1001][1002]...[1255]   256 чисел
   экстент:         (логический 0, физический 1000, длина 256)   одна запись

Посмотреть экстенты файла можно командой filefrag -v файл (Linux). Файл, который дописывали понемногу много месяцев на заполненный диск, состоит из сотен экстентов — это и есть фрагментация.

Каталог — тоже файл

У каталога тоже есть inode (с типом «каталог»), а в его блоках данных лежат записи «имя → номер inode».

   данные каталога /home/u (inode 11):
 
   имя         номер inode
   ─────────────────────────
   .           11      (сам каталог)
   ..          6       (родитель, /home)
   a.txt       13
   report      24

В vsfs записи хранятся простым списком, и поиск имени — линейный просмотр. В каталоге на сто тысяч файлов это медленно, поэтому ext4 строит для больших каталогов хеш-индекс (htree), а XFS — B+-деревья.

Что происходит при open("/home/u/a.txt")

Номер inode корня известен заранее (в ext4 это 2), с него и начинается разрешение пути. Пусть home — это inode 6, u — inode 11, a.txt — inode 13.

   open("/home/u/a.txt"), без кэша:
 
   1. прочитать inode 2         (корень)          ← номер известен заранее
   2. прочитать данные корня    найти "home" → 6
   3. прочитать inode 6         (/home)
   4. прочитать данные /home    найти "u" → 11
   5. прочитать inode 11        (/home/u)
   6. прочитать данные /home/u  найти "a.txt" → 13
   7. прочитать inode 13        проверить права, вернуть дескриптор

На каждый компонент пути — минимум два чтения: inode каталога и его данные. Плюс в больших каталогах данные занимают несколько блоков. На холодном HDD открыть файл в пятом уровне вложенности — это десяток seek по ~10 мс. Поэтому ядро кэширует результаты разрешения путей (dentry cache), а сами блоки inode и каталогов — в page cache, и на тёплой системе open вообще не трогает диск.

Чтение данных после open — это поход по указателям (или экстентам) из inode. У обычного read есть и неочевидная запись: обновить время доступа atime в inode. Если делать это при каждом чтении, каждое чтение порождает запись. Поэтому Linux по умолчанию монтирует ФС с опцией relatime (atime обновляется, только если он старше mtime или прошли сутки), а для серверов с большим числом чтений часто ставят noatime.

Создание файла дороже. Нужно найти свободный inode (прочитать и записать битмап inode), записать новый inode, добавить запись в каталог (прочитать и записать блок данных каталога), обновить inode каталога (mtime, размер). А при первой записи данных — ещё битмап данных, блок данных и снова inode файла. Одна операция «создать и записать» — около десятка обращений к разным местам диска.

Локальность: FFS и группы блоков

В нашей vsfs все inode лежат в начале диска, а данные — дальше. На HDD чтение файла заставляет головку прыгать между таблицей inode и данными, а файлы одного каталога разбросаны как попало. Каждый прыжок — seek.

FFS (Fast File System, BSD, 1984) предложила делить диск на группы цилиндров (cylinder groups); в ext4 они называются группами блоков (block groups). У каждой группы свои битмапы, своя часть таблицы inode и свои блоки данных.

   ┌── группа 0 ───────┬── группа 1 ───────┬── группа 2 ───────┐
   │ битмапы│ I │ DDDD │ битмапы│ I │ DDDD │ битмапы│ I │ DDDD │
   └───────────────────┴───────────────────┴───────────────────┘

Правила размещения:

• блоки файла кладутся в ту же группу, что и его inode;
• файлы одного каталога кладутся в группу этого каталога;
• новые каталоги, наоборот, разносятся по разным группам, чтобы группы заполнялись равномерно.

Так то, что используется вместе, лежит рядом, и seek получаются короткими. На SSD позиционирования нет, но локальность всё равно полезна: крупные последовательные операции эффективнее мелких разрозненных и для флеша (см. SSD).

Одна операция — много записей

Создание файла меняет битмап inode, сам inode, блок каталога и inode каталога — четыре разных места на диске. Если питание пропадёт посередине, на диске окажется несогласованное состояние: например, бит в битмапе занят, а inode пустой. Как файловые системы с этим справляются, разбираем в главе про журналирование. А почему данные вообще могут не дойти до диска, хотя write вернул успех, — в главе fsync и durability.

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

• Считать, что df показывает всё: можно упереться в число inode (df -i) при свободных гигабайтах.
• Представлять, что ext4 хранит указатель на каждый блок файла. Современные ФС используют экстенты.
• Забывать, что чтение может порождать запись (atime), и не знать про relatime/noatime.
• Считать путь к файлу бесплатным: без кэша каждый компонент — минимум два чтения с диска.
• Думать, что создание файла — одна запись на диск.

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

1. Как ФС находит inode по номеру без поиска?
2. Почему в inode держат прямые указатели, если косвенные дают почти весь максимальный размер?
3. Что такое экстент и почему он выгоднее блок-указателей для больших файлов?
4. В vsfs из главы (блок 4 КБ, inode 256 байт, 12 прямых указателей) нужно прочитать байт со смещением 100 000 в файле /var/log/app.log. Перечислите все чтения с холодного диска от open до получения байта. Какой указатель inode понадобится?

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

• Что хранится в inode? Тип, размер, владелец, права, времена, число ссылок, указатели на данные (или экстенты). Имени нет.
• Зачем прямые и косвенные указатели одновременно? Прямые дают быстрый доступ к маленьким файлам, которых большинство. Косвенные позволяют огромные файлы ценой дополнительных чтений.
• Посчитайте максимальный размер файла. (12 + P + P² + P³) × блок, где P = блок / указатель. Для 4 КБ и 4 байт — около 4 ТиБ.
• Что такое экстенты? Описание файла кусками «начало + длина». Короче метаданные, быстрее чтение больших файлов. Используются в ext4 и XFS.
• Сколько обращений к диску на open("/a/b/c") без кэша? Около двух на компонент пути. Спасают dentry cache и page cache.
• Что такое FFS и группы блоков? Деление диска на группы со своими битмапами и inode, чтобы связанные данные лежали рядом.
• No space left on device, а df показывает свободное место. Почему? Кончились inode (df -i), обычно из-за миллионов мелких файлов.
• Почему создание файла не атомарно? Меняются несколько структур в разных местах диска; сбой посередине ломает согласованность.