F2FS
F2FS (Flash-Friendly File System) is a flash file system initially developed by Samsung Electronics for the Linux kernel.
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
F2FS (Flash-Friendly File System) is a flash file system initially developed by Samsung Electronics for the Linux kernel. The motive for F2FS was to build a file system that, from the start, takes into account the characteristics of NAND flash memory-based storage devices (such as solid-state disks, eMMC, and SD cards), which are widely used in computer systems ranging from mobile devices to servers.
Works
F2FS was designed on a basis of a log-structured file system approach, which is adapted to newer forms of storage. Jaegeuk Kim, the principal F2FS author, has stated that it remedies some known issues of the older log-structured file systems, such as the snowball effect of wandering trees and high cleaning overhead.
In addition, since a NAND-based storage device shows different characteristics according to its internal geometry or flash memory management scheme (such as the Flash Translation Layer or FTL), it supports various parameters not only for configuring on-disk layout, but also for selecting allocation and cleaning algorithms. 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 Note that all the node blocks are mapped by the NAT, which means that the location of each node is translated by the NAT.
To mitigate the wandering tree problem, F2FS is able to cut off the propagation of node updates caused by leaf data writes. 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374851533 under CC BY-SA 4.0; modifications have been made.