# 名词介绍
* page
SSD 存储芯片内写操作的最小单元。
* block
SSD 存储芯片内擦除操作的最小单元。
* FTL
Flash Transfer Layer的简写。
# FTL的功能
实现host地址到nand地址到转换。
# FTL mapping的基本机制
* page-level mapping
每一个逻辑的page 都是映射到一个物理page, 映射策略和同一个block内到其他page 无关。
* block-level mapping
对应关系类似上面，只是粒读是比page 更大的block 。
* hybrid mapping
部分block 用page-levle mapping机制，部分block 采取block-level
mapping 机制。如下图所示：
# 常见的FTL算法
## 好算法的评判标准：
* small memory footprint
* good writing performance
## 优化思路
* mapping-entry to flash
对于page level mapping机制：
优点是性能好，缺点是SSD控制器内部占用的内存大，但可以把部分mappint entry 放到flash中去优化。
* log block FTL
对于block level mapping 机制：
优点是总的mapping entry少，但是由于block内部不同page的写需要COW 操作，导致性能低。这可以通过給block 内部添加的额外的page或者block来接受写更新请求来优化，这部分page或block被分别叫做log-page/log-block，而默认的那部分page/block被称为data-page/data-block。后续两者可以一趟合并，无需COW。
* partitioned-flash
思路和依赖体现在下面几点：
1. SSD 能被切分
SSD存储介质能够被切分成多个区域；
2. IO流有高、低频之分
部分数据被频繁更新；部分数据很少跟新；
3. 内部支持hybrid mapping scheme
内部部分NAND的FTL是page-level mapping; 部分是block-level mapping;
4. 独立映射
高频（热数据）使用 page-level FTL；
低频（冷数据）使用 block-level FTL;
## log block FTL
### Mitsubishi
这种机制在每个log page里面包括额外的log page, 这些log page应用程序不可见，只在block里的data page更新的时候才会立即更新。特点是：后续对block的写，会基于log page；如果log page用完了，会进行copy and merge。如下图所示：
### M-systems
M-systems可以理解成block RAID1, 一个logical block 对应两个physical block，： data block和log block 。M-systems有两种管理映射的机制：
* ANAND
相同偏移的page 才能相互映射。第一次覆盖写会落到log block，第二次覆盖写才会触发merge操作。举例如下：
这种方法的优点是 不需要维护data block和log block的映射关系。
* FMAX
对某个page的覆盖写的更新会写到log block的第一个空闲page，之前的page number(在较早的data block里面的）会被拷贝到带外空间（OOB）。data block和log block的merge操作只会发生在log block里空闲空间不足的情况下。
### BAST (Block Associative Sector Translation FTL)
BAST可以理解为log block 数量受到限制的FMAX， FTL mapping table 而非OOB region被用来管理log-block和data-block的1:1映射关系。 当出现下面的情况下会触发merge:
* log block 被用完了；
* 覆盖写的时候free log block 不足。
这个方法的不足在于：当有超过log block 数量的更新同时进行的时候，会触发多个merge 操作，即便此时有的log-block里有效数据很少。
### FAST (Fully Associative Sector Translation FTL)
FAST通过全相关解决了上面 的问题。一个log block 可以映射到多dat block 。在这种策略中， log blocks被分成两个区域。每个区域都包含一个专门給顺序更新的block，因为顺序写如果落到不同block会导致merge 操作效率低下，所以把落在同一个逻辑block 的page 顺序更新都映射到同一个block。此外，每个区域还包括对随机写友好的log block ，这些block 可以在随机更新的时候被最大程度地并行使用，同时最小化了merge 开销。下面这个图很直观地说明了这个过程：
### LAST (Locality Aware Sector Translation FTL)
FAST merge操作的次数少，但是每次merge操作的代价大。因为FAST 中log-block 和page-block是1:N映射的，一个log-page里可能映射到多个data block，这样merge一个log block可能就需要更新多个data block。特别地 有的data block 可能更新比较少，而有的data block 可能比较频繁地更新，如果都混在同一个log block里可能造成实际数据更新比较少的block也频繁merge，显然这样效率不高。为此，自然想到了一种把不同频次的IO 分流到不同的log-block 的方法。
1. 为顺序写分配更多的log-block；
2. 把属于随机写的log-block 分成两个区域：一部分log page 用来接收热数据；一部分用来接收冷数据。
### K-Associative Sector mapping FTL
log-block 和data-block K路组相连的映射方式，来减少FFTL merge操作的开销。
### Hybrid FTL
主要的思路如下：
* 为冷热数据分配不同的log block/log pages;
* 热数据采取 page-levle mapping
* 冷数据采取block-level mapping
*
## Page-level mapping FTL
传统的page-level mapping 由于使用数量巨大的mapping table entry 占用很多内存，通常不是一个最好的选择。业界提出了几种方法。
### DFTL (Demand-based FTL)
主要思路如下：
* 高频访问的mapping table entry 存在控制器RAM里；
* 其他的mappieng table entry 存在flash memory里；
示例图如下：
###
### SFTL (Spatial Locality Aware FTL)
主要思路是利用顺序IO的特性来减少mapping table 的大小。对于顺序IO，不需要加载对mapping table 的多个不同的引用，只需要加载一个引用以及表示还有多少顺序访问的数量就够了。
### CFTL (Convertible FTL)
一种充分利用了程序时间和空间局本性的 FTL。
* 利用空间局部性
使用了cache来存取部分mapping table
* 利用时间局部性
对于密集的读请求使用block-level mapping，而对很频繁的更新请求使用page-level mapping机制。
## FTL with partitioned flash memory
### WAFTL (Workload Aware FTL)
WAFTL根据IO pattern 来存放数据。在这种FTL实现里：
1. flash memory 被物理分成两个区域：
* 基于page映射的区域
managed page-wise called Page Mapped Blocks (PMB), 用来存放：
* 基于block映射的区域
managed block-wise called Block Mapped Blocks (BMB)
2. 根据IO pattern分区存放数据：
* 随机访问的数据以及block 部分更新的数据存放到PMB 区域；
* 顺序访问的数据以及mapping table 存放在 BPM区域；
* WAFTL 内部 把flash memroy 部分空间用作了buffer，在这些数据被copy到BPM区域之前，会被临时、顺序写入到buffer 里面去。
### CACHE-FTL (Cache Aware Configurable Hybrid FTL)
类似上面的WAFTL, flash memroy也划分了分区。考虑到SSD控制器内部也有cache,
其最终目的就是为了加快对flash memory 对访问，同时考虑尽量减小最终落到block内部的 cache上的有效数据和flash memory上的无效数据的merge开销。因此，CACHE-FTL 提出了一种通过统计内部flush.操作下刷单page数量来决定写到 page-mapping 区域还是block mapping 区域：如果这个数量低于某个阈值，就写到page-level mapping 区域，否则写到block-level mapping区域。
此外，CACHE-FTL的GC机制在回收空间的时候，允许数据从page-level mapping区域搬到block-level mapping 区域。
