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

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

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

Твердотельные накопители не осуществляют физический поиск, поэтому непоследовательный доступ к данным на них происходит в сотни раз быстрее, чем на движущихся накопителях, что делает фрагментацию менее серьезной проблемой. Не рекомендуется выполнять дефрагментацию твердотельного накопителя вручную, поскольку это может привести к преждевременному износу накопителей из-за ненужных операций записи-стирания. ^{[ 1 ]}

Причины

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

Типы

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

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

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

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

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

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

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

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

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

Фрагментация структуры данных

Каталоги или индексы, используемые самой файловой системой, также могут со временем фрагментироваться, поскольку содержащиеся в них записи создаются, изменяются или удаляются. Это вызывает больше беспокойства, когда том содержит множество очень маленьких файлов, чем когда том заполнен меньшим количеством файлов большего размера. В зависимости от конкретной конструкции файловой системы файлы или регионы, содержащие эти данные, также могут стать фрагментированными (как описано выше для «обычных» файлов), независимо от какой-либо фрагментации фактических записей данных, хранящихся в этих файлах или регионах. ^{[ 5 ]}

Для некоторых файловых систем (например, NTFS ^{[ с ]} и HFS / HFS Плюс ^{[ 6 ]}), сопоставление / сортировка / сжатие, необходимые для оптимизации этих данных, не могут быть легко выполнены во время использования файловой системы. ^{[ 7 ]}

Негативные последствия

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

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

смягчение последствий

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

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

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

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

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

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

Относительно недавний метод — отложенное выделение в XFS , HFS+. ^{[ 13 ]} и ZFS ; тот же метод также называется выделением при сбросе в reiser4 и ext4 . При записи в файловую систему блоки файловой системы резервируются, но расположение конкретных файлов еще не определено. Позже, когда файловая система будет вынуждена сбросить изменения в результате нехватки памяти или фиксации транзакции, распределитель будет гораздо лучше знать характеристики файлов. Большинство файловых систем с таким подходом пытаются сбрасывать файлы в одном каталоге последовательно. Если предположить, что многократное чтение из одного каталога является обычным явлением, локальность ссылки улучшается. ^{[ 14 ]} Reiser4 также упорядочивает расположение файлов в соответствии с хеш-таблицей каталога , так что при доступе к файлам в естественном порядке файловой системы (как предписывает readdir ) они всегда читаются последовательно. ^{[ 15 ]}

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

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

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

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

См. также

Примечания

^ Некоторые файловые системы, такие как NTFS и ext2 +, могут заранее выделять пустые смежные регионы для специальных целей.
^ Практика оставлять пространство, занимаемое удаленными файлами, практически нетронутым, вот почему программы восстановления могли работать; они просто восстановили файл, имя которого было удалено из каталога, но содержимое которого все еще оставалось на диске.
^ NTFS резервирует 12,5% объема для «зоны MFT», но только до тех пор, пока это пространство не понадобится другим файлам. (т. е. если том ~когда-либо~ заполнится более чем на 87,5%, нефрагментация MFT больше не может быть гарантирована.) ^{[ 5 ]}

Ссылки

^ Фишер, Райан (11 февраля 2022 г.). «Следует ли мне дефрагментировать мой SSD?» . ПК-геймер . Архивировано из оригинала 18 февраля 2022 г. Проверено 26 апреля 2022 г.
^ http://www.8bs.com/hints/083.txt - Описание ошибки расширения . невозможности
^ http://8bs.com/mag/1to4/basegd1.txt — возможная потеря данных из-за невозможности расширения . ошибки
^ Дусер, Джон Р.; Болоски, Уильям Дж. (июнь 1999 г.). «Масштабное исследование содержимого файловой системы» . Обзор оценки производительности ACM SIGMETRICS . 27 (1): 59–70. дои : 10.1145/301464.301480 .
^ Jump up to: ^а ^б «Как NTFS резервирует место для своей главной таблицы файлов (MFT)» . Learn.microsoft.com . Майкрософт . Проверено 22 октября 2022 г.
^ «ДискВоин в глубине» . Также мягкий . Проверено 22 октября 2022 г.
^ «Поддержание пиковой производительности Windows 2000 посредством дефрагментации» . Learn.microsoft.com . Майкрософт . Проверено 22 октября 2022 г.
^ Крайдер, Марк Х. (3 апреля 2006 г.). Будущие технологии хранения данных: взгляд за горизонт (PDF) . Всемирная конференция по сетям хранения данных. Технология Сигейт . Архивировано из оригинала (PDF) 17 июля 2006 года.
^ Jump up to: ^а ^б Маквой, LW; Клейман, С.Р. (зима 1991 г.). «Производительность файловой системы UNIX на уровне экстента» ( PostScript ) . Труды USENIX зима '91 . Даллас, Техас: Sun Microsystems, Inc., стр. 33–43 . Проверено 14 декабря 2006 г.
^ Jump up to: ^а ^б Гензельман, Скотт (3 декабря 2014 г.). «Настоящая и полная история: дефрагментирует ли Windows ваш SSD?» . Блог Скотта Хансельмана .
^ Смит, Кейт Арнольд (январь 2001 г.). «Бенчмарки файловой системы для конкретных рабочих нагрузок» (PDF) . Кембридж, Массачусетс : Гарвардский университет . Архивировано из оригинала (PDF) 17 ноября 2004 г. Проверено 14 декабря 2006 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Лейтон, Джеффри (29 марта 2009 г.). «От ext3 к ext4: Интервью с Теодором Цо» . Журнал Линукс . Куинстрит . Архивировано из оригинала 1 апреля 2009 года. {{cite journal}}: CS1 maint: неподходящий URL ( ссылка )
^ Сингх, Амит (май 2004 г.). «Фрагментация в томах HFS Plus» . Внутреннее устройство Mac OS X. Архивировано из оригинала 18 ноября 2012 г. Проверено 27 октября 2009 г.
^ Суини, Адам; Дусетт, Дуг; Ху, Вэй; Андерсон, Кертис; Нишимото, Майк; Пек, Джефф (январь 1996 г.). «Масштабируемость файловой системы XFS» (PDF) . Материалы ежегодной технической конференции USENIX 1996 г. Сан-Диего, Калифорния : Silicon Graphics . Проверено 14 декабря 2006 г.
^ Райзер, Ганс (6 февраля 2006 г.). «Файловая система Reiser4» . Google TechTalks . Архивировано из оригинала 19 мая 2011 года . Проверено 14 декабря 2006 г.
^ Сингх, Амит (2007). «12 Файловая система HFS Plus» . Внутреннее устройство Mac OS X: системный подход . Эддисон Уэсли . ISBN 0321278542 .

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

