System plików, który wybrać ....doc

Artykuł pochodzi
z CHIP-a nr 10/2002

Tradycyjne systemy plików, stosowane w wielu (zwłaszcza "domowych") systemach operacyjnych, mają sporo wad. Podstawową jest problem z odzyskaniem danych, jaki pojawia się w momencie, gdy OS przerwie nagle działanie. Dlatego też już od lat projektanci oprogramowania systemowego proponują coraz bardziej pomysłowe metody zapisu informacji na dysku twardym. Początkowo były one dostępne jedynie w systemach serwerowych, od niedawna trafiają jednak również na biurka zwyczajnych użytkowników pecetów.
     Spróbujmy przyjrzeć się różnym systemom plików i przeanalizować różnice pomiędzy nimi. Świadomy wybór używanego systemu plików pozwoli nam na komfortowe i bezpieczne korzystanie z narzędzia codziennego użytku, jakim stał się komputer osobisty.
 

Prosto - ale czy dobrze?
Pierwsze dyski twarde pojawiły się pod koniec lat 50. Trudno było wtedy mówić o standardach systemów plików - dyski wielkości sporych piecyków CO (pierwszy dysk IBM-a z 1957 r. składał się z pięćdziesięciu 24-calowych talerzy) były robione na zamówienie - podobnie jak komputery i systemy operacyjne. Dopiero na początku lat 70., kiedy Ken Thompson i Dennis Ritchie na dobre zaangażowali się w projekt tworzenia pierwszego UNIX-a (dla komputera PDP-7), powstał system plików z prawdziwego zdarzenia. Stanowił on podwaliny znanego po dziś dzień systemu s5fs, używanego przez słynny SVR4 (System V Release 4). Powstanie popularnych wersji UNIX-a (BSD, XENIX-a i innych) przypadło na początek lat 80. i wtedy też zaczęły się krystalizować standardy zapisu informacji na dyskach twardych. Większość prostych systemów plików ma podobną budowę, a niektórych ich odmian używamy do dzisiaj.
     Wspomniany s5fs charakteryzuje się strukturą odpowiadającą rysunkowi 1. W początkowych sektorach partycji umieszczony jest blok startowy, mający za zadanie zainicjowanie systemu operacyjnego. Dalej znajduje się superblok, mieszczący tzw. metadane dotyczące całego systemu plików (patrz: ramka "Najważniejsze pojęcia"). Następnym, podstawowym dla funkcjonowania systemu plików s5fs elementem jest tablica i-węzłów. Mieści ona opisy fizycznego umiejscowienia bloków dyskowych (logicznych elementów partycji charakteryzujących się stałą długością) odpowiadających poszczególnym plikom i katalogom oraz ich atrybuty.
     Bloki te są umieszczone w ostatniej, największej części dysku logicznego. Mają stały rozmiar dla całego systemu plików. Jednocześnie blok dyskowy stanowi najmniejszą porcję danych, jaką możemy odczytać lub zapisać w systemie s5fs (i wielu innych). Z tego względu plik ani katalog nie mogą mieć rozmiaru mniejszego niż założony rozmiar bloku dyskowego.
     Rzecz jasna, plik może być większy niż rozmiar bloku - dokładniej, może zajmować na dysku rozmiar będący wielokrotnością rozmiaru bloku. Adresowanie wielu bloków rozwiązane jest w s5fs w sposób pokazany na rysunku 2. Każdy i-węzeł zawiera pole przechowujące maksymalnie 10 adresów bloków z danymi oraz trzy adresy tzw. bloków pośrednich. Blok pośredni jest zwyczajnym blokiem dyskowym, zawierającym adresy kolejnych bloków z danymi (lub kolejnych bloków z adresami - patrz: bloki pośrednie drugiego i trzeciego stopnia na rysunku 2). W przypadku stosunkowo małego rozmiaru bloku równego 1024 KB pozwala to na przechowywanie pliku o maksymalnym rozmiarze nieco ponad 16 GB.
     Tablica i-węzłów ma strukturę liniową. Oznacza to, że w celu odnalezienia na dysku pliku lub katalogu (katalogi są w większości systemów po prostu plikami o odpowiednich atrybutach) musimy przeglądać sekwencyjnie tablicę tak długo, aż natrafimy na interesujący nas wpis. Podczas zapisu danych należy z kolei przejrzeć superblok (w którym znajduje się m.in. lista wolnych i-węzłów i bloków dyskowych) w poszukiwaniu wolnego miejsca na zapis danych.
     W sposób podobny do opisanego działają systemy plików w większości domowych komputerów. Używany przez lata w Linuksie ext2 opiera się na założeniach zawartych w specyfikacji s5fs. Również Microsoft skorzystał z doświadczeń twórców UNIX-ów, tworząc systemy FAT/FAT-16/FAT-32, choć te ostatnie można traktować jako mocno okrojone wersje s5fs (nie przechowują one m.in. wielu metadanych, z których korzystają UNIX-y). Nieco bardziej rozbudowany niż FAT jest system NTFS, wprowadzony w Windows NT - Okienka z serii NT potrafią po prostu o wiele więcej niż domowe odmiany OS-ów z Redmond.

