Файловая система XFS

Содержание:

1	Описание
2	Структура
3	Особенности
4	Достоинства
5	Недостатки

Приложение.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Описание XFS

XFS — высокопроизводительная журналируемая файловая система, созданная компанией Silicon Graphics для собственной операционной системы IRIX. 1 мая 2001 года Silicon Graphics выпустила XFS под GNU General Public License. XFS отличается от других файловых систем тем, что она изначально была рассчитана для использования на дисках большого объёма (более 2 терабайт, и например, RAID-массивы большой емкости).

Поддержка XFS была включена в ядро Linux версий 2.4 (начиная с 2.4.25, когда Марчело Тозатти (Marcelo Tosatti) посчитал её достаточно стабильной) и 2.6, и, таким образом, она стала довольно универсальной для Linux-систем. Инсталляторы дистрибутивов openSUSE, Gentoo, Mandriva, Slackware, Ubuntu, Fedora и Debian предлагают XFS как вариант файловой системы для установки. FreeBSD стала поддерживать XFS в режиме чтения в декабре 2005 года.

Архитектура XFS

Figure 1 дает общую структуру XFS в виде блок-схемы.

Обобщенная структура XFS подобна  обычной файловой системе с добавлением  менеджера транзакций (transaction manager) и менеджера разделов (volume manager). XFS полностью поддерживает все файловые интерфейсы UNIX и соотвествует стандартам POSIX и XPG4. Она располагается ниже интерфейса VNODE в ядре IRIX и ипользует весь спектр сервисов ядра, включая буфферный/страничный кэш (buffer/page cache), кэш поиска имен в каталоге (directory name lookup cache) и динамический vnode кэш.

 

XFS представлена несколькими модулями, каждый из которых реализует  определенную часть ее функциональности. Основная и наиболее важная часть файловой системы – space manager (менеджер пространства). Этот модуль управляет свободным местом в ФС, размещением inodes и выделением дискового пространства конкретным файлам. I/O manager (менеджер ввода-вывода) отвечает за выполнение файловых запросов на ввод-вывод и обращается к space manager для выделения и отслеживания дискового пространства для файлов. Directory manager (менеджер директорий) реализует пространство имен файловой системы. Buffer cache используется всеми частями XFS для кэширования в памяти содержимого наиболее часто запрашиваемых блоков указанного раздела. Он представляет собой интегрированный страничный и файловый кэш, разделяемый всеми ФС в ядре. Transaction manager используется другими частями файловой системы для того, что бы сделать все операции изменения метаданных XFS атомарными, позволяя быстро восстановить целостность файловой системы после сбоя. Модульная реализация XFS достаточно сложна - в настоящее время она включает более 50 000 строк C кода, в то время как EFS представляла собой лишь около 12 000 строк.

Volume manager, используемый в XFS (называемый XLV), реализует слой абстракции файловой системы от конкретного диска. XLV выполняет все дисковые операции чтения, записи и отображения, запрашиваемые файловой системой. Сама XFS ничего не знает о расположении и геометрии тех устройств, на которых она работает. Отделение дисковых операций от основного кода файловой системы сильно упростило ее реализацию и использование.

Особенности

1. Масштабируемость хранения данных

XFS эффективно  поддерживает все атрибуты VLFS. Этот  раздел описывает механизмы, посредством  которых была достигнута такая  хорошая масштабируемость.

XFS является  полностью 64-хбитной файловой  системой. Все глобальные счетчики  в ФС имеют разрядность 64-bit. Адреса блоков и номера inode также 64-битны. Что бы избежать применения во всех структурах данных файловой системы 64-хбитных чисел, физических ФС разделяется на области, называемые Allocation Groups (AG). Это что-то вроде cylinder groups в FFS, однако AGs были введены для улучшения масштабируемости и распараллеливания файловых операций, а не для удобства управления дисковым пространством.

AGs сохраняют размеры структур данных в XFS в таком диапазоне, в котором они могут наиболее эффективно упарвляться, не разбивая ФС на большее число плохо контроллируемых частей. Allocating Groups имеют 0.5 – 4 Gb в размере, каждая из них располагает собственными стуктурами данных для управления свободным местом и inodes в пределах своих границ. Разбиение файловой системы на AG ограничивает размеры структур данных, предназначенных для отслеживания свободного места и inodes. Этот прием также позволяет во внутренних сруктурах AG использовать относительные указатели на блоки и inode, и, таким образом, удерживать разрядность этих указателей в пределах 32 bit. Все это также помогает сохранить размеры структур данных в AG на оптимальном уровне.

