Systemy plików na wybranych przykładach

Wstęp

Niniejsza prezentacja traktuje o systemach plików, jest to temat bardzo obszerny dlatego ogranicze sie do przedstawienia ogólnie zadań tych systemów, problemów i sposobów realizacji tych zadań. Jako przykładów użyje systemu plików FAT i NTFS. Ponadto wspomne też o rozproszonych systemach plików na przykładzie DFS-a
System plików jest sposobem przechowywania danych w pamięci trwałej komputera, dane są przechowywane w plikach chcielibyśmy aby system plików zapewniał:

• rozsądną strukturyzacje danych tj. umieszczenie danych w plikach, plików w katalogach

• możliwie szybki dostęp do danych

• podstawowe operacje na danych (tworzenie, modyfikacja, usuwanie)

• bezpieczeństwo danych

ponadto chcemy przetrzymywać pewne istotne informacje o danych takie jak:

• czas utworzenia modyfikacji pliku

• prawa własności

• prawa dostepu do pliku

• pewne atrybuty pliku (np. read-only, hidden etc.)

Poniżej zaprezentuje pewien pomysł na rozwiązanie tych problemów, wypunktuje jego wady i zalety, powiem czego jeszcze można chcieć od systemu plików i na drugim przykładzie pokaże jak i w jakim stopniu te potrzeby zostały zaspokojone

File Allocation Table (FAT)

Informacje na dysku ułożone są pokolei w jednosktach zwanych sektorami, ponieważ te dane często ulegają modyfikacjom, nie można szytwno przydzielać obszarów w których są składowane, trzeba wiec gdzies pamiętać gdzie umieszczony jest ciąg dalszy pliku. Tę role pełni File Allocation Table (FAT) od której wzieła sie nazwa systemu plików.
Partycja jest podzielona na logiczne jednostki zwane klastrami (ang. clusters) Klaster odpowiada stałej ilośći sektorów, wielkość klastra zależy od wersji FAT-a, wacha sie pomiedzy 2kB a 32kB, zazwyczaj przy sektorach wielkosci 512B przypada 8 sektorów na klaster. Klaster jest przyporządkowany dokładnie jednemu plikowi, aczkolwiek jeden plik może być związany z kilkoma klastrami.
Poniższy rysunek przedstawia schemat budowy partycji FAT.



Bootsector - to zawsze pierwszy sektor partycji, zawiera podstawowe informacje o partycji, między innymi:

• wielkość partycji

• wielkość sektora (w bajatach)

• ilość sektorów w klastrze

• typ partycji (np. FAT32)

• ilość kopi tablicy FAT

• wskaźniki do innych danych

• kod ładujący system operacyjny

Tablica FAT - jak juz było powiedziane jest to struktura danych w której przechowywane są informacje o położeniu pliku na dysku. Każdemu klastrowi odpowiada dokładnie jeden wpis w tablicy, ten wpis to zazwyczaj informacja o tym że klaster jest jakiś specjalny bądź jest to numer klastra zawierajacy ciąg dalszy pliku. Szczegóły pokazane w tabelce poniżej:

Kopia FAT - ze względu na duża wartość informacji przechowywanych w tablicy warto zabezpieczyć sie na wypadek zniszczenia oryginalnej tablicy (lub jej części) poprzez duplikacje danych umieszczonych na niej. Niestety rozwiązanie nie zapewnia należytego bezpieczeństwa z conajmniej dwóch powodów. Ze wzgledu na to że obie tablice są umieszczone obok siebie w przypadku wykrycia bad sektorów w jednej jest duża szansa, że uszkodzona jest też kopia, ponadto usterka może być zduplikowana przed wykryciem błędu.

Root directory - jest to katalog główny systemu plików, występuje w ustalonym miejscu w partycji. W FAT12 i FAT16 ma sztywno ustaloną wielkość - mieści do 512 wpisów (przy długich nazwach jeszcze mniej). W FAT32 nie ma tego ograniczenia.

Obszar danych - pliki (i katalogi) umieszczone w klastrach jeden lub wiecej klastrów przypadających na plik. Reprezentowane są jako ciąg bajtów, jeśli nie starcza klastra kolejne są w następnym itd. Za poprawność operacji następnika odpowiedzialna jest tablica FAT. Katalogi są to pliki specjalnej postaci. Katalog jest podzielony na małe struktury nazywane wpisami. Każde wpis ma rozmiar 32 bajtów i jest informacją o katalogu bądź pliku, zawartym w naszym katalogu. Wpis zawiera pola:

• 8 bajtów - nazwa pliku, (literki, cyferki i $ % @ ' - _ ( ) ~ ! # ^ & później również + , ; = [ ])

• 3 bajty - rozszerzenie,

• 1 bajt - atrybuty pliku:

  • read-only, tylko do odczytu

  • hidden, ukryty

  • system, plik systemowy

  • volume label, tak jest oznaczony jeden plik w katalogu głównym, jego nazwa jest nazwą dysku

  • subdirectory, czy jest to katalog

  • archive, plik, który trzeba skopiować przy nastepnej kopi zapasowej

  • device, plik reprezentuje urządzenie

  • unused, nie używane

• 1 bajt - wielkość liter nazwy i rozszerzenia pliku,

• 1 bajt - czas utworzenia w milisekundach,

• 2 bajty - czas utworzenia,

• 2 bajty - data utworzenia,

• 2 bajty - czas ostatniego dostępu,

• 2 baty - zarezerwowane,

• 2 bajty - czas utworzenia lub ostatniej modyfikacji pliku,

• 2 bajty - data utworzenia lub ostatniej modyfikacji pliku,

• 2 bajty - numer klastera gdzie rozpoczyna się plik,

• 4 bajty - rozmiar pliku.

Nazwy plików
Powyższy spis sugeruje, że nazwy plików zawierają mogą sie składać tylko z 8 znaków + 3 literowe rozszerzenie. W istocie tak było na początku i tak jest np.w MS-DOS. Mankament ten trzeba było usunąć, jednakże na tyle ostrożnie by zachować wsteczną poprawność. W tym celu użyto następującego triku. Tworzy sie alias, w którym nazwa pliku przypomina nazwe oryginalną, a cała nazwa jest zapisywana w specjalnym katalogu o atrybutach (read-only, system, volume label - to po to żeby ten katalog był jakiś dziwny, hidden). Stare systemy nie przejmują sie tymi ekstra katalogami i obowiązuja zaliasowane nazwy. Więc wszystko w porządku.

Podsumowanie

Poniżej tabelka z ograniczeniami poszczególnych wersji FAT-a

Powyższe dane zależą oczywiscie od wielkości klastra, większy rozmiar klastra to większy maksymalny rozmiar partycji ale też wieksza utrata danych (statystycznie połowa klastra jest wolna)

zalety

• działa - w dostatecznym stopniu realizuje podstawowe postulaty ze wstępu

• prostota i popularność - FAT jest wspierany przez wszystkie systemy operacyjne często służy do wymiany danych miedzy platformami

wady fata

• sekwencyjny dostep do plikow

• podatnosc na awarie

• nieefektywny na duzych partycjach

• ubogie wsparcie dla metadanych (m.in brak uprawnień dla plików)

poza tym w miare korzystania z systemu zauważamy, ze brakuje nam jeszcze kilku rzeczy:

• wiecej informacji o samych danych (metadane)

• możliwość ustalania ograniczeń dla poszczególnych użytkowników (quota)

• zagwarantowanie bezpieczeństwa danych jak również metadanych

• dowiązania symboliczne

• wiele strumieni danych

New Technology File System (NTFS)

Te i inne życzenia spowodowały konieczność stworzenia nowego systemu plików
Główne założenia NTFS:

• Niezawodność - duża tolerancja błędów przy zagwarantowaniu bezpieczeństwa danych.

• Bezpieczeństwo i kontrola dostępu - system praw dostępu.

• Przełamanie bariery rozmiaru - rozmiar partycji ograniczony jedynie wymiarem dysku, macierze RAID (Redundant Arrays of Inexpesive Disks).

• Efektywność - lepsze wykorzystanie dostępnej pamięci dzięki nowym rozwiązaniom alokującym pamięć.

• Długie nazwy plików - do 255 znaków dopuszczające także znaki diakrytyczne.

• Sieciowość - właściwości ułatwiające korzystanie z sieci.

NTFS 5.0 jest nowszą wersją stosowaną w Windows 2000 posiadającą własności:

• Reparse points - pliki i katalogi mogą mieć powiązane z nimi akcje, które zostają wykonane w momencie wywołania obiektu w jakiś szczególny sposób. Reparse points wykorzystuje się przy tworzeniu symbolicznych dowiązań plików i katalogów (Symbolic links, Junction points),  montowania dysków (Volume Mount Points), zdalnych serwerów archiwizacyjnych (Remote Storage Server).

• Udoskonalone bezpieczeństwo i system praw - m. in. przydział praw do zasobów, podział na grupy użytkowników.

• Dzienniki zmian (Change Journals) - wszystkie zmiany w systemie są notowane. W przypadku awarii niedokończone akcje zostają wycofane, dzięki czemu system zawsze pozostaje w stabilnym stanie.

• Kodowanie - ze względu na możliwość ominięcia zabezpieczeń NTFS poprzez niskopoziomowy dostęp w wersji 5.0 dodano możliwość kodowania danych z wykorzystaniem klucza prywatnego i publicznego.

• Disk Quotas - kontrola i limitowanie przestrzeni dyskowej użytkowników.

• Sparse File Support - mechanizm oszczędzający miejsce na dysku w przypadku przechowywania dużych plików złożonych z jednolitych części np. samych zer.

• Disk Defragmenter - defragmentator dysku pozwalający redukować straty przestrzeni dyskowej spowodowane fragmentacją.

Idea

Sprostanie tym wymaganiom musiało sie wiązać z zupełnie innym podejściem do problemu przechowywania informacji. Tak samo jak w FAT przestrzeń dyskowa jest podzielona na klastry. Bootsector pozostaje bez zmian. W odróżnieniu od FAT wszystkie dane są przechowywane jako pliki rozróżniamy:

• zwykłe pliki

• pliki z metadanymi

• foldery

Pliki z metadanymi zawierają informacje o danych. Najważniejszym z tych plików jest Master File Table (MFT). Jest to pierwszy z 16 plików specjalnych. Jego rola jest podobna do roli jaką pełni tablica FAT we wcześniej omawianym systemie plików. MFT jest tablicą w której każdy wpis reprezentuje w odróżnieniu od FAT-a nie klaster, ale plik. Każdy plik musi mieć wpis w tablicy MFT, w szczególnośći, sam MFT podobnie jak pozostałe 15 plików specjalnych mają własne wpisy. Poniżej schemat budowy partycji NTFS:



Dla MFT zarezerwowano tzw MFT-area która jest jakąś ustaloną częścią partycji rozmiar MFT-area to 12,5% do 50% wielkości napędu logicznego. Dane (rózne od wpisów do MFT) w MFT-zone zapisuje sie dopiero gdy nie ma miejsca w pozostałych częsciach dysku. Samo MFT jest podzielone na rekordy ustalonej wielkosci np 2kB. Ze względów bezpieczeństwa, pierwsze 16 rekordów (te zawierające pliki z metadanymi), posiada swoją kopie dokładnie na środku bądź na końcu partycji. Poniżej wykaz i opis znaczenia tych metaplików.

Pliki

Pliki w NTFS reprezentowane są jako zbiory struktur zwanych atrybutami. Każdy atrybut może wystąpić dla jednego pliku wielokrotnie, każdy może też mieć przypisaną nazwę.

Standardowo w NTFS istnieją następujące atrybuty:
0x10 $STANDARD_INFORMATION - standardowa informacja o pliku - oprócz wartości znanych z systemu FAT również informacje o quocie, zabezpieczeniach, właścicielu, czasie ostatniej zmiany, itp.
0x20 $ATTRIBUTE_LIST - patrz MFT.
0x30 $FILE_NAME - nazwa pliku.
0x40 $OBJECT_ID - unikalny identyfikator.
0x50 $SECURITY_DESCRIPTOR - szczegółowe informacje o zabezpieczeniach nałożonych na plik.
0x60 $VOLUME_NAME - nazwa partycji.
0x70 $VOLUME_INFORMATION - informacja o partycji
0x80 $DATA - zawartość pliku.
0x90 $INDEX_ROOT - w przypadku katalogu korzeń B-drzewa.
0xA0 $INDEX_ALLOCATION - w przypadku katalogu węzły B-drzewa.
0xB0 $BITMAP - w przypadku katalogu bitmapa wolnych miejsc w katlogu.
0xC0 $REPARSE_POINT - definiuje typ punktu reparsji założonego na pliku. Patrz Reparse Points.
0xD0 $EA_INFORMATION - używany przez OS/2 do emulacji HPFS.
0xE0 $EA - patrz wyżej.
0xF0 $PROPERTY_SET - nieużywany.
0x100 $LOGGED_UTILITY_STREAM - operacje na tym atrybucie są zapisywane w dzienniku logów.

Atrybuty nie są ustalone odgórnie, lecz zapisane w pliku systemowym $AttrDef. Istnieje więc możliwość ich zmiany lub dodania nowych.

Gdzie są trzmane dane?

• Jeśli plik jest mały tj. łączny rozmiar zawartośći jego atrybutów nie przekracza rozmiaru jednego wpisu do MFT to całość jest tam przechowywana.

• Dla nieco większych plików amiast samych danych w MFT jest przechowywana lista wskaźników do klastrów zawierajacych te rzeczy np. atrybut $DATA zawiera numery klastrów gdzie faktycznie są te dane.

• Jeśli dane są naprawde duże (na tyle ze same wskaźniki do nich nie zmieszcza sie w jednym rekordzie MFT) to trzymany jest wskaźnik do miejsca gdzie przetrzymywane są wskaźniki.

Hard links

Twarde dowiązania implementuje się nadając plikowi kilka różnych atrybutów $FILE_NAME. Nazwa tego atrybutu jest równoznaczna z nazwą pliku.

Data streams

Wielokrotne wystąpienie atrybutu $DATA dla jednego pliku umożliwia zapisanie w jednym pliku wielu strumieni danych. Podstawową zawartość pliku określa nienazwane wystąpienie atrybutu $DATA, natomiast do innych strumieni w pliku można się odwoływać poprzez łańcuch "nazwa_pliku:nazwa_strumienia" (gdzie nazwa_strumienia jest nazwą odpowiedniego atrybutu $DATA).

Katalogi

Katalogi podobnie jak w FAT, traktowane są jak zwyczajne pliki, z tą róznicą że zawartość katalogu jest trzymana w B+ drzewie, co znacząco przyspiesza wyszukiwanie. Poniżej rysunek przedstawiający róznice w czasie szukania w porównaniu z liniowym przechodzeniem listy.

Bezpieczeństwo

Uprawnienia
Częstwo istnieje potrzeba ograniczenia uprawnień w dostępie do pików poszczególnym użytkownikom systystemu. Poniżej zestaw podstawowych uprawnień w NTFS

• Read - czytanie

• Write - zapis

• Execute - wykonywanie

• Delete - usuwanie

• Change Permissions - zmiana uprawnień

• Take Ownership - zmiana właściciela pliku
  Transakcyjność i kronikowanie
  Modyfikacje danych takie jak np. kopiowanie często wymagają wiecej niż jednej operacji na dysku. Awaria (np. utrata zasilania) podczas wykonywania tych operacji może powodować rozspójnienie danych na dysku, co wiecej awaria w pewnych newralgicznych punktach np. podczas zmian struktur danych partycji, może spowodować uszkodzenie całego dysku logicznego. Sa oczywiście narzędzia do naprawy i odzyskiwania danych (np. scandisc), jednakże proces ten jest bardzo czasochłonny i nie zawsze daje oczekiwane efekty.
  Z punktu widzenia użytkownika dobrze by było, gdyby wszystkie logiczne operacje na plikach były realizowane w sposób atomowy. Jest to realizowane w następujący sposób. Każda operacja przed wykonaniem jest zapisywana do dziennika $LogFile. Jeśli nastąpi awaria podczas wykonywania tej operacji, przy ponownym montowaniu partycji sprawdzane jest czy wszystkie zapisane w dzienniku operacje zakończyły sie sukcesem. Jeśli tak nie było wycofywano skutki częściowo dokonanych zmian. Co 8 sekund do dziennika jest zapisywany tzw. check-point, co oznacza że wszystkie wcześniejsze wpisy do dziennika są w porządku. To co sie faktycznie zmieniło zapisywane jest w dzienniku zmian (Change Journal) zaraz po fizycznym dokonaniu zmiany. Dzieki temu można określić co sie zmieniło, przy wycofywaniu tranzakcji.
  
  Szyfrowanie
  Czasem istnieje konieczność zaszyfrowania pewnych informacji. Same prawa dostępu nie wystarczą. W tym celu jest stosowane kodowanie plików. NTFS korzysta z modułu Encrypting File System (EFS), co pozwala zabezpieczyć sie przed próbą niskopoziomowego obejścia zabezpieczeń i praw dostępu Dostępne jest kodowanie plików i katalogów na życzenie użytkownika. Kodowanie opiera się o algorytmy wykorzystujące klucz publiczny i klucz prywatny.

Distributed File System (DFS)

Wprowadzenie

W miare rozwoju sieci komputerowych zaistniała potrzeba stworzenia rozproszonego systemu plików, by móc współdzielić dane przechowywane na różnych komputerach. Przed stworzeniem dfs-a korzystanie z sieci zgodne z UNC (Universal Naming Convention). Korzystanie ze wspoldzielonych plikow wymagalo podawania pelnej nazwy postaci: \\server\share\Path\Filename - często mapowanie "\\server\share" do np. "x:").
W dużych sieciach z wieloma serwerami UNC przestał być wygodny, a nawet wystarczający. Mogło np niestarczyć literek na podmapowywanie. DFS łączy nazwy udziałów ("\\server\share") w name-space'y (logiczne struktury). Dzięki temu istnienie serwerów jest niewidoczne dla użytkownika. Kosztem pracy administratora.
Dostep do zasobów Dfs odbywa sie poprzez UNC