Смит, Кейт; Зельцер, Марго. Структура файла и производительность файловой системы (PDF) (бумага). Гарвардский университет .

[2] Некоторые файловые системы, такие как NTFS и ext2 +, могут заранее выделять пустые смежные регионы для специальных целей.

[3] Практика оставлять пространство, занимаемое удаленными файлами, практически нетронутым, вот почему программы восстановления могли работать; они просто восстановили файл, имя которого было удалено из каталога, но содержимое которого все еще оставалось на диске.

[8] NTFS резервирует 12,5% объема для «зоны MFT», но только до тех пор, пока это пространство не понадобится другим файлам. (т. е. если том ~когда-либо~ заполнится более чем на 87,5%, нефрагментация MFT больше не может быть гарантирована.) ^{[ 5 ]}

[1] Фишер, Райан (11 февраля 2022 г.). «Следует ли мне дефрагментировать мой SSD?» . ПК-геймер . Архивировано из оригинала 18 февраля 2022 г. Проверено 26 апреля 2022 г.

[4] ttp://www.8bs.com/hints/083.txt - Описание ошибки расширения . невозможности

[5] ttp://8bs.com/mag/1to4/basegd1.txt — возможная потеря данных из-за невозможности расширения . ошибки

[filesys-contents-6] Дусер, Джон Р.; Болоски, Уильям Дж. (июнь 1999 г.). «Масштабное исследование содержимого файловой системы» . Обзор оценки производительности ACM SIGMETRICS . 27 (1): 59–70. дои : 10.1145/301464.301480 .

[ntfs-reserves-space-for-mft-7] Jump up to: ^а ^б «Как NTFS резервирует место для своей главной таблицы файлов (MFT)» . Learn.microsoft.com . Майкрософт . Проверено 22 октября 2022 г.

[diskwarrior-hfs-hfsplus-9] «ДискВоин в глубине» . Также мягкий . Проверено 22 октября 2022 г.

[windows-2000-defrag-performance-10] «Поддержание пиковой производительности Windows 2000 посредством дефрагментации» . Learn.microsoft.com . Майкрософт . Проверено 22 октября 2022 г.

[seagate-future-11] Крайдер, Марк Х. (3 апреля 2006 г.). Будущие технологии хранения данных: взгляд за горизонт (PDF) . Всемирная конференция по сетям хранения данных. Технология Сигейт . Архивировано из оригинала (PDF) 17 июля 2006 года.

[mcvoy-extent-12] Jump up to: ^а ^б Маквой, LW; Клейман, С.Р. (зима 1991 г.). «Производительность файловой системы UNIX на уровне экстента» ( PostScript ) . Труды USENIX зима '91 . Даллас, Техас: Sun Microsystems, Inc., стр. 33–43 . Проверено 14 декабря 2006 г.

[:0-13] Jump up to: ^а ^б Гензельман, Скотт (3 декабря 2014 г.). «Настоящая и полная история: дефрагментирует ли Windows ваш SSD?» . Блог Скотта Хансельмана .

[workload-benchmarks-14] Смит, Кейт Арнольд (январь 2001 г.). «Бенчмарки файловой системы для конкретных рабочих нагрузок» (PDF) . Кембридж, Массачусетс : Гарвардский университет . Архивировано из оригинала (PDF) 17 ноября 2004 г. Проверено 14 декабря 2006 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[15] Лейтон, Джеффри (29 марта 2009 г.). «От ext3 к ext4: Интервью с Теодором Цо» . Журнал Линукс . Куинстрит . Архивировано из оригинала 1 апреля 2009 года. {{cite journal}}: CS1 maint: неподходящий URL ( ссылка )

[16] Сингх, Амит (май 2004 г.). «Фрагментация в томах HFS Plus» . Внутреннее устройство Mac OS X. Архивировано из оригинала 18 ноября 2012 г. Проверено 27 октября 2009 г.

[xfs-scalability-17] Суини, Адам; Дусетт, Дуг; Ху, Вэй; Андерсон, Кертис; Нишимото, Майк; Пек, Джефф (январь 1996 г.). «Масштабируемость файловой системы XFS» (PDF) . Материалы ежегодной технической конференции USENIX 1996 г. Сан-Диего, Калифорния : Silicon Graphics . Проверено 14 декабря 2006 г.

[reiser4-google-18] Райзер, Ганс (6 февраля 2006 г.). «Файловая система Reiser4» . Google TechTalks . Архивировано из оригинала 19 мая 2011 года . Проверено 14 декабря 2006 г.

[osx-intern-19] Сингх, Амит (2007). «12 Файловая система HFS Plus» . Внутреннее устройство Mac OS X: системный подход . Эддисон Уэсли . ISBN 0321278542 .

[ 1 ]

[ а ]

[ б ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ с ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]