Alokator bloków Orłowa

Alokator bloków Orłowa to algorytm określający, gdzie dany plik będzie rezydował w danym systemie plików (blokowo), aby przyspieszyć operacje na dysku.

Etymologia

Schemat został nazwany na cześć jego twórcy Grigorija Orłowa, który jako pierwszy opublikował w 2000 roku krótki opis i implementację techniki dla OpenBSD , która została później wykorzystana w wariantach jądra BSD Fast Filesystem .

Tło

Wydajność systemu plików zależy od wielu rzeczy; jednym z kluczowych czynników jest sposób, w jaki system plików rozmieszcza pliki na dysku. Ogólnie rzecz biorąc, najlepiej jest trzymać powiązane ze sobą elementy razem. Linux ext2 i ext3 próbowały rozmieścić katalogi na cylindrach dysku. Wyobraź sobie, że tworzysz system z katalogami domowymi użytkowników w /home: jeśli wszystkie katalogi pierwszego poziomu w obrębie /home (tj. katalogi domowe dla wielu użytkowników) są umieszczone obok siebie, może zabraknąć miejsca na zawartość tych katalogów. W ten sposób pliki użytkownika są umieszczane daleko od katalogów, które je zawierają, a wydajność spada.

Rozmieszczenie katalogów na dysku pozwala plikom w tym samym katalogu pozostać mniej lub bardziej ciągłymi w miarę wzrostu ich liczby i/lub rozmiaru, ale w niektórych sytuacjach powoduje to nadmierne rozmieszczenie danych na powierzchni dysku.

Jak to działa

Zasadniczo algorytm Orłowa próbuje dystrybuować katalogi „najwyższego poziomu” przy założeniu, że żaden z nich nie jest powiązany z innymi. Katalogi utworzone w katalogu głównym systemu plików są uważane za katalogi najwyższego poziomu; Theodore Ts'o dodał specjalną flagę i-węzła , która pozwala administratorowi systemu oznaczać również inne katalogi jako katalogi najwyższego poziomu. Jeśli /home znajduje się w głównym systemie plików, proste polecenie chattr sprawi, że system będzie traktował go jako katalog najwyższego poziomu.

Podczas tworzenia katalogu, który nie znajduje się w katalogu najwyższego poziomu, algorytm Orłowa próbuje umieścić go w tej samej grupie cylindrów, co jego element nadrzędny. Jednak zwraca się trochę więcej uwagi, aby zawartość katalogu również pasowała do tej grupy cylindrów; jeśli w grupie nie ma wielu i-węzłów lub bloków, katalog zostanie umieszczony w innej grupie cylindrów, która ma więcej dostępnych zasobów. Rezultatem tego wszystkiego, miejmy nadzieję, jest znacznie lepsza lokalizacja plików, które są naprawdę ze sobą powiązane i prawdopodobnie będą dostępne razem.

Wydajność

Wykazano, że alokator bloków Orlov oferuje wzrost wydajności w przypadku obciążeń, które przechodzą przez drzewa katalogów we FreeBSD. Według stanu na październik 2007 opublikowano tylko jeden wynik testu porównawczego dla ext3 przy użyciu alokatora. Wyniki są obiecujące: czas potrzebny do przejścia przez drzewo jądra Linuksa został skrócony o około 30%.

Ewolucja

Schemat Orłowa wymaga bardziej rygorystycznej analizy porównawczej; wymaga również poważnych testów warunków skrajnych, aby wykazać, że wydajność nie spada, gdy system plików jest zmieniany w czasie.

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Orlov_block_allocator&oldid=990109404 ”