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

В главе Файлы и каталоги мы смотрели на ФС снаружи: что видит программа через open, read, write, путь /home/u/a.txt. Сейчас залезем внутрь и соберём простую файловую систему своими руками. Будем называть её vsfs (very simple file system — очень простая ФС, учебная модель из OSTEP). Реальные ext4/XFS устроены сложнее, но идеи у них те же.

Главная мысль, которую надо усвоить раз и навсегда:

Файловая система — это просто структура данных, разложенная по блокам диска.

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

диск как массив блоков по 4 КБ:
 
 блок:  0     1     2     3     4     5    ...   N-1
      ┌────┬────┬────┬────┬────┬────┬─────┬────┐
      │    │    │    │    │    │    │ ... │    │
      └────┴────┴────┴────┴────┴────┴─────┴────┘
        4КБ  4КБ  4КБ  4КБ  4КБ  4КБ        4КБ

Что нарисовано: диск — линейный массив блоков. ФС берёт этот «голый» массив и наводит в нём порядок: договаривается, в каком блоке что лежит. Дальше — вся магия про то, как именно разложить.

Раскладка диска: кто где живёт

Возьмём маленький диск на 64 блока и разложим по нему нашу vsfs. Большую часть места отдадим под сами данные файлов — это область данных (data region). Но кроме данных нужно хранить служебную информацию: где какой файл, кто свободен, кто занят. Вот полная раскладка:

раскладка vsfs на 64 блока (S=суперблок, i=inode-bitmap,
d=data-bitmap, 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 D ...  D │
     └───┴───┴───┴───────────┴──────────────────────────┘
       │   │   │      │                    │
       │   │   │      │                    └─ область данных (блоки файлов
       │   │   │      │                       и каталогов)
       │   │   │      └─ inode-таблица: массив inode (по 256 байт каждый)
       │   │   └─ data bitmap: какие блоки данных свободны/заняты
       │   └─ inode bitmap: какие inode свободны/заняты
       └─ суперблок: метаданные всей ФС

Что нарисовано: пять областей подряд. Разберём каждую.

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

Битмапы (bitmap, блоки 1 и 2) — карты занятости. Битмап — это просто длинная строка из битов: 1 = занято, 0 = свободно. Один бит на один объект. inode bitmap отслеживает свободные/занятые inode, data bitmap — свободные/ занятые блоки данных. Когда создаём файл — ищем нулевой бит в inode-битмапе, ставим его в 1. Это как доска с ключами в гостинице: повёрнут крючок — номер занят.

inode-таблица (блоки 3–7) — массив структур inode. Это сердце ФС, разберём ниже.

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

inode: всё о файле, кроме имени

inode (index node, «индексный узел») — это структура, которая описывает один файл. Запомни ключевое: в inode НЕТ имени файла. Имя живёт в каталоге (об этом ниже). В inode лежит всё остальное:

• тип (обычный файл / каталог / симлинк);
• размер в байтах;
• права доступа (rwx) и владелец (uid/gid);
• времена (создания, изменения, доступа);
• счётчик ссылок (link count);
• и самое главное — указатели на блоки данных: где на диске лежит содержимое.

Каждый inode имеет номер (i-number). Зная номер, ОС вычисляет, в каком блоке таблицы он лежит, — это просто арифметика: адрес = начало_таблицы + i_number * размер_inode. Поэтому доступ к inode по номеру мгновенный.

inode (256 байт) — внутри:
 
 ┌──────────────────────────────────────┐
 │ тип: обычный файл                     │
 │ размер: 12000 байт                    │
 │ права: rw-r--r--   владелец: u=1000   │
 │ время изменения, доступа, ...         │
 │ link count: 1                         │
 │ ─────────────────────────────────────│
 │ указатели на блоки данных:            │
 │   ptr[0] -> блок 8                    │
 │   ptr[1] -> блок 14                   │
 │   ptr[2] -> блок 9                    │
 │   ...                                 │
 └──────────────────────────────────────┘

Что нарисовано: одна запись inode. Метаданные сверху, массив указателей на блоки данных снизу. Указатель — это номер блока на диске. Чтобы прочитать файл целиком, ОС идёт по указателям и читает соответствующие блоки данных.

Прямые и косвенные указатели: как адресовать большой файл

Вот ловушка. Указателей в inode мало — допустим, 12 прямых (direct) указателей. Прямой указатель ведёт прямо на блок данных. При блоке 4 КБ получаем максимум 12 × 4 КБ = 48 КБ. Для файла на 48 КБ — отлично. А для фильма на 2 ГБ?

Решение — косвенные указатели (indirect pointers). Идея: вместо того чтобы указатель вёл на данные, пусть он ведёт на блок, целиком набитый указателями.

• Одноуровневый косвенный (single indirect): указатель ведёт на блок, в котором лежат не данные, а ещё указатели на блоки данных. В блоке 4 КБ при указателе 4 байта помещается 1024 указателя → ещё 1024 × 4 КБ = 4 МБ.
• Двухуровневый (double indirect): указатель → блок указателей → блоки указателей → данные. 1024 × 1024 = ~1 млн блоков → ~4 ГБ.
• Трёхуровневый (triple indirect): ещё на уровень глубже → ~4 ТБ.

inode с прямыми и косвенными указателями:
 
 inode
 ┌──────────────┐
 │ direct[0]    │──────────────────────────────► [данные]
 │ direct[1]    │──────────────────────────────► [данные]
 │   ...        │
 │ direct[11]   │──────────────────────────────► [данные]
 │ single ind.  │──────► [блок указателей]──┬───► [данные]
 │              │        (1024 шт)          ├───► [данные]
 │              │                           └───► ... 1024
 │ double ind.  │──► [блок указ.]──┬─► [блок указ.]─► [данные]
 │              │                  └─► [блок указ.]─► [данные]
 │ triple ind.  │──► (ещё уровень) ...
 └──────────────┘

Что нарисовано: «несбалансированное дерево» указателей. Первые 12 указателей — прямые, ведут на данные сразу (быстро, для маленьких файлов). Дальше идут косвенные блоки, добавляющие уровни. Почему так? Потому что большинство файлов маленькие. Для них хватает прямых указателей — никаких лишних чтений. А большие файлы редки, и для них мы готовы заплатить лишним «прыжком» через косвенный блок.

Расчёт максимального размера файла

Это любимый вопрос на собесе. Считается сложением вместимостей каждого уровня. Пусть блок = 4 КБ = 4096 байт, указатель = 4 байта. Тогда в одном блоке помещается 4096 / 4 = 1024 указателя. Обозначим P = 1024.

Максимум = (12 + P + P² + P³) × размер_блока. Доминирует последний член — тройная косвенность даёт почти весь объём. Формулу разберём Go-задачей ниже.

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

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

блок данных каталога /home/u :
 
 ┌─────────────┬───────────────┐
 │ имя         │ номер inode   │
 ├─────────────┼───────────────┤
 │ "."         │     6   (сам каталог)
 │ ".."        │     2   (родитель)
 │ "a.txt"     │    13
 │ "report"    │    24
 └─────────────┴───────────────┘

Что нарисовано: содержимое каталога — список пар «имя, inode». Записи . и .. ссылаются на сам каталог и на родителя. Чтобы найти файл по имени, ОС читает блоки каталога и ищет совпадение имени, получая номер inode.

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

Теперь собираем всё вместе. Открытие файла по пути — это проход по пути (path traversal): ОС идёт от корня вниз, на каждом шаге читая inode и блок каталога. Номер inode корня / известен заранее (обычно 2) — это единственная «магическая константа», от которой всё пляшет.

open("/home/u/a.txt") — кто что читает:
 
 1. read inode #2        (корень /)            ◄── известен заранее
 2. read data блок /     найти "home" -> inode #6
 3. read inode #6        (каталог /home)
 4. read data блок /home найти "u"   -> inode #6? нет -> #11
 5. read inode #11       (каталог /home/u)
 6. read data блок /home/u  найти "a.txt" -> inode #13
 7. read inode #13       (файл a.txt) -> нашли! проверяем права
 8. возвращаем файловый дескриптор

Что нарисовано: чередование чтений «inode → блок каталога → inode → блок каталога ...» вниз по дереву. Заметь закономерность: на каждый компонент пути — минимум два чтения (inode каталога + его данные). Чем глубже путь, тем больше обращений к диску.

Вывод для собеса: глубокий путь /a/b/c/d/e/f.txt дороже плоского. Поэтому результаты прохода кешируются (dentry cache в Linux), а сами inode и блоки кешируются в page cache — иначе каждый open бил бы по диску десятки раз.

После того как inode найден, чтение содержимого (read) — это уже поход по указателям из inode на блоки данных (плюс при необходимости чтение косвенных блоков).

Локальность и FFS: класть рядом то, что используется вместе

В нашей наивной vsfs inode лежат все вместе (блоки 3–7), а данные — далеко (блоки 8+). Проблема: чтобы прочитать файл, головка HDD прыгает от inode-таблицы к данным и обратно — это дорогие перемещения головки (seek).

FFS (Fast File System) предложил лечение — группы цилиндров (cylinder groups, в современных терминах block groups). Диск делится на группы, и в каждой группе своя мини-раскладка: свои inode, свои битмапы, свои данные. Правило: inode файла и его блоки данных кладём в одну группу, а файлы одного каталога — тоже рядом. Так связанные вещи лежат близко, и головке не надо летать через весь диск.

FFS: вместо одной кучи inode -> много локальных групп:
 
 ┌── группа 0 ──┬── группа 1 ──┬── группа 2 ──┬─ ... ─┐
 │ [bm][I][DDD] │ [bm][I][DDD] │ [bm][I][DDD] │       │
 └──────────────┴──────────────┴──────────────┴───────┘
   inode и его данные — в одной группе => seek короткий

Что нарисовано: диск разбит на группы, каждая самодостаточна (битмапы, inode, данные). Принцип «локальности»: держи связанное рядом. На SSD seek почти бесплатен, но идея локальности всё равно полезна — крупные последовательные чтения эффективнее.

Связь с журналированием

Заметь: одна операция (создать файл) трогает несколько структур: inode bitmap, inode, data bitmap, блок каталога. Если питание пропадёт посреди этих записей — ФС останется в противоречивом состоянии (бит занятости стоит, а inode пустой). Как это лечат — отдельная большая тема в главе Журналирование (journaling): прежде чем менять структуры, ФС записывает в журнал «намерение», и после сбоя может доиграть или откатить. А почему запись вообще может «пропасть» и зачем нужен fsync — в главе fsync и долговечность.

Go-задача: посчитать максимальный размер файла

Посчитаем максимальный размер файла для нашей схемы: 12 прямых указателей, по одному single/double/triple indirect. Параметры — размер блока и размер указателя.

package main
 
import "fmt"
 
func maxFileSize(blockSize, ptrSize int64) int64 {
	// сколько указателей помещается в один блок
	P := blockSize / ptrSize
 
	const directPtrs = 12
 
	blocks := int64(0)
	blocks += directPtrs        // прямые
	blocks += P                 // single indirect:  P блоков
	blocks += P * P             // double indirect:  P^2 блоков
	blocks += P * P * P         // triple indirect:  P^3 блоков
 
	return blocks * blockSize
}
 
func main() {
	// блок 4 КБ, указатель 4 байта => P = 1024
	size := maxFileSize(4096, 4)
	fmt.Printf("max ~= %d байт ~= %.2f ТБ\n",
		size, float64(size)/(1<<40))
	// max ~= 4402345721856 байт ~= 4.00 ТБ
}

Логика: переводим «сколько указателей в блоке» (P), складываем вместимости уровней в блоках, умножаем на размер блока. Видно, что P*P*P доминирует — тройная косвенность даёт почти весь объём, а прямые указатели нужны лишь для скорости на мелких файлах. Поменяй blockSize на 8192 — и max вырастет кубически, ведь P входит в третьей степени.

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

• Что хранится в inode, а что — нет? В inode — метаданные и указатели на блоки; имени файла там НЕТ, имя живёт в каталоге как пара (имя → i-number).
• Зачем прямые и косвенные указатели одновременно? Прямые — быстрый доступ к маленьким файлам без лишних чтений (а их большинство); косвенные (1/2/3 уровня) дают огромный максимальный размер ценой дополнительных «прыжков».
• Посчитай максимальный размер файла при заданных размере блока и указателя: (12 + P + P² + P³) × блок, где P = блок / указатель. Умей вывести формулу.
• Сколько обращений к диску на open("/a/b/c")? Примерно по два на компонент пути (inode каталога + его данные); поэтому глубокие пути дороже и спасает кеш (dentry/page cache).
• Что такое FFS и группы цилиндров? Раскладка с локальностью: inode и данные файла — в одной группе, файлы каталога — рядом, чтобы сократить seek на HDD.
• Почему создание файла — не атомарная операция? Меняются несколько структур (битмапы, inode, каталог); сбой посреди ведёт к несогласованности — отсюда нужда в журналировании.