SYSTEM PLIKÓW LFS

Na początku lat dziewięćdziesiątych grupa Berkeley, kierowana przez profesora Johna Ousterhouta i studenta Mendela Rosenbluma, opracowała nowy system plików, zwany Log-structured File System (RO91*). Ich motywacja do tego była oparta na następujących spostrzeżeniach:

  • Pamięć systemu rośnie: gdy pamięć staje się większa, więcej pamięci może być przechowywanych w buforze. W miarę buforowania danych, ruch dysku w coraz większym stopniu podnosi liczbę zapisów, ponieważ jest obsługiwana pamięć podręczna. Zatem wydajność systemu plików zależy w dużej mierze od skuteczności zapisu dysku.
  • Duża przepaść między losową wydajnością I/O i wydajnością I/O sekwencyjną: Szerokie pasmo przenoszenia dysku twardego znacznie wzrosło w ciągu lat gdy więcej bitów upakowywanych jest na powierzchni napędu, przy szerokim paśmie dostęp do wspomnianych bitów wzrasta. Czas poszukiwania i rotacji opóźnia się powoli, aby tanie i małe silniki szybciej rozkręcały talerze lub przesuwały ramię z głowicami. Tak więc, jeśli będziesz w stanie korzystać z dysków w sposób sekwencyjny, uzyskujesz znaczną przewagę wydajności w stosunku do podejść, które powodują wyszukiwanie i rotacje.
  • Istniejące systemy plików słabo działają na wielu typowych obciążeniach: Na przykład FFS (MJLF84) wykonał dużą liczbę zapisów, aby utworzyć nowy plik o rozmiarze jednego bloku: jeden dla nowego węzła, jeden dla aktualizacji mapy bitowej węzła, jeden dla bloku danych katalogowych, w którym jest plik, jeden do węzła katalogu aby go zaktualizować, jeden do nowego bloku danych, który jest częścią nowego pliku, a drugi do mapy bitowej danych, aby zaznaczyć blok danych. Tak więc, mimo że FFS umieszcza wszystkie te bloki w tej samej grupie bloków, FFS ponosi wiele krótkich prób i kolejnych opóźnień w ruchu, a zatem wydajność nie sprzyja szczytowej przepustowości pasma.
  • Systemy plików nie są rozpoznawane w trybie RAID: Na przykład zarówno RAID-4, jak i RAID-5 mają problem z małym zapisem, w którym logiczny zapis w jednym bloku powoduje 4 fizyczne we/wy. Istniejące systemy plików nie próbują uniknąć tego najgorszego zachowania zapisu RAID

WSKAZÓWKA: “SZCZEGÓŁY”

Wszystkie ciekawe systemy składają się z kilku ogólnych pomysłów i wielu szczegółów. Czasami, gdy uczymy się o tych systemach, myślimy sobie: “Och, mam ogólny pomysł; reszta to tylko szczegóły ” i używamy tylko połowicznie, aby dowiedzieć się, jak rzeczy naprawdę działają. Nie róbmy tego! Wiele razy szczegóły są krytyczne. Jak zobaczymy z LFS, ogólny pomysł jest łatwy do zrozumienia, ale naprawdę by zbudować system pracujący, musimy przemyśleć wszystkie trudne przypadki.

Idealny system plików skoncentruje się więc na wydajności zapisu i spróbuje wykorzystać kolejną szerokość pasma dysku. Ponadto dobrze byłoby to robić na wspólnych obciążeniach, które nie tylko zapisują dane, ale również często aktualizują struktury metadanych na dysku. Wreszcie działa on dobrze zarówno na dyski RAID, jak i na dyski pojedyncze. Nowy typ systemu plików Rosenblum i Ousterhout (RO91 – od nazwisk autorów i roku w którym powstał) wprowadzono pod nazwą LFS, skrót od Log-structured File System. Podczas zapisywania na dysk LFS najpierw buforuje wszystkie aktualizacje (w tym metadane!) w  wewnętrznym segmencie pamięci, gdy segment jest pełny, jest on zapisywany na dysku w jednym długim transferze do nieużywanej części dysku. LFS nigdy nie zastępuje istniejących danych, ale zawsze stara się zapisywać segmenty do wolnych lokalizacji. Ponieważ segmenty są duże, dysk jest używany efektywnie, a wydajność systemu plików zbliża się do jego zenitu.