Allocating groups только иногда применяются для более удобного сосредоточения данных. Вообще они слишком велики, что бы эффективно решать эти задачи. Мы же группируем данные вокруг отдельных файлов и директорий. Как и в FFS, каждый раз при создании нового каталога мы не помещаем его в AG, в которой располагается родительский каталог. Как только директория была размещена (allocated), мы пытаемся выделять место для inodes ее самих файлов физизчески вокруг данной директории. Этот алгоритм отлично работает для каталогов с большим количеством мелких файлов – они все размещаются на диске смежно. Работая с большими файлами, мы пытаемся выделять зоны около inode, а в последствие – рядом с уже существующими блоками файла, выбирая свободные блоки таким образом, что бы файл располагался на диске как можно более непрерывно. Конечно, файлы и директории не ограничены свободным местом в пределах одной AG. Пока структуры обслуживают данные внутри своей AG, в них применяются относитльные указатели, а глобальные структуры данных, описывающие лишь некоторые файлы и каталоги, могут ссылаться на блоки и inodes в любом месте ФС.

Другая цель allocating groups – достижение явного параллелизма в управлении свободным местом и размещении inodes. Файловые системы предыдущего поколения, такие, как EFS, имеют однопоточный механизм выделения и освобождения дискового пространства. На больших файловых системах с множеством использующих их процессов такой алгоритм может создать серьезные проблемы. Сделав структуры в каждой AG независимыми, мы в XFS добились, что операции с дисковым пространством и inodes могут выполняться параллельно по всей ФС. Таким образом, несколько пользовательских процессов могут одновременно запросить свободное место или новый inode, и ни один из них не будет заблокирован (т. е. не будет ждать, пока с метаданными поработает другой процесс (пер.)).

-Управление свободным пространством (free space management)

 

Space management – ключ к хорошим показателям масштабируемости и производительности файловой системы. Эффефктивно выделяя и освобождая дисковое пространство, мы существенно уменьшаем фрагментацию файловой системы и увеличиваем ее производительность. На замену блочно-ориентированным битовым картам в XFS пришли заточенные под зоны (extents) структуры, состоящие из пары B+ деревьев в каждой AG. Элементы этих деревьев – десктрипторы зон свободного пространства в AG – содержат относительный адрес стартового блока и длину зоны. Одно из деревьев индексирует зоны по стартовому блоку, другое – по длине. Двойное индексирование позволяет гибко и эффективно находить свободные зоны в зависимости от типа запроса на выделение (по адресу или по длине).

Поиск по таким B+ деревьям гораздо эффективнее  перебора битовой карты, т. к. не тратиться  время на сканирование уже размещенных  блоков и нахождение длины зоны. Согласно нашим моделям, B+ деревья  свободных зон гораздо более  эффективны и гибки, чем иерархические  bitmap-схемы. К сожалению, результаты этого моделирования были потеряны, поэтому нам придется дать аналитические разъяснения. В отличие от бинарных схем, B+ деревья не имеют никаких ограничений на выравнивание и размер свободных зон – вот почему мы считаем их гибкими. Поиск зоны данного размера по B+ дереву, индексированному (возможно, правильнее перевести – отсортированному (пер.)) по длине, и поиск зоны рядом с данным блоком по дереву, индексированному по стартовому адресу – это операции сложности O(logN) (в отличие от последовательного сканирования битовой карты, имеющего сложность O(N) (пер.)). Поэтому мы считаем B+ деревья более эффективными, нежели бинарные схемы учета свободно пространства. Конечно, реализация B+ деревьев гораздо более сложна, чем у бинарных схем, однако мы уверены, что выигрыш в гибкости и производительности, получаемый с их помощью, компенсирует все затраты.

- Поддержка больших файлов

XFS обеспечивает 64-хбитное разреженное адресное  пространство для каждого файла. 64-хбитные указатели позволяют  теоретически иметь поистине  огромные файлы. Что бы сохранять  небольшми размеры карты файла (file allocation map), XFS использует карту зон вместо карты блоков. Элементы зонной карты – это дескрипторы протяженных участков выделенных файлу блоков. Каждый элемент содержит смещение блока элемента в файле (consists of the block offset of the entry in the file), длину зоны и адрес ее первого блока.

Не смотря на экономию места с помощью зонных карт, разреженные файлы все еще  могут потребовать большого числа  элементов в карте зон файла. Когда количество выделенных файлу  зон превысит максимально возможное  для размещения в XFS inode, мы используем B+ дерево с корнем в inode (we use a B+ tree rooted within the inode) для управления дескрипторами зон. Дерево индексировано по полю block offset в дескрипторе зоны. Структура B+ дерева позволяет нам отсеживать миллионы дескрипторов зон, и, в отличие от решений в стиле FFS, не вынуждает зоны иметь одинаковый размер.

