F2FS - F2FS

F2FS
Deweloper(zy) Samsung Electronics , Motorola Mobility , Huawei i Google
Pełne imię i nazwisko System plików przyjazny dla Flash
Wprowadzono v3.8, 2012-12-20 z Linuksem
Struktury
Zawartość katalogu wielopoziomowa tablica mieszająca
Przydział plików bitmapa (wolne miejsce), tabela
Rozruchowy Tak, począwszy od GRUB 2.04 (05.07.2019)
Limity
Maks. wielkość woluminu 16 TB
Maks. rozmiar pliku 3,94 TB
Maks. liczba plików Zależy od wielkości woluminu
Maks. długość nazwy pliku 512 bajtów
Cechy
Daty zarejestrowania modyfikacja (mtime), modyfikacja atrybutu (ctime), dostęp (atime)
Rozdzielczość daty 1 ns
Atrybuty POSIX, rozszerzone atrybuty
Uprawnienia systemu plików POSIX, ACL
Przezroczysta kompresja LZO, LZ4 (od Linuksa 5.6), zstd (od Linuksa 5.7)
Przejrzyste szyfrowanie tak
Inne
Obsługiwane systemy operacyjne Linux i Android
Strona internetowa f2fs .wiki .jądro .org

F2FS ( Flash-Friendly File System ) to system plików flash opracowany początkowo przez firmę Samsung Electronics dla jądra Linux .

Motywem f2fs było zbudowanie systemu plików , że od samego początku bierze pod uwagę charakterystykę pamięci flash NAND opartych o urządzeniach magazynujących (takich jak dyski SSD , eMMC i SD kart), które są powszechnie stosowane w komputerze systemy od urządzeń mobilnych po serwery.

F2FS został zaprojektowany w oparciu o podejście oparte na systemie plików o strukturze logu , które jest przystosowane do nowszych form przechowywania. Jaegeuk Kim, główny f2fs autor stwierdził, iż środki niektóre znane problemy ze starszych systemów plików dziennika strukturze, takich jak efekt kuli śniegowej z wędrujących drzew i napowietrznych wysokiego czyszczenia. Ponadto, ponieważ urządzenie pamięci masowej oparte na NAND wykazuje różne cechy w zależności od wewnętrznej geometrii lub schematu zarządzania pamięcią flash (takich jak Flash Translation Layer lub FTL), obsługuje różne parametry nie tylko konfiguracji układu na dysku, ale także wybór algorytmów alokacji i czyszczenia.

Cechy

  • Rejestrowanie wielogłowicowe
  • Wielopoziomowa tablica mieszająca dla wpisów w katalogu
  • Statyczna/dynamiczna separacja danych gorących i zimnych
  • Adaptacyjny schemat rejestrowania
  • Konfigurowalne jednostki operacyjne
  • Podwójny punkt kontrolny
  • Odzyskiwanie typu roll-back i roll-forward
  • Alokacja bloków w stylu sterty
  • TRIM / FITRIM wsparcie
  • Defragmentacja fs online / defragmentacja plików
  • Wbudowane pliki xattrs/data/dir
  • Sprawdzanie systemu plików offline (sprawdź i napraw niespójność)
  • Operacje atomowe
  • Szyfrowanie na poziomie systemu plików
  • Zmiana rozmiaru w trybie offline (zmniejszanie nie jest obsługiwane).
  • Wewnętrzny okresowo opróżnianie danych
  • Pamięć podręczna zakresu
  • Transparentna kompresja plików przy użyciu LZO lub LZ4 (w Linuksie 5.6) lub zstd (w Linuksie 5.7)

Projekt

Układ na dysku

F2FS dzieli cały wolumen na kilka segmentów, z których każdy ma stałą wielkość 2 MB. Sekcja składa się z kolejnych odcinków, a strefa z zestawu odcinków. Domyślnie rozmiary sekcji i stref są ustawione na ten sam rozmiar, ale użytkownicy mogą łatwo zmienić rozmiar za pomocą mkfs.

F2FS dzieli cały wolumen na sześć obszarów, a wszystkie poza obszarem superbloku składają się z wielu segmentów, jak opisano poniżej.

Superblok (SB)
SB znajduje się na początku partycji. Istnieją dwie kopie, aby uniknąć uszkodzenia systemu plików. Zawiera podstawowe informacje o partycjach i niektóre domyślne parametry F2FS.
Punkt kontrolny (PK)
CP zawiera informacje o systemie plików, mapy bitowe dla poprawnych zestawów NAT/SIT, listy osieroconych i-węzłów oraz wpisy podsumowania bieżących aktywnych segmentów.
Tabela informacji o segmencie (SIT)
SIT zawiera prawidłową liczbę bloków i mapę bitową ważności wszystkich bloków obszaru głównego.
Tabela adresów węzła (NAT)
NAT to tablica adresów dla bloków węzłów obszaru głównego.
Obszar podsumowania segmentu (SSA)
SSA zawiera wpisy zawierające informacje o właścicielu bloków danych obszaru głównego i węzłów.
Główna strefa
Obszar główny zawiera dane plików i katalogów oraz ich indeksy.

