Log-structured File System (BSD)
| LFS (BSD) | |
|---|---|
| Розробник | Марго Селтцер, Кіт Бостік, Маршалл Кірк Макк'юсік, Карл Стелін |
| Повна назва | Log-structured File System |
| Представлено | 1992 (4.4BSD-Alpha); 1993 (4.4BSD) (4.4BSD-Alpha) |
| Структура | |
| Вміст директорій | Каталоги у форматі UFS |
| Виділення простору під файли | Сегментований журнал, карта індексних дескрипторів |
| Обмеження | |
| Можливості | |
| Операційні системи в яких підтримується | NetBSD (експериментальна підтримка) |
Log-structured File System (LFS, також BSD-LFS) — файлова система із послідовним записуванням даних і метаданих, створена для операційних систем родини BSD та включена до випусків 4.4BSD. Вона є окремою реалізацією концепції журнально-структурованих файлових систем: зміни не перезаписують блоки на попередніх місцях, а додаються до журналу, організованого в сегменти. На відміну від файлових систем із допоміжним журналом змін, у LFS журнал є основним способом зберігання даних. Система використовує структури даних, споріднені з UFS, і механізм очищення сегментів для повторного використання простору.[1]
LFS збереглася в NetBSD, де підтримуються засоби створення, монтування й обслуговування таких томів. Водночас у документації NetBSD її класифіковано як експериментальну файлову систему.[2]
Концепцію файлової системи з послідовним записом розробляли наприкінці 1980-х років Джон Остерхут та Фред Дугліс. Згодом Мендель Розенблюм і Остерхут створили експериментальну Sprite LFS для дослідницької операційної системи Sprite. Її архітектура мала зменшити кількість переміщень головок магнітного диска під час запису дрібних файлів завдяки накопиченню змін і записуванню їх великими послідовними порціями.[3]
Власну реалізацію для UNIX і BSD розробила група Марго Селтцер, Кіта Бостіка, Маршалла Кірка Макк'юсіка та Карла Стеліна. Роботу над нею розпочали 1991 року. На відміну від дослідницької Sprite LFS, BSD-LFS інтегрували в підсистему VFS і спроєктували для спільного використання значної частини коду з традиційною файловою системою Berkeley Fast File System (FFS). Ранню версію включили до 4.4BSD-Alpha (1992), а наступну — до 4.4BSD (1993); архітектуру та результати випробувань дослідники опублікували 1993 року.[1][4]
Реалізація продовжила існування в NetBSD. У випуску NetBSD 4.0 (2007) повідомляли про суттєві виправлення стабільності, новий процес очищення сегментів і можливість використовувати LFS як кореневу файлову систему.[5] Подальша розробка не припинилася: у змінах гілки NetBSD 12.0 за 2025–2026 роки зазначено реалізацію відновлення записів у ядрі (roll-forward), ядерного очищувача сегментів і перевірки 64-бітних томів LFS.[6]
LFS ділить простір тому на сегменти, які можуть розташовуватися в різних місцях фізичного диска, але логічно становлять безперервний журнал. Кожен сегмент містить службовий опис (segment summary), блоки даних і метадані. Службовий опис містить відомості про записані блоки, контрольні суми та покажчик на наступний сегмент. Змінені блоки спершу накопичуються у буферному кеші, після чого система записує їх у вільну ділянку журналу разом із необхідними метаданими. За недостатньої кількості змін може записуватися не весь сегмент, а його частина.[1]
Замість зміни даних на місці LFS записує їхню нову версію. Оновлюються також непрямі блоки, що містять адреси даних, і індексні дескриптори (inode). Оскільки фізичне розташування inode змінюється, система використовує окрему карту inode (inode map), яка пов'язує номер дескриптора з його актуальною адресою на диску. Завдяки цьому зберігається можливість довільного читання файлів, хоча їхні нові версії додаються до журналу послідовно.[1]
У BSD-LFS використано близькі до FFS формати inode, непрямих блоків і каталогів. Спільні процедури роботи з каталогами, правами доступу та іншими властивостями файлів винесли до шару UFS, а компоненти FFS і LFS окремо відповідають за розміщення блоків та операції введення-виведення. У праці 1993 року автори зазначали, що такий поділ дозволив повторно використати близько 60 % коду FFS.[7]
Після перезапису або видалення файлу його застарілі блоки можуть залишатися у старих сегментах, але вже не вважатися чинними. Щоб повернути зайнятий ними простір, спеціальний компонент — очищувач сегментів (segment cleaner) — вибирає сегменти, визначає блоки, на які ще є посилання, переносить їх до нового місця журналу, а звільнений сегмент позначає придатним для повторного використання. Для вибору сегментів він використовує таблицю їхнього заповнення та інші службові відомості.[8]
В оригінальній BSD-LFS очищувач працював у просторі користувача, взаємодіючи з ядром через системні виклики. Цей підхід спрощував експерименти з алгоритмами вибору сегментів. У NetBSD тривалий час використовували програму lfs_cleanerd; з 2025 року розробники також реалізували очищувач у ядрі, а у змінах до NetBSD 12.0 ядерний варіант визначено типовим для mount_lfs.[9][6]
Періодично LFS записує узгоджений стан службових структур — контрольну точку (checkpoint). Після аварійного завершення роботи система може відновити стан від останньої контрольної точки, послідовно переглянувши пізніші записи журналу (roll-forward). Це зменшує обсяг даних, які потрібно переглянути для відновлення після збою. Водночас перевірка логічної цілісності каталогів і покажчиків, зокрема після пошкодження носія, залишається окремим завданням; механізм журналу не усуває потреби в таких перевірках за всіх обставин.[10]
Послідовне групування записів покликане зменшити витрати на пошук доріжок під час роботи з магнітними дисками. Випробування розробників 1993 року виявили переваги BSD-LFS над традиційною FFS під час окремих операцій зі створення та записування файлів. Проте вдосконалена FFS із групуванням читань і записів у низці тестів показувала подібні або кращі результати. Отже, перевага LFS залежить від характеру навантаження, а не є універсальною.[11]
Головний додатковий видаток — очищення старих сегментів: щойно вільного місця стає менше, потрібно дедалі частіше копіювати чинні блоки, а така робота конкурує з операціями користувача. В експериментах із транзакційним навантаженням при заповненні диска на 85 % витрати на очищення настільки знизили пропускну здатність, що BSD-LFS поступилася FFS. Іншою проблемою є фрагментація файлів, блоки яких змінюються протягом тривалого часу: нові фрагменти можуть опинятися далеко від попередніх.[11]
Послідовна організація журналу сама собою не означає наявності функцій знімків файлової системи чи збереження попередніх версій файлів. Автори BSD-LFS розглядали такі можливості як перспективні розширення, але вони не були частиною початкової реалізації.[11]
Для роботи з LFS у NetBSD передбачено службові програми newfs_lfs (створення файлової системи), mount_lfs (монтування), fsck_lfs (перевірка) та інструменти обслуговування сегментів. Тип розділу позначається як 4.4LFS. У newfs_lfs можна вибирати формат тому версії 1 або 2 (типово — версія 2), а також 32- чи 64-бітне представлення службових структур; для 32-бітного варіанта документація встановлює межу розміру тому 2 ТБ.[12]
Попри наявність засобів адміністрування та численні виправлення, у документації про параметри ядра NetBSD LFS позначено як експериментальну. Тому факт наявності коду й підтримки у системі не слід ототожнювати з рекомендацією використовувати LFS для зберігання критично важливих даних.[2]
- 1 2 3 4 Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (1993). An Implementation of a Log-Structured File System for UNIX (PDF). USENIX Winter 1993 Conference. USENIX Association. с. 307—315. Процитовано 11 листопада 2026.
- 1 2 options(4) — NetBSD Manual Pages. The NetBSD Project. Процитовано 11 листопада 2026.
- ↑ Rosenblum, Mendel; Ousterhout, John K. (1992). The Design and Implementation of a Log-Structured File System (PDF). ACM Transactions on Computer Systems. 10 (1): 26—52. doi:10.1145/146941.146943. Процитовано 11 листопада 2026.
- ↑ bsd-family-tree. FreeBSD Source Tree. The FreeBSD Project. Процитовано 11 листопада 2026.
- ↑ Announcing NetBSD 4.0. The NetBSD Project. 19 грудня 2007. Процитовано 11 листопада 2026.
- 1 2 Significant changes from NetBSD 11.0 to 12.0. The NetBSD Project. Процитовано 11 листопада 2026.
- ↑ Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (1993). An Implementation of a Log-Structured File System for UNIX (PDF). USENIX Winter 1993 Conference. USENIX Association. с. 314—318. Процитовано 11 листопада 2026.
- ↑ Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (1993). An Implementation of a Log-Structured File System for UNIX (PDF). USENIX Winter 1993 Conference. USENIX Association. с. 308—309, 313—315. Процитовано 11 листопада 2026.
- ↑ lfs_cleanerd(8) — NetBSD Manual Pages. The NetBSD Project. Процитовано 11 листопада 2026.
- ↑ Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (1993). An Implementation of a Log-Structured File System for UNIX (PDF). USENIX Winter 1993 Conference. USENIX Association. с. 309—312. Процитовано 11 листопада 2026.
- 1 2 3 Seltzer, Margo; Bostic, Keith; McKusick, Marshall Kirk; Staelin, Carl (1993). An Implementation of a Log-Structured File System for UNIX (PDF). USENIX Winter 1993 Conference. USENIX Association. с. 319—325. Процитовано 11 листопада 2026.
- ↑ newfs_lfs(8) — NetBSD Manual Pages. The NetBSD Project. Процитовано 11 листопада 2026.
- An Implementation of a Log-Structured File System for UNIX — праця розробників BSD-LFS (1993, PDF).
- newfs_lfs(8) і mount_lfs(8) — сторінки довідника NetBSD.