Zagadka:

JAK zrobić wszystkie zapisy ciągłymi (sekwencyjnymi)?

Jak można przekształcić system plików w pisanie sekwencyjne? Dla odczytu to zadanie jest niemożliwe, ponieważ pożądany blok, który ma być odczytywany, może znajdować się w dowolnym miejscu na dysku. W przypadku zapisów system plików zawsze ma wybór i właśnie ten wybór mamy nadzieję wykorzystać.

  1. Sekwencyjnie zapisywanie na dysku. Mamy więc pierwsze wyzwanie: jak przekształcamy wszystkie aktualizacje stanu systemu plików w szereg kolejnych zapisów na dysk? Aby lepiej zrozumieć, użyjmy prostego przykładu. Wyobraźmy sobie, że piszemy blok danych D do pliku. Zapisywanie bloku danych na dysku może prowadzić do następującego układu na dysku, przy czym D jest zapisywany pod adresem dysku A0:

LFS fot1

Jednakże, gdy użytkownik zapisze blok danych, to nie tylko dane zapisywane są na dysku. Istnieją również inne metadane, które muszą zostać zaktualizowane. W tym przypadku zapisując inode (I) pliku na dysku wskazujemy na punkt bloku danych D. Podczas zapisu na dysk bloku danych i inode-a wyglądałoby to tak: (zauważ, że inode wygląda jak duży blok danych, co w większości przypadków nie występuje, w większości systemów bloki danych mają wielkość 4 KB, podczas gdy inod jest znacznie mniejszy, około 128 bajtów):

LFS fot2

Ten prosty i podstawowy pomysł zapisu wszystkich aktualizacji (takich jak bloki danych, inodes, itp.) na dysk, jest umiejscowiony w sercu LFS. Jeśli to zrozumiesz, otrzymasz podstawę idei tego pomysłu. Ale jak wszystkie skomplikowane systemy, diabeł jest w szczegółach.

Zapisywanie sekwencyjne i skuteczne

Niestety, sekwencyjne zapisywanie na dysku nie jest wystarczające, aby zagwarantować jego wydajność. Na przykład, wyobraźmy sobie, że gdybyśmy zapisali pojedynczy blok do adresowania A, w czasie T. Następnie odczekujemy chwilę i zapiszemy na dysk pod adresem A+1 (następny adres bloku w sekwencyjnym porządku), ale w czasie T+δ. Podczas pierwszego i drugiego zapisu niestety dysk został obrócony; podczas wydawania drugiego zapisu będzie czekać na większość obrotów zanim zostanie dopełniony (w szczególności, jeśli obrót trwa, Trotation , dysk będzie czekać Trotation – δ, zanim będzie mógł wypełnić drugi zapis na powierzchni dysku). A zatem można mieć nadzieję, że po prostu zapis na dysk w kolejności nie wystarczy, aby osiągnąć maksymalną wydajność, Musimy wydać dużą liczbę ciągłych zapisów (lub jednego dużego zapisu) na dysk, aby osiągnąć dobrą wydajność zapisu. Aby osiągnąć ten cel, LFS używa starożytnej techniki znanej jako buforowanie zapisu. Przed zapisaniem na dysk LFS śledzi aktualizacje pamięci i gdy otrzyma wystarczającą liczbę aktualizacji, zapisuje je na dysk na raz, co zapewnia efektywne wykorzystanie dysku. Duży fragment aktualizacji LFS zapisuje w jednym czasie jest określany przez nazwę segmentu. Chociaż ten termin jest nadmiernie wykorzystywany w systemach komputerowych, tutaj oznacza po prostu duży kawałek, który LFS używa do grupowania zapisów. Tak więc podczas zapisywania na dysk bufory LFS aktualizują się w segmencie pamięci, a następnie zapisuje segment na raz na dysku. Dopóki segment jest wystarczająco duży, zapisywanie będzie skuteczne. Oto przykład, w którym LFS buforuje dwa zestawy aktualizacji w małym segmencie; rzeczywiste segmenty są większe (kilka MB). Pierwsza aktualizacja składa się z czterech zapisów bloku do pliku j, druga to jeden blok dodawany do pliku k. LFS następnie zobowiązuje cały segment siedmiu bloków na dysk na raz. Wynikowy układ tych bloków jest następujący:

LFS fot 3

Jak dużo można buforować?

Powstaje tu pytanie: jak wiele aktualizacji powinno wchodzić do bufora LFS przed zapisaniem na dysk? Odpowiedź oczywiście zależy od samego dysku, w szczególności tego, jak wysokie napowietrzenie pozycjonowania jest porównywalne z szybkością transferu. Na przykład załóżmy, że pozycjonowanie (to znaczy rotacja i wyszukiwanie przez głowice) przed każdym zapisem zajmuje około sekund Tposition. Załóżmy dalej, że szybkość transferu dysku wynosi Rpeak MB/s. Ile powinien być bufor LFS przed zapisem podczas pracy na takim dysku? Sposób myślenia o tym jest taki, że za każdym razem, gdy zapisujesz, płacisz stały koszt ogólny kosztów pozycjonowania. Więc ile trzeba zapisać w celu amortyzacji tego kosztu? Im więcej zapisujesz, tym lepiej (oczywiście), i bliżej do osiągnięcia szczytowej przepustowości. Aby uzyskać konkretną odpowiedź, załóżmy, że wypuszczamy D MB. Czas na zapisanie tego fragmentu danych (Twrite) to czas pozycjonowania Tposition plus czas dla transferu D(D/Rpeak) lub:

LFS fot 4

A zatem efektywna szybkość zapisu (Reffective), która jest tylko ilością zapisanych danych, podzielona przez całkowity czas zapisu, to:

LFS fot 5

Co nas interesuje, uzyskuje się skuteczną stopę (Reffective) w pobliżu szczytowej stawki. W szczególności chcemy, aby efektywna stawka była jakąś frakcją F szybkości szczytowej, gdzie 0 <F <1 (typowy F może wynosić 0,9 lub 90% wartości szczytowej). W formie matematycznej oznacza to, że chcemy Reffective = F x Rpeak

W tym momencie możemy rozwiązać problem dla D:

LFS fot 6

Zróbmy przykład, z dysku z czasem pozycjonowania 10 milisekund i szybkości transferu szczytowego 100 MB s; przyjmujemy, że chcemy efektywnej szerokości pasma szczytowego wynoszącej 90% (F = 0,9). W tym przypadku D = 0,9/0,1 x 100 MB/s × 0,01 sekundy = 9 MB. Wypróbujmy różne wartości, aby zobaczyć, jak bardzo musimy buforować, aby podejść do szczytowej przepustowości. Ile potrzeba, aby osiągnąć 95% szczyt? a ile dla 99%?

Problem: Znajdowanie Inode-ów (węzłów)

Aby zrozumieć, jak znajdziemy inode-a w LFS, krótko przeanalizujmy jak znaleźć inode-a w typowym systemie plików UNIX. W typowym systemie plików, takim jak FFS, a nawet starym systemie plików UNIX, znajdowanie inodes jest łatwe, ponieważ są one zorganizowane w tablicy i umieszczane na dysku w stałych miejscach. Na przykład stary system plików UNIX przechowuje wszystkie węzły w stałej części dysku. Zatem biorąc pod uwagę numer inode-y i adres początkowy, aby znaleźć konkretną inodę, można obliczyć dokładny adres dysku po prostu przez pomnożenie numeru inode-y przez rozmiar inode-y i dodanie do adresu początkowego tablicy na dysku. Znalezienie inode-a znając numer inody w FFS jest nieco bardziej skomplikowane, ponieważ FFS dzieli  inode-y na kawałki i umieszcza grupę inodeów w każdej grupie cylindrów. Zatem trzeba wiedzieć, jak duży jest każdy fragment inodes i adresy początkowe każdej z nich. Następnie, obliczenia są podobne i łatwe. W LFS życie jest trudniejsze. Czemu? Cóż, udało nam się rozproszyć wszystkie węzły w całym dysku! Co gorsza, nigdy nie nadpisujemy miejsca, a zatem najnowsza wersja inody (tj. tej, którą chcemy) ciągle się przemieszcza.