Aby uniknąć niedopasowania między systemem plików a pamięcią flash, F2FS wyrównuje adres bloku początkowego CP z rozmiarem segmentu. Wyrównuje również adres bloku początkowego obszaru głównego z rozmiarem strefy, rezerwując niektóre segmenty w obszarze SSA.

Struktura metadanych

F2FS używa schematu punktów kontrolnych do utrzymania integralności systemu plików. W czasie montowania F2FS najpierw próbuje znaleźć ostatnie prawidłowe dane punktu kontrolnego, skanując obszar CP. Aby skrócić czas skanowania, F2FS używa tylko dwóch kopii CP. Jedna z nich zawsze wskazuje ostatnie poprawne dane, co nazywa się mechanizmem kopii w tle. Oprócz CP, NAT i SIT również używają mechanizmu kopiowania w tle. Aby zapewnić spójność systemu plików, każdy punkt CP wskazuje, do którego kopie NAT i SIT są ważne.

Struktura indeksu

Kluczową strukturą danych jest „węzeł”. Podobnie jak w przypadku tradycyjnych struktur plików, F2FS ma trzy typy węzłów: i-węzeł, węzeł bezpośredni, węzeł pośredni. F2FS przypisuje 4 KB do bloku i-węzła, który zawiera 923 indeksy bloków danych, dwa bezpośrednie wskaźniki węzłów, dwa pośrednie wskaźniki węzłów i jeden podwójny pośredni wskaźnik węzła, jak opisano poniżej. Bezpośredni blok węzłowy zawiera 1018 indeksów bloków danych, a pośredni blok węzłowy zawiera 1018 indeksów bloków węzłowych. Tak więc jeden blok i-węzła (tj. plik) obejmuje: 

4 KB × (923 + 2×1018 + 2×10182 + 10183) = 3.94 TB

Zauważ, że wszystkie bloki węzłów są mapowane przez NAT, co oznacza, że ​​lokalizacja każdego węzła jest tłumaczona przez NAT. Aby złagodzić problem wędrującego drzewa, F2FS jest w stanie odciąć propagację aktualizacji węzłów spowodowanych zapisami danych liścia.

Struktura katalogów

Wpis katalogu (dentry) zajmuje 11 bajtów, na co składają się następujące atrybuty.

Struktura wpisów do katalogu
haszysz Wartość skrótu nazwy pliku
ja nie Numer i- węzła
len Długość nazwy pliku
rodzaj Typ pliku, taki jak katalog, dowiązanie symboliczne itp.

Blok dentystyczny składa się z 214 gniazd dentystycznych i nazw plików. Mapa bitowa jest używana do reprezentowania, czy każde wgniecenie jest prawidłowe, czy nie. Blok dentystyczny zajmuje 4 KB i ma następujący skład: 

Dentry Block (4 K) = bitmap (27 bytes) + reserved (3 bytes) +
                      dentries (11 * 214 bytes) + file name (8 * 214 bytes)

F2FS implementuje wielopoziomowe tablice mieszające dla struktury katalogów. Każdy poziom ma tablicę haszującą z dedykowaną liczbą wiader haszujących, jak pokazano poniżej. Należy zauważyć, że „A(2B)” oznacza, że ​​zasobnik zawiera 2 bloki danych.

Semestr
A oznacza wiadro
B wskazuje blok
N oznacza MAX_DIR_HASH_DEPTH
level #0    A(2B)
level #1    A(2B) - A(2B)
level #2    A(2B) - A(2B) - A(2B) - A(2B)
    ...
level #N/2  A(2B) - A(2B) - A(2B) - A(2B) - A(2B) - ... - A(2B)
    ...
level #N    A(4B) - A(4B) - A(4B) - A(4B) - A(4B) - ... - A(4B)

Gdy F2FS znajdzie nazwę pliku w katalogu, najpierw obliczana jest wartość skrótu nazwy pliku. Następnie F2FS skanuje tablicę mieszającą na poziomie #0, aby znaleźć zębinę składającą się z nazwy pliku i jego numeru i-węzła. Jeśli nie zostanie znaleziony, F2FS skanuje następną tablicę mieszającą na poziomie #1. W ten sposób F2FS skanuje tablice mieszające na każdym poziomie przyrostowo od 1 do N . Na każdym poziomie F2FS musi skanować tylko jeden kubełek określony następującym równaniem, które pokazuje złożoność O(log(liczba plików)). 

 bucket number to scan in level #n = (hash value) % (# of buckets in level #n)

