F2FS - F2FS

F2FS
Entwickler Samsung Electronics , Motorola Mobility , Huawei und Google
Vollständiger Name Flash-freundliches Dateisystem
Eingeführt v3.8, 20.12.2012 mit Linux
Strukturen
Verzeichnisinhalt mehrstufige Hash-Tabelle
Dateizuordnung Bitmap (freier Speicherplatz), Tabelle
Bootfähig Ja, ab GRUB 2.04 (2019-07-05)
Grenzen
max. Volumengröße 16 TB
max. Dateigröße 3,94 TB
max. Anzahl der Dateien Abhängig von der Volumengröße
max. Dateinamenlänge 512 Byte
Merkmale
Daten aufgezeichnet Modifikation (mtime), Attributänderung (ctime), Zugriff (atime)
Datumsauflösung 1 ns
Attribute POSIX, erweiterte Attribute
Dateisystemberechtigungen POSIX, ACL
Transparente Kompression LZO, LZ4 (seit Linux 5.6), zstd (seit Linux 5.7)
Transparente Verschlüsselung Jawohl
Sonstiges
Unterstützte Betriebssysteme Linux und Android
Webseite f2fs .wiki .kernel .org

F2FS ( Flash-Friendly File System ) ist ein Flash-Dateisystem, das ursprünglich von Samsung Electronics für den Linux-Kernel entwickelt wurde .

Das Motiv für F2FS war, ein Dateisystem aufzubauen , das von Anfang an die Eigenschaften von NAND-Flash-Speicher- basierten Speichergeräten (wie Solid-State-Disks , eMMC und SD- Karten) berücksichtigt , die in Computern weit verbreitet sind Systeme von mobilen Geräten bis hin zu Servern.

F2FS wurde auf Basis eines log-strukturierten Dateisystemansatzes entwickelt , der an neuere Speicherformen angepasst ist. Jaegeuk Kim, der Haupt F2fs Autor, hat erklärt , dass es Heilmittel einig bekannten Probleme der älteren protokollstrukturierte Dateisysteme, wie zum Beispiel des Schneeballeffekt von Bäumen wandern und hohen Reinigungsaufwand. Da ein NAND-basiertes Speichergerät außerdem je nach interner Geometrie oder Flash-Speicherverwaltungsschema (wie Flash Translation Layer oder FTL) unterschiedliche Eigenschaften aufweist , unterstützt es verschiedene Parameter nicht nur für die Konfiguration des On-Disk-Layouts, sondern auch für Auswahl von Zuweisungs- und Reinigungsalgorithmen.

Merkmale

  • Mehrkopfprotokollierung
  • Mehrstufige Hash-Tabelle für Verzeichniseinträge
  • Statische/dynamische Heiß- und Kaltdatentrennung
  • Adaptives Protokollierungsschema
  • Konfigurierbare Betriebseinheiten
  • Doppelkontrollpunkt
  • Rollback- und Rollforward-Wiederherstellung
  • Blockzuweisung im Heap-Stil
  • TRIM/FITRIM- Unterstützung
  • Online-FS- Defragmentierung /Dateidefragmentierung
  • Inline-xattrs/data/dir
  • Offline- Dateisystemprüfung (Inkonsistenz prüfen und beheben)
  • Atomare Operationen
  • Verschlüsselung auf Dateisystemebene
  • Offline-Größenänderung (Verkleinerung wird nicht unterstützt.)
  • Innere periodische Datenspülung
  • Cache erweitern
  • Transparente Dateikomprimierung mit LZO oder LZ4 (mit Linux 5.6) oder zstd (mit Linux 5.7)

Entwurf

On-Disk-Layout

F2FS unterteilt das gesamte Volume in mehrere Segmente, von denen jedes auf 2 MB festgelegt ist. Ein Abschnitt besteht aus aufeinanderfolgenden Segmenten und eine Zone besteht aus einer Reihe von Abschnitten. Standardmäßig sind Abschnitts- und Zonengrößen auf dieselbe Größe eingestellt, aber Benutzer können die Größe einfach mit ändern mkfs.

F2FS teilt das gesamte Volume in sechs Bereiche auf, und alle außer dem Superblock-Bereich bestehen aus mehreren Segmenten, wie unten beschrieben.