Nic nie jest idealne
Wszystkie operacje dyskowe w tradycyjnych systemach plików zajmują sporo czasu - pomijając nawet nie najlepszy czas dostępu do pamięci dyskowej, można się spodziewać, że operacje plikowe są wąskim gardłem działania każdego systemu komputerowego. Tak też jest w rzeczywistości. Aby nieco przyspieszyć współpracę OS-u z dyskiem, stosuje się buforowanie odczytywanych i zapisywanych danych w pamięci RAM - zapis czy odczyt większej porcji danych jest, sum-ma summarum, o wiele szybszy niż natychmiastowe wykonywanie każdej operacji dyskowej. To powoduje jednak dosyć poważne problemy np. w przypadku nagłego zaniku zasilania. Pewna liczba ostatnich zmian jest bowiem tracona (część danych "znika" przecież z pamięci podręcznej). Sytuacja staje się szczególnie groźna, gdy utracony zostanie zapis modyfikacji metadanych - np. zmiana praw dostępu do pliku czy informacji o zajętości i-węzłów i bloków dyskowych.
     Systemy plików o opisywanej architekturze wymagają, w przypadku np. nagłego zaniku zasilania, przejrzenia wszystkich wpisów w tablicy i-węzłów oraz w superbloku oraz sprawdzenia, czy informacje tam zawarte są spójne (czy np. pozycje w katalogach nie wskazują na już zwolnione bloki danych). Co więcej, w razie wykrycia niespójności danych nie zawsze istnieje np. możliwość ścisłego określenia przynależności "zagubionych" bloków z danymi - można je co najwyżej zapisać na dysku w postaci osobnych plików.
     Sytuacjom takim zapobiega się na wiele sposobów, zależnych od konkretnej implementacji. Jednym z wyjść zmniejszających ryzyko awarii jest możliwość wymuszenia na OS-ie natychmiastowego wykonania operacji dyskowej czy też okresowy zapis zawartości bufora na dysk (niezależnie od tego, co się w nim znajduje). W odzyskiwaniu danych pomagają odpowiednie programy narzędziowe, takie jak fsck (czy chkdsk pod DOS-em). Wszystko to nie wpływa jednak znacząco ani na poprawę bezpieczeństwa danych, ani na wydajność systemu plików. Spowodowało to powstanie kilku rozwiązań alternatywnych do s5fs i jego pochodnych.
 

Coraz szybciej
W 1983 roku światło dzienne ujrzała wersja 4.2 systemu BSD - jednego z najpopularniejszych do dziś systemów UNIX-owych, rozwijanych pod patronatem Uniwersytetu w Berkeley. We wspomnianej edycji BSD zaimplementowano nowy, poprawiony system plików - FFS (Fast File System). Ze zmodyfikowanej odmiany FFS korzystają po dziś dzień najnowsze odmiany BSD.
     Poprawki w systemie FFS obejmują przede wszystkim uwzględnianie przy zapisywaniu plików fizycznej struktury dysku twardego. Powierzchnia partycji jest mianowicie dzielona na grupy cylindrów (znajdujących się na różnych talerzach dysków ścieżek o tej samej odległości od środka dysku - patrz: rysunek 3). System operacyjny stara się zapisywać sąsiadujące w katalogach pliki w tej samej grupie cylindrów, dzięki czemu optymalizowany jest ruch głowic dyskowych. Ponadto każda grupa cylindrów zawiera własną kopię superbloku systemu plików - wpływa to pozytywnie zarówno na bezpieczeństwo danych, jak i na szybkość operacji dyskowych.
     W systemie FFS zaimplementowano też wiele innych usprawnień - długość nazw plików zwiększyła się do 255 znaków (w porównaniu z 14 w s5fs), ustalono większy rozmiar bloków dyskowych, w 4.2BSD dopuszczalne było również dzielenie bloków na fragmenty (przynależne do różnych plików). Ważnym rozszerzeniem funkcjonalności w odniesieniu do wcześniej stosowanych systemów plików była implementacja dowiązań symbolicznych (symbolic links) i quoty (ograniczeń dostępnej przestrzeni dla poszczególnych użytkowników OS-u). Warto zauważyć, że części wymienionych usprawnień niektórzy producenci popularnych systemów operacyjnych dorobili się niemal 20 lat później.

