[041][译]f2fs.txt

解决游荡树问题
- 引入包含所有"node"位置的节点地址表（NAT）块;这将切断更新传播。

加速目录的查询速度
-F2FS为目录结构实现多级哈希表

减少清理开销
- 支持后台清理过程
- 支持贪婪和成本效益算法的victim选择策略
- 支持 静态/动态 冷热数据分离的多头日志
- 引入自适应日志以实现高效的块分配

================================================================================
什么是Flash-Friendly File System (F2FS)?
================================================================================
基于NAND闪存的存储设备，如SSD、eMMC和SD卡，已经被装备从移动到服务器系统的各种系统。
因为它们具备不同于传统旋转磁盘的特性，这类存储设备的文件系统应该适配从设计草图级别上的改变。

F2FS是一个利用基于NAND闪存的存储设备的文件系统，它基于日志结构文件系统（LFS）。设计的重点是
解决LFS中的基本问题，即游荡树的雪球效应和高清理开销。

因为基于NAND闪存的存储设备显示出不同的特性，根据其内部几何结构或闪存管理方案，即FTL，
F2FS及其工具不仅支持在磁盘上配置的各种参数布局，也可用于选择分配和清理算法。

下面的git树提供了文件系统格式化工具（mkfs.f2fs），一个一致性检查工具（fsck.f2fs）和
一个调试工具（dump.f2fs）。
>> git clone http://git.kernel.org/pub/scm/linux/kernel/git/jaegeuk/f2fs-tools.git

要报告错误和发送修补程序，请使用以下邮件列表：
>> linux-f2fs-devel@lists.sourceforge.net

================================================================================
背景和设计问题
================================================================================

日志结构文件系统（LFS）
--------------------------------
"日志结构的文件系统将所有修改按顺序写入磁盘一种类似日志的结构，从而加快文件写入和崩溃恢复。
日志是磁盘上唯一的结构；它包含索引信息，以便可以有效地从日志中读取文件。为了保持磁盘上有用于快速
写入的大的空闲区域，我们将日志分成若干segment，并使用segment清理器用于压缩来自严重碎片的实时信息"
摘自Rosenblum，M.和Ousterhout，J.K.，
1992年，"日志结构文件系统的设计和实现", 计算机系统 10，1，26–52。

游荡树问题
----------------------
在LFS中，当文件数据被更新并写入日志末尾时，它的直接指针块由于位置更改已更新。然后间接指针块由于
直接指针块更新，块也会更新。以这种方式，inode, inode map, 和checkpoint block等上层索引结构
也是递归更新。这个问题叫做游荡树问题[1]，为了提高性能，应该尽可能多消除或放松这种更新的传播。

[1] Bityutskiy, A. 2005. JFFS3 design issues. http://www.linux-mtd.infradead.org/

清理开销
-----------------
因为LFS是基于不适当的写操作，所以它会产生很多失效的块分散在整个仓库里。为了提供新的空日志空间，它
需要将这些失效的块无缝地回收给用户。这个工作叫做作为一个清理过程。

该过程包括以下三个操作:
1.通过引用segment的使用表来选择victim segment。
2.加载由segment摘要块标识的victim中所有数据的父索引结构。
3.检查数据与其父索引结构之间的交叉引用。
4.有选择地移动有效数据。

这项清理工作可能会导致意想不到的长时间延迟，因此最重要的目标就是对用户隐藏延迟。当然，应该减少
要移动的有效数据量，并快速移动它们。

================================================================================
关键功能
================================================================================
闪光意识
---------------
- 扩大随机写入区域以获得更好的性能，但提供高的空间位置
- 尽最大努力将FS(FileSystem)的数据结构与FTL（日志结构文件系统）中的操作单元一一对应

游荡树问题
----------------------
- 使用表示索引节点和各种指针块的术语"node"
- 引入包含所有"node"位置的节点地址表（NAT）块;这将切断更新传播。

