FTL 解密

# 名词介绍

*  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 区域。