W przypadku tworzenia pliku F2FS znajduje puste kolejne gniazda, które zakrywają nazwę pliku. F2FS przeszukuje puste miejsca w tablicach mieszających całych poziomów od 1 do N w taki sam sposób, jak operacja wyszukiwania.

Domyślna alokacja bloków

W czasie wykonywania F2FS zarządza sześcioma aktywnymi dziennikami w obszarze „Main Area:” w węźle Hot/Warm/Cold oraz danymi Hot/Warm/Cold.

Polityka alokacji bloków
Gorący węzeł Zawiera bezpośrednie bloki węzłów katalogów.
Ciepły węzeł Zawiera bloki węzłów bezpośrednich z wyjątkiem bloków węzłów aktywnych.
Zimny ​​węzeł Zawiera pośrednie bloki węzłów.
Gorące dane Zawiera bloczki dentystyczne.
Ciepłe dane Zawiera bloki danych z wyjątkiem gorących i zimnych bloków danych.
Zimne dane Zawiera dane multimedialne lub zmigrowane bloki danych.

LFS ma dwa schematy zarządzania wolną przestrzenią: log wątkowy oraz kopiowanie i zagęszczanie. Schemat kopiowania i zagęszczania, który jest znany jako czyszczenie, jest odpowiedni dla urządzeń wykazujących bardzo dobrą wydajność zapisu sekwencyjnego, ponieważ wolne segmenty są cały czas podawane do zapisu nowych danych. Jednak cierpi z powodu czyszczenia narzutu podczas dużego użytkowania. I odwrotnie, schemat dziennika wątkowego cierpi z powodu losowych zapisów, ale nie jest potrzebny żaden proces czyszczenia. F2FS przyjmuje schemat hybrydowy, w którym schemat kopiowania i kompaktowania jest przyjmowany domyślnie, ale zasady są dynamicznie zmieniane na schemat dzienników wątkowych zgodnie ze stanem systemu plików.

W celu wyrównania F2FS z bazową pamięcią flash opartą na pamięci flash, F2FS przydziela segment w jednostce sekcji. F2FS oczekuje, że rozmiar sekcji będzie taki sam jak rozmiar jednostki wyrzucania elementów bezużytecznych w FTL. W odniesieniu do szczegółowości mapowania w FTL, F2FS przydziela każdą sekcję aktywnych dzienników do jak największej liczby różnych stref. FTL może zapisywać aktywne dane dziennika w jednej jednostce alokacji zgodnie z jej ziarnistością mapowania.

Proces czyszczenia

F2FS sprząta zarówno na żądanie, jak iw tle. Czyszczenie na żądanie jest uruchamiane, gdy nie ma wystarczającej liczby wolnych segmentów do obsługi wywołań VFS. Czyszczenie w tle jest wykonywane przez wątek jądra i uruchamia zadanie czyszczenia, gdy system jest bezczynny.

F2FS obsługuje dwie zasady selekcji ofiar: chciwość i algorytmy kosztów i korzyści. W algorytmie zachłannym F2FS wybiera segment ofiary mający najmniejszą liczbę prawidłowych bloków. W algorytmie kosztów i korzyści F2FS wybiera segment ofiary zgodnie z wiekiem segmentu i liczbą prawidłowych bloków w celu rozwiązania problemu thrashingu bloków logu obecnego w algorytmie zachłannym. F2FS wykorzystuje algorytm zachłanny do czyszczenia na żądanie, narzędzie do czyszczenia tła wykorzystuje algorytm kosztów i korzyści.

Aby określić, czy dane w segmencie ofiary są prawidłowe, czy nie, F2FS zarządza mapą bitową. Każdy bit reprezentuje ważność bloku, a mapa bitowa składa się ze strumienia bitów obejmującego całe bloki w obszarze głównym.

Przyjęcie

Motorola Mobility używa F2FS w swoich telefonach Moto G / E / X i Droid od 2012 roku. Google po raz pierwszy użył F2FS w swoim Nexusie 9 w 2014 roku. Jednak inne produkty Google nie przyjęły F2FS aż do Pixela 3, kiedy F2FS został zaktualizowany za pomocą wbudowanego krypto wsparcie sprzętowe.

Huawei używa F2FS od Huawei P9 w 2016 roku. OnePlus używa F2FS od OnePlus 3T w 2016 roku. ZTE używa F2FS od ZTE Axon 10 Pro w 2019 roku.

Arch Linux i Gentoo Linux obsługują F2FS, Debian obsługuje go również od wersji 10 w górę.

Zobacz też

Bibliografia

Zewnętrzne linki