Systemy plików

Prezentacja w ramach przedmiotu Systemy Operacyjne 2002

Autor: Andrzej Karczyński

ReiserFS

Wstęp

ReiserFS jest systemem plików tworzonym open-source dla systemu Linux. Jednakże nie mógłby powstać bez sponsoringu wielu firm informatycznych. Podstawowym założeniem autorów było stworzenie efektywnego systemu plików ogólnego zastosowania.

Podstawowe cechy ReiserFS to:

· fast journaling – żeby zminimalizować czas sprawdzania integralności dysku

· używanie szybkich drzew zbalansowanych – żeby poprawić efektywność dla katalogów zawierających bardzo dużo plików

· efektywne wykorzystywanie miejsca - “upychanie” wielu małych plików w jednym bloku

Wyrównywanie plików do początków i końców bloków

Wyrównywanie plików do granic bloku ma następujące efekty:

· minimalizuje liczbę bloków dla pliku (jest to szczególnie zaletą dla dużych plików, gdy odwołujemy się do ich danych w sposób mało lokalny)

· marnuje przestrzeń dysku i bufora, przechowując całe, nie do końca zapisane bloki

· marnuje czas operacji wejścia-wyjścia na ściąganie całych, nie do końca zapisanych bloków

· zwiększa średnią ilość bloków potrzebnych dla dostępu do każdego pliku w katalogu

· ma prostszy kod

Przechowywanie plików w zrównoważonych drzewach

System ReiserFS przechowuje zarówno pliki, jak i nazwy plików w zrównoważonym drzewie. Małe pliki, katalogi, i-węzły oraz końce dużych plików (ogony) są efektywnie upakowane, dzięki odejściu od wyrównywania plików do bloków i i-węzłów o stałych rozmiarach. Duże pliki przechowywane są w niesformatowanych węzłach przyłączonych do drzewa, ale bez możliwości przenoszenia w algorytmach balansowania drzewa.

ReiserFS używa B+ drzew. B+ drzewa różnią się od B-drzew tym, że dane przechowywane są na samym dole drzew w liściach. W tej implementacji krótkie informacje (tzn. Katalogi, nazwy plików, małe pliki i ogony dużych plików) przechowywane są bezpośrednio w liściach, a duże pliki przechowywane są pod liściami.

Słabe strony pakowania wielu plików do bloku

· kiedy ogon pliku (pliki poniżej 4K są całe ogonem) urośnie na tyle, żeby zająć cały węzeł, zostaje usunięty ze sformatowanego węzła i przeniesiony do niesformatowanego węzła

· jeśli ogon jest mniejszy od całego węzła może zostać rozdzielony pomiędzy dwa węzły, co powoduje konieczność dwóch operacji dyskowych

· separowanie ogona od reszty plików może zmniejszyć efektywność czytania

· dodanie jednego bajta do pliku lub ogona, który nie jest na końcu węzła powoduje przeniesienie średnio połowy wielkości węzła w pamięci; sytuacja ta może się zdarzyć podczas niestandardowego niebuforowanego zapisu do pliku (funkcje biblioteczne I-O zapewniają buforowany dostęp do danych)

Zalety pakowania wielu plików do bloku

· większa efektywność wykorzystania operacji wejścia-wyjścia

· brak znaczących różnic w szybkości dla różnych rozmiarów bloków

Struktura drzewa

Drzewo zrównoważone w ReiserFS składa się z trzech rodzajów węzłów: internal nodes (węzły wewnętrzne), formatted nodes (liście) i unformatted nodes (podliście; węzły, które mogą wystąpić bezpośrednio pod liściami).

Internal nodes pełnią zwykłą funkcję węzłów wewnętrznych B-drzewa.

Formatted nodes są liściami B-drzewa. Składają się z items. Items zawierają unikatowy klucz do wyszukiwań i mogą być jednym z rodzajów:

· direct item – zawiera ogony plików

· indirect item – zawiera wskaźnik do unformatted node, zawierającego dane pliku (ale nie ogon)

