ReiserFS

Krzysztof Kowalczyk

Wstęp

System plików RaiserFS jest systemem plików stworzonym specjalnie dla Linux'a przez Hans'a Raiser'a. Podczas tworzenia RaiserFS'a autorowi przyświecały dwa cele. Po pierwsze zoptymalizować obsługę dużych ilości małych (dużo mniejszych od bloku dyskowego) plików. Drugim celem było zaimplementowanie systemu plików z ujednoliconym interfejsem dostępu do różnych danych zapisanych na dysku: metadanych, plików, katalogów (technologia Unifying Name Spaces).

W tym dokumencie będę opisywał budowę i działanie RaiserFS'a w wersji trzeciej. Gotowa jest już specyfikacja wersji czwartej, która to wersja ma się ukazać na początku stycznia 2003. Wersja czwarta różni się znacznie od trzeciej, wszystkie dane przechowywane są na jednym poziomie w B+ drzewie, rozszerzono listy uprawnień, wprowadzono modularność dzięki wtyczkom (plugins).

Budowa RaiserFS

W RaiserFS'ie wszystkie dane przechowywane są w drzewie zrównoważonym - B+ drzewie. B+ drzewo jest to B drzewo, w którym elementy są trzymane tylko w liściach natomiast w wierzchołkach wewnętrzych są trzymane tylko dane dodatkowe (klucze).

Rozróżniamy dwa rodzaje objektów: pliki i katalogi. Każdy obiekt w momęcie tworzenia ma nadawany unikalny identyfikator (object id), na podstawie którego jest później rozpoznawany w strukturze systemu plików.

Item

Drugim ważnym pojęciem jest item. Wyróżniamy następujące rodzaje item:

Dane bezpośrednie przechowują:

Dane pośrednie przechowują listę wskaźników do bloków na dysku.

Dane katalogu przechowują klucze pozycji w katalogu oraz ich nazwy.

Dane informacyjne przechowują:

Każdemu item nadawany jest w bardzo przemyślny sposób klucz, który będzie służył do szeregowania wpisów o pliku w B+ drzewie. O kluczu tym można myśleć jak o numerze inoda w ext2. Nadawanie klucza jest tak wymyślone by

znalazły się możliwie blisko siebie w porządku B+ drzewa.

Klucz jest nadawany item w następujący sposób:
Nazwa Rozmiar
(bytes)		 Opis
k_dir_id 4  Identyfikator katalogu nadrzędnego
k_object_id 4  Identyfikator objektu
k_offset 4  Offset w bajtach od początku pliku do miejsca w rozpoczynają się dane zapamiętane przez item
k_uniqueness 4  Typ item (StatData = 0, Direct = -1, InDirect = -2, Directory = 500)

B+ Drzewo

W B+ drzewie jako elementy trzymane są item, porządek drzewowy ustalony jest przy użyciu klucza item.


W drzewie tym wyróżniamy następujące rodzaje wierzchołków:

  1. Węzły wewnętrzne (Internal Nodes) - fioletowe
  2. Węzły sformatowane (Formatted Nodes) - zielone
  3. Węzły niesformatowane (Unformatted Nodes) - niebieskie
Wielkość węzła jest stała i równa wielkości bloku dyskowego.
  1. Węzły wewnętrzne

     Nagłówek węzła   Klucz 0  Klucz 1 ---  Klucz N  Wsk. 0  Wsk. 1 ---  Wsk. N  Wsk. N+1 Wolne miejsce

    Węzły wewnętrzne zawierają listę par kluczy i wskaźników do poddrzew, gdzie klucz jest równy pierwszemu kluczowi w pierwszym węźle sformatowanym poddrzewa, na które wskazuje wskaźnik.

  2. Węzły sformatowane

     Nagłówek węzła   Nagłówek wpisu 0  Nagłówek wpisu 1  ---  Nagłówek wpisu N Wolne miejsce  Item N  ---  Item 1  Item 0

    Węzły sformatowane składają się z listy item. Zawierają dane (gdy item informacyjny, bezpośredni lub katalog) lub listę wskaźników do węzłów niesformatowanych (gdy item pośredni).

  3. Węzły niesformatowane

    Węzły niesformatowane przechowują dane, ciąg bajtów.

Warstwa fizyczna

Poszukiwanie bloku do zapisania wierzchołka na dysku rozpoczyna się od bloku, w którym zapisany jest lewy sąsiad w porządku drzewowym rozpatrywanego wierzchołka. Następnie szukany jest pierwszy wolny blok, przechodząc bitmape zajętości w kierunku, w którym szliśmy przy poprzednim zapisie.
Lokalne systemy plików