Lokalne sytemy plików bez kronikowania

0. SystemV FS

Starsze Linuxowe systemy plików bardzo silnie bazowały na UNIXowych rozwiązaniach w tej dziedzinie. Powodem takiego stanu rzeczy był fakt korzystania przez pierwsze wersje Linuxa z systemu plików Minix. System ten został napisany przez Tanenbauma jako kopia strukturalna UNIXowego systemu plików sVfs (w warstwie implementacji jest już dużo różnic, gdyż kod Systemu V nie był jawnie dostępny). Kolejne systemy plików Linuxa bazowały na ogólnie dostępnych rozwiązaniach zawartych w systemie plików Minix.

Cechy systemu sVfs:

• brak bitmap opisujących wolne i-węzły i bloki
• wolne i-węzły i bloki są przechowywane na listach
• stały rozmiar bloku - bloki mogą mieć rozmiary od 512b do 2048b
• superblok przechowywany w jednym miejscu
• 14-znakowe nazwy plików
• stała liczba i-węzłów

1. Ffs

Na potrzeby dystrybucji BSD powstał system plików o nazwie fast filesystem. Możliwości starszych systemów plików były ograniczone. Na ogół bazowały na blokach wielkości 512-bajtów. Co gorsza ich rozmieszczenie na dysku było z góry ustalone. Mały rozmiar bloku powodował słabą wydajność systemów przy obsłudze plików większych niż rozmiar bloku. Kolejnym problemem było odseparowanie meta-danych (w postaci i-węzłów) od właściwej informacji, co skutkowało znaczącym udziałem czasu wyszukiwania w długości całej operacji odczytu/zapisu.

Jedną z największych zmian dokonanych w budowie nowego systemu, był nowy projekt rozkładu danych na dyskach. Ffs został podzielony na grupy cylindrów, które odpowiadały fizycznej strukturze cylindrów na dysku. Każda grupa cylindrów zawierała własną kopię superbloku, ustaloną ilość i-węzłów, bitmapy opisujące wolne i-węzły oraz wolne bloki, tabelę opisującą sposób wykorzystania bloków danych, oraz same bloki danych. Liczba i-węzłów była stała. Ich liczba przypadająca na grupę cylindrów była obliczana tak, aby i-węzeł odpowiadał 2048 bajtom. Dodatkowo, aby uniknąć umieszczania meta-danych wyłącznie na jednym talerzu, przyjęto konwencję mówiącą, że metadane drugiej grupy bloków leżą na drugim talerzu, trzeciej na trzecim talerzu itd. Skutkiem takiego ułożenia metadanych, w wielu grupach cylindrów metadane były umieszczone pomiędzy blokami danych.

Ffs wprowadził do systemów plików nową koncepcję - podziału bloku na fragmenty. Projektanci ffs doszli do wniosku, że bardzo często pliki zajmują tylko fragment przydzielonego im bloku. Jeżeli tak, to pozostały fragment bloku pozostaje bezużyteczny, a więc powiększa się fragmentacja wewnętrzna. Aby przeciwdziałać takim anomaliom umożliwiono dokonywanie podziału bloku na 2, 4 bądź 8 fragmentów bloku, których rozmiar jest odpowiednim ułamkiem rozmiaru bloku.

Projektanci systemu ffs mogli skorzystać z wielu udogodnień jakie rozwijały się wraz z postępem w budowie dysków. Wykorzystanie mechanizmów sprzętowych miało w dużym stopniu poprawić pracę systemu. Aby system współpracował z charakterystycznymi cechami sprzętu ustalono następującą politykę alokacji plików:

1. Bloki dla jednego pliku są alokowane wewnątrz jednej grupy cylindrów dopóki jest to możliwe. Jednocześnie system próbuje odwzorować kolejność danych na kolejność fizycznie alokowanych bloków, co przyśpiesza operacje na pliku.
2. Informacje powiązane ze sobą w jakiś sposób są trzymane razem o ile to możliwe. Tworzenie nowego pliku powinno odbywać się w grupie cylindrów zawierającej już i-węzły opisujące katalog w którym tworzymy plik. Takie podejście nie jest jednak dobre w stosunku do katalogów. Katalogi powinny być tworzone w tych grupach cylindrów, w których jest dużo wolnych i-węzłów, ale jest mało katalogów.
3. Dany plik powinien znajdować się w tej samej grupie cylindrów, co i-węzeł opisujący ten plik
4. Duże pliki nie powinny być umieszczane w całości w jednej grupie cylindrów. Stąd odgórne ustalenia mówiące, że po pierwszych 48kB należy zmienić grupę cylindrów w której zapisujemy plik, a następnie zmieniać grupy co 1MB danych. Powoduje to rozrzucenie pliku po grupach cylindrów, a więc unika się sytuacji w której jeden plik zajmuje znaczący fragment grupy cylindrów, co wpływa niekorzystnie na wyniki operacji I/O.

Kolejne testy prowadziły do nowych heurystyk. Ustalono, że system plików spełnia swoje zadania funkcjonalne o ile istnieje wystarczająco duża ilość wolnego miejsca na dysku. Za wartość graniczną, zezwalającą na poprawne działanie systemu plików przyjęto 10% całej partycji. Aby uniknąć sytuacji przepełnienia, system plików nie pozwala na zapisanie następnych danych, o ile partycja jest zajęta w 90%. Od tej reguły istnieje odstępstwo w przypadku superużytkownika.

Opisane wyżej zmiany odnoszą się do struktury systemu plików na dysku. Jak na czasy w których ffs powstawał, rzeczywiście dawało to sporą poprawę w wynikach działania. Testy wskazywały na mniejszą liczbę dostępów do dysku i zwiększenie przepustowości systemu, bez pogarszania innych cech systemu. Jednocześnie należy tu wspomnieć, że system plików ffs w bardzo wielkim stopniu zależał od układu danych na dysku. Projektanci próbowali wykorzystać wszelkie możliwe heurystyki do poprawiania wyników działania systemu. Tymczasem nowoczesne dyski ukrywają swoją wewnętrzną strukturę, udostępniając jedynie strukturę logiczną. Stąd heurystyki wykorzystywane do przyśpieszenia pracy systemu w niektórych przypadkach mogą nawet pogorszyć jego wyniki.

Ffs wprowadza także wiele usprawnień funkcjonalnych:

1. Wprowadzono linki symboliczne. Systemy UNIXowe zawierały ówcześnie jedynie twarde linki.
2. Nazwy plików przestały mieć ustaloną długość. Pierwsze implementacje ffs pozwalały na nazwy długości 255
3. Wprowadzono wbudowany system blokowania plików (blokady dzielone i wyłączne).
4. Zaimplementowano pojedynczą funkcję systemową rename(). Poprzednio wymagane były trzy wywołania systemowe co mogło prowadzić do błędów skutkujących zawieszeniem systemu
5. Dodano wsparcie dla ograniaczania przestrzeni dyskowej dostępnej dla użytkownika (quota).

2. Minix