Rozwiązanie metodą Indirection: Mapa Inode-ów (węzłów)

Aby rozwiązać ten problem, projektanci systemu LFS wprowadzili poziom wzajemnej zależności między numerami inode a inode-ami poprzez strukturę danych zwaną mapą inode (imap). Imap to struktura, która pobiera numer inode jako dane wejściowe i tworzy najnowszej wersji inode-y jej nowy adres.

WSKAZÓWKA: UŻYCIE POZIOMU ​​NIEBEZPOŚREDNIEGO

Ludzie często twierdzą, że rozwiązanie wszystkich problemów w informatyce jest po prostu poziomem obojętności. To nie jest prawda, jest to tylko rozwiązanie większości problemów. Z pewnością można myśleć o każdej wirtualizacji, którą studiowaliśmy, na przykład, pamięci wirtualnej lub pojęcia pliku, jako prostym poziomie wzajemności. I na pewno mapa węzłów w LFS jest wirtualizacją numerów węzłów. Mam nadzieję, że w tych przykładach zobaczysz wielką moc niebezpośredniości, co pozwala swobodnie przenosić struktury  bez potrzeby zmieniania ich odniesienia. Oczywiście, kierunek może mieć również wadę: dodatkowe przepełnienie. Więc następnym razem, gdy masz jakiś problem, spróbuj rozwiązać ten problem z kolejnym kierunkiem, ale pamiętaj, aby najpierw przemyśleć takie działania. Jak Wheeler sławnie powiedział: “Wszystkie problemy z informatyką można rozwiązać kolejnym poziomem niebezpośrednim, z wyjątkiem oczywiście problemu zbyt wielu niebezpośredniości”.

W ten sposób można sobie wyobrazić, że byłaby ona często implementowana jako prosta tablica z 4 bajtami (wskaźnikiem dysku) na wpis. Za każdym razem, gdy na dysku jest zapisany węzeł, imap jest aktualizowana w nowej lokalizacji. Imap powinna niestety utrzymywać się w sposób trwały. Dzięki temu LFS może śledzić lokalizację węzłów w trakcie awarii, a zatem działać zgodnie z potrzebami. Pytanie: gdzie imap powinien znajdować się na dysku? Oczywiście mogłaby być na stałej części dysku. Niestety, ponieważ często się aktualizuje, wymagałoby to aktualizacji struktur plików, po których następuje zapisywanie w imap, a tym samym spada wydajność. Zamiast tego LFS umieszcza fragmenty mapy węzłów obok miejsca, w którym zapisuje wszystkie inne nowe informacje. Tak więc, przy dodawaniu bloku danych do pliku k, LFS faktycznie zapisuje nowy blok danych, jego węzeł i kawałek mapy węzłów razem na dysk, w następujący sposób:

LFS fot 7

Na tym obrazku element tablicy imap przechowywany w bloku oznaczonym imap informuje LFS, że węzeł k jest na adresie dysku A1; ten węzeł z kolei mówi LFS, że jego blok danych D znajduje się pod adresem A0.

Dokończenie rozwiązania: Region Checkpoint

Mądry czytelnik mógł zauważyć problem. Jak znajdziemy teraz mapę węzłów, skoro jej fragmenty są teraz porozrzucane po dysku? W końcu nie ma magii: system plików musi mieć pewną stałą i znaną lokalizację na dysku, aby rozpocząć wyszukiwanie plików. LFS ma w tym celu takie miejsce na dysku, znane jako region kontrolny (CR). Region kontrolny zawiera punkty do (np. adresów) najnowszych fragmentów mapy inode, a zatem kawałki mapy węzłów można znaleźć, czytając CR jako pierwszy. Zauważ, że region kontrolny jest okresowo aktualizowany (co 30 sekund), a zatem wydajność nie jest zakłócona. Tak więc ogólna struktura układu na dysku zawiera obszar kontrolny (który wskazuje na ostatni punkt  mapy węzłów) gdzie każdy kawałek mapy węzłów zawiera adresy węzłów wskazujące na pliki (i katalogi), podobnie jak typowe systemy plików UNIX. Oto przykład regionu kontrolnego (należy zauważyć, że jest na początku dysku, w adresie 0) i pojedynczego bloku imap, węzła i danych. Prawdziwy system plików oczywiście miałby znacznie większe CR, wiele kawałków węzłów i oczywiście wiele innych węzłó, bloków danych itp.