清理开销
-----------------
- 支持后台清理过程
- 支持贪婪和成本效益算法的victim选择策略
- 支持 静态/动态 冷热数据分离的多头日志
- 引入自适应日志以实现高效的块分配

================================================================================
MOUNT 选项
================================================================================

background_gc=%s       开启/关闭清洁操作，即垃圾回收，当I/O子系统无所事事。
                       如果background_gc=on关闭垃圾回收
                       如果background_gc=off关闭垃圾回收
                       默认值是on. 所以垃圾回收开启

disable_roll_forward   禁用前滚恢复例程

discard                清除段时发出放弃/修剪命令

no_heap                禁用从主区域开始的数据段或者对于主区域末端的节点找到空闲的，按照堆样式段分配

nouser_xattr           禁用扩展用户属性
                       注意：默认已启用xattr，如果选择了CONFIG_F2FS_FS_XATTR

noacl                  禁用POSIX访问控制列表
                       注意：默认已启用acl，如果选择了CONFIG_F2FS_FS_POSIX_ACL

active_logs=%u         支持配置活动日志的数量。在当前的设计，f2fs只支持2、4和6个日志
                       默认数字是6

disable_ext_identify   禁用mkfs配置的扩展列表，因此f2fs不知道冷文件，如媒体文件

inline_xattr           启用内联xattrs功能

inline_data            启用内联data功能：新建小型（<~3.4k）文件可以写入inode块

flush_merge            尽可能合并并发缓存刷新命令以消除冗余的命令问题
                       如果设备处理缓存刷新命令的速度相对较慢，建议启用此选项

nobarrier              此选项用于是否存储保证缓存数据应该写入到novolatile区域。
                       如果设置了此选项，则不会发出缓存刷新命令，但是f2fs仍然保证所有数据写入。

================================================================================
DEBUGFS条目
================================================================================
/sys/kernel/debug/f2fs/ 包含所有按照f2fs挂在的分区的信息，每一个文件展示完整的f2fs的信息。

/sys/kernel/debug/f2fs/status 包括:
- 当前由f2fs管理的主要文件系统信息
- 关于整个segment的平均SIT信息
- f2fs消耗的当前内存占用。

================================================================================
SYSFS条目
================================================================================
有关于挂在f2f2文件系统的信息可以在/sys/fs/f2fs中被找到，每一个被挂在的文件系统将会有一个目录在
/sys/fs/f2fs基于设备名 (i.e., /sys/fs/f2fs/sda)。
每一个设备目录下的文件将会按照下面的格式进行展示

/sys/fs/f2fs/<devname>目录下文件
(也可以见在Documentation/ABI/testing/sysfs-fs-f2fs)
..............................................................................
 文件                          内容
 gc_max_sleep_time            此调整参数控制垃圾回收线程的最大睡眠时间。
                              时间以毫秒为单位。

 gc_min_sleep_time            此调整参数控制垃圾回收线程的最小睡眠时间。
                              时间以毫秒为单位。

 gc_no_gc_sleep_time          此调整参数控制垃圾回收线程的默认睡眠时间。
                              时间以毫秒为单位。

 gc_idle                      此参数控制受害者的选择垃圾收集策略。
                              设置gc_idle = 0(默认)将会关闭此选项.
                              设置gc_idle = 1将会选择成本效益法
                              设置gc_idle = 2将会选择贪婪的围裙

 reclaim_segments             此参数控制要回收的段的预释放的数目。
                              如果预释放的段的数量大于占总数的比例卷大小，f2fs尝试对回收预释放段以释放段。
                              默认情况下，超过分段总数的5%。

 max_small_discards           此参数控制小于2MB的小块的丢弃命令的数量
                              将要丢弃的候选对象缓存直到检查点被触发
                              默认情况下，使用0将其禁用。

 ipu_policy                   此参数控制f2fs中in-place-updates的策略
                              有五种策略：
                               0x01: F2FS_IPU_FORCE, 0x02: F2FS_IPU_SSR,
                               0x04: F2FS_IPU_UTIL,  0x08: F2FS_IPU_SSR_UTIL,
                               0x10: F2FS_IPU_FSYNC.

 min_ipu_util                 此参数控制触发in-place-updates的阈值
                              数字表示文件系统利用率百分比
                              用于F2FS_IPU_UTIL和F2FS_IPU_SSR_UTIL两种策略.

 min_fsync_blocks             此参数控制触发in-place-updates的阈值当F2FS_IPU_FSYNC模式被设置.
                              数字表示脏页的数量
                              当fsync需要刷新其调用路径时，如果这个数字小于这个值，它会触发in-place-updates

 max_victim_search            此参数控制了寻找受害段的审判数量当实时SSR和清理操作
                              默认值4096将会包含8GB块地址区域.（4096*2MB）

 dir_level                    此参数控制了支持的支持大目录等级
                              如果一个目录有很多文件，增加此目录级别值，减少文件查找延迟
                              否则，它需要将该值减小到减少空间开销
                              默认是0

 ram_thresh                   此参数控制了用于空闲nids和缓存nat entries在内存中占比
                              默认,设置为10, 表示 10 MB / 1 GB RAM.