Superblock (SB)
Der SB befindet sich am Anfang der Partition. Es gibt zwei Kopien, um eine Beschädigung des Dateisystems zu vermeiden. Es enthält grundlegende Partitionsinformationen und einige Standard-F2FS-Parameter.
Kontrollpunkt (CP)
Der CP enthält Dateisysteminformationen, Bitmaps für gültige NAT/SIT-Sätze, verwaiste Inode-Listen und Zusammenfassungseinträge der aktuellen aktiven Segmente.
Segmentinformationstabelle (SIT)
Die SIT enthält die gültige Blockzählung und die Gültigkeits-Bitmap aller Hauptbereichsblöcke.
Knotenadresstabelle (NAT)
Die NAT ist eine Adresstabelle für die Knotenblöcke des Hauptbereichs.
Segmentzusammenfassungsbereich (SSA)
Die SSA enthält Einträge, die die Besitzerinformationen der Hauptbereichsdaten und Knotenblöcke enthalten.
Hauptbereich
Der Hauptbereich enthält Datei- und Verzeichnisdaten und deren Indizes.

Um eine Fehlausrichtung zwischen Dateisystem und Flashspeicher zu vermeiden, gleicht F2FS die Startblockadresse des CPs an die Segmentgröße an. Außerdem wird die Startblockadresse des Hauptbereichs an die Zonengröße angepasst, indem einige Segmente im SSA-Bereich reserviert werden.

Metadatenstruktur

F2FS verwendet das Checkpoint-Schema, um die Integrität des Dateisystems aufrechtzuerhalten. Beim Mounten versucht F2FS zuerst, die letzten gültigen Checkpoint-Daten zu finden, indem es den CP-Bereich scannt. Um die Scanzeit zu reduzieren, verwendet F2FS nur zwei Kopien des CP. Einer von ihnen zeigt immer die letzten gültigen Daten an, was als Schattenkopie-Mechanismus bezeichnet wird. Neben dem CP verwenden auch NAT und SIT den Schattenkopie-Mechanismus. Aus Gründen der Dateisystemkonsistenz zeigt jeder CP, auf welche NAT- und SIT-Kopien gültig sind.

Indexstruktur

Die Schlüsseldatenstruktur ist der "Knoten". Ähnlich wie bei herkömmlichen Dateistrukturen hat F2FS drei Arten von Knoten: Inode, direkter Knoten, indirekter Knoten. F2FS weist einem Inode-Block 4 KB zu, der 923 Datenblockindizes, zwei direkte Knotenzeiger, zwei indirekte Knotenzeiger und einen doppelten indirekten Knotenzeiger enthält, wie unten beschrieben. Ein direkter Knotenblock enthält 1018 Datenblockindizes und ein indirekter Knotenblock enthält 1018 Knotenblockindizes. Somit deckt ein Inode-Block (dh eine Datei) Folgendes ab: 

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

Beachten Sie, dass alle Knotenblöcke von der NAT abgebildet werden, was bedeutet, dass die Position jedes Knotens von der NAT übersetzt wird. Um das Wandering-Tree-Problem zu mildern, ist F2FS in der Lage, die Verbreitung von Knotenaktualisierungen, die durch das Schreiben von Blattdaten verursacht werden, zu unterbinden.

Verzeichnisaufbau

Ein Verzeichniseintrag (dentry) belegt 11 Byte, die sich aus den folgenden Attributen zusammensetzen.

Eine Verzeichniseintragsstruktur
hash Hashwert des Dateinamens
ino Inode- Nummer
len Die Länge des Dateinamens
Typ Dateityp wie Verzeichnis, Symlink usw.

Ein Dentry-Block besteht aus 214 Dentry-Slots und Dateinamen. Eine Bitmap wird verwendet, um darzustellen, ob jede Dentry gültig ist oder nicht. Ein Dentry-Block belegt 4 KB und hat folgende Zusammensetzung: 

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

F2FS implementiert mehrstufige Hash-Tabellen für die Verzeichnisstruktur. Jede Ebene hat eine Hash-Tabelle mit einer dedizierten Anzahl von Hash-Buckets, wie unten gezeigt. Beachten Sie, dass "A(2B)" bedeutet, dass ein Bucket 2 Datenblöcke enthält.

Begriff
A steht für Eimer
B zeigt Block an
N steht für 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)

Wenn F2FS einen Dateinamen in einem Verzeichnis findet, wird zunächst ein Hashwert des Dateinamens berechnet. Dann durchsucht F2FS die Hash-Tabelle in Level #0, um den Dentry zu finden, der aus dem Dateinamen und seiner Inode-Nummer besteht. Wenn sie nicht gefunden wird, scannt F2FS die nächste Hash-Tabelle in Ebene #1. Auf diese Weise scannt F2FS Hash-Tabellen in jeder Ebene inkrementell von 1 bis N . In jeder Ebene muss F2FS nur einen Bucket scannen, der durch die folgende Gleichung bestimmt wird, die die Komplexität von O(log(# of files)) zeigt. 

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

