名词解释
cleaning 是append文件系统中常用术语，和trim有联系，但也需要注意他们之间的区别和联系：
cleaning: LFS 删去无效数据的过程
trim: SSD 内部删把dirty块设置成invalid，以备后续使用的过程
背景
鉴于之前评测的nvme SSD场景下 f2fs 整体性能表现出色，有必要分析其背后的根本原因。f2fs作为一种append模式的文件系统，
cleaning流程的设计和实现起着影响性能的重要的作用。为此有必要深入了解f2fs的GC的原理和实现。
f2fs GC的整体介绍
f2fs GC模块和其他模块的交互（接口）
- mkfs.f2fs 时的操作
在磁盘格式化成f2fs的时候，会做一遍全盘trim。 - trim API
f2fs提供了标准的POSIX trim接口，供外部直接触发trim。
f2fs GC模块内部的原理
触发时机
/*
* [GC triggering condition]
* 0. GC is not conducted currently.
* 1. There are enough dirty segments.
* 2. IO subsystem is idle by checking the # of writeback pages.
* 3. IO subsystem is idle by checking the # of requests in
* bdev's request list.
*
* Note) We have to avoid triggering GCs frequently.
* Because it is possible that some segments can be
* invalidated soon after by user update or deletion.
* So, I'd like to wait some time to collect dirty segments.
*/
后台GC机制的触发时机：
/*
* Background GC is triggered with the following conditions.
* 1. There are a number of invalid blocks.
* 2. There is not enough free space.
*/
响应机制
1. foreground cleaning
当free sections不够的时候：会触发 foreground cleaning
2. background cleaning
f2fs文件系统有一个内核线程会周期地检查并执行cleaning 过程
src的选择
1. greedy 策略
每次选择valid blocks 数量最小的section, 用在foreground cleaning，
目的是为了减小latency(因为需要搬迁的valid数据量少）;
2. cost-best 策略
每次不仅仅考虑section的利用率，还考察其age。 f2fs 根据一个section内的segments
的平均age来决定其age。每个segment的age可以在SIT更新的时候记录下来。
分情况进行处理：
1. 如果是foreground cleaning:
从parent node 的索引里获取一个新的free log，然后把上面选定的section中valid blocks数据搬移到free log里面去；
2. 如果是background cleaning:
并不是马上触发IO。而是把上面选定的section中valid blocks数据读到page cache，并且设置为dirty，这样能合并小块的写，
然后让page cache周期刷到新的空闲块上。
f2fs GC的特色
上面操作做完之后，上面选定的section被标记为pre-free, 只有等到checkpoint做完之后，上面的状态才变为free，可以被再次
分配出去。原因如下：如果没有做checkpoint 就直接把那个块释放掉，如果它被别人使用之后突然掉电之后再次拉起来，之前的数据会丢。
3. f2fs 如何判断用户IO是否繁忙
思路：根据一段时间内：用户提交的请求；page cache刷回的数据的次数
# 不同策略下cost 的比较方法 为了统一cost-best 和greedy 策略，f2fs 为这两种方法都提供了get_cost接口，分别实现如下： 优先选择cost成本低的segment去做GC： ## greedy 算法 cost 是segment中有效数据block的数量static inline unsigned int get_gc_cost(struct f2fs_sb_info *sbi,
unsigned int segno, struct victim_sel_policy *p)
{
if (p->alloc_mode == ×××)
return get_seg_entry(sbi, segno)->ckpt_valid_blocks;
/* alloc_mode == LFS */
if (p->gc_mode == GC_GREEDY)
return get_valid_blocks(sbi, segno, true);
else
return get_cb_cost(sbi, segno);
}## cost-best 算法 计算比较复杂： 基于时间局部性原理，最近更新的可能马上还有更新，为此降低其做GC的优先级，对应提高其做GC cost；反之， 对应降低其做GC cost。static unsigned int get_cb_cost(struct f2fs_sb_info *sbi, unsigned int segno)
{
struct sit_info *sit_i = SIT_I(sbi);
unsigned int secno = GET_SEC_FROM_SEG(sbi, segno);
unsigned int start = GET_SEG_FROM_SEC(sbi, secno);
unsigned long long mtime = 0;
unsigned int vblocks;
unsigned char age = 0;
unsigned char u;
unsigned int i;
for (i = 0; i < sbi->segs_per_sec; i++)
mtime += get_seg_entry(sbi, start + i)->mtime;
vblocks = get_valid_blocks(sbi, segno, true);
mtime = div_u64(mtime, sbi->segs_per_sec);
vblocks = div_u64(vblocks, sbi->segs_per_sec);
u = (vblocks * 100) >> sbi->log_blocks_per_seg;
/* Handle if the system time has changed by the user */
if (mtime < sit_i->min_mtime)
sit_i->min_mtime = mtime;
if (mtime > sit_i->max_mtime)
sit_i->max_mtime = mtime;
if (sit_i->max_mtime != sit_i->min_mtime)
age = 100 - div64_u64(100 * (mtime - sit_i->min_mtime),
sit_i->max_mtime - sit_i->min_mtime);
return UINT_MAX - ((100 * (100 - u) * age) / (100 + u));
}
上面gc 策略计算公式 UINT_MAX - ((100 * (100 - u) * age) / (100 + u)) 的说明如下：
u: 单个block内部的使用率（有效块的数量占block内部所有块的比例）
age: 当前block的访问时间距离所有block最近一次访问的时间间隔（sit_i->max_mtime - mtime)，在所有block最久远和最近访问时间间隔(sit_i->max_mtime - sit_i->min_mtime)中
的分为占比百分数
cost : UINT_MAX - ((100 * (100 - u) * age) / (100 + u))
u固定的情况下，距离最近访问的时间越久远（age越大），cost 值越小，越可能被选中；
age固定的情况下，上述公式等价于 2u/(1+u)，意味着 腾挪数据越陈本越低的block 越优先被选取。
参考：
Greedy算法
固件需要维护一张Block属性表，记录每个Block当前的Valid Page数量。假设每次GC处理8个Block，查表挑出Valid Page最少的8个Block进行GC，这样做的好处是复制Valid Page的开销最小。
Cost-Benefit算法
u代表valid page在该Block中的比例，age代表该Block距离最近一次修改的时间。
1-u是对这个Block进行GC以后能够获得Free Page的数量
2u是对这个Block进行GC的开销，读取Valid Page（1个u）然后写入到新的Block（再1个u）
（1-u）/2u可以理解为产出投入比
固件需要维护的Block属性表里，需要记录每个Block最后一次被写入的时间，GC时选择更久没有被修改的Block（冷数据）
该策略就是选择投入产出比更高，未修改时间更长的Block进行GC，两者相乘数字更大的优先被GC
CAT算法
CAT的全称是Cost Age Times，在Benefit-Cost算法的基础上，增加了对数据寿命和擦除次数的考虑。
μ代表一个Block里Valid Page的比例；
μ/(1-μ)理解为为了释放出（1-μ）的free page必须付出迁移μ的valid page，也就是整体的Cost；
1/age代表Hot degree跟Age成反比
NumberOfCleaning代表Hot degree跟Block的PE Cycle成正比
对每个Block进行计算，选择那些结果最高的Block进行GC过程。
触发trim的条件
需要前端GC配合，寻找得哪些segment需要被trim.
trim的实现
nvme SSD 内部的trim
看论文的启发
- 是否需要支持normal logging 和threaded logging ?
- 为了避免SSD内部GC的影响，测试的时候 只使用部分SSD（大约一半空间）；
- 测试用例： 参考论文
看代码启发
- GC 也不能太频繁，因为有的数据可能会很快被无效掉（发生了覆盖写或者删除操作）
- 如果不用thread logging 的方法，在磁盘空间接近用满的时候，如果为了继续保持append，是不是就需要继续从一个比较大的联系空闲块开始写才行（怎么才不影响性能？）和从启始地址开始，有何区别？
- 如何保证GC的速度能够赶上空间被消耗掉速度？