wFSCK
队伍介绍
我们队伍名称为刘航志强，来自哈尔滨工业大学（深圳），基本情况如下：
| 赛题 | proj117-smart-flash-fs |
|---|---|
| 小组成员 | 刘航、刘强、孙志航 |
| 校内指导老师 | 夏文、李诗逸、仇洁婷 |
| 校外指导老师 | 郑立铭（华为） |
项目简介
wfsck是一个智能的文件系统检查恢复和任务管理框架。主要包含三个目标：
- 第一个目标是加速对文件系统的检查恢复。以fsck.f2fs作为原型，并参考pfsck引入多线程并发机制，使检查和修复的过程更加敏捷，而不影响C/R（检查和恢复）的正确性。智能感知系统资源使用情况，动态调整线程个数，以减少对其他程序的影响。
- 第二个目标是完成对f2fs前台gc任务的优化，减少无效的gc，使gc更智能，从而提升性能。
- 第三个目标是在fsck.f2fs检查过程中收集信息，优化后续挂载等情况。fsck.f2fs在检查文件系统的过程中，会遍历所有的文件元数据信息，这信息可以被记录下来，用于优化后续对文件系统的挂载等情况，使f2fs运行的更智能。
创新点
- 完成了论文pFSCK在fsck.f2fs上的移植，克服了移植的难点，将论文pFSCK的思想移植到fsck.f2fs中，使得fsck.f2fs更加智能敏捷，性能提升25%-50%。
- 发现了f2fs在一些场景下，存在大量无效gc的问题。并用简单有效的方法减少了无效gc，，最多将写性能从50个文件/秒提升到900个文件/秒，使得gc更加智能。
- 我们利用了fsck.f2fs收集的文件系统信息，优化后续f2fs的挂载，使得f2fs更加智能。
项目架构图
项目难点
目标一的难点如下：
- 难点1:如何将pFSCK的并发思想移植到fsck.f2fs中。pFSCK的检查逻辑与fsck.f2fs是不一样的。pFSCK是分阶段地进行检查，先检查inode，再检查目录等等。但fsck.f2fs的检查是直接从根Node递归地对整个Node树进行检查。
- 难点2:如何划分任务。理解fsck.f2fs原本的检查逻辑，从中划分出不同的任务。这个任务划分不能是简单的将每个Node的检查作为一个任务，因为每个Node需要对每个子Node检查的返回值进行处理，这样划分会影响检查的正确性。
- 难点3：如何正确地对每个任务的返回值进行处理。每个任务执行完成后需要对其返回值进行处理，在并发环境下，如何保证处理逻辑的正确是一个难点。
- 难点4：如何在复杂的文件系统布局中，高效安全访问共享数据结构。并发情况下，如果只是简单加一个粗粒度的锁，对共享数据结构进行串行化访问，会成为系统的瓶颈。如果只是细化锁的粒度，每个变量对应一个锁，也会比较低效。需要对不同的共享数据结构进行区分，重新设计数据结构。例如有的变量是只写的，可以添加到线程私有数据，为线程设计一个类似于线程上下文的结构存放私有数据。有的变量，又读又写，加细粒度的锁处理。有的变量如目录项虽然又读又写，但是只与某个Node为根的Node树检查有关，需要添加到线程私有数据中，才能保证正确性。
- 难点5：如何更智能地动态调整线程个数，使得检查工具能感知资源使用情况，做出调整，减少对其他程序的影响。
- 难点6：如何充分利用存储设备I/O。当前系统的I/O缓存不是为并发设计的，不同线程访问缓存可能导致低效的驱逐情况，需要为每个线程设计一个I/O缓存。
目标二的难点如下：
- 难点1：理解f2fs的gc过程。包括前台gc和后台gc在触发时机、gc的代价、gc效果等方面的差异，gc时如何挑选要回收的segment，gc时如何迁移数据等。
- 难点2：理解f2fs的写数据过程。包括写数据时何时会触发gc，gc触发时为何会有许多有效块特别多的脏segment
- 难点3：分析无效gc产生的原因。特别是为何会频繁产生待回收segment有效块特别多的情况。
- 难点4：如何通过有效的手段减少无效gc。
目标三的难点如下：
- 难点1：内核不能直接读取文件，如何将fsck.f2fs收集到的信息传递给内核。
- 难点2：fsck收集到的信息保存在一个复杂的结构体当中，如何将信息导出 供内核使用。
- 难点3：如何判定fsck收集到的信息中哪些是有价值，从而指导对f2fs文件 系统的优化。
文档
完成情况
| 目标编号 | 内容 | 基本完成情况 | 额外说明 |
|---|---|---|---|
| 1 | 加速fsck.f2fs | 完成（100%） | ① 可节省25%到50%左右的运行时间； ② 可动态调整线程个数 |
| 2 | 优化f2fs的gc | 完成（100%） | ① 减少两种无效的gc； ② 最多将写性能从50个文件/秒提升到900个文件/秒 |
| 3 | 利用fsck.f2fs收集的信息 | 完成（100%） | ① 可将fsck.f2fs中的超级块信息传递给f2fs供挂载使用 |
决赛完成内容
| 目标编号 | 内容 | 基本完成情况 | 额外说明 |
|---|---|---|---|
| 2 | 优化f2fs的gc | 完成（100%） | ① 减少两种无效的gc； ② 最多将写性能从50个文件/秒提升到900个文件/秒 |
| 3 | 利用fsck.f2fs收集的信息 | 完成（100%） | ① 可将fsck.f2fs中的超级块信息传递给f2fs供挂载使用 |
特色
已实现
- 可加速文件系统检查与修复工具执行速度，提高可靠性，使其更敏捷。并可智能动态调整线程个数，减少对系统其他程序的影响
- 智能减少f2fs中两种无效的gc，大幅提升写性能
- 将fsck与f2fs进行配合，fsck收集的信息供挂载使用，得到更智能的文件系统
测试结果
加速fsck.f2fs
功能测试
wfsck功能测试
测试中我们生成了一大小为1GB的文件系统镜像，向该镜像的sit、nat、ssa区域或main area区域随机写入数据，破坏该镜像。使用原始fsck工具与wfsck分别进行检查和修复。比对两者日志一致，说明两者行为一致。所以功能测试通过。
wfsck动态调整线程个数测试
wfsck和一个cpu密集型程序(通过stress-ng模拟)同时运行，stress-ng周期性执行，两次执行时间间隔为5秒。wfsck线程变化如图所示，可在总CPU利用率低时，增加wfsck线程个数。在总CPU利用率高，wfsck进程CPU利用率低时减少线程个数。
stress程序的性能如图所示，origin为stress程序单独运行的性能，no-scheduler为stress程序与没有动态调整线程个数的wfsck同时运行时身前者的性能，scheduler为stress程序与开启动态调整线程个数的wfsck同时运行时前者的性能。动态调整线程个数减少了对stress程序性能的影响。且wfsck本身性能下降不超过5%。
性能测试
- 物理测试结果
我们在物理机上创建了大小为1GB，10GB，50GB的文件系统镜像，分别测试了原始的fsck程序，以及使用不同线程数的wfsck程序的运行时间，并取3次运行的平均时间作为最终运行时间。结果统计如图所示。图中纵坐标为程序运行时间，横坐标为wfsck使用的线程数，红色的虚线为原始fsck程序的运行时间，作为baseline进行比较。wfsck相比fsck.f2fs可以加速约25%-29%。
- 虚拟机测试结果
我们在虚拟机上创建了大小为1GB，2GB，5GB的文件系统镜像，进行与情景1相同的测试，结果统计如图所示。图中纵坐标为程序运行时间，横坐标为wfsck使用的线程数，红色的虚线为原始fsck程序的运行时间，作为baseline进行比较。wfsck相比fsck.f2fs可以加速约28%-50%。
优化f2fs的gc
我们针对原始版本和改进后的版本，多次调用fsmark，每次创建一定数量的文件。记录该次的执行时间和总的gc次数，无效的gc次数，其中无效的gc分为invalid gc和useless gc。invalid gc是指没有segment可以回收，useless gc是指待回收的segment有效块非常多。图中横坐标为fsmark调用的次数，左边的纵坐标为写文件的速率，右边的纵坐标为gc的次数。折线origin write代表原始版本写文件的速率，折线our write代表改进版本写文件的速率。折线origin gc_count代表原始版本gc的总次数，折线our gc_count代表改进版本gc的总次数。折线origin invalid代表原始版本invalid gc次数，折线our invalid代表改进版本invalid gc次数，折线origin useless代表原始版本useless gc次数，折线our useless代表改进版本useless gc的次数。
-
出现第一种无效gc
如图所示，一块空的磁盘，大小为100M，fsmark每次写500个文件，每个文件大小为2048B。随着fsmark调用次数增加，磁盘的利用率也在增加。在第23次时，空间将要不足，原始版本触发前台gc，导致性能下降。而这里触发的gc，几乎全是invalid gc（图中origin gc_count与origin invalid几乎重合），也就是根本没有segment可以回收。而改进版本在触发一次无效gc后将停一会写流程中触发前台gc的逻辑，所以改进版本前台gc次数很少，fsmark写的性能也没有下降。 -
出现第一种及第二种无效gc
如图所示，一块空的磁盘，大小为100M，fsmark每次写400个文件，每个文件大小为2048B。随着fsmark调用次数增加，磁盘的利用率也在增加。在第29次时，空间将要不足，原始版本触发前台gc，导致性能下降。而这里触发的gc，几乎全是invalid gc（图中origin gc_count与origin invalid几乎重合），也就是根本没有segment可以回收。特别注意，第35次时，出现了许多useless gc （回收的segment有效block较多），性能下降比较严重。而改进版本在触发一次无效gc后将停一会写流程中触发前台gc的逻辑，所以改进版本前台gc次数很少，fsmark写的性能也没有下降。
利用fsck收集的信息
测试过程中进行了3次挂载。只有第二次是通过fsck-info模块提供的信息挂载，第一次和第三次都是无fsck-info的正常挂载流程。在每次过载的过程中对文件系统读写，然后判断文件系统的一致性来验证我们成功实现利用fsck-info模块信息进行挂载
仓库介绍
src: wfsck代码。基于fsck.f2fs，在main.c，fsck.c，thpool.c中添加了代码
test: 测试代码
具体如下
.
├── README.md
├── src ######## 源代码目录 #########
│ └── f2fs-tools # f2fs-tools工具包
│ ├── 省略...
│ ├── fsck
│ │ ├── common.h
│ │ ├── compress.c
│ │ ├── compress.h
│ │ ├── defrag.c
│ │ ├── dict.c
│ │ ├── dict.h
│ │ ├── dir.c
│ │ ├── dqblk_v2.h
│ │ ├── dump.c
│ │ ├── f2fs.h # f2fs文件系统内存结构
│ │ ├── fsck.c # 检查逻辑代码
│ │ ├── fsck.h
│ │ ├── main.c # 程序入口代码
│ │ ├── Makefile.am
│ │ ├── mkquota.c
│ │ ├── mount.c
│ │ ├── node.c
│ │ ├── node.h
│ │ ├── quotaio.c
│ │ ├── quotaio.h
│ │ ├── quotaio_tree.c
│ │ ├── quotaio_tree.h
│ │ ├── quotaio_v2.c
│ │ ├── quotaio_v2.h
│ │ ├── resize.c
│ │ ├── segment.c
│ │ ├── sload.c
│ │ ├── thpool.c # 线程池代码
│ │ ├── thpool.h
│ │ ├── xattr.c
│ │ └── xattr.h
│ ├── include
│ │ ├── 省略..
│ │ └── f2fs_fs.h # f2fs文件系统硬盘结构
│ ├── lib
│ │ └── 省略...
│ └── 省略...
├── test ######## 测试代码 #########
│ ├── config
│ │ ├── config_template.py
│ │ ├── function_test_config_template.sh
│ │ └── performance_test_config.sh
│ ├── fs_mark-3.3 # fs_mark文件填充工具
│ │ ├── fs_mark
│ │ └── 省略..
│ ├── image_manager.py
│ ├── include
│ │ ├── android_config.h
│ │ ├── f2fs_fs.h
│ │ └── quota.h
│ ├── README.md
│ ├── requirements.txt
│ ├── scripts
│ │ └── clear_cache.sh
│ ├── src
│ │ ├── destory.f2fs # 文件系统破坏工具
│ │ ├── 省略...
│ │ └── README.md
│ ├── test.py # 测试文件入口
│ ├── function_test.sh # 功能测试脚本
│ ├── performance_test.sh # 性能测试脚本
│ └── utils.py
└── wFSCK文档.pdf # 介绍文档