史高峰，李小勇

0 引言

SSD是一种基于闪存的电可擦除可编程的新型存储器件，本文主要介绍SSD闪存的数据结构和算法以及SSD闪存在分层存储中的应用。

闪存的读、写或擦除操作与易失的 RAM 和磁盘有很大的不同。闪存的每个单元只能擦写有限次（10，000到1，000，000次），超过这个最大次数后，闪存就变得不可靠了。

闪存种类主要有两种，NOR和NAND，这两种有很大的区别。写操作都是把“1”置为“0”，而擦除操作需要把一整个擦除单元的所有位都置为“1”。一个固定设备的擦除大小是固定的，从几KB到上百KB。NOR闪存的每个位（bit）都能被处理机直接访问并擦除，但是NOR的擦除时间比较长，而NAND闪存，擦除时间比较短，但是处理机不能访问到每个位（bit），访问的最小单位是页（page），一个擦除单元由很多页构成，典型的页大小为 512字节（byte）。一个擦除周期中的一个页只能被修改几次，因为修改几次后，页中的数据就不再可靠了。

因为这些特殊性，基于磁盘的一些存储技术就不太适合闪存了。随着闪存的广泛应用，在20世纪90年代后，基于闪存的存储技术不断发展。这些技术中，有一小部分是针对闪存的发明设计，而大部分发明是源自其他的存储技术。本文就是分析比较了闪存的各种数据结构和算法。

1 块映射技术

将闪存块当做磁盘块使用，会产生两个问题：

第一，一些块的修改次数远远大于其他块，对于磁盘块不会有任何问题，但是闪存中的这种块就会由于擦除太多而达到擦除上限，这种问题可以通过损耗均衡技术解决。……