LFS fot 8Czytanie pliku z dysku: ocena

Aby zrozumieć, jak działa LFS, przejdźmy teraz do tego, co musi się zdarzyć, aby przeczytać plik z dysku. Załóżmy na początek, że nic nie mamy w pamięci. Pierwszą strukturą danych na dysku, którą musimy przeczytać, jest region kontrolny. Region kontrolny zawiera punkty kontrolne (tj. adresy dysków) w całej mapie węzłów, a zatem LFS odczytuje całą mapę węzłów i zapisuje ją w pamięci. Po tym momencie, kiedy zostaje podany numeru pliku węzła, LFS wyszukuje numer węzła inode-diskaddress w imap i odczytuje w najnowszą wersję węzła. Aby odczytać blok z pliku, w tym momencie LFS proceduje dokładnie tak, jak w przypadku typowego systemu plików UNIX, przy użyciu bezpośrednich wskaźników lub pośrednich wskaźników lub podwójnie pośrednich wskaźników w razie potrzeby. We wspólnym przypadku LFS powinien wykonywać tę samą liczbę wejść/wyjść jako typowy system plików podczas odczytywania pliku z dysku. Cały plik imap jest przechowywany w pamięci podręcznej, a zatem dodatkowe zadanie LFS podczas odczytu polega na sprawdzaniu adresu węzła w imap.

Co o katalogach?

Do tej pory upraszczaliśmy naszą dyskusję nieco biorąc pod uwagę węzły oraz bloki danych. Aby uzyskać dostęp do pliku w systemie plików (np. /Home/marco/foo), niektóre katalogi również muszą być dostępne. W jaki sposób LFS przechowuje dane katalogowe? Na szczęście struktura katalogów jest w zasadzie identyczna z klasycznymi systemami plików UNIX, w tym katalogu jest tylko zbiór mapowań (nazwa, numer węzła). Na przykład podczas tworzenia pliku na dysku program LFS musi napisać nowy węzeł, niektóre dane, a także dane katalogowe i ich węzeł, które odnoszą się do tego pliku. Pamiętaj, że LFS będzie to robić kolejno na dysku (po buforowaniu aktualizacji przez jakiś czas). Tak więc utworzenie pliku foo w katalogu spowodowałoby utworzenie następujących nowych struktur na dysku:

LFS fot 9

Kawałek mapy węzłów zawiera informacje o lokalizacji zarówno katalogu pliku dir, jak i nowo utworzonego pliku f. W związku z tym podczas uzyskiwania dostępu do pliku foo (z numerem węzła k) najpierw powinniśmy spojrzeć na mape węzłów (zwykle w pamięci podręcznej w pamięci), aby znaleźć lokalizację węzła katalogu dir (A3), następnie odczytać katalog węzła, który zawiera lokalizację danych katalogowych (A2). Odczyt bloku danych daje mapowanie nazw numerów-węzłów (foo, k). Następnie ponownie odwiedzamy mapę węzłów, aby znaleźć lokalizację numeru węzła k (A1) i wreszcie odczytać żądany blok danych w adresie A0. W LFS jest jeden inny poważny problem, który rozwiązuje mapa węzłów, znany jako problem rekursywnej aktualizacji [Z+12]. Problem pojawia się w każdym systemie plików, który nigdy się nie aktualizuje (np. LFS), ale przenosi aktualizacje do nowych lokalizacji na dysku. Konkretnie, gdy tylko zostanie on uaktualniony, jego położenie na dysku zmienia się. Gdybyśmy nie uważali, oznaczałoby to również zaktualizowanie katalogu wskazującego na ten plik, który następnie wymusiłby zmianę jednostki nadrzędnej tego katalogu i tak dalej, aż po drzewie systemu plików . LFS sprytnie unika tego problemu z mapą węzłów. Mimo, że lokalizacja węzła może się zmienić, zmiana nigdy nie jest odzwierciedlana w samym katalogu – raczej struktura imap jest aktualizowana. Dzięki temu, LFS unika problemu rekurencyjnego aktualizowania.