================================================================================
用法
================================================================================
1. 下载用户区的工具并编译.

2. 跳过, 如果f2fs已经静态编译进kernel
   否则, 插入f2fs.ko模块
 # insmod f2fs.ko

3. 创建一个目录尝试挂载
 # mkdir /mnt/f2fs

4. f2fs格式化设备，然后挂在
 # mkfs.f2fs -l label /dev/block_device
 # mount -t f2fs /dev/block_device /mnt/f2fs

mkfs.f2fs
---------
mkfs.f2fs用于格式化分区按照f2fs文件系统
将会建立一个基本的磁盘阵列

选项:
-l [label]   : 提供一个label，最多512个unicode
-a [0 or 1]  : 拆分为基于堆分配的每个区域的开始位置
               1为默认设置, 代表执行.
-o [int]     : 设置超供应比例，基于size的百分比
               5为默认设置.
-s [int]     : 设置每个section的segment数
               1为默认设置.
-z [int]     : 设置每个zone的section数
               1为默认设置.
-e [str]     : 设置基本扩展列表. e.g. "mp3,gif,mov"
-t [0 or 1]  : 是否禁用放弃命令.
               1为默认设置, 使用放弃指令.

fsck.f2fs
---------
fsck.f2fs是一个检查f2fs格式分区一致性的工具，它检查文件系统元数据和用户创建的数据
是否正确交叉引用。
请注意，工具的初始版本不会修复任何不一致。

选项:
  -d debug level [default:0]

dump.f2fs
---------
dump.f2fs显示特定inode的信息，并将SSA和SIT转储到文件。每个文件都是dump_ssa和dump_sit

dump.f2fs用于调试f2fs文件系统的磁盘数据结构。显示由给定inode号重新确定的磁盘上inode信息，并且
能够将所有SSA和SIT条目转储到预定义文件中，分别用./dump_ssa和./dump_sit

