Несуперечливість у файловій системі

Найпростіше запобігти суперечливостям файлової системи, забезпечивши синхронні операції записування. Ідея проста: виконуючи записування блоку на диск, необхідно дочекатися від диска підтвердження перед тим, як записувати наступний блок.

Насправді такий підхід не може бути застосований для всіх операцій записування (інакше продуктивність знизилася б неприпустимо, наприклад, перестало б працювати кешування). Треба зрозуміти, для якої підмножини операцій його застосування не призводить до неприйнятних результатів. Для цього розглянемо, які суперечливості можуть бути у файловій системі. Як приклад візьмемо індексоване розміщення файлів.

Наведемо кілька правил (інваріантів), які треба виконувати в несуперечливій файловій системі.

· Усі вільні блоки мають перебувати в списку вільних блоків (і навпаки, всі елементи списку вільних блоків мають справді бути вільними).

· Дисковий блок має бути використаний тільки одним файлом (два індексних дескриптори не можуть вказувати на один і той самий блок).

· Лічильник жорстких зв'язків файлового дескриптора має збігатися із числом жорстких зв'язків, що справді посилаються на нього.

Розглянемо проблеми, що виникають у разі порушення цих інваріантів.

Некоректний список вільних блоків

Для ілюстрації цієї проблеми почнемо з послідовності кроків під час виконання операції створення файла.

1. Шукають у поточному робочому каталозі файл із тим самим ім'ям. Якщо він є, повертають помилку, у протилежному випадку відшукують місце для елемента каталогу.

2. Шукають вільний індексний дескриптор. Знайдений дескриптор позначають як виділений.

3. Ім'я та номер дескриптора додають в елемент каталогу.

У разі збою між кроками 2 і 3 дескриптор залишиться позначений як виділений, але фактично таким не буде. У результаті з'являються втрачені дані.

Проблема втрачених даних виникає під час ситуації, коли невикористані ресурси позначають як виділені, звичайно це відбувається за наявності списку або карти вільних блоків. Для запобігання її появі потрібно дотримуватися такого правила: не можна постійно зберігати покажчик на об'єкт, що перебуває у списку вільних блоків (як це зробили на кроці 2).

Подібна проблема виникає і під час вивільнення блоків. Як приклад можна навести операцію скорочення файла, коли довжину файла скорочують, а зайві блоки вивільняють. її можна виконувати так.

1. Покласти покажчик на блок в індексному дескрипторі рівним нулю.

2. Помістити блок у список вільних блоків.

Якщо поміняти місцями кроки 1 і 2 (спочатку помістити блок у список вільних блоків, а потім вилучити із дескриптора), то збій між цими діями спричиняє невірне припущення, що блок вивільнений, хоча фактично вільним він не є (на нього вказує індексний дескриптор).

Тому можна сформулювати друге правило, протилежне до першого: повторно використати ресурс можна тільки після того, як були обнулені всі покажчики на нього.

Для відновлення списку вільних блоків після збою можна застосовувати й оптимістичний підхід, реалізований утилітою типу fsck. Для цього використовують збирання сміття із маркуванням і очшценням (див. розділ 10.6.2). Спочатку припускають, що список вільних блоків включає всі блоки диска (якщо він реалізований як бітова карта, це зробити легко); це буде етап маркування. Після цього потрібно почати із кореневого каталогу і рекурсивно обійти всі підкаталоги, вилучаючи всі їхні блоки зі списку вільних блоків - це буде етап очищення. Цей алгоритм одночасно відновлює виділені блоки, позначені як вільні, та втрачені блоки. Його недоліком є те, що потрібен обхід усього дерева каталогів (для великих файлових систем це може займати багато часу).

Некоректні значення лічильника зв'язків

Для ілюстрації цієї проблеми розглянемо послідовність кроків під час виконання операції вилучення жорсткого зв'язку для файла (unlink).

1. Здійснюють обхід каталогу в пошуку цього імені. Якщо його не знайдено, повертають помилку.

2. Очищають елемент каталогу.

3. Зменшують лічильник жорстких зв'язків індексного дескриптора.

4. Якщо лічильник жорстких зв'язків дорівнює нулю, очищають індексний дескриптор і всі блоки, на які він вказує.