Pierwszym systemem plików dla którego zaimplementowano wsparcie pod Linuxem był Minix (autorstwa Tanenbaum'a). Wynikało to stąd, że Linus Torvalds rozpoczynał pisanie swego systemu operacyjnego właśnie pod Minixem. Latwiej było mu zaimplementować wsparcie dla istniejącego systemu plików, niż napisać własny od początku.

Głównym celem przy pisaniu Minixa było dostarczenie materiałów edukacyjnych na temat systemów operacyjnych. Minix miał w dużym stopniu odzwierciedlać strukturę UNIXa, którego źródła nie były jawne. Stąd wynika duża liczba rozwiązań zaczerpniętych z UNIX'owego systemu plików s5fs. Podobieństwa w strukturze nie zawsze przenosiły się na warstwę implementacji poszczególnych zagadnień.

Własności:

1. oparcie o rozwiązania s5fs
2. 16-bitowe adresowanie
3. mapy bitowe do alokacji i-węzłów i bloków danych
4. brak adresowania potrójnie pośredniego
5. bloki 1kB
6. maksymalna wielkość partycji równa 64MB dla bloków 1kB
7. nazwy mają do 14 znaków
8. zastosowanie alokacji strefami (domyślnie strefa to 1 blok); przy większych strefach maksymalny rozmiar partycji może być większy

Jak widać system Minix ma bardzo poważne ograniczenia. Szczególnie ważnymi ograniczeniami Minixa było adresowanie 16-bitowe, oraz ograniczenie długości nazw do 14 znaków. W wyniku tych niedogodności, bardzo szybko pojawiły się alternatywne systemy plików dla Linuxa. Jako, że problemy Minixa nie leżały w warstwie ideowej, wiele rozwiązań stosowanych w tym systemie wyznaczało szlaki dla nowocześniejszych systemów plików.

Impulsem do budowy nowszych systemów plików było dołączenie do jądra Linuxa warstwy VFS - Virtual File System. Warstwa ta domyślnie miała ułatwić tworzenie nowych systemów plików.

3. Ext, Xia, Ext2

3.1. Ext

Po wprowadzeniu VFS do jądra linuxa, powstał nowy system plików: Ext, zaimplementowany w 1992 roku. Ext usuwał dwa najpoważniejsze ograniczenia Minixa: maksymalny rozmiar partycji osiągnął pułap 2GB, natomiast maksymalna długość nazwy pliku wynosiła już 255 znaków.

Z drugiej jednak strony, pozostało wiele nierozwiązanych problemów. M.in. nie wbudowano w system znaczników czasowych (timestamps), system używał list do pilnowania pustych bloków i i-węzłów, co skutkowało bardzo kiepską wydajnością: listy nie były posortowane i wzrastała fragmentacja.

3.2. Xia

Xia jest w dużym stopniu oparty na systemie Minix. Rozwiązywał problemy systemu Minix z wielkością partycji dyskowej (dopuszczalny rozmiar to 2GB), długością nazw (dopuszczał nazwy 248 znakowe), a także wprowadzał stemple czasowe. System Xia pojawił się mniej więcej w tym samym czasie co Ext2. Początkowo miał przewagę nad Ext2, gdyż w przeciwieństwie do Ext2 oparty był na dobrze znanym i stabilnym kodzie systemu Minix. Jednak te cech z czasem przerodziły się w wady, gdyż systemu plików Xia nie można było rozszerzać w takim stopniu w jakim pozwalał na to Ext2. Obecnie Ext2 stał się podstawowym systemem plików dla większości dystrybucji linuxa, natomiast Xia nie spełnia wymagań dzisiejszych użytkowników linuxa.

3.3. Ext2

Ext2 powstał w tym samym czasie co Xia, jednak systemy te bardzo różniły się od siebie. Ext2 miał o wiele bardziej otwartą architekturę, pozwalającą na dynamiczny rozwój systemu. Gdy w miarę upływu czasu eliminowano błędy Ext2 system ten spopularyzował się do tego stopnia, że jest on obecnie standardowym systemem plików dla Linuxa.

Do systemu Ext2 wprowadzono wiele zmian w porównaniu z jego pierwszą wersją. Główne cechy Ext2 to:

• obsługa partycji o rozmiarze do 4TB
• nazwy plików mają zmienną długość - maksymalnie 255 znaków
• dopuszczona zostaje dwojaka semantyka plików - w czasie montowania możliwe jest wybranie pomiędzy semantyką BSD a SVR5
• dopuszczone zostały różne rozmiary bloków (rozmiar zostaje ustalony w momencie montowania systemu plików)
• system pozwala na zarezerwowanie pewnej przestrzeni w ramach partycji na potrzeby plików root'a (max. 5%)
• szybkie linki symboliczne - linki symboliczne są trzymane w i-węzłach a nie w specjalnie alokowanych blokach

System Ext2 został dokładnie omówiony na wykładzie, dlatego nie będę wnikał w dalsze szczegóły.

Porównanie systemów plików