LFS 中的创建文件过程。新文件的文件名为“g”，inode 号为7
块10 和块11 为在此操作中未做修改的日志
块12 到14 为创建操作中被无效化的日志。块15 到18 为创建操作过程中新增的日志
直接重用无效空间并不容易：
- 日志中的有效数据和无效数据交织混杂在一起。想要重新利用日志中的空间，必须先识别出日志中哪些数据是有效的，哪些数据是无效的，只有无效数据所占用的空间才能进行重新利用
- 日志中无效数据所占据的空间大多是分散而不连续的。如果直接使用这些空间，可能会引入大量随机磁盘写入而造成性能下降，这并不符合LFS 希望顺序写入日志的初衷
对于第一个问题，即有效数据识别问题，LFS 可通过增加新的结构记录有效数据块位置的方式来解决。现在我们先假设LFS 已经能够快速识别日志空间中的有效数据，并以此为前提来看第二个问题
对于第二个问题，即无效数据占据的空闲空间的组织问题，有两种比较简单的解决方法：
- 空闲链表：一种比较直观的方法，是将空闲的空间使用链表连接起来。当文件系统需要使用新的空间时，可以从链表中拿出一块空闲空间，作为接下来的日志空间进行使用；当一段空闲空间使用完之后，再从链表中找出另一块空间继续使用
- 空间整理：假设数据保存在存储设备A 上，我们可以再找一个同等容量的设备B，然后顺序扫描存储设备A 上的日志空间，将有效数据依次移动到设备B 的日志空间中。整理完成后，有效数据全部都保存在了设备B 的日志空间的前一半部分空间，无效数据所占用的空间便被“移动”到了设备B 的尾部。
优劣：
空间链表：
- 操作比较简单
- 但是随着文件系统不断被使用，整个空间越来越“碎片化“：磁盘中大段连续的空闲空间越来越少，顺序写入越来越困难，取而代之的是大量的随机写入，这导致LFS 的优势完全消失。此外，虽然空闲链表维护起来非常方便，但是用于存放有效数据的有效空间越来越零碎，这导致有效数据段的维护变得越来越复杂且耗时。
空间整理：
-
保证每次整理后有效数据和空闲区域分别都是连续的
这保证了LFS 总是能够进行大量的顺序写操作，从而保持了LFS 的优势
-
每次在整理空间时，都需要扫描整个空间；而且，由于此过程中需要整理和移动有效数据，整个过程会非常耗时
为了平衡这两种方法，LFS 提出了段（Segment）的概念，以求既能同时拥有这两种方法的优点，又尽可能降低两者的缺点。
- 设备被拆分为定长的区域，称为段
- 段大小需要足以发挥出顺序写的优势，512KB、1MB等
- 每段内只能顺序写入
- 只有当段内全都是无效数据之后，才能被重新使用
- 干净段用链表维护（对应串联方法）
▲ 2份元数据 -> 数据一致性
▲ 由于LFS 中许多结构并没有固定位置，LFS 在进行挂载和崩溃恢复时，需要扫描存储空间中的所有日志，才能在内存中重构出文件系统结构的缓存。扫描整个存储空间比较耗时，造成文件系统的 挂载甚至整个系统的启动时间的延长。为了提升挂载和恢复的效率，，LFS 使用了检查点（Checkpoint）和前滚（Roll-forward）两种技术
LFS 创建检查点的过程分为两步：
- 由于文件系统会在内存结构中缓存部分修改，LFS 在创建检查点时，需要先将所有的修改追加到日志中，包括文件数据块、索引块、inode 结构、inode 表和段使用表
- 当所有的修改均已写入日志后，LFS 在检查点区域固定的位置写入一个检查点。其内容包括inode 表的地址，段使用表的地址、当前时间和最后一个写入的段的位置
一旦检查点创建完毕，在进行挂载和恢复时，LFS 无需扫描整个存储空间。其只需要找到检查点，并根据检查点中记录的结构找出检查点创建时的有效数据即可。检查点避免了LFS 对于无效数据的扫描，从而缩短了挂载和恢复的时间
🔺 由于检查点决定了挂载时文件系统中的有效数据，检查点自身的数据完整性也十分重要。如果在创建检查点时发生崩溃，文件系统可能会使用一个不完整的检查点，从而造成文件系统格式损坏和数据丢失。为了保证检查点数据的完整性，LFS 交替使用两个不同的位置创建检查点 -> 不会覆盖
检查点只能将文件系统恢复到创建检查点时的状态，如果想要恢复那些在创建检查点之后写入日志的修改，还需要进行前滚操作
前滚操作在检查点恢复之后进行，其通过扫描在检查点之后写入的日志，尽可能恢复在检查点之后进行的修改。具体来说，前滚操作会找到检查点之后修改过的段，并读取其中的段概要进行恢复。例如，如果在段概要中记录了一个新创建的、不在inode 表中的inode 结构，前滚操作会将新的inode 结构添加到inode 表中。考虑到日志的写入顺序，将inode 结构恢复之后，inode结构所引用的那些数据块和索引块，连带被进行了恢复。当然，此时恢复的inode 结构可能由于目录项的丢失而处于从根开始的文件系统树之外，这就引出了另外一个问题：目录项和inode 的一致性问题。
情况：inode被持久化，但是指向其的目录项未被持久化
解决 ： 目录修改日志
- 目录修改日志
- 记录了每个目录操作的信息
- create、link、rename、unlink
- 以及操作的具体信息
- 目录项位置、内容、inode的链接数
- 记录了每个目录操作的信息
- 目录修改日志的持久化在目录修改之前
- 恢复时根据目录修改日志保证inode的链接数是一致的
- 非对称的读写与擦除操作
- 页 (page) 是读写单元 (8-16KB)
- 块 (block) 是擦除单元 (4-8MB)
- Program/Erase cycles
- 写入前需要先擦除
- 每个块被擦除的次数是有限的
- 随机访问性能
- 没有寻道时间
- 随机访问的速度提升，但仍与顺序访问有一定差距
- 磨损均衡
- 频繁写入同一个块会造成写穿问题
- 将写入操作均匀的分摊在整个设备
- 多通道
- 高并行性
- 异质Cell
- 存储1到4个比特：SLC 、MLC、TLC、 QLC
-
逻辑地址到物理地址的转换
- 对外使用逻辑地址
- 内部使用物理地址
- 可软件实现，也可以固件实现
- 用于垃圾回收、数据迁移、磨损均衡（wear-levelling）等
- 递归更新问题
-
单一log顺序写入
无法利用到现代Flash设备的高并行性
- 引入一层 indirection：NAT（node地址转换表）
- NAT：Node Address Table
- 维护node号到逻辑块号的映射
- Node号需转换成逻辑块号才能使用
- F2FS中的文件结构
- 直接node：保存数据块的逻辑块号
- 间接node：保存node号 （相当于索引块）
- 数据块：保存数据
▲NAT 就相当于一个表格，记录了node到逻辑块号的映射
本来一个数据块修改了，它的逻辑块号变了，指向它的索引块要修改，二级索引块也要修改，二 级索引块的逻辑块号变了那么，inode也要变，inode map也要变
现在inode里面记录了间接node的node号，要通过NAT表翻译得到间接node的逻辑块号来找到 间接node，间接node记录了直接node的node号，也要通过NAT翻译得到直接node块号，直接 node里记录了数据块的逻辑块号。
当数据块修改时，相当于逻辑块号变了，所以直接node也要修改，这样直接node的逻辑块号也 变了，但是因为间接node是通过NAT翻译node得到直接node的位置的，所以间接node不用修 改，修改NAT表格就可以了，这样更新就不会一直向上传递了
- 通道（Channel） – 控制器可以同时访问的闪存芯片数量
- 多通道（Multi-channel） – 低端盘有2或4个通道 – 高端盘有8或10个通道
- Block：4KB，最小的读写单位
- Segment：2MB
- Section：多个segment（垃圾回收/GC粒度）
- Zone：多个section
系统元数据（随机写）
- 存放在一起：局部性更好
- CP：检查点
- SIT：段信息表
- NAT：node地址转换表
- SSA：段概要区域
数据区（多Log顺序写入）
- 区分冷/温/热数据
- 区分文件数据（data segment） 与元数据（node segment）
- 按热度将结构分类
- 每个类型和热度对应一个log
- 默认打开6个log
- 用户可进一步配置
▲ 以section为粒度 （与硬件FTL的GC单位是对齐的）
过程
- 选择需要清理的section
- Greedy：选择有效块最少的section
- Cost-effective：同时考虑数据修改时间
- 识别有效数据
- 有效数据拷贝到干净section
- 标记被清理的section为pre-free
- 在下一次checkpoint之后被标记为free
▲ 为什么不直接标记为free
容错
- 文件系统使用一段时间后，干净section不足，需要频繁清理
- F2FS动态调整数据段的日志方法
- 干净section充足时，使用常规方法
- 日志写到干净section中
- 没有干净section时需要进行清理操作
- 干净section不足时，使用 threaded logging
- 使用脏段中无效的块
- 避免清理操作
- 但会产生一些随机写
- 干净section充足时，使用常规方法
回滚：回滚到最近的检查点
前滚：恢复检查点之后fsync过的数据
- 查找带有fsync标记的直接node
- 对于每个直接node，对比其中的数据块指针，识别新旧数据块
- 更新SIT，标记旧的数据块为无效
- 根据直接node中新数据块的记录，更新NAT和SIT
- 创建新的检查点
fsync()
- 无需创建新的检查点
- 持久化文件数据块和直接node，并在直接node上附带fsync标记
- 前滚：恢复检查点之后fsync过的数据
见PPT
符号连接和硬链接是访问文件的两种捷径方式，但是它们在使用和实现上有许多不同。请列举出至少4点不同。
（1）符号链接本身是一个特殊的文件，硬链接只是多了一个指向inode的指针，并且增加引用计数
（2）符号链接没有文件限制，且可以指向一个空文件。硬链接不能指向目录、也不能指向空文件
（3）符号链接可以跨文件系统，硬链接不能跨文件系统
（4）符号链接在目标文件删除后失效，而硬连接则不会
（5）访问目标文件时，符号链接需要走两次文件系统，而硬连接只需一次。
在某些文件系统中，例如ext4，不允许使用硬链接来链接目录。
（1）请举一个例子说明如果文件系统支持到目录的硬链接会出现什么问题。
（2）如果确实需要支持到目录的硬链接，那么如何设计文件系统？并且，请从复杂性和性能等方面分析您的设计。
（1）仅使用引用计数器不能删除某些文件。例如：
路径：/ a / b / c / d /
在目录d下，增加到目录c的硬链接e：root-> a-> b-> c-> d-> e-> c
移除b-> c后：root-> a-> b，c-> d-> e-> c。
第二条路径是无法删除的循环。
（2）例如，循环检查。会增加每次删除时的性能开销。（其他合理答案均可）
请给出一个由于系统崩溃而导致的文件系统不一致的例子。
在目录下创建文件。分配了索引节点，但是在索引索引链接到目录之前，系统崩溃了。
什么是文件系统的持久性和原子性？如何保证文件系统操作的持久性和原子性？
**持久性：**如果执行并提交了一个文件操作，它将永久保留在磁盘上。
原子性：操作的效果要么做了，要么没做，不能看到做到一半的中间状态。
为了保证持久性，可以使用同步I/O。为了保证原子性，可以将数据拷贝出一个新的版本并在复制后的新数据上执行更新，最后更新使用原子指令将旧指针重定向到新指针。
有三种支持一致性的技术：写时复制，journal和log-structured update。
（1）请解释它们之间的区别。
（2）如何在不同的情况下选择这些技术？请给出一些各个技术所适合的场景。
（1）
写时复制：对于文件系统中的更新，递归地从叶复制到根，并在新节点中写入更新，然后切换到新节点。
Journal：在磁盘上保留一个区域作为日志，首先写入日志，然后更新数据
Log-structured update：所有文件系统都以只能追加的形式组织，并且每个修改都作为日志附加到末尾，但是读取速度很慢，需要检查是否被提交
（2）
写时复制需要大量空间来重建块（4K或更大）以进行较小的修改。
Journal的粒度可能很小，但是每次需要写两次（一次日志，一次更新数据）。
对于闪存的磨损问题，文件系统如何在短时间内避免其导致闪存容量下降的问题？如果某些块已用完，文件系统如何处理它们？ （假设硬件提供了某种方式来报告块是否已磨损。
文件系统可以平均使用闪存中的所有块。文件系统可以保留一个表来记录已用完的块，以后不使用它们。