У разі збою між кроками 2 і 3 буде отримано надто велике значення лічильника зв'язків (зв'язок вилучений, а лічильник не змінився). Блоки, що належать до цього файла, ніколи не вивільняться (оскільки лічильник зв'язків тепер ніколи не досягне нуля). Для великих файлів це може спричинити істотні втрати дискового простору.

Припустимо, що очищення елемента каталогу і зменшення лічильника поміняли місцями (тобто спочатку зменшують лічильник, а потім вилучають зв'язок). Тепер, якщо збій відбудеться між цими двома операціями, буде надто мале значення лічильника зв'язків (коли зв'язків стане більше, ніж значення лічильника). Ця проблема ще серйозніша, ніж попередня, оскільки використовувані блоки будуть позначені як вільні. Є багато різних проявів цієї проблеми: від «зниклого» вмісту файлів (що перейшов до іншого файла) до переміщення у вільні блоки вмісту системних файлів, наприклад, файла паролів.

Є два способи боротьби з цією проблемою.

1. Оптимістичний — обходити дерево каталогів і коригувати значення лічильника зв'язків для кожного індексного дескриптора в рамках утиліти типу fsck.

2. Песимістичний - ніколи не зменшувати лічильник зв'язків до обнулення покажчика на об'єкт (наприклад, завжди синхронно зберігати на диску список вільних блоків під час кожного розміщення та вивільнення блока). При цьому використовують 1-2 додаткові операції записування на диск.

Приклад організації боротьби із суперечливостями у FFS

На завершення наведемо приклад реалізації описаних раніше підходів у вже знайомій файловій системі FFS.

Насамперед зазначимо, що ця файлова система поєднує оптимістичний і песимістичний підходи до реалізації суперечливості.

3 одного боку, вона використовує утиліту fsck для корекції списку вільних блоків і значень лічильника зв'язків відповідно до описаних раніше алгоритмів.

3 іншого боку, реалізація песимістичних підходів до суперечності ґрунтується на виконанні двох інваріантів.

1. Усі імена в каталогах завжди посилаються на коректні індексні дескриптори.

2. Жоден блок не використовується більш як одним індексним дескриптором.

Підтримку справедливості цих інваріантів реалізують на основі виконання трьох правил.

1. Новий індексний дескриптор зберігають на диску до того, як ім'я зв'язку додають у каталог.

2. Ім'я зв'язку вилучають із каталогу до вивільнення індексного дескриптора.

3. Вивільнений індексний дескриптор зберігають на диску до того, як його блоки помістять у список вільних блоків.

У результаті створення і вилучення файла необхідні по дві синхронні операції обміну із диском.

Ще однією властивістю FFS є можливість пошуку втрачених індексних дескрипторів. Вони можуть бути втрачені, коли каталог буде ушкоджено або відбудеться збій до встановлення жорсткого зв'язку. Такий пошук ґрунтується на двох особливостях реалізації системи.

1. Індексні дескриптори заздалегідь розміщують у відомих місцях на диску. У результаті місцезнаходження кожного дескриптора може бути знайдене незалежно від того, є на нього покажчики чи ні.

2. Вміст вільних індексних дескрипторів заповнюють нулями. Із цього система може зробити висновок, що будь-який дескриптор з ненульовим вмістом дотепер використовують. Під час обходу fsck поміщає дескриптори з ненульовим вмістом, для яких не задано жодного зв'язку, у спеціальний каталог /lost+found.

Зазначимо, що більшість названих вирішень використовують і у файловій системі ext2fs для Linux.

 

Журнальні файлові системи

Великий обсяг дисків робить виконання програми перевірки і відновлення під час завантаження після збою досить тривалим процесом (для диска розміром у десятки Гбайтів така перевірка може тривати кілька годин). У деяких ситуаціях (наприклад, на серверах баз даних з оперативною інформацією) подібні затримки із відновленням роботоздатності системи після кожного збою можуть бути недопустимими. Необхідно організувати збереження інформації таким чином, щоб відновлення після збою не вимагало перевірки всіх структур даних на диску. Спроби розв'язати цю проблему привели до виникнення журнальних файлових систем (logging file systems).

Основна мета журнальної файлової системи - надати можливість після збою, замість глобальної перевірки всього розділу, робити відновлення на підставі інформації журналу (log) - спеціальної ділянки на диску, що зберігає опис останніх змін. Використання журналу засноване на важливому спостереженні: під час відновлення після збою потрібно виправляти тільки інформацію, яка перебувала у процесі зміни у момент цього збою. Це та інформація, що не встигла повністю зберегтися на диску (зазвичай вона займає тільки малу його частину).

Основна ідея таких файлових систем - виконання будь-якої операції зміни даних на диску у два етапи.

1. Спочатку інформацію зберігають у журналі (у ньому створюють новий запис). Таку операцію називають випереджувальним записуванням (write-ahead) або веденням журналу (journaling).

2. Коли ця операція повністю завершена (було підтверджено зміну журналу), інформацію записують у файлову систему (можливо, не відразу). Після того, як зміну журналу було підтверджено, усі записи в журналі, створені на етапі 1, стають непотрібними і можуть бути вилучені. Зауважимо, що синхронізація журналу і реальних даних на диску може відбуватися і явно; виконання такої операції називають точкою перевірки (checkpoint). Дані із журналу після цієї перевірки теж можуть бути вилучені.

Читання даних завжди здійснюють із файлової системи, журнал у цій операції не бере участі ніколи.

Після того, як інформація про зміни потрапила в журнал, самі ці зміни можуть бути записані у файлову систему не відразу. Часто об'єднують кілька операцій зміни даних у файловій системі, якщо вони належать до одного кластера, для того щоб виконати їх усі разом. У результаті кількість операцій звертання до диска істотно знижується. Ще однією важливою обставиною підвищення продуктивності, є той факт, що операції записування в журнал виконують послідовно і без пропусків. Найкращої продуктивності можна домогтися, помістивши журнал на окремий диск.

Розмір журналу має бути достатній для того, щоб у ньому помістилися ті зміни, які на момент збою можуть перебувати у пам'яті.

Є різні підходи до того, яка інформація має зберігатися в журналі.

· Тільки описи змін у метаданих (до метаданих належить вся службова інформація: індексні дескриптори, каталоги, імена тощо). Такий журнал забезпечує несуперечливість файлової системи після відновлення, але не гарантує відновлення даних у файлах. 3 погляду продуктивності це найшвидший спосіб.

· Змінені кластери повністю. Такий підхід не вирізняється високою продуктивністю, натомість з'являється можливість відновити дані повністю. Файлові системи звичайно дають змогу вибрати варіант збереження інформації в журналі (це може бути зроблено під час монтування системи). На практиці вибір підходу залежить від конкретної ситуації.

Програма відновлення файлів має розрізняти дві ситуації.

1. Збій відбувся до підтвердження зміни журналу. У цьому разі здійснюють відкат (rollback): цю зміну ігнорують, і файлова система залишається в несуперечливому стані, у якому вона була до операції. Зазначимо, що такі атомарні операції мають багато спільного із транзакціями — атомарними операціями у базі даних (відомо, що сервери баз даних для підтримки транзакцій також реалізують роботу із журналом).

2. Збій відбувся після підтвердження зміни журналу. За цієї ситуації потрібно відновити дані на підставі інформації журналу (такий процес ще називають відкатом уперед - rolling forward).

Журнал транзакцій у базі даних дає змогу підтверджувати і скасовувати визначений користувачем набір операцій зміни даних, що і є транзакцією. На відміну від цього, підтвердження і відкат на підставі інформації журналу файлової системи можуть зачіпати тільки результати виконання окремих системних ви-кликів. Припустимо, що відбувається копіювання великого файла частинами, при цьому алгоритм копіювання в циклі звертається до системного виклику write() для копіювання кожної частини. Коли під час такого копіювання відбудеться збій між окремими викликами write(), то за будь-яких стратегій реалізації журналу файл залишиться скопійованим неповністю — не можна підтверджувати або скасовувати кілька викликів як єдине ціле.

Сучасні операційні системи все більше переходять до використання журнальних файлових систем; наприклад, для Linux є декілька їх реалізацій (ext3fs, ReiserFS, XFS). Файлова система NTFS також підтримує ведення журналу.

Розділ 4

Реалізація файлових систем

· Інтерфейс файлової системи VFS

· Файлові системи Linux: ext2fs, ext3fs i /proc

· Файлові системи лінії FAT

· Файлова система NTFS

· Системний реєстр Windows XP