F2FS

F2FS divide todo el volumen en varios segmentos, cada uno de los cuales tiene un tamaño fijo de 2  MB. Una sección se compone de segmentos consecutivos, y una zona consta de un conjunto de secciones. Por defecto, los tamaños de las secciones y las zonas se establecen al mismo tamaño, pero los usuarios pueden modificar fácilmente el tamaño con mkfs.

F2FS divide todo el volumen en seis áreas, y todas, excepto el área del superbloque, constan de múltiples segmentos como se describe a continuación.

Superbloque (SB)

El SB se encuentra al inicio de la partición. Existen dos copias para evitar la corrupción del sistema de archivos. Contiene información básica de la partición y algunos parámetros predeterminados de F2FS.

Punto de control (PC)

El CP contiene información del sistema de archivos, mapas de bits para conjuntos NAT/SIT válidos, listas de inodos huérfanos y entradas de resumen de los segmentos activos actuales.

Tabla de información de segmentos (SIT)

El SIT contiene el recuento de bloques válidos y el mapa de bits de validez de todos los bloques del Área Principal.

Tabla de direcciones de nodo (NAT)

La NAT es una tabla de direcciones para los bloques de nodos del Área Principal.

Área de Resumen de Segmentos (SSA)

El SSA contiene entradas que incluyen la información del propietario de los bloques de datos y nodos del Área Principal.

Área principal

El área principal contiene datos de archivos y directorios, así como sus índices.

Para evitar desalineaciones entre el sistema de archivos y el almacenamiento flash, F2FS alinea la dirección del bloque de inicio del CP con el tamaño del segmento. Asimismo, alinea la dirección del bloque de inicio del Área Principal con el tamaño de la zona reservando algunos segmentos en el área SSA.

F2FS utiliza el esquema de puntos de control para mantener la integridad del sistema de archivos. Al montar un archivo, F2FS intenta primero encontrar los últimos datos válidos del punto de control escaneando el área CP. Para reducir el tiempo de escaneo, F2FS utiliza solo dos copias del CP. Una de ellas siempre indica los últimos datos válidos, lo que se conoce como mecanismo de copia de sombra. Además del CP, NAT y SIT también utilizan este mecanismo de copia de sombra. Para garantizar la coherencia del sistema de archivos, cada CP indica qué copias de NAT y SIT son válidas.

La estructura de datos clave es el "nodo". Al igual que las estructuras de archivos tradicionales, F2FS tiene tres tipos de nodos: inodo, nodo directo y nodo indirecto. F2FS asigna 4  KB a un bloque de inodo, que contiene 923 índices de bloques de datos, dos punteros de nodo directo, dos punteros de nodo indirecto y un puntero de nodo doblemente indirecto, como se describe a continuación. Un bloque de nodo directo contiene 1018 índices de bloques de datos, y un bloque de nodo indirecto contiene 1018 índices de bloques de nodo. Por lo tanto, un bloque de inodo (es decir, un archivo) abarca:

4  KiB × (923 + 2×1018 + 2×1018 2 + 1018 3 ) = 4.228.213.756  KiB = 4.129.114,996  MiB = 4.032,338863  GiB = 3,937830921  TiB

Cabe destacar que todos los bloques de nodos se mapean mediante NAT, lo que significa que la ubicación de cada nodo se traduce mediante NAT. Para mitigar el problema del árbol errante, F2FS puede interrumpir la propagación de las actualizaciones de nodos causadas por la escritura de datos en las hojas.

A directory entry (dentry) occupies 11 bytes, which consists of the following attributes.

A dentry block consists of 214 dentry slots and file names. A bitmap is used to represent whether each dentry is valid or not. A dentry block occupies 4 KB and has the following composition:

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

F2FS implements multi-level hash tables for the directory structure. Each level has a hash table with a dedicated number of hash buckets as shown below. Note that "A(2B)" means a bucket includes 2 data blocks.

Term

A indicates bucket

B indicates block

N indicates 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) 