选项:
  -d debug level [default:0]
  -i inode no (hex)
  -s [SIT dump segno from #1~#2 (decimal), for all 0~-1]
  -a [SSA dump segno from #1~#2 (decimal), for all 0~-1]

举例
# dump.f2fs -i [ino] /dev/sdx
# dump.f2fs -s 0~-1 /dev/sdx (SIT dump)
# dump.f2fs -a 0~-1 /dev/sdx (SSA dump)

================================================================================
设计
================================================================================

磁盘布局
--------------
F2FS将整个卷分成若干segment，每个segment都是固定的大小为2MB。一个section由连续的segment组成，
一个zone由一部分section组成。默认情况下，section=zone=1 segment，但用户可以很容易地通过mkfs修改大小。

                                            align with the zone size <-|
                 |-> align with the segment size
     _________________________________________________________________________
    |            |            |   Segment   |    Node     |   Segment  |      |
    | Superblock | Checkpoint |    Info.    |   Address   |   Summary  | Main |
    |    (SB)    |   (CP)     | Table (SIT) | Table (NAT) | Area (SSA) |      |
    |____________|_____2______|______N______|______N______|______N_____|__N___|
                                                                       .      .
                                                             .                .
                                                 .                            .
                                    ._________________________________________.
                                    |_Segment_|_..._|_Segment_|_..._|_Segment_|
                                    .           .
                                    ._________._________
                                    |_section_|__...__|_
                                    .            .
                            .________.
                                |__zone__|
- Superblock (SB)
 : 在分区的开头, 有两个复制，避免文件系统奔溃
   包含基本的分区信息和默认的f2fs参数

- Checkpoint (CP)
 : 包含文件系统信息，有效的NAT/SIT套bitmaps, 孤立的inode列表，当前激活segments的摘要条目

- Segment Information Table (SIT)
 : 包含segment信息例如有效块数， 所有有效块数的bitmap

- Node Address Table (NAT)
 : 由存储在主区域中的所有node块的块地址表组成。

- Segment Summary Area (SSA)
 : 包含摘要条目，包括所有存在Main Area的data块和node块的拥有信息

- Main Area
 : 包含文件目录信息，当然也包括他们索引

为了避免文件系统和基于闪存的存储之间的不一致，F2FS将CP的起始块地址与段大小对齐。
此外，它还将保留部分段以区域大小开始主区域的块地址在SSA地区。

有关其他技术细节，请参考以下调查。
https://wiki.linaro.org/WorkingGroups/Kernel/Projects/FlashCardSurvey

文件系统元数据结构
------------------------------

F2FS采用检查点机制来维护文件系统的一致性。在挂载时间，F2FS首先尝试通过扫描CP区域，查找最后一个有效的检查点数据
CP区域。为了减少扫描时间，F2FS只使用了CP的两个拷贝。其中一个始终指示最后一个有效数据，称为卷影副本机制。
除了CP，NAT和SIT也采用了卷影复制机制。

为了保持文件系统的一致性，每个CP都指向有效的NAT和SIT副本，如下所示。
  +--------+----------+---------+
  |   CP   |    SIT   |   NAT   |
  +--------+----------+---------+
  .         .          .          .
  .            .              .              .
  .               .                 .                 .
  +-------+-------+--------+--------+--------+--------+
  | CP #0 | CP #1 | SIT #0 | SIT #1 | NAT #0 | NAT #1 |
  +-------+-------+--------+--------+--------+--------+
     |             ^                          ^
     |             |                          |
     `----------------------------------------'

索引结构
---------------

管理数据位置的关键数据结构是node，类似传统的文件结构。
F2FS有三种类型的节点：inode，direct node，indirect node
F2FS将4KB分配给inode块包含923数据块的索引、两个direct node指针、两个indirect node指针和一个二级indirect node
指针。
如下所述。一个direct node包含1018数据块，并且一个indirect node还包含1018个节点块。因此，
一个inode块（即一个文件）支持的最大文件size

  4KB * (923 + 2 * 1018 + 2 * 1018 * 1018 + 1018 * 1018 * 1018) := 3.94TB.

     Inode block (4KB)
     |- data (923)
     |- direct node (2)
     |          `- data (1018)
     |- indirect node (2)
     |            `- direct node (1018)
     |                       `- data (1018)
     `- double indirect node (1)
                         `- indirect node (1018)
                          `- direct node (1018)
                                             `- data (1018)

注意，所有节点块都由NAT映射，这意味着每个节点都由NAT表转换。考虑到流浪
树问题，F2FS能够切断叶数据写入导致的节点更新的传播

目录结构
-------------------

目录条目占用11个字节，由以下属性组成。
- hash      文件名
- ino       inode号
- len       文件名的长度
- type      文件类型，例如directory, symlink, etc

一个dentry块由214个dentry槽和文件名组成。其中位图是用于表示每个dentry是否有效。
一个dentry块占用4KB，其组成如下

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

                         [Bucket]
             +--------------------------------+
             |dentry block 1 | dentry block 2 |
             +--------------------------------+
             .               .
       .                             .
  .       [Dentry Block Structure: 4KB]       .
  +--------+----------+----------+------------+
  | bitmap | reserved | dentries | file names |
  +--------+----------+----------+------------+
  [Dentry Block: 4KB] .   .
         .               .
            .                          .
            +------+------+-----+------+
            | hash | ino  | len | type |
            +------+------+-----+------+
            [Dentry Structure: 11 bytes]

F2FS为目录结构实现多级哈希表。每一层都有具有专用哈希桶数的哈希表，如下所示。请注意
“A（2B）”是指包含2个数据块的bucket。

----------------------
A : bucket
B : block
N : 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)

The number of blocks and buckets are determined by,

                            ,- 2, if n < MAX_DIR_HASH_DEPTH / 2,
  # of blocks in level #n = |
                            `- 4, Otherwise

                             ,- 2^(n + dir_level),
                 |        if n + dir_level < MAX_DIR_HASH_DEPTH / 2,
  # of buckets in level #n = |
                             `- 2^((MAX_DIR_HASH_DEPTH / 2) - 1),
                          Otherwise

当F2FS在目录中找到文件名时，首先是计算文件名的哈希值。然后，F2FS扫描0级的哈希表，以找到
dentry由文件名及其inode号组成。如果找不到，F2FS扫描级别1中的下一个哈希表。这样，F2FS在
每一层从1到N递增。在每一层中，F2FS只需要扫描一个存储桶，由以下等式确定，其中显示O（日志（文件）
复杂性。

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

在创建文件的情况下，F2FS会找到覆盖文件名。F2FS从1到N的方式与查找操作相同。

下图显示了两个包含子目录的案例
       --------------> Dir <--------------
       |                                 |
    child                             child

    child - child                     [hole] - child

    child - child - child             [hole] - [hole] - child

   Case 1:                           Case 2:
   Number of children = 6,           Number of children = 3,
   File size = 7                     File size = 7


默认块分配
------------------------

运行时, F2FS管理了6个活跃的日志在"Main"区域: 
Hot/Warm/Cold node 和 Hot/Warm/Cold data.

- Hot node  contains direct node blocks of directories.
- Warm node contains direct node blocks except hot node blocks.
- Cold node contains indirect node blocks
- Hot data  contains dentry blocks
- Warm data contains data blocks except hot and cold data blocks
- Cold data contains multimedia data or migrated data blocks

LFS有两种可用空间管理方案：threaded log和copy-and-compac-tion。
copy-and-compac-tion被经常清理使用，非常适合对于需要展示非常好的顺序写入性能的设备，
因为空闲段一直为写入新数据服务，但是，在高利用率的情况下存在清洁开销。
相反，threaded log案受随机写入的影响，但不需要清理过程。
F2FS采用混合动力，默认采用copy-and-compac-tion，但根据文件系统状态动态调成为threaded log。

为了使F2FS与底层的基于flash的存储保持一致，F2FS分配一个segment为合集的section。F2FS希望section大小为
与FTL中垃圾收集的单位大小相同。对于FTL中的映射粒度，F2FS尽可能多的从不同的zones，分配每一个section的活动日志。
由于FTL可以根据其映射粒度将活动日志中的数据写入一个分配单元


清理过程
----------------

F2FS可以按需清理和后台清理。
按需清理：当没有足够的空闲段来服务VFS调用时触发。
后台清理：由内核线程操作，当系统空闲，触发清理任务。

F2FS支持两种受害者选择策略：贪婪算法和成本效益算法。
在贪婪算法中，F2FS选择一个有效区块最少的的受害段。
在成本效益算法中，为了解决贪婪算法中的日志块抖动问题，F2FS根据段龄和有效块数选择一个受害段。
F2FS按需清理采用贪婪算法，后台清理采用成本效益算法。

为了确定受害者段中的数据是否有效，F2FS管理位图。每个位代表一个块的有效性，并且
位图是由一个覆盖整个主区域块的位流组成。