Conference

FAST’15

Authors

Changman Lee, Dongho Sim, Joo-Young Hwang, Sangyeun Cho

Summary

Motivation

NAND flash memory has been widely used. However, file systems do not consider the characteristics of flash storage devices. In this paper, authors presented F2FS, a new file system optimized for modern flash storage devices.

Flash-friendly on-disk layout

F2FS divides the whole volume into fixed-size segments. The segment is a basic unit of management in F2FS. A section is comprised of consecutive segments, and a zone consists of a series of sections.

F2FS splits the entire volume into six areas: Superblock (SB), Checkpoint (CP), Segment Information Table (SIT), Node Address Table (NAT), Segment Summary Area (SSA), Main Area.

File structure

Instead of inode map in the original LFS, F2FS utilizes the “node” structure that extends the inode map to locate more indexing blocks. Each node block has a unique identification number, “node ID”. By using node ID as an index, NAT serves the physical locations of all node blocks. A node block represents one of three types: inode, direct and indirect node. F2FS uses pointer-based file indexing to eliminate update propagation (i.e., “wandering tree” problem).

Inode block a file’s metadata, such as file name, inode number, file size, atime, and dtime
Direct node block addresses of data
Indirect node node IDS locating another node blocks

F2FS supports inline data and inline extended attributes, which embed small-sized data or extended attributes in the inode block itself.

Directory structure

In, F2FS, a directory entry (”dentry”) block is composed of a bitmap and two arrays of slots and names in pairs. The bitmap tells whether each slot is valid or not. A slot carries a hash value, inode number, length of a file name and file type (normal file, directory and symbolic link).

Multi-head logging

f2fs-multihead

Cleaning

In F2FS, cleaning is done in the unit of a section.

  • Foreground cleaning is triggered only when there are not enough free sections, while a kernel thread wakes up periodically to conduct cleaning in background.
  • Background cleaning

A cleaning process:

  1. Victim selection The greedy policy selects a section with the smallest number of valid blocks. The cost-benefit policy is practiced in the background cleaning process. This policy selects a victime section not only based on its utilization but also its “age”.
  2. Valid block identification and migration
  3. Post-cleaning process

Adaptive logging

  • Normal logging

blocks are written to clean segments, yielding strictly sequential writes. As the free space shrinks to nil, however, this policy starts to suffer high cleaning overheads.

  • Threaded logging

blocks are written to holes (invalidated, obsolete space) in existing dirty segments. This policy requires no cleaning operations, but triggers random writes and may degrade performance as a result.

Checkpointing

F2FS implements checkpointing to provide a consistent recovery point from a sudden power failure or system crash. F2FS triggers a checkpoint procedure as follows:

  1. All dirty node and dentry blocks in the page cache are flushed
  2. It suspends ordinary writing activities including system calls such as create, unlink and mkdir
  3. The file system metadata (NAT, SIT, and SSA) are written to their dedicated areas on the disk
  4. F2FS writes a checkpoint pack (consisting of header and footer, NAT and SIT bitmaps, NAT and SIT journals, summary blocks of active segments, and orphan blocks) to the CP area.
  • Roll-back recovery

After a sudden power-off, F2FS rolls back to the latest consistent checkpoint.

  • Roll-forward recovery

F2FS implements an efficient roll-forward recovery mechanism to enhance fsync performance. The key idea is to write data blocks and their direct node blocks only, excluding other node or F2FS metadata blocks. In order to find the data blocks selectively after rolling back to the stable checkpoint, F2FS remains a special flag inside direct node blocks.