XFS: структуры на диске и алгоритмы работыXFS: on-disk structures and working algorithms

XFS появилась в декабре 1994 года вместе с IRIX 5.3 — собственной UNIX-системой SGI для рабочих станций и серверов, где основной нагрузкой были огромные видеофайлы и научные данные, а не тысячи мелких документов. Уже к 1996 году она стала файловой системой по умолчанию в IRIX 6.2, в 1997-м научилась выравнивать выделение блоков под геометрию аппаратных RAID-массивов, а к 1999-му получила version-2 директории, масштабируемые до десятков миллионов файлов в одном каталоге. Порт на Linux начала команда SGI в Мельбурне, код открыли под GPL в 2000-м, первый стабильный релиз для Linux вышел в 2001-м, а в мейнлайн ядро XFS попала в 2002 году (Linux 2.5.36). С середины 2010-х XFS — файловая система по умолчанию в Red Hat Enterprise Linux и его производных.XFS appeared in December 1994 alongside IRIX 5.3 — SGI's own UNIX for workstations and servers, where the primary workload was huge video files and scientific data rather than thousands of small documents. By 1996 it was already the default filesystem in IRIX 6.2, in 1997 it learned to align block allocation to hardware RAID array geometry, and by 1999 it gained version-2 directories, scaling to tens of millions of files in a single directory. The Linux port was started by an SGI team in Melbourne, the code was opened under the GPL in 2000, the first stable Linux release shipped in 2001, and XFS landed in the mainline kernel in 2002 (Linux 2.5.36). Since the mid-2010s, XFS has been the default filesystem in Red Hat Enterprise Linux and its derivatives.

Центральная идея XFS — разбить весь раздел на allocation group (AG), каждая из которых почти самодостаточна: имеет собственную копию суперблока, собственные B+-деревья свободного места и inode, и может выделять блоки и inode независимо от остальных AG. Именно это позволяет нескольким процессам писать в разные части файловой системы параллельно без конкуренции за общую блокировку:The central idea of XFS is splitting the entire partition into allocation groups (AGs), each nearly self-sufficient: it has its own superblock copy, its own free-space and inode B+-trees, and can allocate blocks and inodes independently of the other AGs. This is exactly what lets several processes write to different parts of the filesystem in parallel without contending for a shared lock:

Свободное место внутри AG отслеживается не одним, а двумя B+-деревьями одновременно, индексирующими одни и те же диапазоны по разным ключам — это позволяет отвечать сразу на два разных вопроса без полного перебора:Free space within an AG is tracked not by one but by two B+-trees at once, indexing the same ranges under different keys — this lets two different questions be answered without a full scan:

Оба дерева обновляются в одной транзакции при каждом выделении/освобождении блоков — отсюда и нужен резервный список AGFL: без него операция вставки в оба B+-дерева могла бы сама потребовать выделения нового блока под узел дерева, создавая рекурсивную зависимость («чтобы выделить место, нужно место»), которую AGFL разрывает, держа несколько блоков в резерве заранее.Both trees are updated in a single transaction on every block allocation/free — which is exactly why the AGFL reserve list is needed: without it, inserting into either B+-tree could itself require allocating a new block for a tree node, creating a recursive dependency ("allocating space requires space") that the AGFL breaks by keeping a few blocks reserved in advance.

Данные файла адресуются собственным B+-деревом — bmbt (block map B-tree), логически тем же приёмом, что extent-дерево ext4, но реализованным как полноценное B+-дерево, а не компактный формат внутри inode с ограниченной глубиной:A file's data is addressed by its own B+-tree — the bmbt (block map B-tree), logically the same trick as ext4's extent tree, but implemented as a full B+-tree rather than a compact inode-embedded format with limited depth:

С версии 4.9 (для XFS с фичей rmap) появилось третье дерево на AG — rmap btree, обратное отображение «какой физический блок кому принадлежит» вместо прямого «какой логический блок файла где физически лежит». Это не дублирование bmbt, а другой ключ к тем же данным, необходимый там, где bmbt принципиально не справляется — когда один физический блок используется сразу несколькими владельцами:Since version 4.9 (for XFS with the rmap feature) a third per-AG tree appeared — the rmap btree, a reverse mapping of "which physical block belongs to whom" instead of the forward "where does this file's logical block physically live". This isn't a bmbt duplicate — it's a different key into the same data, needed exactly where bmbt fundamentally falls short: when one physical block is used by several owners at once:

Журналирование в XFS защищает те же метаданные, что и JBD2 в ext4, но устроено иначе на уровне реализации — delayed logging откладывает физическую запись изменений в лог-буфер, накапливая их в памяти в структуре CIL (Committed Item List):Journaling in XFS protects the same metadata as JBD2 does in ext4, but works differently at the implementation level — delayed logging postpones physically writing changes to the log buffer, accumulating them in memory in a structure called the CIL (Committed Item List):

• изменения метаданных сначала накапливаются в CIL в памяти, а не сразу пишутся в лог-буферы на диске — несколько независимых транзакций, трогающих один и тот же объект метаданных подряд, схлопываются в одну итоговую запись вместо несколькихmetadata changes accumulate in the in-memory CIL first, rather than being written straight to on-disk log buffers — several independent transactions touching the same metadata object in a row collapse into one final record instead of several
• при событии синхронизации лога (log force — например, fsync или естественное истечение таймера) весь CIL целиком сбрасывается на диск одной checkpoint-транзакцией; ограничение только одно: она не может быть больше примерно половины размера самого логаon a log sync event (a log force — an fsync, say, or a natural timer expiry), the entire CIL is flushed to disk as a single checkpoint transaction; there's just one limit: it can't be larger than roughly half the log's own size
• после записи в лог элементы переносятся в AIL (Active Item List) и уже оттуда асинхронно записываются на их постоянное место на диске — восстановление после сбоя проигрывает лог от последнего checkpoint, тем же принципом «применить всё подтверждённое, отбросить незавершённое», что и JBD2once written to the log, items move to the AIL (Active Item List) and are asynchronously written from there to their permanent on-disk location — crash recovery replays the log from the last checkpoint, the same "apply everything committed, discard the incomplete" principle as JBD2

Практический эффект delayed logging — журнал перестаёт быть узким местом при интенсивной модификации одних и тех же метаданных (например, частое обновление времени доступа в одном и том же каталоге с множества потоков): физически на диск попадает не поток отдельных изменений, а их итоговый результат за интервал между checkpoint-ами.The practical effect of delayed logging is that the journal stops being a bottleneck under heavy modification of the same metadata (say, frequent access-time updates in the same directory from many threads): what actually hits the disk isn't a stream of individual changes but their net result over the interval between checkpoints.

• kernel.org docs — The SGI XFS Filesystem
• kernel.org docs — XFS Online Fsck Design
• kernel.org docs — XFS Delayed Logging Design
• xfs.org — Papers and Documentation