Nowy problem: Co ze śmieciami

Być może zauważyłeś inny problem z LFS. Wielokrotnie zapisuje najnowszą wersję pliku (w tym jego węzeł i dane) do nowych miejsc na dysku. Ten proces, zachowując skuteczność zapisu, oznacza, że ​​LFS pozostawia stare wersje struktur plików rozproszonych na całym dysku. Nazywamy te stare wersje – śmieciami. Załóżmy na przykład, że mamy istniejący plik o numerze węzła k, który wskazuje na pojedynczy blok danych D0. Teraz aktualizujemy ten blok, generując zarówno nowy węzeł, jak i nowy blok danych. Powstały układ LFS na dysku wyglądałby mniej więcej tak: (pamiętaj, aby pominąć imap i inne struktury dla uproszczenia, nowy kawałek imap musiałby zostać zapisany na dysku, aby wskazywać nowy węzeł).

LFS fot 10

Na diagramie widać, że zarówno węzeł jak i blok, mają dwie wersje na dysku, jedną starą (po lewej) i jedną bieżącą, a więc żyjący (po prawej). Przy prostym akcie (logicznym) uaktualnieniu bloku danych, LFS musi utrzymywać wiele nowych struktur, pozostawiając stare wersje wspomnianych bloków na dysku. Jako kolejny przykład, wyobraźmy sobie dołączenie tego bloku do oryginalnego pliku k. W tym przypadku generowana jest nowa wersja węzła, ale stary blok danych jest nadal wskazany przez inną. W związku z tym nadal jest żywy i częścią obecnego systemu plików:

LFS fot 11

Więc co mamy zrobić z tymi starszymi wersjami węzłó, bloków danych itd.? Można zachować te starsze wersje i zezwalać użytkownikom na przywracanie starych wersji plików (na przykład podczas przypadkowego zastąpienia lub usunięcia pliku może to być przydatne). Taki system plików jest znany jako system plików wersji, ponieważ śledzi różne wersje pliku. LFS zamiast tego przechowuje tylko najnowszą wersję pliku (w tle), LFS musi okresowo odnaleźć stare, nieaktualne wersje plików, węzłów i innych struktur oraz oczyścić je. Czyszczenie powinno w ten sposób tworzyć bloki na wolnym dysku do użycia w kolejnych zapisach. Należy pamiętać, że proces czyszczenia to forma zbierania śmieci, w językach programowania, która automatycznie uwalnia niewykorzystaną pamięć dla programów.

     Wcześniej omawialiśmy segmenty jako ważne mechanizmy umożliwiające duże zapisy na dysku w LFS. Jak się okazuje, są one również integralną częścią skutecznego czyszczenia. Wyobraźmy sobie, co by się stało, gdyby oczyszczacz LFS po prostu przeszedł i uwolnił pojedyncze bloki danych, węzły itd. podczas czyszczenia. Wynik: system plików z pewną liczbą wolnych dziur pomieszanych między przydzieloną ilością miejsca na dysku. Wydajność zapisu znacznie się obniżyła, ponieważ LFS nie byłby w stanie odnaleźć dużego, ciągłego regionu do zapisu na dysk w sposób ciągły i z dużą wydajnością. Zamiast tego środek czyszciciel LFS działa w oparciu o segmenty, co eliminuje duże fragmenty przestrzeni do późniejszego zapisu. Podstawowy proces czyszczenia działa w następujący sposób. Okresowo użytkownik czyszczący LFS czyta w wielu starych (częściowo używanych segmentach), określa, które bloki są aktywne w obrębie tych segmentów, a następnie wpisuje nowy zestaw segmentów z po prostu aktywnymi blokami wewnątrz nich, uwalniając stare do zapisu. W szczególności oczekujemy od użytkownika odczytu w M istniejących segmentach, kompaktowania ich zawartości w N nowych segmentach (gdzie N<M), a następnie zapisać segmenty N na dysku w nowych miejscach. Stare segmenty M są następnie zwolnione i mogą być używane przez system plików do późniejszych zapisów. Mamy jednak dwa problemy. Pierwszy to mechanizm: jak LFS może wskazać, jakie bloki w segmencie są żywe, a które nie? Druga to polityka: jak często czyszczenie powinno być uruchamiane i które segmenty powinny być wybrane do czyszczenia?

