Как ext4 организует блоки на диске и почему деревья экстентов изменили подход к хранению файлов

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

ext4 - четвёртая итерация расширенной файловой системы Linux, ставшая стандартом для большинства дистрибутивов. Корни её уходят к ext2 начала 1990-х, но внутреннее устройство было принципиально переработано. Ключевое нововведение, изменившее подход к хранению данных - это extent trees, деревья экстентов, пришедшие на смену устаревшей схеме косвенных блоков.

Косвенные блоки ext2 и почему этот подход не масштабировался

Чтобы оценить деревья экстентов, нужно понять, от чего они спасли. В ext2 и ext3 каждый файл описывался через структуру inode с 15 указателями на блоки данных. Первые 12 указателей были прямыми - они указывали непосредственно на блоки данных. При размере блока 4 КБ это давало прямой доступ к первым 48 КБ файла.

Для файлов больше 48 КБ использовались косвенные блоки. Тринадцатый указатель указывал на блок, содержащий 1024 указателя на блоки данных - один уровень косвенности. Четырнадцатый указатель вводил два уровня косвенности: указатель на блок указателей на блоки данных. Пятнадцатый - три уровня.

Проблема этой схемы становилась очевидной при работе с большими файлами. Видеофайл размером 1 ГБ требовал 262 144 записей в таблицах косвенных блоков - по одной на каждые 4 КБ. Удаление такого файла означало обход всей этой структуры и освобождение каждой записи отдельно. На практике удаление больших файлов в ext3 могло занимать десятки секунд, а операция fsck на большом томе превращалась в часовое ожидание. В ext4 старая схема косвенного отображения блоков была заменена деревом экстентов. Выделение непрерывного диапазона из 1000 блоков при старой схеме требовало косвенного блока для хранения всех 1000 записей - в дереве экстентов то же самое отображается единственной структурой ext4_extent с полем ee_len=1000.

Структура экстента и как четыре записи умещаются прямо в inode

Экстент - это диапазон последовательных физических блоков. Один экстент в ext4 способен отображать до 128 МБ непрерывного пространства при размере блока 4 КБ. Вместо хранения адреса каждого блока по отдельности экстент описывает начальный физический блок и длину непрерывного диапазона. Это принципиальное изменение: вместо O(N) записей для N последовательных блоков - одна запись.

Каждый экстент в ext4 - это структура ext4_extent размером 12 байт:

• ee_block (4 байта) - номер первого логического блока в файле
• ee_len (2 байта) - длина экстента в блоках
• ee_start_hi (2 байта) - старшие биты физического адреса
• ee_start_lo (4 байта) - младшие биты физического адреса

В особом случае нулевой глубины дерева экстентов поле i_block inode непосредственно содержит структуры ext4_extent. Поле i_block имеет размер 60 байт, что позволяет хранить четыре экстента и заголовок ext4_extent_header - при выделении пятого экстента глубина дерева увеличивается для размещения нового экстента.

Это означает, что большинство реальных файлов - небольшие документы, конфигурационные файлы, исходный код - полностью описываются прямо в inode без единого обращения к дополнительным метаданным.

# Посмотреть дерево экстентов конкретного файла
debugfs -R "extents /path/to/file" /dev/sda1

# Альтернативный способ через debugfs
debugfs /dev/sda1
debugfs: ex /path/to/file

# Информация об инодах и их экстентах
debugfs -R "dump_extents /path/to/file" /dev/sda1

Дерево экстентов и как оно растёт с размером файла

Когда файлу требуется больше четырёх экстентов, дерево растёт вглубь. Если узел является внутренним узлом с глубиной больше нуля, за заголовком следуют структуры ext4_extent_idx, каждая из которых указывает на блок с новыми узлами дерева. Если узел листовой с глубиной равной нулю - за заголовком следуют структуры ext4_extent, указывающие непосредственно на блоки данных файла.

Каждый блок индексного узла дерева вмещает до 340 экстентов. Это вычисляется следующим образом: блок имеет размер 4 КБ, первые 12 байт занимает заголовок, последние 4 байта - контрольная сумма, оставшиеся 4080 байт делятся на 12 байт размера каждого экстента. Двухуровневое дерево способно описать 340 × 340 = 115 600 экстентов. Трёхуровневое - больше 39 миллионов. На практике даже очень фрагментированные файлы редко требуют глубины дерева больше двух.

