闪存的性质
基于 NAND 的闪存
基于 NAND 的闪存是一种非易失性的 EEPROM 存储设备，闪存芯片的最小读写单元是页（page，通常 4KB），多个连续的页组成了块（block），闪存的擦除操作按块进行。图 1-a 给出了一个闪存芯片结构的示意图，其中每个块包含 128 个 4 KB 的页。
闪存与传统存储介质有以下几点差异：（1）读和写具有不同的延迟，写的代价高了一个数量级。（2）不支持原地写回，如果一个数据页中已经有数据了，只有将该页所属的块整体擦除，新的数据才能写入这个页。（3）每个存储单元只有有限的擦写寿命。
固态硬盘 SSD
固态硬盘通常由主机接口、闪存阵列、RAM 和 SSD 控制器组成，如图 1-b 所示。SSD 控制器的主要作用是将外部的读写请求转换为对闪存芯片的操作，并利用 RAM 对读写数据进行缓存，这些操作由控制器中的闪存转换层（FTL）固件来管理。
为了提高 SSD 的读写带宽，通常在硬件和 FTL 上使用一种交叉（interleaving）技术。一个写操作被分为两个步骤完成：（1）将数据装入闪存芯片内部的页寄存器；（2）将已经装载的数据编程写入对应的闪存页单元。因为数据编程写入闪存单元比装入寄存器需要更多的时间，因此在编程写入闪存单元的同时，可以在其它闪存芯片上载入数据。图 2 展示了一个 4-路交叉写入的情况，这种技术隐藏了闪存编程写入的延迟。如果 SSD 中有多个独立的闪存阵列通道，那利用它们的并行性可以极大地提高 SSD 的性能。
闪存转换层（FTL）
闪存转换层是 SSD 上的主要控制软件，它隐藏了闪存独特的性质，模拟了与传统块设备相同的外部主机接口。FTL 最主要的作用是将外部的写操作请求重定位，写入到一个已经被擦除的空白的区域。因此 FTL 需要维护一个地址映射表，将文件系统的逻辑数据块地址（LBA）转换为内部的物理地址。为了快速的访问，在每个闪存页中存储它们对应的逻辑地址，每次启动时构建地址映射表，并将映射表装载到易失性存储介质中。
FTL 的地址映射可以是页级别的，也可以是块级别的。页级别的映射可以有效地解决先擦后写的限制，因为一个对页的请求可以被重定向到闪存中任意的空白页，如果一个块中有 N 个页，那 N 次写操作之后平均只需要一次块擦除操作，但是这种页级别的映射导致映射表太大，而无法装入易失性存储介质中。如果是块级别的映射，物理块中的页的偏移一定要与逻辑块中该页的偏移相同，否则将无法对页进行定位。然而，当更新一个页的内容时，必须写入一个空白块中相同的页，而原来块中其余的页也要被拷贝到新的块中，这样一次写请求产生了一个块擦除和 N 个页的写入操作。
为了克服这种技术问题，混合的 FTL 映射方式结合了页级别和块级别的映射。这种方法划分了一部分闪存块作为日志块，外部的写操作都是直接写入日志块，并且日志块的地址映射是页级别的，因此可以避免频繁的块擦除操作。其余的闪存块作为数据块，采用块级别的映射方式，通常数据块的数量远大于日志块的数量。每个日志块对应一个数据块，对该数据块的写操作被写入该日志块，当一个日志块中的所有页都被写入，则将它与对应的数据块进行合并。当没有空白的日志块可以处理写请求时，就需要选取一个没有完全填充的日志块进行释放，即将该日志块的内容与对应的数据块合并。日志块与数据块合并的过程就是将每个页的可用版本拷贝到一个新的数据块，并擦除原来的日志块和数据块，因此一个合并操作产生了两次擦除操作。理想的情况是，如果一个日志块包含了所有可用的页，那可以简单的将这个日志块标记为新的数据块，这样就只需要一次擦除原来数据块的操作，这种情况被称为切换合并（switch merge）。
随机写的影响
SSD 内的闪存阵列通过多条总线连接在控制器上，并且每条总线上的闪存芯片可以实现 interleaving 技术，为了利用这种固有的并行性，SSD 通常将来自不同闪存芯片上的多个页组合为一个内部的读写单元，称为组合页（clustered page）。组合页的大小对于 I/O 性能具有非常重要的影响，如果写请求只更新组合页中的一部分，那控制器需要将原始组合页中其余的部分读出来，与请求更新的部分合并之后再写入新的组合页，如图 3-a 所示。因此，这种 read-modify-write 操作导致了额外的代价，增加了写操作的延迟。
为了提升垃圾回收的性能，与组合页类似的，SSD 将不同闪存芯片上的多个块组成内部的擦除单元，因此可以并行地擦除多个物理块。进行垃圾回收时，如果一个组合块中只有部分页是失效的，那要将其余的页拷贝到 SSD 中的空闲区域，这种复制代价降低了 SSD 垃圾回收的性能，就是说组合块的内部碎片导致了性能的下降。
我们考虑什么情况下会产生这种组合块的内部碎片。首先考虑图 3-b 中的第一种情况，写操作的请求大小小于组合页的大小，假定垃圾回收进程选择了最左侧的一个块进行回收。当数据被顺序地写入时，该块的全部数据被更新，因此该块没有可用数据，垃圾回收除了擦除该块外不需要额外代价。但是，如果随机写入情况下，该块只有部分数据被更新，产生了内部碎片，因此垃圾回收进程要将其余的数据拷贝出去，降低了写操作的性能。
接下来考虑图 3-b 中的后两种情况，如果写操作请求的大小是组合页大小的倍数，那每次随机写会整体更新组合块，并使得组合块中的全部数据失效，垃圾回收时只需要擦除选择的组合块而没有额外的代价，与顺序写的代价相同。在 FTL 的混合映射方式下，对应了切换合并（switch merge）这种最理想的情况。
综上所述，因为小尺寸的随机写导致 SSD 的内部碎片，产生额外的垃圾回收代价。因此，SSD 上的存储引擎设计应该充分考虑这种 I/O 模式的影响，增加写操作的局部性，或者使用更大的读写单元与组合页对齐。
