FTL(Flash Translation Layer) 方案
概念
flash 的特性较为独特，有以下概念：
- sector(扇区)：最小可擦除单元
- block(块)：固定数量的 sector 的组合，逻辑概念
- page(页)：单次写入和读取单元，一般小于 sector 大小，flash 可以按照字节写入，也可按 page 写入。
静态均衡
一般而言，应用数据会按其修改频率分为两类:
- 冷数据：很少被修改的数据
- 热数据：频繁被修改的数据
静态均衡就是保证 flash 所有块的擦写次数均衡，也就是会对冷数据进行定期搬移，防止其所在块无法被擦除。
| 数据类型 | 块 1(冷数据) | 块 2(热数据) | 块 3(热数据) |
|---|---|---|---|
| 不均衡时擦除次数 | 0 | 100 | 100 |
| 静态均衡时擦除次数 | 67 | 67 | 67 |
日志型映射表
映射表是类似于文件系统中元数据的概念，存放了逻辑页和物理页的映射关系，便于找到逻辑页数据所在的实时位置。
取 flash 固定位置的两块(一般为 0,1 两块)为超级块(或元数据块)，用于存放映射表。映射表采用日志追加写入的方式，一条记录为<逻辑页号，物理页号>。
| <逻辑页号 | 物理页号> | <逻辑页号 | 物理页号> |
|---|---|---|---|
| 2 Bytes | 2 Bytes | 2 Bytes | 2 Bytes |
每次修改页时分配一个新的物理页用于写入，之后在超级块中追加一条记录。
多级映射表
为了更加细化地管理，同时提升映射读取效率，可以考虑使用多级页表
顶层为一个块映射表，其中每个映射项指向块内的页映射表。
| <逻辑块号 | 页映射表位置> | <逻辑块号 | 页映射表位置> |
|---|---|---|---|
| 1 Bytes | 1 Bytes | 1 Bytes | 1 Bytes |
| <块内逻辑页号 | 物理页号> | <块内逻辑页号 | 物理页号> |
|---|---|---|---|
| 1 Bytes | 2 Bytes | 1 Bytes | 2 Bytes |
映射表 cache
如果用这种方式存放映射表，每次读取页时需要全部扫描会较慢，可以在 RAM 建立一个映射子表作为 cache，只保存 10 条映射条目，关于这些映射条目的替换可以使用 LRU 最近最少使用算法。
映射表整理
当一个超级块被写满时，需要将其中的所有信息整理后将有效条目移动到另一个块中，然后擦除原来的块。
整理后的映射信息应该是排序后的，可以按逻辑页从小到大排序，由于有规律性，这些条目的逻辑页号可以省略，由位置信息隐含：
| 物理页号(对应逻辑页 1) | 物理页号(对应逻辑页 2) | … | 物理页号(对应逻辑页 1024) |
|---|---|---|---|
| 2 Bytes | 2 Bytes | … | 2 Bytes |
之后再追加记录时，由于映射信息不固定，才需要附带逻辑页号。
冷热数据分离管理
热数据管理
热数据会频繁的写入，也就是逻辑页对应的物理页在不断发生变化。
所以其写入策略为追加写入，当所有页即将写完时，需要垃圾回收。
垃圾回收
当正在写的块即将写满(或空白数据块不足)时，必须启动垃圾回收流程：
- 寻找最合适的待写数据块（有效数据最少的块优先，擦写次数最少的块优先，版本差距过大的块优先）
- 搬移其中的有效数据
- 擦除该块并标记为待写块
快速写入
对于热数据的写入，提供两个接口：
- 快速写入：返回时间敏感，不执行垃圾回收（除非不得已，如连续调用太多次快速写入）
- 慢速写入：可执行垃圾回收
块信息
以 4096 Bytes/块，64 Bytes/页为例：
| 擦除次数 | 预留 | 日志记录 | 数据 |
|---|---|---|---|
| 4Bytes | 60Bytes | 64Bytes | 62Pages X 64Bytes |
冷数据管理
冷数据写入频次较低，一般来说逻辑页和物理页的映射较为固定，所以不为其单独保存映射表，而是使用固定映射。
也就是说逻辑页在块内的相对位置固定，只需为这些块做映射，只要找到块就能找到对应页。
就地修改
对于要修改的块，直接利用一个交换块或新块实现就地修改。每个块的位置需要单独维护映射表。缺点是每修改一页都会带来同块内所有其他页的无效搬移。
块信息
以 4096 Bytes/块，64 Bytes/页为例。
冷数据：
| 擦除次数 | 预留(逻辑块及其版本号) | 数据 |
|---|---|---|
| 4Bytes | 60Bytes | 63Pages X 64Bytes |
均衡
为了实现静态磨损平衡，需要定期交换冷数据和热数据关联的块的映射。
块映射表
如果使用冷热数据分区的方式，原有的页映射表不再需要，可改为块映射表：
1
2
3
4
5
6
7
三段记录：
<逻辑块 1 对应物理块><逻辑块 2 对应物理块>...<逻辑块 8 对应物理块><逻辑块 2 ，对应物理块>
---
<最新修改物理块><最新修改物理块>
---
<物理块擦除(保留擦除次数信息)>
对于冷数据所属的逻辑块，由最前面的几条记录指向，当映射关系修改时追加记录修改（或所有记录整理并重写）；对于热数据所属逻辑块，需记录最新修改的物理块，相关的逻辑页映射信息保存在每个块内的元数据区域中；还要记录擦除动作，防止擦除不完整以及保存其对应的擦除次数信息防丢失。
优化方案 1
固定数据块（9 个）：
| 擦除次数 | 版本号(1-127) | 待擦标志(1) | 逻辑块号 | 搬移日志 | 是否修改指示位 | 数据 |
|---|---|---|---|---|---|---|
| 3Bytes | 1Bytes | 1Bytes | 1Bytes | 4Bytes | pages 数 X 1Bit | (1-63)pages X 64Bytes |
- 版本号：版本号可以用来表示该块更改的频次。
搬移日志
目标块号 目标擦除次数 1Bytes 3Bytes
待写数据块（1-6 个）：
| 擦除次数 | 版本号(128-254) | 待擦标志(1) | 搬移(擦除)日志 | 反向映射 | 数据 |
|---|---|---|---|---|---|
| 3Bytes | 1Bytes | 1Bytes | 4Bytes | 62pages X 10Bits | 62pages X 64Bytes |
- 待擦标志：因为擦除操作较为耗时，当块需要被擦除时，仅将待擦标志置 0，以便在空闲时擦除，此时要保证块内没有有效数据。
空闲数据块（至少 1 个）：
| 擦除次数 | 版本号(?) | 待擦标志(0) | 空白 |
|---|---|---|---|
| 3ytes | 1Bytes | 1Bytes | 剩余 |
RAM:
每个物理块状态（共 4x16=64 字节）：
| 块类型 | 逻辑块号 | 版本号 | 最新关联块(仅固定数据块，可保存两条记录)+块上数量 |
|---|---|---|---|
| 2Bit | 6Bit | 1Bytes | 1Bytes+1Bytes |
- 最新关联块：为一个冷的固定数据块指定一个关联的块，所有修改的页仅包含在该块内，若需要修改或搬移，则同一固定数据块内页必须全部搬移到新块。
整理过程
触发时机：
- 空闲时：将没有有效数据的待写块标记为待擦，将有效数据较少的块内的内容移动到可以写入的且有效数据较多的块内。
- 固定数据块(冷)中有较多页被修改时
- 待写数据块不足时
- 空闲数据块的擦除次数与固定数据块相差过大时：交换两者
空闲数据块和固定数据块转换：
- 寻找一块空闲数据块
- 在要搬移的固定数据块中填写日志——<搬移目标块，目标块当前擦除次数>
- 擦除目标块
- 目标块写入当前擦除次数+1
- 搬移数据区至目标块（整合修改内容）
- 目标块写入版本号+1(1-127)
- 目标块写入块号
- 原块待擦标志置 0（成为空闲数据块）
待写数据块转空闲数据块：
策略：
- 版本号最小优先(FIFO)
- 擦除次数最小的优先
- 有效数据最少的优先
- 若有有效数据，则将有效数据写到当前写入块或写回固定数据块
- 确认原块内没有有效数据，将待擦标志置为 0
空闲数据块转待写数据块：
- 该操作会导致空闲数据块减少，因此必须保证当前有两个空闲数据块，若不满足则执行待写数据块转空闲数据块操作。
- 在最新版本的待写数据块的日志区填写日志
- 擦除空闲数据块
- 填写擦除次数+1
- 填写版本号为最新版本+1
擦除空闲数据块必须伴随着日志记录，不能随便擦除
上电恢复操作
- 扫描每个块的前 64 字节，共 16x64=1024 字节
- 对于版本号为 1-127 且待擦标记为 1 且逻辑块号合法的块视为固定数据块，若有两个块具有相同的逻辑块号，以版本高的为准，同时将版本号低的块的待擦标记置为 0。然后扫描每个固定数据块的搬移日志，若需要搬移到空闲数据块，说明操作还未完成，继续执行直到成功。
- 对于版本号为 128-254 且待擦标记为 1 的视为待写数据块，扫描这些块的写入标志，将未写满的(写入标志不全为 0)视为当前正在写的块，版本小于它的为已写块，版本大于它的为未写块。读取最新版本的待写数据块的日志，如果其中有信息，表示有空闲数据块转待写数据块操作还未完成，继续执行直到完成。
- 将其他块视为空闲数据块。
替换策略
- 逻辑块序号大小：预置的数据热度
- 块版本号：实际运行时的热度
- 块擦除次数：应该将冷数据放到擦除次数较多的块上
- 固定数据块被更改过的页数量：当较多页被修改过时（特别是预计是冷数据的块）需要考虑将数据归位。
- 关联的待写数据块数量：当关联的数据块数量较多时，应考虑优先交换
写过程
优化方案 2
分段
在文件读写领域有两个概念：
- 时间一致性
- 空间一致性