--- title: "Как устроена файловая система (vsfs)" description: "В прошлой главе мы смотрели на файлы снаружи: open, read, inode, каталоги, дескрипторы. Теперь заглянем внутрь и соберём простую файловую систему. Назовём её vsfs (very simple…" canonical: https://graphlms.ru/os/book/fs-implementation course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Как устроена файловая система (vsfs) > Источник: https://graphlms.ru/os/book/fs-implementation — курс «Операционные системы», GraphLMS. ## Файловая система — структура данных на диске В [прошлой главе](/os/book/files-directories) мы смотрели на файлы снаружи: `open`, `read`, inode, каталоги, дескрипторы. Теперь заглянем внутрь и соберём простую файловую систему. Назовём её **vsfs** (very simple file system) — это учебная модель из OSTEP. Настоящие ext4 и XFS сложнее, но держатся на тех же идеях, а где они отличаются, скажем отдельно. Диск для файловой системы — это массив пронумерованных **блоков** одинакового размера, обычно 4 КБ. Прочитать или записать можно только блок целиком. ```text блок: 0 1 2 3 4 ... N-1 ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │ │ │ │ │ ... │ │ по 4 КБ └─────┴─────┴─────┴─────┴─────┴─────┴─────┘ ``` Файловая система договаривается, что в каком блоке лежит, и поддерживает этот порядок при каждой операции. По сути это структура данных, только живёт она не в памяти, а на диске, и должна пережить выключение питания. ## Раскладка диска Возьмём крошечный диск на 64 блока. Большую часть отдадим под содержимое файлов — это **область данных**. Остальное — служебные структуры. ```text 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 нет — оно в каталоге (см. [прошлую главу](/os/book/files-directories)). Найти inode по номеру — простая арифметика. Inode номер 20 при 16 inode на блок лежит в блоке `3 + 20 / 16 = 4` со смещением `(20 % 16) × 256 = 1024` байта. Ничего искать не надо, поэтому доступ по номеру мгновенный. ```text 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 ТБ. ```text inode ┌──────────────┐ │ direct[0] │──────────────────────────────────► [данные] │ ... │ │ direct[11] │──────────────────────────────────► [данные] │ single │──► [1024 указателя] ─────────────► [данные] × 1024 │ double │──► [1024 указателя] ─► [1024 ук.] ► [данные] × 1024² │ triple │──► ещё один уровень ► [данные] × 1024³ └──────────────┘ ``` Получается несбалансированное дерево. Почему так, а не сразу дерево одной глубины? Потому что большинство файлов маленькие: исследования реальных систем раз за разом показывают, что типичный файл — единицы килобайт. Маленькому файлу хватает прямых указателей, и чтение не тратит лишних обращений к диску. Большому файлу придётся прочитать один-два-три блока указателей — но больших файлов мало, и для них это небольшая доля от объёма чтения. ### Максимальный размер файла Любимая задачка на собеседовании. Блок 4096 байт, указатель 4 байта, 12 прямых указателей и по одному косвенному каждого уровня. P = 4096 / 4 = 1024. ```text максимум = (12 + P + P² + P³) × размер блока ``` Посчитаем, сколько даёт каждый уровень: ```go play 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)) } ``` ```text 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»](/os/tasks/inode-maxsize). ### Как это сделано в ext4 и XFS: экстенты Указатель на каждый блок — расточительная схема для больших файлов. Файл на 1 ГБ занимает 262 144 блока, значит, нужно хранить 262 144 номера, то есть около 1 МБ указателей, и при чтении проходить по косвенным блокам. Современные ФС описывают файл **экстентами** (extent): «начиная с логического блока L, лежат B блоков подряд, с физического блока P». Если файл записан на диск одним непрерывным куском, его описывает один экстент. В ext4 один экстент покрывает до 32 768 блоков (128 МБ при блоке 4 КБ), в самом inode помещаются четыре экстента, а при большем числе они складываются в небольшое дерево. XFS устроена похоже, только деревья там B+-деревья. ```text блок-указатели: [1000][1001][1002]...[1255] 256 чисел экстент: (логический 0, физический 1000, длина 256) одна запись ``` Посмотреть экстенты файла можно командой `filefrag -v файл` (Linux). Файл, который дописывали понемногу много месяцев на заполненный диск, состоит из сотен экстентов — это и есть **фрагментация**. ## Каталог — тоже файл У каталога тоже есть inode (с типом «каталог»), а в его блоках данных лежат записи «имя → номер inode». ```text данные каталога /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. ```text 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](/os/book/hdd). **FFS** (Fast File System, BSD, 1984) предложила делить диск на **группы цилиндров** (cylinder groups); в ext4 они называются **группами блоков** (block groups). У каждой группы свои битмапы, своя часть таблицы inode и свои блоки данных. ```text ┌── группа 0 ───────┬── группа 1 ───────┬── группа 2 ───────┐ │ битмапы│ I │ DDDD │ битмапы│ I │ DDDD │ битмапы│ I │ DDDD │ └───────────────────┴───────────────────┴───────────────────┘ ``` Правила размещения: - блоки файла кладутся в ту же группу, что и его inode; - файлы одного каталога кладутся в группу этого каталога; - новые каталоги, наоборот, разносятся по разным группам, чтобы группы заполнялись равномерно. Так то, что используется вместе, лежит рядом, и seek получаются короткими. На SSD позиционирования нет, но локальность всё равно полезна: крупные последовательные операции эффективнее мелких разрозненных и для флеша (см. [SSD](/os/book/ssd)). ## Одна операция — много записей Создание файла меняет битмап inode, сам inode, блок каталога и inode каталога — четыре разных места на диске. Если питание пропадёт посередине, на диске окажется несогласованное состояние: например, бит в битмапе занят, а inode пустой. Как файловые системы с этим справляются, разбираем в главе про [журналирование](/os/book/journaling). А почему данные вообще могут не дойти до диска, хотя `write` вернул успех, — в главе [fsync и durability](/os/book/fsync-durability). > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/fs-implementation ## Частые ошибки - Считать, что `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 понадобится? Ответы. (1) Вычисляет адрес: начало таблицы + номер × размер inode. (2) Большинство файлов маленькие, и прямые указатели позволяют читать их без лишних обращений к блокам указателей. (3) Одна запись «начало + длина» описывает много блоков подряд: метаданных меньше, чтение большого файла проще. (4) inode корня, данные корня, inode `var`, данные `var`, inode `log`, данные `log`, inode `app.log`, блок single indirect, блок данных — девять чтений. 100 000 / 4096 ≈ 24,4, то есть блок с индексом 24: прямых указателей 12, значит, нужен одинарный косвенный. ## Что спрашивают на собесе - **Что хранится в 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`), обычно из-за миллионов мелких файлов. - **Почему создание файла не атомарно?** Меняются несколько структур в разных местах диска; сбой посередине ломает согласованность. ## Вопросы для самопроверки **Квиз «Устройство ФС (vsfs)»** 1. Где хранится ИМЯ файла в vsfs? - В суперблоке - В data bitmap - В inode файла - В блоке данных каталога, как пара (имя → номер inode) (верно) - Пояснение: inode хранит метаданные и указатели на блоки, но НЕ имя. Имя живёт в каталоге как запись (имя → i-number). Поэтому один inode может иметь несколько имён (hard links). 2. Зачем в inode держат и прямые, и косвенные указатели? - Прямые нужны только для каталогов - Прямые — для скорости на мелких файлах (их большинство), косвенные — для большого максимального размера (верно) - Косвенные быстрее прямых - Это историческая ошибка, сейчас не используется - Пояснение: Большинство файлов маленькие — им хватает прямых указателей без лишних чтений. Косвенные (1/2/3 уровня) дают огромный max размер ценой дополнительных обращений, и нужны редко. 3. Блок = 4096 байт, указатель = 4 байта. Сколько указателей помещается в один косвенный блок (P)? - Ответ: 1024 - Пояснение: P = размер_блока / размер_указателя = 4096 / 4 = 1024 указателя в одном блоке. 4. Сколько примерно обращений к диску нужно, чтобы пройти путь /home/u/a.txt (без кеша)? - Ровно три, по числу слэшей - Ноль, путь резолвится в суперблоке - Одно — сразу читаем файл - Примерно по два на компонент пути: inode каталога + его блок данных (верно) - Пояснение: Проход по пути чередует чтения inode и блока каталога на каждом уровне. Грубо — два чтения на компонент. Поэтому глубокие пути дороже, и их спасает dentry/page cache. 5. Что верно про FFS и группы цилиндров? (выберите все) - Файлы одного каталога размещают рядом (верно) - inode файла и его блоки данных стараются класть в одну группу (верно) - Каждая группа полностью игнорирует битмапы - Цель — сократить перемещения головки (seek) на HDD (верно) - Пояснение: FFS вводит локальность: связанное лежит рядом (inode+данные в одной группе, файлы каталога близко), что сокращает seek. У каждой группы свои битмапы, а не игнорирование. 6. Почему создание файла не атомарно и требует журналирования? - Меняется сразу несколько структур (битмапы, inode, блок каталога); сбой посреди оставит ФС в несогласованном состоянии (верно) - Потому что inode слишком большой - Атомарность обеспечивает суперблок автоматически - Потому что диск медленный - Пояснение: Одна логическая операция трогает inode bitmap, inode, data bitmap и блок каталога. Сбой между записями ломает согласованность. Журналирование сначала пишет намерение, чтобы после сбоя доиграть/откатить.