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

Allocation Groups

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, не вынуждает зоны иметь одинаковый размер. Сохраняя смещение и длину каждой записи в качестве записи в зонной карте, мы получаем преимущества наличия записей в карте, которые могут указывать на зоны различной длины; в обмен на более сложную реализацию карты и меньшее разветвление на каждом уровне дерева карты (так как отдельные записи стали больше мы умещаем меньшее их количество в каждый блок).

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