Określanie żywotności bloku

Najpierw adresujemy mechanizm. Biorąc pod uwagę blok danych D w dyskowym segmencie S, LFS musi być w stanie określić, kiedy D jest żywe. W tym celu LFS dodaje dodatkowe informacje do każdego segmentu, który opisuje każdy blok. W szczególności, dla każdego bloku danych D zawiera numer węzła i jego przesunięcie. Informacje te są zapisywane w strukturze na czele segmentu określanego jako blok podsumowania segmentów.

     Biorąc pod uwagę te informacje, jest jasne, czy blok jest żywy czy martwy. Dla bloku D znajdującego się na dysku na adresie A, spójrz w bloku podsumowania segmentu i znajdź jego numer węzła N oraz jego  przesunięcie T. Następnie spójrzmy do imap, aby znaleźć miejsce, w którym znajduje się N i odczytajmy N z dysku (być może jest już w pamięci , co jest jeszcze lepsze). Na koniec, używając offsetu T, poszukajmy w bloku, aby ustalić, gdzie węzeł uważa, że ​​blok T tego pliku znajduje się na dysku. Jeśli wskazuje dokładnie adres dysku A, LFS może stwierdzić, że blok D jest żywy. Jeśli wskaże gdziekolwiek indziej, LFS może stwierdzić, że D nie jest używany (tj. Jest martwy), a zatem wie, że ta wersja nie jest już potrzebna. Poniżej znajduje się podsumowanie pseudokodów tego procesu:

  • (N, T) = SegmentSummary[A];
  • inode = Read(imap[N]);
  • if (inode[T] == A)
  • // block D is alive
  • else
  • // block D jest śmietnikiem

Oto schemat przedstawiający mechanizm, w którym blok podsumowania segmentu (oznaczony SS) rejestruje, że blok danych w adresie A0 jest w rzeczywistości częścią pliku k w offsecie 0. Sprawdzając imap dla k można znaleźć węzeł i zobaczyć, że rzeczywiście wskazuje na to miejsce.

LFS fot12

Istnieją pewne skróty, które LFS potrzebuje, aby proces skuteczniejszego oceniania był bardziej efektywny. Na przykład, gdy plik jest obcięty lub usunięty, LFS zwiększa jego numer wersji i zapisuje nowy numer wersji w imap. Poprzez zapisanie numeru wersji w segmencie na dysku, LFS może zwierać dłuższą kontrolę opisaną powyżej, po prostu porównując numer wersji na dysku z numerem wersji w imapie, co pozwala uniknąć dodatkowych odczytów.

Pytanie o politykę: jakie bloki należy czyścić i kiedy?

Oprócz mechanizmu opisanego powyżej LFS musi zawierać zestaw zasad określających, kiedy należy czyścić i które bloki są czyszczone. Określenie kiedy czyszczenie jest łatwiejsze – okresowo, w czasie bezczynności, lub gdy trzeba, ponieważ dysk jest pełny. Określenie, które bloki do czyszczenia są trudniejsze i były przedmiotem wielu prac badawczych. W oryginalnym opisie LFS [RO91] autorzy opisują podejście próbujące segregować gorące i zimne segmenty. Gorący segment to taki, w którym treść jest często nadpisywana, w związku z tym w przypadku takiego segmentu najlepszą polityką jest poczekać dłuższy czas przed jej czyszczeniem, ponieważ coraz więcej bloków przechodzi nadpisywanie (w nowych segmentach), a tym samym uwalnia się do użytku. Zimny ​​segment w przeciwieństwie, może mieć kilka martwych bloków, ale reszta jego zawartości jest stosunkowo stabilna. W związku z tym należy później wyczyścić zimne segmenty szybciej a gorące później a następnie opracować heurystykę, która dokładnie to robi. Jednakże, podobnie jak w przypadku większości polityk, polityka ta nie jest doskonała.

Odzyskiwanie w przypadku awarii i dziennik (log)

