Фрагментація файлової системи
Фрагмента́ція фа́йлової систе́ми (старіння файлової системи) — це неспроможність файлової системи розмістити пов'язані дані послідовно (неперервно); явище притаманне файловим системам, що дозволяють пряму модифікацію даних. Є особливим випадком фрагментації даних.
У механічних дискових накопичувачах фрагментація файлової системи збільшує кількість переміщень головки зчитування даних, що, в свою чергу, зменшує пропускну здатність. Щоб позбутися існуючої фрагментації потрібно перемістити файли в суміжні області, окремо від вільного простору. Цей процес називається дефрагментацією і виконується спеціальними утилітами, що часто входять до складу операційної системи.
Існує багато алгоритмів і правил дефрагментації.
Коли файлова система вперше ініціалізована на диску (деякий розділ форматований, використовуючи цю файлову систему), цей розділ містить лише кілька невеликих внутрішніх структур, або, іншими словами, є неперервним блоком вільного простору (з точки зору файлової системи).[1] Це означає, що алгоритм розподілу даних може розмістити новостворені файли будь-де на диску. Протягом деякого часу після створення файли у файловій системі можуть розміщуватися майже оптимально. Коли встановлюється операційна система та програми, або розпаковуються інші архіви, послідовне розміщення файлів означає, що пов'язані файли, найбільш імовірно, будуть розміщені близько один біля одного.
Проте, щойно існуючі файли видаляються або зменшуються в розмірі, утворюються нові області вільного простору. Коли ж файли доповнюються, часто неможливо продовжити запис з місця, де файл завершився, бо там можуть вже бути розміщені інші файли, тому потрібно створити новий фрагмент. З плином часу через ці фактори вільний простір разом із файлами, які часто доповнюються, як правило, фрагментується все більше і більше. Існування коротких вільних областей означає також, що файлова система більше не спроможна розмістити нові, більш-менш великі файли неперервно і повинна розділяти їх на фрагменти. Особливо це справджується, коли файлова система більш заповнена — чим більша довжина вільних областей, тим менша імовірність їхньої появи.
Потрібно зазначити, що сказане є спрощеним поданням досить складної теми. Метод, який буде тут пояснено, був загальноприйнятим при розподілі файлів на диску та інших носіях з довільним доступом до пам'яті протягом більш ніж 30 років. Деякі операційні системи не просто розподіляють файли один за одним, інші використовують різні методи, щоб запобігти фрагментації, але загалом рано чи пізно через наявні причини з плином часу буде виникати фрагментація на будь-якій системі, на якій файли регулярно видаляються чи змінюються у розмірі.
Розглянемо наступний сценарій, як показано на рисунку 2.
Новий диск містить 5 збережених файлів A, B, C, D та E, і кожен файл займає 10 блоків пам'яті (тут розмір блоку неважливий). Оскільки вільний простір є неперервним, файли розміщуються один за одним (Приклад (1)).
Якщо видалити файл B, утворюється друга область з 10 блоків вільного простору. Файлова система може дефрагментувати диск одразу після видалення, що призведе до сильного зменшення продуктивності в непередбачувані моменти, але в загальному, там просто залишається порожнє місце, яке позначається доступним для подальшого використання, і заповнюється за потреби[2] (Приклад (2)).
Тепер, коли новий файл потребує 7 блоків пам'яті, він може бути розміщений на місці колишнього файлу B, і ще залишиться 3 порожні блоки після нього (Приклад (3)). Якщо додається новий файл G, який потребує лише 3 блоки пам'яті, він може зайняти місце після F і перед C (Приклад (4)).
Згодом, якщо потрібно збільшити файл F, оскільки простір після нього вже зайнято, існує три можливих варіанти: (1) додати новий блок в іншому місці та зазначити, що F має другу частину; (2) перемістити файли, які заважають розширенню, в інше місце так, щоб F залишився неперервним; або (3) перемістити сам файл F, щоб він залишився неперервним, але більшого розміру. Другий варіант швидше за все є непрактичним через негативний вплив на продуктивність, так само як і третій у випадку дуже великого файлу. Дійсно, третій варіант є неможливим, коли на диску немає неперервної області вільної пам'яті достатньо великої, щоб розмістити новий файл. Отже, загальноприйнято створювати нову частину в іншому місці і прив'язувати її як продовження попереднього файлу (Приклад (5)).
Дані, додані до кінця файлу F, будуть частиною його продовження. Але якщо є так багато даних, що їх не можна помістити після цього продовження, тоді буде створена інша частина і так далі. Зрештою, файлова система буде мати порожні сегменти в багатьох місцях, і деякі файли можуть бути розділені на багато частин. Час доступу до цих файлів (або всіх файлів) може сильно збільшитися.
Підбиваючи підсумок, можна навести чинники, які, як правило, спричиняють фрагментацію або сприяють їй:
- мало вільного місця;
- часте видалення, зменшення чи розширення файлів;
- надмірне використання фрагментованих файлів.
Деякі ранні файлові системи не могли фрагментувати файли. Одним з таких прикладів була файлова система Acorn DFS, яка використовувалася на BBC Micro. Через неспроможність розділяти файли на частини деколи з'являлися повідомлення помилки «can't extend» («не можна розширити») і користувач часто не міг зберегти файл, навіть якщо на диску було достатньо вільного простору.
DFS використовувала дуже просту структуру диска, і файли на ньому можна було знайти лише за їхньою довжиною і сектором початку. Це означало, що всі файли повинні були складатися з неперервних блоків і фрагментація не була можливою. За прикладом вище, спроба розширити файл F на кроці 5 не вдалася б на такій системі з повідомленням про помилку розширення. Не зважаючи на те, скільки сумарно вільної пам'яті доступно на диску, цей файл розширити було неможливо.
Стандарти обробки помилок на той час були дуже примітивними і, в будь-якому разі, програми, які ледве вміщалися в обмеженій пам'яті BBC Micro, рідко коли могли собі дозволити марнувати цю пам'ять на спроби елегантної обробки помилок. Замість цього користувач був би переміщений назад у командний рядок з повідомленням про помилку розширення, і всі дані, які потрібно було доповнити до файлу, були би втрачені. Розчарування було б більшим, якщо б користувач заздалегідь перевірив би вільне місце на диску і його було б достатньо. Навіть якщо може бути достатньо вільного простору на диску, той факт, що його не було там де потрібно, не можна було побачити без детального аналізу чисел з дискового каталогу. На додаток до цього, майже всі без винятку користувачі DFS використовували касети для зберігання файлів, на яких не виникала ця помилка. Перехід на дискети був досить дорогим, але він звільнив користувачів від ненадійності і вкрай низької швидкості роботи касетних систем, де оновлення може без попередження привести до втрати даних з їх останніх змін.[3][4]
 | Цей розділ потребує доповнення. |