When F2FS finds a file name in a directory, first a hash value of the file name is calculated. Then, F2FS scans the hash table in level #0 to find the dentry consisting of the file name and its inode number. If not found, F2FS scans the next hash table in level #1. In this way, F2FS scans hash tables in each level incrementally from 1 to N. In each level F2FS needs to scan only one bucket determined by the following equation, which shows O(log(# of files)) complexity.

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

In the case of file creation, F2FS finds empty consecutive slots that cover the file name. F2FS searches the empty slots in the hash tables of whole levels from 1 to N in the same way as the lookup operation.

At runtime, F2FS manages six active logs inside the "Main Area:" Hot/Warm/Cold node and Hot/Warm/Cold data.

LFS cuenta con dos esquemas para la gestión del espacio libre: registro multihilo y copia y compactación. El esquema de copia y compactación, también conocido como limpieza, es ideal para dispositivos con un excelente rendimiento de escritura secuencial, ya que los segmentos libres se utilizan constantemente para escribir nuevos datos. Sin embargo, genera una sobrecarga de limpieza durante periodos de alta utilización. Por otro lado, el esquema de registro multihilo permite escrituras aleatorias, pero no requiere ningún proceso de limpieza. F2FS adopta un esquema híbrido en el que el esquema de copia y compactación se utiliza por defecto, pero la política se modifica dinámicamente al esquema de registro multihilo según el estado del sistema de archivos.

Para alinear F2FS con el almacenamiento flash subyacente, F2FS asigna un segmento en una unidad de sección. F2FS espera que el tamaño de la sección sea igual al tamaño de la unidad de recolección de basura en FTL. Con respecto a la granularidad de mapeo en FTL, F2FS asigna cada sección de los registros activos a tantas zonas diferentes como sea posible. FTL puede escribir los datos de los registros activos en una unidad de asignación según su granularidad de mapeo.

F2FS realiza la limpieza tanto bajo demanda como en segundo plano. La limpieza bajo demanda se activa cuando no hay suficientes segmentos libres para atender las llamadas VFS. El limpiador en segundo plano se ejecuta mediante un hilo del kernel y activa la tarea de limpieza cuando el sistema está inactivo.

F2FS admite dos políticas de selección de víctimas: algoritmos voraces y de costo-beneficio. En el algoritmo voraz, F2FS selecciona un segmento víctima con el menor número de bloques válidos. En el algoritmo de costo-beneficio, F2FS selecciona un segmento víctima según la antigüedad del segmento y el número de bloques válidos para abordar el problema de sobrecarga de bloques del registro presente en el algoritmo voraz. F2FS utiliza el algoritmo voraz para la limpieza bajo demanda, mientras que el limpiador en segundo plano utiliza el algoritmo de costo-beneficio.

Para determinar si los datos del segmento afectado son válidos o no, F2FS gestiona un mapa de bits. Cada bit representa la validez de un bloque, y el mapa de bits se compone de una secuencia de bits que abarca bloques completos en el Área Principal.

Google utilizó F2FS por primera vez en su Nexus 9 en 2014. ^{[ 20 ]} Sin embargo, otros productos de Google no adoptaron F2FS hasta el Pixel 3, cuando F2FS se actualizó con soporte de hardware criptográfico en línea. ^{[ 21 ]}

Huawei ha utilizado F2FS desde el Huawei P9 en 2016. ^{[ 22 ] [ 23 ]} OnePlus ha utilizado F2FS en el OnePlus 3T. ^{[ 24 ]}

Motorola Mobility utiliza F2FS en sus teléfonos Moto G/E/X y Droid desde 2012.

Samsung utilizó F2FS por primera vez para el Galaxy Note 10 en 2019. ^{[ 25 ]}

ZTE ha utilizado F2FS desde el ZTE Axon 10 Pro en 2019. ^{[ 26 ]}

F2FS se fusionó con el kernel de Linux a finales de 2012. ^{[ 27 ]} Numerosas distribuciones lo soportan. ^{[ 28 ] [ 29 ] [ 30 ]}