Jedyny ostateczny problem: co się stanie jeśli system się zawiesza, podczas gdy LFS zapisuje na dysku? Jak pamiętasz w poprzednim rozdziale dotyczącym dzienników, awarie podczas aktualizacji są trudne w przypadku systemów plików, a co za tym idzie również sprawy LFS. Podczas normalnej pracy bufory LFS zapisują w segmencie a następnie (gdy segment jest pełny lub gdy upłynął okres) zapisuje ten segment na dysku. LFS organizuje te zapisy w dzienniku, tzn. obszar punktów kontrolnych wskazuje na segment głowy i ogona a każdy segment wskazuje na kolejny segment, który ma być zapisany. LFS okresowo aktualizuje również region kontrolny. Zdarzenia mogą się wydarzyć podczas jednej z tych operacji. W jaki sposób LFS poradzi sobie z awariami podczas zapisywania do tych struktur? Załóżmy najpierw drugą sprawę. Aby zapewnić, że aktualizacja CR nastąpi atomowo, LFS faktycznie trzyma dwie pamięci CR, jedną na każdym końcu dysku i zapisuje do nich na przemian. LFS implementuje także ostrożny protokół podczas aktualizowania CR z najnowszymi wskaźnikami do mapy węzłów i innymi informacjami. W szczególności, najpierw zapisuje nagłówek (ze znacznikiem czasu), potem ciało CR, a następnie ostatni blok (również z znacznikiem czasu). Jeśli system ulegnie awarii podczas aktualizacji CR, LFS może to wykryć, widząc niespójną parę znaczników czasu. LFS zawsze wybierze najnowszą wersję CR, która ma zgodne timestamps, a tym samym osiąga spójną aktualizację CR. Załóżmy teraz pierwszy przypadek. Ponieważ LFS zapisuje CR co 30 sekund, ostatnia spójna migawka systemu plików może być dość stara. Tak więc, po ponownym uruchomieniu, LFS może łatwo odzyskać po prostu czytając w obszarze kontrolnym, na wskazując na kawałki imap a następnie pliki i katalogi. Utracone jednak zostanie ostatnie kilka sekund aktualizacji. Aby polepszyć to, LFS próbuje odbudować wiele z tych segmentów za pomocą techniki zwanej rolą w społeczności bazy danych. Podstawową ideą jest rozpoczęcie od ostatniego obszaru kontrolnego, odnalezienie końca dziennika (który jest zawarty w CR), a następnie użycie go do odczytywania kolejnych segmentów i sprawdzenia, czy w nim są poprawne aktualizacje. Jeśli tak, LFS aktualizuje system plików, a tym samym odzyskuje wiele danych i metadanych zapisanych od ostatniego punktu kontrolnego. Więcej szczegółowych informacji na ten temat można znaleźć w rozprawie Rosenblum [R92].

Podsumowanie

LFS wprowadza nowe podejście do aktualizowania dysku. Zamiast nadpisywać pliki w miejscach, LFS zawsze zapisuje do niewykorzystanej części dysku, a następnie odzyskuje stare miejsce przez czyszczenie. To podejście, które w systemach baz danych nazywa się funkcją shadow-paging a system plików-system nazywany jest czasami copy-on-write, pozwala na bardzo wydajne zapisywanie, ponieważ LFS może zebrać wszystkie aktualizacje w segmencie pamięci i następnie zapisać je razem sekwencyjnie.

Minusem tego podejścia jest to, że generuje śmieci, stare kopie danych są rozproszone na całym dysku, a jeśli ktoś chce odzyskać taką przestrzeń do późniejszego użycia, to musi okresowo czyczyścić stare segmenty. Czyszczenie stało się przedmiotem wielu kontrowersji w LFS, a obawy dotyczące kosztów czyszczenia mogą ograniczać początkowy wpływ LFS w stosunku do innych systemów. Jednak niektóre nowoczesne komercyjne systemy plików, w tym WAFL NetApp, Sun’s ZFS i Linux btrfs, a nawet nowoczesne pamięci flash typu flash, przyjmują podobne podejście typu copy-on-write a tym samym intelektualne dziedzictwo LFS żyje w tych nowoczesnych systemach plików. W szczególności, WAFL rozwiązał problemy związane z czyszczeniem, przekształcając je w funkcję i udostępniając stare wersje systemu plików za pośrednictwem migawek, użytkownicy mogą uzyskać dostęp do starych plików, gdy przypadkowo je usuną.