# Статистика фрагментации файловой системы
e2fsck -fn /dev/sda1 2>&1 | grep fragmented

# Фрагментация конкретного файла
filefrag -v /path/to/large/file

# Общая статистика экстентов через tune2fs
tune2fs -l /dev/sda1 | grep -i extent

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

Delayed allocation и multiblock allocator как союзники экстентов

Деревья экстентов решают проблему хранения метаданных о блоках. Но для того чтобы файлы действительно сохранялись компактно, нужен умный алгоритм выделения самих блоков. ext4 использует технику allocate-on-flush, известную как отложенное выделение блоков: ext4 откладывает выделение блоков до сброса данных на диск, тогда как некоторые файловые системы выделяют блоки немедленно, даже когда данные остаются в кэше записи. Отложенное выделение улучшает производительность и снижает фрагментацию, эффективно выделяя большие объёмы данных за один раз.

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

ext4 использует многоблочный аллокатор mballoc, выделяющий множество блоков за один вызов вместо одного блока за вызов, что устраняет значительные накладные расходы. Это особенно важно при совместной работе с отложенным выделением: к моменту реальной записи на диск аллокатор знает полный объём данных и принимает оптимальное решение о размещении.

# Проверить что файловая система использует extent trees
tune2fs -l /dev/sda1 | grep "Filesystem features" | grep extent

# Создать файловую систему ext4 с явным включением extent trees
mkfs.ext4 -O extent /dev/sdb1

# Смонтировать с отключённым delayed allocation (для тестирования)
mount -o nodelalloc /dev/sdb1 /mnt/test

Flex block groups и как ext4 организует метаданные на большом томе

Диск разделён на группы блоков, каждая из которых является самодостаточной единицей с собственной таблицей инодов, блоками данных и битовыми картами для отслеживания свободного пространства. Традиционно каждая группа блоков хранила собственные метаданные рядом с данными - это ограничивало максимальный размер группы и создавало накладные расходы при операциях с маленькими файлами.

Функция flex_bg в ext4 объединяет несколько групп блоков в один гибкий суперблок. Таблицы инодов и битовые карты всех групп, входящих в flex_bg, собираются в начале первой группы. Это концентрирует метаданные в одном месте и позволяет выделять очень большие непрерывные экстенты для данных - вплоть до нескольких гигабайт в одном экстенте при наличии свободного пространства.

# Посмотреть параметры flex_bg
tune2fs -l /dev/sda1 | grep -i flex

# Статистика групп блоков
dumpe2fs /dev/sda1 | grep "Group [0-9]*:" | head -20

# Использование пространства по группам блоков
dumpe2fs /dev/sda1 2>/dev/null | grep -E "Free blocks|Free inodes" | head -20

Онлайн-дефрагментация и инструменты работы с экстентами

Несмотря на все усилия аллокатора, со временем фрагментация накапливается. Особенно страдают файловые системы с высокой степенью заполнения и частыми операциями создания и удаления файлов разных размеров. ext4 поддерживает онлайн-дефрагментацию смонтированной файловой системы через утилиту e4defrag:

# Оценить степень фрагментации без дефрагментации
e4defrag -c /mnt/data

# Дефрагментировать конкретный файл
e4defrag /path/to/fragmented/file

# Дефрагментировать весь том
e4defrag /mnt/data

# Фрагментация конкретного файла через filefrag
filefrag -e /path/to/file

# Принудительно сбросить отложенные выделения на диск
sync && echo 3 > /proc/sys/vm/drop_caches

Механизм дефрагментации в ext4 использует специальный ioctl EXT4_IOC_MOVE_EXT, перемещающий экстенты из одного inode в другой. Утилита создаёт временный файл-донор с оптимальным размещением, перемещает туда экстенты оригинального файла, а затем обменивает метаданные между инодами. Для работающих приложений этот обмен происходит атомарно - файл никогда не оказывается в промежуточном состоянии.

Понимание того, как ext4 организует блоки через деревья экстентов, объясняет многое в поведении файловой системы под нагрузкой. Компактное представление больших непрерывных файлов, быстрое удаление гигабайтных файлов, эффективный fsck, умный аллокатор, откладывающий решение о размещении до последнего момента - всё это следствия одного архитектурного решения, принятого при переходе от ext3 к ext4. Файловая система, устроенная таким образом, работает тем лучше, чем крупнее файлы и чем более последовательны паттерны записи - именно то, что нужно для большинства серверных и десктопных нагрузок.