Фрагментація файлової системи, за прогнозами, стане більш проблематичною на новіших комп'ютерах через збільшення різниці між швидкістю послідовного доступу і затримкою обертання (і меншого часу пошуку продовження) на жорстких дисках споживчого класу,[5] на яких зазвичай і встановлюють файлові системи. Через це фрагментація — це важлива проблема в дослідженнях та дизайні сучасних файлових систем. Стримування фрагментації залежить не тільки від внутрішнього формату файлової системи на диску, але також значною мірою від її реалізації.[6]
У простих тестах продуктивності файлової системи фактор фрагментації часто опускається через справжнє так зване «старіння» файлової системи, яке складно змоделювати. Швидше за все, для простоти порівняння більшість тестів продуктивності файлової системи часто виконують на порожніх (або мало користованих) файлових системах, і не дивно, що результати можуть сильно відрізнятися в залежності від характеру її використання в реальному житті.[7]
Фрагментація файлової системи має значно менший вплив на продуктивність твердотілих накопичувачів (SSD) через те, що на них немає часу механічного пошуку, як на носіях обертання, хоча додаткові непослідовні операції вводу/виводу впливають на продуктивність системи, і багато архітектур файлових систем споживають додаткові внутрішні ресурси, коли накопичувач фрагментований.
Фрагментація файлової системи може з'являтися на кількох рівнях:
- фрагментація окремих файлів і їхніх метаданих;
- фрагментація вільного простору, яка ускладнює неперервне розміщення нових файлів;
- погіршення знаходження посилань між окремими, але пов'язаними файлами.
Фрагментація окремих файлів виникає, коли цілий файл розділяється на багато частин (їх називають продовженнями у відповідних файлових системах). Файлові системи для жорстких дисків намагаються зберігати файли неперервно, але це не завжди можливо без значної втрати продуктивності. Знаряддя (утиліти) для перевірки файлової системи та її дефрагментації зазвичай відповідають користувачу про фрагментацію файлів у статистиці «відсотка фрагментації» й, іноді, карти файлової системи.
Фрагментація вільного (невиділеного) простору виникає, коли є кілька невикористаних областей файлової системи, де можуть бути записані файли або метадані. Небажані вільні області зазвичай утворюються під час видалення або зменшення файлів, але файлова система також може навмисно вставляти порожні фрагменти («бульбашки») для того, щоб полегшити розширення сусідніх файлів (див. запобігання фрагментації нижче).
Сегментація файлів, яку також називають фрагментацією пов'язаних файлів або фрагментацією рівня програми, — ускладнення пошуку посилань на носії між пов'язаними файлами. На відміну від двох попередніх типів фрагментації, розсіювання файлів — це менш чітке поняття, оскільки воно сильно залежить від характеру доступу до файлів конкретної програми. Це також робить об'єктивне і навіть приблизне оцінювання дуже складним. Проте, можливо, це найважливіший тип фрагментації, оскільки, як показали дослідження, найчастіше використовувані файли, як правило, малого розміру, порівняно з доступною пропускною здатністю диска.[8]
Для запобігання фрагментації пов'язаних файлів і покращення пошуку за посиланням (у цьому випадку близькість файлів) потрібно робити припущення й експерименти щодо поведінки програм на окремо взятій файловій системі. Досить часто припускають, що виправдано тримати малі файли в одному каталозі разом і розмістити їх у природний для файлової системи спосіб. У той час, як це припущення часто справджується, воно не завжди має місце. Наприклад, програма може зчитувати кілька різних файлів, можливо в різних каталогах, в тому ж порядку, в якому вони були записані. Отже, файлова система, яка просто записує всі файли послідовно, може працювати швидше для даної програми.
Маючи кілька методів позбуття фрагментації, зазвичай, виділяють дві категорії: примітивні та методи зворотної сили. Але через складність передбачення характеру доступу до файлів ці алгоритми часто мають евристичну природу і можуть погіршувати продуктивність при несподіваних навантаженнях.
Примітивні методи намагаються тримати фрагментацію на мінімумі під час запису даних на диск. Найпростіше — додавати дані до існуючих фрагментів, де це можливо, замість виділення нових блоків для нових фрагментів.
Більшість сучасних операційних систем намагаються наперед виділити більші шматки або шматки з різних фрагментів вільного простору — продовження файлів, які часто доповнюються. Це переважно запобігає фрагментації, коли кілька файлів одночасно доповнюються, таким чином запобігаючи їх сильному переплетенню.[6]
Якщо відомий кінцевий розмір потрібного файлу, можна наперед виділити пам'ять під цілий файл. Наприклад, файл підкачки Microsoft Windows може динамічно змінювати розмір, і тому може виявитися сильно фрагментованим. Цьому можна запобігти вказуючи однаковий мінімальний і максимальний розмір файлу підкачки і наперед ефективно виділити пам'ять під весь файл.
BitTorrent та інші peer-to-peer програми спільного використання файлів обмежують фрагментацію, наперед виділяючи пам'ять під цілий файл, коли починається його завантаження.[9]
Відносно новим методом є відкладене виділення пам'яті у XFS, HFS+[10] and ZFS; такий же метод називається allocate-on-flush на reiser4 і ext4. Коли виконується запис, резервуються блоки файлової системи, але самі файли ще не записуються. Пізніше, коли файлова система змушена зберігати зміни як наслідок тиску пам'яті чи проведення транзакції, розподілювач матиме більше інформації про характеристики файлів. Більшість файлових систем, які використовують цей підхід, намагаються неперервно записати файли в одній папці. Вважаючи, що читання з одної папки є загальновживаним, пошук посилань покращується.[11] Reiser4 також пропонує розміщувати файли у папці відповідно до хеш-таблиці папки, так що коли отримується доступ до файлів, у природному для файлової системи порядку (як записано у readdir), вони завжди зчитуються послідовно.[12]
Дефрагментацією є метод зворотної дії, що намагається зменшити фрагментацію, або негативні ефекти від фрагментації, після того, як вона вже виникла. Багато файлових/операційних систем надають інструменти для дефрагментації, які намагаються перевпорядкувати фрагменти файлів, і деколи зменшити їх розсіяність (тобто покращити їхню суміжність) зберігаючи або малі файли в папках чи дереві каталогів, або навіть послідовності файлів близько один біля одного на диску.
| Цей розділ потребує доповнення. |
Файлова система HFS Plus постійно дефрагментує файли менші 20 MiB і розділені на 8 або більше фрагментів, коли файл відкривається.[13]
Застаріла на сьогодні файлова система Commodore Amiga Smart File System (SFS) дефрагментувала себе, коли використовувалася. Процес дефрагментації має практично незалежні кроки (крім місця, над яким він працює), тому він може бути миттєво зупинений чи початий. Протягом дефрагментації цілісність даних не порушується як для звичайних так і для метаданих.
- ↑ Деякі файлові системи, такі як NTFS або ext2+, можуть під час ініціалізації виділяти довгі порожні регіони для спеціальних потреб.
- ↑ The practice of leaving the space occupied by deleted files largely undisturbed is why undelete programs were able to work; they simply recovered the file whose name had been deleted from the directory, but whose contents were still on disk.
- ↑ http://www.8bs.com/hints/083.txt - Description of the can't extend error
- ↑ http://8bs.com/mag/1to4/basegd1.txt - Possible data loss caused by the can't extend error
- ↑ Dr. Mark H. Kryder (3 квітня 2006). Future Storage Technologies: A Look Beyond the Horizon (PDF). Storage Networking World conference. Seagate Technology. Архів оригіналу (PDF) за 17 липня 2006. Процитовано 14 грудня 2006.
- ↑ а б L. W. McVoy, S. R. Kleiman (Winter 1991). Extent-like Performance from a UNIX File System. Proceedings of USENIX winter '91. Dallas, Texas: Sun Microsystems, Inc. с. pages 33–43. Архів оригіналу (PostScript) за 21 лютого 2007. Процитовано 14 грудня 2006.
{{cite conference}}:|pages=має зайвий текст (довідка) - ↑ Keith Arnold Smith (January 2001). Workload-Specific File System Benchmarks (PDF). Harvard University. Архів оригіналу (PDF) за 17 листопада 2004. Процитовано 14 грудня 2006.
- ↑ John R. Douceur, William J. Bolosky (June 1999). A Large-Scale Study of File-System Contents. ACM SIGMETRICS Performance Evaluation Review. Microsoft Research. 27 (1): 59—70. doi:10.1145/301453.301480.
- ↑ Jeff Layton (29 березня 2009). From ext3 to ext4: An Interview with Theodore Ts'o. Linux Magazine. Архів оригіналу за 27 травня 2015. Процитовано 27 травня 2015.
- ↑ Amit Singh (May 2004). Fragmentation in HFS Plus Volumes. Mac OS X Internals. Архів оригіналу за 18 листопада 2012. Процитовано 27 травня 2015.
- ↑ Adam Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, Geoff Peck (January 1996). Scalability in the XFS File System (PDF). Proceedings of the USENIX 1996 Annual Technical Conference. San Diego, California: Silicon Graphics. Архів оригіналу (PDF) за 18 березня 2007. Процитовано 14 грудня 2006.
- ↑ Hans Reiser (6 лютого 2006). The Reiser4 Filesystem. A lecture given by the author, Hans Reiser. Архів оригіналу (Google Video) за 19 травня 2011. Процитовано 14 грудня 2006.
- ↑ Amit Singh (19 червня 2006). The HFS Plus File System. Mac OS X Internals: A Systems Approach. Addison Wesley. ISBN 0-321-27854-2.