System plików Reiser4




Kilka słów o idei

Hans Reiser i jego team dzielą filozofię, w której myśl najlepszymi systemami plików są te, które pomagają wykreować pojedyńcze środowisko współdzielone, lub przestrzeń nazw, gdzie aplikacje mogą współdziałać bardziej bezpośrednio i wydajnie. W tym celu, system plików powinien wychodzić na przeciwko potrzebom użytkownika odnośnie wydajności i możliwości. W ten sposób, użytkownicy mogą kontynuować raczej używanie bezpośrednio systemu plików , niż budować powloki o specjalnym zastosowaniu, które działają na szczycie systemu plików, jak bazy danych itp.


Struktura drzewiasta

Namesys zdecydował skupić się na początku na jednym aspekcie działania systemu plików - na wydajności dla małych plików. Generalnie,
systemy plików jak ext2 i ufs nie radzą sobie w tym temacie zbyt dobrze, zazwyczaj zmuszając deweloperów do zwrócenia się w kierunku baz danych i im podobnych mechanizmów organizacyjnych w celu otrzymania pożadanej wydajności. Z czasem, ten rodzaj podejścia ( obchodzenie problemu ) sprzyja negatywnemu zjawisku, jakim jest powstawanie wielu niekompatybilnych API o specyficznym przeznaczeniu. ReiserFS radzi sobie z małymi plikami zdumiewająco dobrze - jest około 8-15 razy szybszy niż ext2 w kategorii plików mniejszych niż 1k. Co więcej, ta wydajność nie łaczy się z wydatkiem kosztem wydajności dla innych typów plików - ReiserFS przewyższa ext2 w niemal każdym obszarze działalności systemu plików, choć naprawdę błyszczy dopiero gdy chodzi o pracę z małymi plikami.