Cechy Dfs

• Hierarchiczna struktura

• Elastyczna modyfikacja struktury

• Możliwość duplikacji danych

• Rozkladanie obciążenia

• Name transparency

• Integracja z zabezpieczeniami Win Nt

• Cachowanie informacji

• Graficzny interfejs

Łączenie zasobów

Post-Junction Junction - zagnieżdżanie punktów mountowania
Alternative Volumes - te same dane w kilku kopiach pod jedną nazwą. (Dfs nie sprawdza czy to naprawde te same rzeczy).
Down-Level Volumes - polaczenia z innymi systemami niż Dfs.

Partition Knowledge Table

• lokalnie tworzona dla kazdego zamapowanego udziału. Wpisy dodawane w momencie przekraczania punktow montowania, żywotne na 5 minut.

• po stronie serwera jedna na maszyne, przechowywane w rejestrach systemu

Server Message Block (SMB)

Server Message Block Opracowany w latach 80 prze Intel Microsoft IBM protokol wymiany plikow i drukarek. Klient-Server.
Implementacja pod NetBEUI NetBois obecnie TCP/IP. podst komendy:

• Laczenie i odlaczanie od udziałów

• Otwieranie Zamykanie plików

• Odczyt/Zapis

• Tworzenie/Usuwanie plików