- Поддержка большого количества файлов

Поддерживая очень большие файлы, XFS так же поддерживает очень много файлов. Количество файлов в файловой системе  ограничено только ее размером. Взамен статическому размещению inodes при создании ФС, XFS имеет механизм динамического выделения inodes по запросу. Это освобождает пользователя от необходимости предсказывать количество необходимых файлов и пересоздавать в последствие ФС, если это количество было угадано неверно.

Механизм  динамического выделения inodes требует использования нескольких служебных структур данных для отслеживания физического расположения этих inodes. В XFS каждая allocating group управляет inodes, размещенными в ее пределах. AG использует B+ древо для индексирования координат (location) своих inodes. Inodes размещены в группах по 64 inodes. Дерево inodes в каждой AG хранит данные о положении этих групп и о том, находится ли каждый inode в группе в использовании. Сами inode не содержаться в B+ дереве. Элемент дерева только показывает, где в пределах AG располагается данная группа.

B+ дерево  inodes, содержащее только смещение каждой группы inode, может, тем не менее, управлять миллионами inodes. Платой за такую гибкость послужила дополнительная сложность реализации ФС. Алгоритм принятия решения о размещении нового пакета inodes и сохранении данных о нем требует сложности, которая отсутствует в других файловых системах. Наконец, наличие разреженного пространства номеров inodes (sparse inode numbering space) заставлило нас использовать 64-хбитные номера, что вызвало необходимость доработки целого ряда системных интерфейсов с целью возвращения приложению стандартного описателя файла.

- Поддержка больших директорий

Миллионы  файлов на разделе XFS нуждаются в  представлении в пространстве имен файловой системы. XFS реализует традиционное для UNIX name space. Однако, в отличае от существующих UNIX-ФС, XFS может эффективно поддерживать большое количество файлов в директории, использую для их индексации дисковые (on-disk) B+ дереья.

B+ деревья  каталогов немного отличаются  от других древовидных структур  в XFS. Дело в том, что ключи  для индексирования элементов  дерева – имена файлов в  директории – могут иметь длину  от 1 до 255 байт. Что бы скрыть этот  факт от алгоритма управления  деревом, имена элементов каталога  хэшируются специальной функцией, возвращающей 4-хбайтное число, используемое в дальнейшем при индексации элементов дерева. Элементы каталога хранятся в листьях B+ дерева, содержащих полное имя и номер inode для данного элемента. Так как хэш-функция, используемая в данном алгоритме, несовершенна, он (алгоритм) должен обеспечить корректное управление элементами каталога с совпадающими ключами – такие элементы хранятся последовательно (друг за другом) в B+ дереве. Использование фиксированного размера кюча во внутренних узлах B+ дерева упрощает код управления деревом, но отсутствие гарантии уникальности ключей (из-за несовершенства хэш-алгоритма) вновь серьезно его усложняет. Однако мы уверены, что это усложнение алгоритмов индексации дерева более чем оправдано за счет увеличения скорости работы с каталогами, которую дают нам B+ деревья.

Использование маленьких, постоянных по размеру ключей во внутренних узлах дерева увеличивает  его ширину и уменьшает высоту (сравнительно с использованием больших  ключей переменной длины). Т.к. внутренние узлы имеют фиксированный размер, равный размеру блока в ФС, то маленьких ключей в узле поместиться  больше. Поэтому внутренние узлы имеют  больше потомков, и ширина дерева возрастает. Уменьшая за счет этого высоту дерева, мы уменьшаем число уровней , которые придется просканировать для поиска заданного элемента. B+ деревья делают операции удаления, вставки и поиска элемента в каталоге невероятно эффективными, однако операция получения листинга каталога с миллионами элементов все еще крайне непрактична – в том числе из-за объемов выходных данных.

 

- Поддержка быстрого восстановления после сбоя

Файловая  система с размерами и сложностью XFS практически не может быть восстановлена  процедурой, проверяющей корректность всех метаданных. Это будет продолжаться бесконечно долго. Рассмотрим, к примеру, операцию восстановления таблицы inodes в XFS. Т. к. inodes размещены не в известном заранее одном месте, а произвольно, просмотр всех inodes в худшем случае – при рарушении B+ деревьев – может потребовать сканирования всего диска. Что бы избежать этих проблем, XFS использует схему предварительной записи изменений метаданных, позволяющую вносить эти изменения атомарно.