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

Поддерживая очень большие файлы, 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 использует схему предварительнойзаписи изменений метаданных, позволяющую вносить эти изменения атомарно.

XFS журналирует все изменения метаданных, включая операции с суперблоком, AGs, inodes, каталогами и свободным пространством. XFS не журналирует пользовательски данные. Например, создание файла требуется сохранить в журнал блок каталога, содержащий новый элемент, вновь размещенный inode, блок inode allocation tree, описывающий этот inode, блок заголовка AG и суперблок, содержащие количество свободных inodes. Элемент журнала по каждому из этих пунктов содержит заголовочную информацию, описывающую данный блок или inode, и копию самого блока или inode.

Сохранение в журнале копий модифицируемых метаданных делает процедуру восстановления ФС независимой от ее размера и сложности. Восстановление метаданных из журнала сводится к простому переносу копий блоков из лога в те места на диске, где они должны были находиться. Алгоритм журналирования не знает, что он, к примеру, восстанавливаетB+ дерево - он просто перезаписывает определенные блоки в файловой системе.

К сожалению, использование журнала транзакций не позволяет полностью отказаться от программ восстановления ФС. Аппаратные и программные ошибки, затирающие случайные дисковые блоки, вообще неисправимы с помощью журналирования – они могут привести к недоступности содержимого даже журналируемой файловой системы. Мы не выпустили подобную программу с первым релизом XFS, наивно полагая, что она не понадобится, однако пользователи убедили нас, что мы ошиблись – у них оставался единственный способ вернуть к жизни разрушенную XFS: пересоздать ее с помощью mkfs и восстановить данные с резервных копий. Мы планируем предоставить пользователям программу восстановления XFS в ближайшем будущем.

индекс статьи
страница 1 : страница без заголовка
страница 2 : страница без заголовка
страница 3 : страница без заголовка
страница 4 - текущая : страница без заголовка
страница 5 : страница без заголовка
страница 6 : страница без заголовка
страница 7 : страница без заголовка