· directory item – zawiera klucz pierwszego directory entry i liczbę directory entries, które zawiera

· stat data – zawiera dodatkowe dane dla pliku lub katalogu; znajduje się zawsze na początku pliku lub katalogu

Drzewo zapisane jest w blokach dysku. Każdy blok należący do drzewa zaczyna się od Block_head.

Internal node

Block_Head

Key 0

Key 1

---

Key N

Pointer 0

Pointer 1

---

Pointer N

Pointer N+1

....Free Space....

Formatted node

Block_Head

IHead 0

IHead 1

IHead 2

---

IHead N

....Free Space....

Item N

---

Item 2

Item 1

Item 0

Unformatted node

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Struktury internal node

Disc block

Block_Head

Key 0

Key 1

---

Key N

Pointer 0

Pointer 1

---

Pointer N

Pointer N+1

....Free Space....

struct block_head

Field Name	Type	Size (bytes)	Description
blk_level	unsigned short	2	Level of block in the tree (  1-leaf;  2,3,4,... - internal;
blk_nr_item	unsigned short	2	Number of Keys in an Internal block.  Or  Number of Items in a Leaf block.
blk_free_space	unsigned short	2	Block Free Space in bytes
blk_right_delim_key	struct key	16	Right delimiting key for this block (for Leaf nodes only)
	total	6 (8) 22 (24)	(6) 8 bytes for internal nodes ; (22) 24 bytes for leaf nodes

struct key

Field Name	Type	Size (bytes)	Description
k_dir_id	__u32	4	ID of the parent directory
k_object_id	__u32	4	ID of the object (also it is the number of inode)
k_offset	__u32	4	Offset from beginning of the object to the current byte of the object
k_uniqueness	__u32	4	Type of the item  (StatData = 0, Direct = -1, InDirect = -2,  Directory = 500)
	total	16	16 bytes

struct disc_child (wskaźnik do bloku dyskowego)

Field Name	Type	Size (bytes)	Description
dc_block_number	unsigned long	4	Disk child's block number.
dc_size	unsigned short	2	Disk child's used space.
	total	6	(6) 8 bytes

Struktury formatted (leaf) node

Struktura formatted node zawiera nagłówki i ciała items.

disc block

Block_Head

IHead 0

IHead 1

IHead 2

---

IHead N

Item N

---

Item 2

Item 1

Item 0

struct item_head

Field Name	Type	Size (bytes)	Description
ih_key	struct key	16	Key to search the item. All item headers is sorted by this key
u.ih_free_space u.ih_entry_count	__u16	2	Free space in the last unformatted node for an InDirect item; 0xFFFF for a Direct item ; 0xFFFF for a Stat Data item. The number of directory entries for a Directory item.
ih_item_len	__u16	2	total size of the item body
ih_item_location	__u16	2	an offset to the item body within the block
ih_reserved	__u16	2	used by reiserfsck
	total	24	24  bytes

struct stat_data

Field Name	Type	Size (bytes)	Description
sd_mode	__u16	2	file type, permissions
sd_nlink	__u16	2	number of hard links
sd_uid	__u16	2	owner id
sd_gid	__u16	2	group  id
sd_size	__u32	4	file size
sd_atime	__u32	4	time of last access
sd_mtime	__u32	4	time file was last modified
sd_ctime	__u32	4	time inode (stat data) was last changed (except changes to sd_atime and sd_mtime)
sd_rdev	__u32	4	device
sd_first_direct_byte	__u32	4	Offset from the beginning of the file to the first byte of direct item of the file.   ( -1) for directory   (    1) for small files (file has direct items only)  ( >1) for big files (file has indirect and direct items)  ( -1) for big files (file has indirect, but has not direct item)
	total	32	32  bytes

Directory item

deHead 0

deHead 1

deHead 2

---

deHead N

fileName N

---

fileName 2

fileName 1

fileName 0

Struct reiserfs_de_Head (deHead)

Field Name	Type	Size (bytes)	Description
deh_offset	__u32	4	third component of the directory entry key (all reiserfs_de_head sorted by this value)
deh_dir_id	__u32	4	objectid of the parent directory of the object, that is referenced by directory entry
deh_objectid	__u32	4	objectid of the object, that is referenced by directory entry
deh_location	__u16	2	offset of name in the whole item
deh_state	__u16	2	1) entry contains stat data (for future) 2) entry is hidden (unlinked)
	total	16	16 bytes