To wszystko jeszcze nie to...
Pomimo oczywistej poprawy wydajności oferowanej przez system FFS (w porównaniu do np. s5fs) sprawa bezpieczeństwa danych, ważna szczególnie w przypadku dużych OS-ów serwerowych, nie została do końca rozwiązana. Kłopotliwe i trudne do zneutralizowania - z punktu widzenia projektantów systemów operacyjnych - były zwłaszcza błędy związane z operacjami na metadanych. Prostym przykładem sytuacji, kiedy mogą wystąpić trudne do naprawienia błędy, jest usuwanie pliku z katalogu. Załóżmy, że awaria systemu operacyjnego nastąpiła pomiędzy operacją usunięcia pliku z katalogu a zwolnieniem konkretnego i-węzła (wskazującego fizyczne położenie danych na dysku). W ten sposób powstaje plik, który nie jest powiązany z żadnym katalogiem.
     Z opisanych powodów twórcy kolejnych systemów operacyjnych nie zasypiali gruszek w popiele. Oprócz wprowadzania poprawek do koncepcji FFS (dokonywanych m.in. przez Suna) trwały prace nad zupełnie nowymi metodami organizacji danych na dyskach twardych. Starania te zaowocowały pojawieniem się na przełomie lat 80. i 90. systemów plików wykorzystujących tzw. kronikowanie (ang. journaling albo logging).
     Kronikowanie miało zapobiec podstawowym wadom tradycyjnych systemów plików - tzn. ich nie najlepszej wydajności oraz problemów z bezpieczeństwem danych i usuwaniem skutków awarii. Mówiąc w ogromnym uproszczeniu, kronikowanie polega na zapisywaniu w jednym pliku wszystkich dokonywanych w systemie plików zmian. Plik ten, przeznaczony tylko do zapisu, jest uaktualniany dużymi porcjami danych (w celu przyspieszenia średniego czasu zapisu informacji). W efekcie w przypadku "padu" OS-u konieczne jest jedynie przejrzenie ostatnio zapisywanej części kroniki i sprawdzenie, czy wszystkie wpisy w niej są spójne - nie musimy przeglądać całego dysku, jak to ma miejsce w "zwyczajnym" systemie plików. Co prawda, ze względu na buforowanie w pamięci operacji odczytu i zapisu danych na dysku zawsze zachodzi ryzyko utraty pewnej porcji danych, istnieją jednak metody minimalizacji tego - niezbyt zresztą wielkiego - prawdopodobieństwa.
     Ze względu na to, jakie dane podlegają kronikowaniu, systemy plików z journalingiem można podzielić na: 
- systemy o strukturze kroniki,
- systemy z kronikowaniem metadanych.
Journaling jest procesem złożonym i wymagającym od projektantów systemu operacyjnego rozwiązania wielu różnorodnych problemów. Przyjrzyjmy się kilku implementacjom tej techniki w działających i sprawdzających się od lat systemach plików.
 

Idźmy na całość!
W 1993 roku na rynku pojawiła się kolejna wersja Berkeley Software Distribution, oznaczona jako 4.4BSD. Wyposażono go w system plików BSD-LFS. Wszystkie dane w tym systemie były przechowywane w kronice podzielonej na spore bloki o stałym rozmiarze (w granicach pół megabajta). Każdy segment zawiera wskaźnik do następnego, co pozwala rozmieszczać poszczególne segmenty w dowolnych miejscach partycji. Kronikę można sobie wyobrazić jako pierścień utworzony z segmentów - ostatni segment na dysku wskazuje na pierwszy (mówi się, że kronika jest "zawijana").
     Jak już wspomniałem, w kronice BSD-LFS zapisywane jest wszystko - i-węzły oraz dane (opisywany system plików korzysta z podobnych struktur danych co s5fs czy FFS). Zgodnie z założeniem idei journalingu dane są zawsze dopisywane na końcu kroniki (zapis sekwencyjny jest stosunkowo szybki). Jeśli więc dany i-węzeł istniał już wcześniej na dysku, nie jest usuwany, lecz system dodaje do kroniki jego nową wersję.
     Jak zatem uzyskać dostęp do konkretnych danych, czyli do aktualnego i-węzła, odpowiadającego plikowi? Otóż BSD-LFS używa do tego celu osobnej struktury, nazywanej mapą i-węzłów. Jest ona okresowo zapisywana w ustalonych punktach kontrolnych systemu plików. Znajdują się w niej pozycje aktualnych i-węzłów w kronice. W momencie odnalezienia odpowiedniego i-węzła odczyt następuje w "tradycyjny" sposób (za pomocą bezpośrednich i pośrednich adresów bloków, podobnie jak w s5fs).
     Opisany sposób organizacji systemu plików powoduje, że miejsce na dysku twardym ulega szybkiemu wyczerpaniu - często modyfikowane pliki i i-węzły mogą być wielokrotnie zapisywane. Dlatego też konieczne jest zaimplementowanie odpowiedniego mechanizmu "odśmiecania" pliku kroniki. Pomocna jest przy tym kolejna dodatkowa struktura, nazywana tablicą użycia segmentów (ang. segment usage table). Przechowuje ona dane dotyczące aktualności elementów zapisywanych w poszczególnych segmentach kroniki. Informacja ta jest wykorzystywana przez działający równolegle z innymi usługami systemowymi tzw. proces sprzątający (w BSD-LFS nosi on nazwę cleaner). Odnajduje on bloki, w których znajduje się relatywnie dużo nieaktualnych danych, przenosi "ważne" informacje w inne miejsca kroniki i zwalnia niepotrzebne już bloki.