Фрагментация файловой системы - File system fragmentation

Визуализация фрагментации, а затем дефрагментации

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

В современных компьютерах с SSD «диски», которые не вращаются и на самом деле не являются дисками в общепринятом смысле, фрагментация файловой системы не является такой большой проблемой производительности (которая должна быть «исправлена»), поскольку отсутствует движение головок или дисков. Фактически, чрезмерная дефрагментация таких дисков может постепенно сократить срок их службы.

Причины

Когда сначала инициализируется файловая система на раздел, он содержит всего несколько небольших внутренних структур и в остальном представляет собой один непрерывный блок пустого пространства.[а] Это означает, что файловая система может размещать вновь созданные файлы в любом месте раздела. Некоторое время после создания файлы могут располагаться почти оптимально. Когда Операционная система и Приложения установлены или архивы распаковываются, отдельные файлы в конечном итоге появляются последовательно, поэтому связанные файлы располагаются близко друг к другу.

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

Пример

Упрощенный пример того, как происходит фрагментация свободного пространства и файлов

Следующий пример представляет собой упрощение иначе сложной темы. Рассмотрим следующий сценарий: на новом диске было пять файлов с именами A, B, C, D и E, сохраненных непрерывно и последовательно в указанном порядке. Каждый файл использует 10 блоки пространства. (Здесь размер блока не имеет значения.) Остаток дискового пространства - один свободный блок. Таким образом, дополнительные файлы могут быть созданы и сохранены после файла E.

Если файл B удален, создается вторая область из десяти блоков свободного пространства, и диск становится фрагментированным. Пустое пространство просто остается там, помечается как и доступно для дальнейшего использования, а затем используется снова по мере необходимости.[b] Файловая система мог дефрагментировать диск сразу после удаления, но это может привести к серьезному снижению производительности в непредсказуемые моменты времени.

Теперь новый файл с именем F, для которого требуется семь блоков пространства, может быть помещен в первые семь блоков вновь освобожденного пространства, в котором ранее находился файл B, и три следующих за ним блока останутся доступными. Если добавляется еще один новый файл с именем G, которому требуется всего три блока, он может занимать пространство после F и перед C.

Если впоследствии F необходимо расширить, поскольку пространство сразу после него занято, есть три варианта для файловой системы:

  1. Добавление нового блока где-то еще и указание, что у F есть второй степень
  2. Перемещение файлов по пути расширения в другое место, чтобы позволить F оставаться непрерывным
  3. Перемещение файла F таким образом, чтобы он мог быть одним непрерывным файлом нового, большего размера

Второй вариант, вероятно, непрактичен по соображениям производительности, как и третий, когда файл очень большой. Третий вариант невозможен, когда нет единого непрерывного свободного пространства, достаточно большого для размещения нового файла. Таким образом, обычная практика - просто создать степень в другом месте и привяжите новый экстент к старому.

Материал, добавленный в конец файла F, будет частью того же экстента. Но если материала так много, что после последнего экстента не остается места, тогда еще один протяженность должна быть создана и так далее. В конечном итоге в файловой системе есть свободные сегменты во многих местах, и некоторые файлы могут быть распределены по разным размерам. Время доступа к этим файлам (или ко всем файлам) может стать чрезмерно большим.

Необходимость

Некоторые ранние файловые системы не могли фрагментировать файлы. Одним из таких примеров был Желудь DFS файловая система, используемая на BBC Micro. Из-за невозможности фрагментировать файлы сообщение об ошибке не может продлить время от времени появлялись, и пользователь часто не мог сохранить файл, даже если на диске было достаточно места для него.

DFS использовала очень простую структуру диска и файлы на диск располагались только по длине и стартовому участку. Это означало, что все файлы должны были существовать как непрерывный блок секторов, и фрагментация была невозможна. Используя пример в таблице выше, попытка развернуть файл F на шаге 5 не удалась бы в такой системе с не может продлить сообщение об ошибке. Независимо от того, сколько свободного места могло остаться на диске в целом, было невозможно расширить файл данных.

Стандарты обработка ошибок в то время были примитивными, и в любом случае программы, втиснутые в ограниченную память BBC Micro, редко могли позволить себе тратить пространство, пытаясь изящно обрабатывать ошибки. Вместо этого пользователь обнаружил бы, что в командной строке пользователь Не могу продлить сообщение, и все данные, которые еще не были добавлены в файл, будут потеряны. Проблему нельзя было решить, просто предварительно проверив свободное место на диске. Хотя свободное пространство на диске может существовать, размер самого большого непрерывного блока свободного пространства не был бы сразу очевиден без анализа чисел, представленных каталогом дисков, и поэтому не заметил бы пользователя. Кроме того, почти все пользователи DFS ранее использовали кассета для хранения файлов, который не страдает этой ошибкой. Обновление до дискета система была дорогостоящим обновлением, и было шоком, что обновление без предупреждения могло вызвать потери данных.[1][2]

Типы