direct item

........................Small File Body............................

undirect item

unfPointer 0

unfPointer 1

unfPointer 2

---

unfPointer N

unfPointer - pointer to unformatted block (unfPointer size = 4 bytes)

Wstawianie węzła do drzewa

Przeszukuję się bitmapę wolnych bloków zaczynając od lewego sąsiada ostatnio używanego węzła i poruszając się w tym samym kierunku, co ostatnio.

W testach okazało się, że metoda ta jest lepsza od następujących alternatyw:

· wyszukiwanie pierwszego wolnego bloku w bitmapie

· branie pierwszego za ostatnio przydzielonym i poruszanie się w tym samym kierunku, co ostatnio (3% szybsze przy zapisie i 10-20% wolniejsze przy odczycie)

· zaczynanie od lewego sąsiada i poruszanie się w kierunku, branym od prawego sąsiada

Okazało się również, że metoda jest o ~10% szybsza niż gdybyśmy zaczynali od aktualnego węzła, mimo, że ryzykujemy jeden odczyt sięgnięcia do ojca, jeśli lewego sąsiada by nie było.

Porządek w drzewie

Porządek użyty w drzewie ma duże znaczenie dla wydajności systemu. Wpływa na lokalność czytania danych i efektywność upakowywania ogonów.

Struktura klucza składa się z pól: locality_id, object_id, offset, uniqueness.

Locality_id standardowo wskazuje na object_id katalogu nadrzędnego, co zapewnia nam lokalność.

Każdy plik, czy katalog ma unikatowy object_id.

Optymalizacje w balansowaniu drzewa

Priorytety:

· minimalizacja ilości użytych węzłów

· minimalizacja ilości węzłów poddających się operacji balansowania

· minimalizacja ilości unchached (nieskaszowanych?) węzłów poddających się operacji balansowania

· jeśli przenoszenie do innego formatted node jest potrzebne, maksymalizacja przenoszonych danych

Ostatni warunek oparty jest na lokalizacji. Istnieje duża szansa, że następna operacja dyskowa będzie w tym samym miejscu. W związku z tym, robimy sobie miejsce na następne operacje dyskowe.

Reiser 4

Przyszła wersja systemu (dostępna już wkrótce) ma zawierać wiele udoskonaleń:

· system transakcji, który jeszcze bardziej rozszerza pojęcie journalingu

· możliwość dołączania własnych plug-inów; użytkownik będzie mógł na przykład stworzyć swoją własną abstrakcję katalogu

· lepsze zapewnianie bezpieczeństwa

· lepsza wydajność

· zmiana architektury systemu na bardziej obiektową

· używanie repackera – specjalnego programu, który upakowuje ogony, jeszcze bardziej oszczędzając miejsce

· zmiana struktury drzew na drzewa “tańczące”; w czasie działania systemu struktura drzewa zmienia się dopiero przy operacji flush lub commit, a nie dla każdej operacji dyskowej

Nowe drzewa w innym miejscu podłączają duże pliki:

Podsumowanie

ReiserFS używa innowacyjnych technik przechowywania danych, znanych wcześniej w systemach bazodanowych. Użycie zrównoważonych drzew wydaje się być kosztowne algorytmicznie, ale testy dowodzą, że efektywność systemu jest porównywalna z ext2fs. ReiserFS doskonale się sprawdza przy przechowywaniu małych plików, oszczędzając dużo miejsca. Równie dobrze działa obsługa katalogów z bardzo dużą ilością plików (np. 100 000).

Materiały

http://www.namesys.com oficjalna strona ReiserFS. Można tu znaleźć szczegółowe informacje o tym systemie plików, chociaż tekst jest długi i zawiły, a autor często odbiega od tematu.