• Przeszukiwanie katalogów

• Blokowanie fragmentów plików

Opportunistic locks

Jedną z ciekawszych rzeczy jest obsługa blokad. Klient blokuje plik pracuje na lokalnej kopii, ktos inny żada dostepu; blokada jest zrywana; serwer SMB wysyla do niego żadanie wykonania zapisu zmian; drugi klient otrzymuje dostep.
Poniżej przykładowy scenariusz używania oplock-ów.

Exclusive oplock - klient ma wyłączność na dostęp do pliku.
Klient A po otrzymaniu takiego oplocka ma wylaczny dostęp do pliku. Jeżeli inny klient (B) zażąda otwarcia pliku, serwer wyśle do A iformacje o przerwaniu jego blokady. Zmusza to A do wykonania zaległych zapisów do pliku i zamkniecie go do lub odłączenia się od niego. Po wykonaniu tej synchronizacji plik udostępniany jest klientowi B.

Batch oplock - utrzymanie otwartego pliku nawet po zamknieciu go przez klienta. W przypadku, kiedy aplikacja klienta A często otwiera i zamyka plik batch oplock redukuje ruch sieciowy - pozwala klientowi A uniknąć ciągłego wysyłania żądań otwarcia i zamknięcia pliku. Jeżeli nadejdzie żądanie dostępu do pliku od innego klienta (B), serwer informuje A, że musi zmienić tryb dostępu

Level II oplock - pozwala na równoczesny odczyt pliku przez wielu klientów
Jeżeli klient A ma exclusive oplock, ale otworzył plik w trybie tylko do odczytu i nadejdzie żądanie otwarcia pliku przez innego klienta (B), klienta A jest informowany, że jego blokada musi zostać przerwana i zostaje mu przydzielona blokada Level II. Po dokonaniu tej zmiany, klient B może również otrzymać blokade Level II.

Samba - darmowa implementacja SMB dla Unixa

Bibliografia

http://www.reference.com/browse/wiki/Comparison_of_file_systems
http://www.reference.com/browse/wiki/File_Allocation_Table
http://www.reference.com/browse/wiki/NTFS
http://ntfs.com
http://en.wikipedia.org/wiki/Server_Message_Block
http://en.wikipedia.org/wiki/Distributed_file_system
wybrane prezentacje z SO - 2002/2003

Marcin Młodzki mm214559@studetns.mimuw.edu.pl