Фрагментация файловой системы может происходить на нескольких уровнях:

  • Фрагментация внутри личности файлы
  • Фрагментация свободного пространства
  • Уменьшение местонахождение ссылки между отдельными, но связанными файлами

Фрагментация файлов

Фрагментация отдельного файла происходит, когда один файл разбит на несколько частей (называемых экстенты в файловых системах на основе экстентов). Хотя дисковые файловые системы пытаются сохранить непрерывность отдельных файлов, часто это невозможно без значительного снижения производительности. Инструменты проверки и дефрагментации файловой системы обычно учитывают только фрагментацию файлов в своей статистике «процент фрагментации».

Фрагментация свободного пространства

Фрагментация свободного (нераспределенного) пространства происходит, когда в файловой системе есть несколько неиспользуемых областей, в которые можно записывать новые файлы или метаданные. Нежелательная фрагментация свободного пространства обычно вызывается удалением или усечением файлов, но файловые системы также могут намеренно вставлять фрагменты («пузыри») свободного пространства, чтобы облегчить расширение соседних файлов (см. предотвращение фрагментации ниже).

Разброс файлов

Смотрите также: Последовательность файлов

Сегментация файлов, также называемая фрагментацией связанных файлов или фрагментацией (файла) на уровне приложения, означает отсутствие местонахождение ссылки (на носителе) между связанными файлами (см. последовательность файлов для более подробной информации). В отличие от двух предыдущих типов фрагментации, разброс файлов - это гораздо более расплывчатое понятие, поскольку оно сильно зависит от схемы доступа конкретных приложений. Это также очень затрудняет его объективное измерение или оценку. Однако, возможно, это наиболее критический тип фрагментации, поскольку исследования показали, что файлы, к которым чаще всего обращаются, обычно имеют небольшой размер по сравнению с доступной пропускной способностью диска в секунду.[3]

Чтобы избежать фрагментации связанного файла и улучшить локальность ссылки (в данном случае называется смежность файлов), должны быть сделаны предположения или активные наблюдения о работе приложений. Очень часто делается предположение, что лучше хранить файлы меньшего размера в одном каталог вместе и разложите их в естественном порядке файловой системы. Хотя это часто разумное предположение, оно не всегда выполняется. Например, приложение может читать несколько разных файлов, возможно, в разных каталогах, в том же порядке, в котором они были записаны. Таким образом, файловая система, которая просто упорядочивает все записи последовательно, может работать быстрее для данного приложения.

Отрицательные последствия

Фрагментация файловой системы более проблематична с потребительским уровнем жесткие диски из-за увеличения несоответствия между последовательный доступ скорость и задержка вращения (и в меньшей степени время поиска ), на которых обычно размещаются файловые системы.[4] Таким образом, фрагментация является важной проблемой при исследовании и проектировании файловых систем. Сдерживание фрагментации не только зависит от формата файловой системы на диске, но и во многом от его реализации.[5] Фрагментация файловой системы оказывает меньшее влияние на производительность. твердотельные накопители, так как нет механического время поиска участвует.[6] Однако файловая система должна хранить дополнительные метаданные для каждой несмежной части файла. Каждая часть метаданных сама по себе занимает место и требует вычислительной мощности и времени процессора. Если достигается максимальный предел фрагментации, запросы на запись завершаются ошибкой.[6]

В простой файловой системе ориентиры фактор фрагментации часто не учитывается, поскольку реалистичное старение и фрагментацию сложно смоделировать. Скорее, для простоты сравнения тесты файловой системы часто запускаются на пустых файловых системах. Таким образом, результаты могут сильно отличаться от реальных схем доступа.[7]

Смягчение

Было разработано несколько методов борьбы с фрагментацией. Обычно их можно разделить на две категории: упреждающий и ретроактивный. Из-за сложности прогнозирования схем доступа эти методы чаще всего эвристический по своей природе и может снизить производительность при неожиданных рабочих нагрузках.

Предотвращение фрагментации

Упреждающие методы пытаются свести фрагментацию к минимуму во время записи данных на диск. Самым простым является добавление данных к существующему фрагменту на месте, где это возможно, вместо выделения новых блоков новому фрагменту.

Многие из сегодняшних файловых систем пытаются предварительно выделить более длинные фрагменты или фрагменты из разных фрагментов свободного пространства, что называется экстенты к файлам, которые активно добавляются в. Это в значительной степени позволяет избежать фрагментации файлов при одновременном добавлении нескольких файлов, что позволяет избежать их чрезмерного переплетения.[5]

Если известен окончательный размер файла, подлежащего модификации, можно предварительно выделить хранилище для всего файла. Например, Майкрософт Виндоус файл подкачки (файл подкачки) может динамически изменяться в размере при нормальной работе и, следовательно, может стать сильно фрагментированным. Этого можно избежать, указав файл подкачки с одинаковыми минимальным и максимальным размерами, эффективно предварительно выделив весь файл.

BitTorrent и другие пиринговый обмен файлами приложения ограничивают фрагментацию, предварительно выделяя все пространство, необходимое для файла при запуске загрузки.[8]