Bei der Dateierstellung findet F2FS leere aufeinander folgende Slots, die den Dateinamen abdecken. F2FS durchsucht die leeren Slots in den Hash-Tabellen ganzer Ebenen von 1 bis N auf die gleiche Weise wie die Lookup-Operation.

Standardblockzuweisung

Zur Laufzeit verwaltet F2FS sechs aktive Protokolle im "Hauptbereich": Hot/Warm/Cold-Knoten und Hot/Warm/Cold-Daten.

Zuweisungsrichtlinie blockieren
Hot-Knoten Enthält direkte Knotenblöcke von Verzeichnissen.
Warmer Knoten Enthält direkte Knotenblöcke mit Ausnahme von Hot-Node-Blöcken.
Kalter Knoten Enthält indirekte Knotenblöcke.
Heiße Daten Enthält Zahnblöcke.
Warme Daten Enthält Datenblöcke außer heißen und kalten Datenblöcken.
Kalte Daten Enthält Multimediadaten oder migrierte Datenblöcke.

LFS verfügt über zwei Schemata für die Verwaltung des freien Speicherplatzes: Threaded Log und Copy-and-Compaction. Für Geräte mit sehr guter sequentieller Schreibleistung eignet sich das sogenannte Bereinigen des Kopier- und Komprimierungsschemas, da immer freie Segmente zum Schreiben neuer Daten bedient werden. Es leidet jedoch unter dem Reinigungsaufwand bei hoher Auslastung. Umgekehrt leidet das Threaded-Log-Schema unter zufälligen Schreibvorgängen, aber es ist kein Bereinigungsprozess erforderlich. F2FS verwendet ein hybrides Schema, bei dem das Kopier- und Komprimierungsschema standardmäßig übernommen wird, die Richtlinie jedoch entsprechend dem Dateisystemstatus dynamisch in das Threaded-Protokollschema geändert wird.

Um F2FS mit dem zugrunde liegenden Flash-basierten Speicher auszurichten, weist F2FS ein Segment in einer Einheit eines Abschnitts zu. F2FS erwartet, dass die Abschnittsgröße der Größe der Garbage Collection-Einheit in FTL entspricht. In Bezug auf die Mapping-Granularität in FTL ordnet F2FS jeden Abschnitt der aktiven Protokolle so vielen verschiedenen Zonen wie möglich zu. FTL kann die aktiven Protokolldaten gemäß ihrer Mapping-Granularität in eine Zuordnungseinheit schreiben.

Reinigungsprozess

F2FS führt die Reinigung sowohl bei Bedarf als auch im Hintergrund durch. Die bedarfsgesteuerte Bereinigung wird ausgelöst, wenn nicht genügend freie Segmente vorhanden sind, um VFS-Anrufe zu bedienen. Der Hintergrundreiniger wird von einem Kernel-Thread ausgeführt und löst den Reinigungsjob aus, wenn das System im Leerlauf ist.

F2FS unterstützt zwei Richtlinien zur Auswahl von Opfern: gierige und Kosten-Nutzen-Algorithmen. Beim Greedy-Algorithmus wählt F2FS ein Opfersegment mit der kleinsten Anzahl gültiger Blöcke aus. Beim Kosten-Nutzen-Algorithmus wählt F2FS ein Opfersegment entsprechend dem Segmentalter und der Anzahl gültiger Blöcke aus, um das im Greedy-Algorithmus vorhandene Log-Block-Thrashing-Problem anzugehen. F2FS verwendet den Greedy-Algorithmus für die Reinigung nach Bedarf, der Hintergrundreiniger verwendet den Kosten-Nutzen-Algorithmus.

Um zu erkennen, ob die Daten im Opfersegment gültig sind oder nicht, verwaltet F2FS eine Bitmap. Jedes Bit repräsentiert die Gültigkeit eines Blocks, und die Bitmap besteht aus einem Bitstrom, der ganze Blöcke im Hauptbereich abdeckt.

Annahme

Motorola Mobility verwendet F2FS seit 2012 in seinen Moto G/E/X- und Droid-Telefonen. Google hat F2FS erstmals 2014 in seinem Nexus 9 verwendet . Die anderen Produkte von Google haben F2FS jedoch erst beim Pixel 3 übernommen, als F2FS mit Inline-Krypto aktualisiert wurde Hardware-Unterstützung.

Huawei verwendet F2FS seit dem Huawei P9 im Jahr 2016. OnePlus verwendet F2FS seit dem OnePlus 3T im Jahr 2016. ZTE verwendet F2FS seit dem ZTE Axon 10 Pro im Jahr 2019.

Arch Linux und Gentoo Linux unterstützen F2FS, Debian unterstützt es auch ab Version 10 aufwärts.

Siehe auch

Verweise

Externe Links