Работа Linux основана на операциях с файлами, поэтому для работы в этой операционной системе необходима дисковая файловая система, поддерживающая множество операций управления файлами, таких как поиск, просмотр, перемещение, копирование и удаление файлов. Linux различает много типов файлов в дополнение к стандартным файлам и каталогам. Файлом в Linux может быть все, что угодно, будь то каталог, жесткий диск, раздел на жестком диске, параллельный порт, подключение к веб-сайту и т.д.
В настоящее время в ядре Linux присутствует множество как дисковых (minixfs, ext2/3/4[1], xfs, bmfs), так и виртуальных файловых систем(vfs). При этом только в последнее время начали появляться файловые системы со встроенными средствами борьбы с фрагментаций данных. Фрагментация на уровне файловой системы влияет на производительность, как на уровне ядра, так и на уровне приложений пользовательского уровня.
Целью данной статьи является описание различных способов борьбы с фрагментацией, использованных при разработке дисковой файловой системы в ОС Linux.
1. Виды фрагментации
Существует два основных вида фрагментации, как самих данных, так и метаданных, на уровне файловой системы:
- Внутренняя фрагментация вызвана тем, что в большинстве ОС[2] для решения задачи распределения данных на диске используется минимальная единица данных, называемая блоком. В современных жестких дисках и файловых системах в качестве размера блока принята величина 4 килобайта. Т.е. если файл весит 2 килобайта, то оставшиеся 2 килобайта его первого блока не смогут быть использованы файловой системой для распределения данных других файлов. Фактор внутренней фрагментации является очень значительным, если в вашей файловой системе имеется большое количество файлов малого размера. В виду большой сложности реализации в разработанной файловой системе[3] нет методов борьбы с внутренней фрагментацией.
- Внешняя фрагментация вызвана проблемами при распределении дисковых блоков между файлами. Как известно, большинство современных персональных компьютеров в качестве устройства постоянного хранения информации используют жесткие диски HDD (hard disk drive), в которых имеется большая разница между скоростью одноблочных и последовательных чтений множества блоков. Поэтому расположение данных одного файла максимально плотным образом позволяет увеличить скорость чтения данных из файла.
Описанные выше проблемы касаются самих данных, но в случае с метаданными в ОС Linux также существуют проблемы, такие как хранение inode-ов (сущностей, хранящих метаинформацию о файле: размер файла, дата последнего изменения и т.д.) и управление элементами директорий (directory entry).
2. Структура разработанной файловой системы
Для рассмотрения решений по борьбе с фрагментацией необходимо в первую очередь описать структуру разработанной файловой системы, которую условно можно разделить на несколько модулей:
- модуль монтирования файловой системы, необходимый для чтения superblock с диска и создание при первом монтировании или чтении корневой директории при последующих случаях монтирования.
- модуль работы с inode необходим для создания, удаления и поиска по номеру нужного inode.
- модуль работы с элементами директорий отвечает за создание, удаление, добавление, переименования, поиск по имени элементов директорий.
- модуль размещения данных на диске отвечает как за выделение данных, так и за освобождение выделенного под данные или метаданные пространства.
- модуль адресации блоков файла.
3. Разметка блоков файловой системы
Т.к. проблема фрагментации неразрывно связана с размещением данных на диске, ниже при рассмотрении разметки файловой системы будут описаны ее основные структуры, элементы, а также решения, использованные для дефрагментации данных.
- Первый блок выделен для хранения superblock(суперблока). Суперблок – это главная структура, хранящая метаинформацию о всей файловой системе, в частности – количество свободных и всего блоков на носителе, общее количество inode-ов, кол-во свободных inode, примитивы блокировок для реализации параллельного доступа и изменения суперблока.
- Дескрипторы групп inode-ов. Для борьбы с фрагментацией на уровне метаданных, а именно inode-ов, было решено объединить inode-ы в группы по 2^16 объектов. Такой способ был в первую очередь продиктован тем, что размер inode-а фиксирован для всех файлов, и группировка inode-ов вместе для последующей борьбы с фрагментацией позволила изменить систему поиска inode-а по номеру. К примеру, inode с номером 1123122 находится в группе inode-ов номер 17 (1123122 div 2^16 = 17) и является 9010 inode-ом в группе. Так как группа inode-ов хранится как непрерывная последовательность блоков, то для считывания информации о местоположении inode-а нет необходимости производить дисковые операции. В каждой группе inode-ов помимо самих inode-ов 2 блока занято под битовую карту группы inode-ов.
- Дескриптор группы inode-ов хранит информацию о кол-ве свободных inode-ов в группе и номер первого блока группы. Общее кол-во дескрипторов групп inode-ов равно 2^16 степени.
- Дескрипторы групп блоков. В качестве метода борьбы с фрагментацией на уровне данных файловой системы и для структурирования хранения данных было решено группировать блоки в непрерывные последовательности размером меньше и равно 256 Мб. Такой размер был выбран в первую очередь из расчета на то, что для адресации блока в группе блоков нужно ровно 2 байта. Помимо этого, учитывался тот фактор, что средняя скорость многоблочного чтения и записи современных жестких дисков на персональных компьютерах при 7200 об/с равна 100мб/c, т.е. можно предусмотреть возможность дефрагментации данных на группе блоков путем считывания целиком всей группы блоков в ОЗУ, ее перегруппировки и последующей записи на диск.
Информация о дескрипторах групп блоков записывается на диск при первом монтировании исходя из общего количества блоков носителя. Каждый дескриптор хранит информацию о номере блока, с которого начинается данная группа блоков, кол-во свободных блоков в группе и общее кол-во блоков в группе.
Общее кол-во дескрипторов групп блоков рассчитывается как целое от деления общего объема в мегабайтах носителя на 256 мегабайт плюс 1. В каждой группе блоков первые 2 блока заняты под битовую карту блоков.
- Весь остальной объем носителя, за вычетом суперблока, дескрипторов групп блоков и групп inode-ов, выделен для хранения данных самих файлов, описания директорий, групп inode-ов.
4. Алгоритмы дефрагментации данных
Помимо архитектурных решений, позволивших решить множество проблем фрагментации на уровне метаданных, следует рассмотреть алгоритмы выделения и освобождения блоков данных, так как они являются основной причиной внешней фрагментации данных. По этой причине были разработаны 2 алгоритма аллокации блоков – алгоритм выделения непрерывной последовательности блоков и алгоритм поблочной аллокации блоков.
Первый алгоритм аллокации блоков используется при выделении группы inode-ов, метаданных адресации, при увеличении размера файла через операцию truncate. Второй алгоритм аллокации блоков используется при расширении файла.
Ниже описаны оба алгоритма аллокации.
4.1. Алгоритм аллокации непрерывной последовательности блоков.
- Проверка на наличие необходимого количества блоков на диске, если его нет, то выход из подпрограммы.
- Цикл по всем дескрипторам групп блоков.
- Проверка, есть ли в группе блоков необходимое кол-во блоков, если нет, то следующая итерация.
- Читаем битовую карту i-ой группы блоков.
- Начиная с номера первого свободного блока итерируемся по битовой карте и ищем непрерывную последовательность блоков.
- Если последовательность найдена, то выдаем номер блока, с которого начинается выделенная непрерывная последовательность блоков, как результат. Иначе продолжаем итерироваться по битовой карте.
Недостаток выделения непрерывной последовательности заключается, во-первых, в том, что мы не можем выделить более 256 Мб за раз, и во-вторых, в том, что вероятность нахождения непрерывной последовательности большого размера в группе относительно мала.
Поэтому была создана функция выделения группы непрерывных последовательностей блоков. Суть ее заключается в итерировании по группам блоков с целью выделения непрерывных последовательностей размером в 1024 или менее блоков в каждой группе блоков ровно до тех пор, пока не будет выделено необходимое кол-во блоков или не закончится итерация по группам блоков.
4.2. Поблочный алгоритм аллокации блоков.
- Проверка на наличие необходимого количества блоков на диске, если нет, то выход из подпрограммы.
- Цикл по всем дескрипторам групп блоков или до тех пор, пока не выделим нужное нам количество блоков.
- Проверка, есть ли в группе блоков необходимое количество блоков, если нет, то переход к следующей итерации.
- Читаем битовую карту i-ой группы блоков.
- Начиная с номера первого свободного блока, проходим по битовой карте i-ой группы блоков и ищем свободные блоки. Помечаем найденные как занятые.
Заключение
В работе были рассмотрены основные виды фрагментации данных и метаданных в файловых системах, описаны архитектурные решения и алгоритмы для борьбы с внешней фрагментацией и фрагментацией метаданных, некоторые из них были использованы при разработке файловой системы.
Библиографический список
- Wikipedia. Ext2 filesystem – Wikipedia, The Free Encyclopedia. 2015. Режим доступа: https://ru.wikipedia.org/wiki/Ext2. (дата обращения: 20.08.2015)
- Э. Танненбаум. Современные операционные системы. 4-е изд. Питер, 2015.
- Habrahabr. Пишем файловую систему в ядре Linux – Habrahabr, 2015. Режим доступа: http://habrahabr.ru/company/spbau/blog/218833/. (дата обращения: 15.09.2015)
Количество просмотров публикации: Please wait