Dzieje się tak, gdyż ReiserFS używa specjalnie zoptymalizowanych drzew zbalansowanych (w poprzednich wersjach systemu plików reiser'a stosowano b+drzewa, w najnowszej obecnie wersji (Reiser4) stosuje się drzewa "tańczące"). Zastosowanie drzew zbalansowanych pozwala ReiserFS'owi na dynamiczną alokację inode'ow zamiast kreowania określonego zbioru na etapie tworzenia systemu plików. W ten sposób system jest elastyczniejszy w dziedzinie wymagań odnośnie zawartości dysku.
W drzewie trzymane są wszystkie informacje o systemie plików - znajdują się tam zarówno treści plików, ich nazwy, jak i uprawnienia, meta-dane i inne informacje.


Rodzaje wierzchołków w drzewie, czyli liście, gałązki i gałęzie

W drzewie, które zawiera wszystkie dane nt. zawartości dysku, są określone 3 rodzaje wierzchołków:

    Liscie (leafs)- nie posiadają dzieci.

Wewnętrznymi wierzchołkami są wierzchołki, które posiadają liście (synów). Wierzchołki, które zawierają itemy są nazywane wierzchołkami sformatowanymi. Jeśli obiekt jest duży, nie jest skompresowany i nie potrzebuje wspierać wydajnych wstawień (skompresowane obiekty są specyficzne, bo potrzebują być w stanie zmienić swoją objętość przy pisaniu do ich środka - kompresja może nie być równie wydajna dla nowych danych), wtedy może być bardziej wydajnie przechowywać je w wierzchołkach bez użycia itemów w ogóle. Ten mechanizm jest stosowany dla obiektów większych niż 16k. Niesformatowane liscie (unfleafs) to takie, które zawierają jedynie dane, bez żadnych informacji formatujących. Naturalnie tylko liście mogą zawierać nieformatowane dane. Wskaźniki znajdują się w itemach, więc wewnętrzne wierzchołki muszą być sformatowane. Wskaźniki do unfleafs'ów są inne w strukturze od wskaźników do sformatowanych wierzchołków.
Extent pointers wskazują na unfleafs'y. Extent jest sekwencją sasiednich (według numeru bloku) unfleafs'ów, które należa do tego samego obiektu. Wskaźnik na extent zawiera numer bloku startowego extentu i jego długość. Ponieważ extent należy tylko do jednego obiektu, możemy przechowywać tylko jeden klucz dla extentu, i obliczać klucz każdego bajtu wewnątrz extentu. Jesli extent ma co najmniej 2 bloki długości, wskaźniki na extenty są mniejsze niż zwykle wskaźniki na wierzchołki. Wskaźniki na wierzchołki są wskaźnikami na sformatowane wierzchołki. Nie ma jeszcze skompresowanej wersji wskaźnikow na wierzchołki, ale to się prawdopodobnie pojawi wkrótce.

    Gałązki (twigs)- są ojcami lisci. wskaźniki na extenty istnieją tylko w gałązkach.

    Gałęzie (branch)- są wierzchołkami wewnętrznymi, które nie są gałązkami.

Poziom numer 1 jest poziomem liści, jako że drzewo przyrasta od gory. Wysokość drzewa zależy od liczby obiektów które mamy do przechowania i od przeciętnego rozgałęzienia gałązek i gałęzi. Minimalnym drzewem jest drzewo wysokosci 2, korzeń jest zawsze wierzchołkiem wewnętrznym.

 treev4_Reiser4X.gif


Itemy, czyli sposób na przechowywanie wierzchołków.

Wierzchołki w drzewie są mniejsze niż niektóre z obiektów tak przechowywanych, jak również od niektórych większe. Pewnym sposobem ich przechowywania jest wstawienie ich do itemów. Item jest kontenerem danych złożonym z pojedyńczego wierzchołka, a to pozwala na zarzadzanie pamięcią wewnątrz wierzchołków. W domyślnym formacie wierzchołka 4.0, każdy item posiada klucz, offset do miejsca w wierzchołku, gdzie item się zaczyna, długość itemu, oraz pluginid, który wskazuje na typ itemu. Itemy pozwalają nie zaokrąglać do 4k miejsca na dysku do przechowywania obiektów - otrzymujemy dużą oszczędność miejsca w przypadku małych plików, jak również ogonów plików.

Struktura itemu:

Item_Body   . . separated . .   Item_Head
    Item_Key Item_Offset Item_Length Item_Plugin_id


Istnieje kilka typów itemów, które są zaprojektowane do przechowywania różnych rodzajów informacji.


b+drzewa.

W oryginalnym algorytmie b-drzew, w wewnętrznych wierzchołkach nie są przechowywane jedynie wskazniki, lecz również dane. B+drzewa zmieniają to - w gałęziach i gałązkach trzymamy tylko wskaźniki i klucze - wszystkie obiekty są przechowywane na poziomie liści:

B-plus-tree.gif

Naturalnie z wyeliminowaniem danych w wierzchołkach wewnętrznych, zwiększa się średni stopień rozgałęzienia wierzchołków. W ten sposób zmniejszamy ilość wierzchołków wewnętrznych (na rzecz liści) a zatem mamy większe mozliwości ich wszystkich cache'owania. W przeciętnym przypadku jest to wydajniejsze.


Drzewa tańczące

Drzewa tańczace scalają niewystarczająco pełne wierzchołki nie przy każdej modyfikacji drzewa, ale za to:



Atomowosc systemu plików Reiser4.

Redukcja zniszczeń po crashu. Kiedy komputer zalicza wypadek, dane w RAMie, które nie dostały się jeszcze na dysk, są tracone. Co gorsza, niektóre dane nie są tracone - może to prowadzić do poważnych blędów. Tu pojawia się potrzeba transakcyjnego wykonywania operacji na systemie plików.
Kiedy pewien zestaw operacji ma być wykonany cały, albo w ogóle, nazywamy tą calość atomem. Reiser4 implementuje wszystkie swoje plikowe wywołania systemowe jako w pełni atomowe operacje i pozwala na zdefiniowanie nowych operacji atomowych z użyciem infrastruktury pluginów.


Pluginy

Rozszerzalność przez pluginy rodzaje pluginów czynia Reiser4 'the most tweakable filesystem going'.

W systemie Reiser4 interakcje użytkownika z plikiem są obsługiwane przez pluginy plikowe, stanowiące skończone i ustrukturyzowane zbiory takich interakcji (metod). Każda metoda jest skomponowana z biblioteki funkcji, które, jak twórcy systemu uznali, byłyby użyteczne w konstruowaniu metod pluginów. każdy plik posiada identyfikator pluginu pliku. Gdziekolwiek podejmowana jest próba oddziaływania na plik, brana jest nazwa pliku, znajdowane id pluginu dla tego pliku, wewnątrz kernela istnieje tablica pluginów, zatem pluginid używany jest jako offset dla pluginu tego pliku wewnątrz tablicy. W konsekwencji, w celu dodania nowego pluginu pliku, nalezy zrekompilowac kernel i dodać plugin na koniec listy - nie można użyc ponownie, albo zmienić identyfikatoru pluginu, w przeciwnym wypadku należałoby przejrzeć cały system plików i zmieniać wszystkie pluginid, które już nie są poprawne.

W przyszłości planowane jest stworzenie dynamicznie ładowanego systemu pluginów.

file plugins - każdy plik i katalog posiada id pluginu. Te identyfikatory identyfikują zbiór metod. Metody te będą ucielesniały w systemie wszystkie możliwe interakcje z danym obiektem, które przychodzą ze źródeł zewnętrznych do ReiserFS'a. To jest powłoka dodana pomiędzy zewnętrzny interface do ReiserFS'a a jego resztę. Każda metoda posiada swój identyfikator. Naturalnie można mieszać i łączyć metody z innych pluginów podczas tworzenia nowego pluginu.
directory plugins - Reiser4 implementuje pluginy dla tradycyjnych katalogów - implementuje katalogowy styl dostępu do atrybutów plików, jako część pluginu dla regularnych plików. Kwestia dodania pozostałych pluginów dla katalogów jest kwestia sponsorowania - moze pojawi się w pozniejszych wersjach.
hash plugins - katalogi mapują z nazwy pliku do samego pliku. To mapowanie jest zaimplementowane przez wewnętrzne drzewa zbalansowane Reiser4. Niestety nazwy plików nie mogą być użyte jako klucze, jak długo klucze różnej dlugosci nie są zaimplementowane, lub nierozsądne ograniczenia na maksymalna długość nazwy pliku nie są zniesione. żeby to obejść, nazwy plików są hashowane i hash jest używany jako klucz w drzewie. Tu pojawia się problem - nie ma doskonałych funkcji hashujących i trzeba się zawsze liczyć z możliwoscią wystapięnia kolizji. Poprzednia wersja ReiserFS'a używała 'licznika generacji' do obejścia tego problemu: klucze dla nazw plików mające te same wartości funkcji hashującej były rozróżniane przez posiadanie różnych liczników generacji. To pozwalało zamortyzować kolizje funkcji hashujących kosztem zredukowania liczby bitów użytych na hashowanie. Technika licznika generacji jest aktualnie pewną formą wspierania niejednoznacznych kluczy ad hoc. Świadomość, że niektóre formy tego muszą byc zaimplementowane tak czy inaczej, popchnęła tworców systemu ReiserFS do implementacji bardziej regularego wsparcia dla niejednoznaczych kluczy w Reiser4.

written by Olgierd Skibski