Относительно недавний метод отложенное распределение в XFS, HFS +[9] и ZFS; тот же метод также называется выделением на одном уровне в Reiser4 и ext4. Когда выполняется запись в файловую систему, блоки файловой системы зарезервированы, но расположение конкретных файлов еще не установлено. Позже, когда файловая система вынуждена сбрасывать изменения в результате нехватки памяти или фиксации транзакции, распределитель будет гораздо лучше знать характеристики файлов. Большинство файловых систем с таким подходом пытаются сбрасывать файлы в одном каталоге непрерывно. Предполагая, что многократное чтение из одного каталога является обычным явлением, улучшается локальность ссылки.[10] Reiser4 также упорядочивает расположение файлов в соответствии с каталогом. хеш-таблица, чтобы при доступе к файлам в естественном порядке файловой системы (как диктуется Readdir ), они всегда читаются последовательно.[11]

Дефрагментация

Основная статья: Дефрагментация

Ретроактивные методы пытаются уменьшить фрагментацию или негативные эффекты фрагментации после того, как она произошла. Многие файловые системы предоставляют дефрагментация инструменты, которые пытаются изменить порядок фрагментов файлов, а иногда также уменьшить их разброс (т.е. улучшить их смежность или местонахождение ссылки ), сохраняя файлы меньшего размера в каталоги, или деревья каталогов, или даже последовательности файлов близко друг к другу на диске.

В HFS Plus файловая система прозрачно дефрагментирует файлы размером менее 20 МиБ по размеру и разбиваются на 8 и более фрагментов при открытии файла.[12]

Устаревший теперь Commodore Amiga Умная файловая система (SFS) дефрагментировала себя во время использования файловой системы. Процесс дефрагментации почти полностью не имеет состояния (за исключением местоположения, в котором он работает), поэтому его можно остановить и запустить мгновенно. Во время дефрагментации обеспечивается целостность как метаданных, так и обычных данных.

Смотрите также

Примечания

  1. ^ Некоторые файловые системы, например NTFS и ext2 +, может предварительно выделить пустые смежные области для специальных целей.
  2. ^ Практика оставлять пространство, занятое удаленными файлами, в основном нетронутым - вот почему восстановить программы смогли работать; они просто восстановили файл, имя которого было удалено из каталога, но содержимое которого все еще находилось на диске.

Рекомендации

  1. ^ http://www.8bs.com/hints/083.txt - Описание не может продлить ошибка
  2. ^ http://8bs.com/mag/1to4/basegd1.txt - Возможная потеря данных из-за не может продлить ошибка
  3. ^ Douceur, John R .; Болоски, Уильям Дж. (Июнь 1999 г.). «Масштабное исследование содержимого файловой системы». Обзор оценки эффективности ACM SIGMETRICS. 27 (1): 59–70. Дои:10.1145/301464.301480.
  4. ^ Крайдер, Марк Х. (2006-04-03). Технологии хранения будущего: взгляд за горизонт (PDF). Всемирная конференция Storage Networking. Seagate Technology. Архивировано из оригинал (PDF) 17 июля 2006 г.
  5. ^ а б McVoy, L.W .; Клейман, С. Р. (зима 1991 г.). «Экстент-подобная производительность файловой системы UNIX» (PostScript ). Труды USENIX зима '91. Даллас, Техас: Sun Microsystems, Inc. стр. 33–43. Получено 2006-12-14.
  6. ^ а б Гензельман, Скотт (3 декабря 2014 г.). «Реальная и полная история - дефрагментирует ли Windows ваш SSD?». Блог Скотта Хансельмана.
  7. ^ Смит, Кейт Арнольд (январь 2001 г.). «Тесты файловой системы для конкретных рабочих нагрузок» (PDF). Кембридж, Массачусетс: Гарвардский университет. Архивировано из оригинал (PDF) в 2004-11-17. Получено 2006-12-14. Цитировать журнал требует | журнал = (помощь)
  8. ^ Лейтон, Джеффри (29 марта 2009 г.). "От ext3 к ext4: интервью с Теодором Цо". Журнал Linux. QuinStreet.
  9. ^ Сингх, Амит (май 2004 г.). «Фрагментация в объемах HFS Plus». Mac OS X Внутреннее устройство.
  10. ^ Суини, Адам; Дусетт, Дуг; Ху, Вэй; Андерсон, Кертис; Нисимото, Майк; Пек, Джефф (январь 1996). «Масштабируемость в файловой системе XFS» (PDF). Материалы Ежегодной технической конференции USENIX 1996 г.. Сан-Диего, Калифорния: Силиконовая Графика. Получено 2006-12-14.
  11. ^ Райзер, Ганс (2006-02-06). "Файловая система Reiser4". Google TechTalks. Архивировано из оригинал 19 мая 2011 г.. Получено 2006-12-14.
  12. ^ Сингх, Амит (2007). «12 Файловая система HFS Plus». Внутреннее устройство Mac OS X: системный подход. Эддисон Уэсли. ISBN  0321278542.

дальнейшее чтение