原文 http://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/

在这个部分，我会解释写操作在页和块级是如何处理的，以及写入放大和损耗均衡计算的基本概念。此外，我描述了闪存转换层（FTL）的概念，以及应用了闪存转换层的两个技术：逻辑块地址映射和垃圾回收。更详细的说，我解释了在混合逻辑块映射背景下的写操作是怎么实现的。

3. 基本操作

3.1 读出、写入、擦除

因为NAND闪存单元的组织结构限制，单独读写一个闪存单元是不可能的。存储单元被组织起来并有着十分特别的属性。要知道这些属性对于为固态硬盘优化数据结构的过程和理解其行为来说是很重要的。我 在下方描述了关于读写擦除操作的SSD的基本属性

读是以页大小对齐的

一次读取少于一页的内容是不可能的。操作系统当然可以只请求一字节，但是SSD会访问整个页，强制读取远超所需的数据。

写是以页大小对齐的

将数据写入SSD的时候，写入的增量也是页大小。因此即使一个写入操作只影响到一个字节，无论如何整个页都会写入。写入比所需更多的数据的行为被称为写入放大，其概念在3.3节。另外，向某页写入的行为有时候被称为“编置（to program）”一页，因此在大多数关于SSD的出版物和文章中“write 写”和“program编置”是可以互相替换的

页不能被复写

NAND闪存页只有在其“空闲”着的时候才能写入。当数据改变后，这页的内容被拷贝到一个内部寄存器，此时数据更新而新版本的数据存储在一个“空闲”的页中，这被称为“读-改-写”操作。数据并非就地更新，因为“空闲”页与原来存储数据的页不是同一个页。一旦数据被硬盘保存，原先的页被标记为“stale（意为 腐败的 不新鲜的）”，直到其被擦除。

擦除以块对齐

页不能被复写，而一旦其成为stale，让其重新空闲下来的唯一方法是擦除他们。但是对单个页进行擦除是不可能的，只能一次擦除整个块。在用户看来，访问数据的时候只有读和写命令。擦除命令则是当SSD控制器需要回收stale页来获取空闲空间的时候，由其垃圾回收进程触发。

3.2 写入的例子

让我们用个例子来理清3.1节的这些概念。下边的图4是向SSD写入的一个例子。只显示了两个块，每个块有4个页。显然这是一个为了简化我在这使用的例子而精简的NAND闪存封装示意。图中的每一步里，图右侧的圆点解释了发生的事情

图4：向固态硬盘中写数据

3.3 写入放大

因为写入是按页大小对齐的，任何没有对齐一个或者多个页大小的写操作都会写入大于所需的数据，这是写入放大的概念[13]。写一个字节最终导致一整页都要写入，而一页的大小在某些型号的SSD中可能达到16KB，这是相当没有效率的。

而这不是唯一的问题。除了写入过多的数据外，这些额外的写入也会触发更多不必要的内部操作。实际上，用未对齐的方法写入数据会导致在更改和写回硬盘之前需要页读到缓存，这比直接写入硬盘要慢。这个操作被称为读-改-写，且应该尽可能的避免[2, 5]。

绝不进行少于一页的写入

避免写入小于NAND闪存页大小的数据块来最小化写入放大和读-改-写操作。现在一页的大小最大的是16KB，因此这个值应作为缺省值使用。闪存页大小的值基于SSD型号并且在未来SSD发展中可能会增加。

对齐写入

以页大小对齐写入，并写入大小为数个页大小的数据块。

缓存化小写入

为了最大化吞吐量，尽可能的将小数据写入RAM缓存中，当缓存满了之后执行一个大的写入来合并所有的小写入。

3.4 损耗均衡

如我们在1.1节讨论的那样，NAND闪存单元因其有P/E循环限制导致其有生命限制。想象一下我们有一个SSD，数据总是在同一个块上写入。这个块将很快达到其P/E循环限制、耗尽。而SSD控制器井标记其为不可用。这样硬盘的容量将减小。想象一下买了一个500GB的硬盘，过了几年还剩250G，这会非常恼火。

因此，SSD控制器的一个主要目标是实现损耗均衡，即是将P/E循环在块间尽可能的平均分配。理想上，所有的块会在同一时间达到P/E循环上限并耗尽。[12, 14]

为了达到最好的全局损耗均衡，SSD控制器需要明智的选择要写入的块，且可能需要在数个块之间移动，其内部的进程会导致写入放大的增加。因此，块的管理是在最大化损耗均衡和最小话写入放大之间的权衡。

制造商想出各种各样的功能来实现损耗均衡，例如下一节要讲的垃圾回收。

损耗均衡

因为NAND闪存单元会耗尽，FTL的一个主要目标是尽可能平均的将工作分配给各个闪存单元，这样使得各个块将会在同一时间达到他们的P/E循环限制而耗尽。

4.闪存转换层(FTL)

4.1 FTL存在的必要性

使用SSD如此容易的主要因素是其使用和HDD相同的主机接口。尽管一组逻辑块地址（LBA）的出现使其感觉像HDD的扇区一样可被复写，但其并非完全符合闪存的工作方式。因此需要一个额外的组件来隐藏NAND闪存的内部特征，并只向主机暴露一组LBA。这个组件称为闪存转换层（FTL），位于SSD控制器中。FTL很关键，并有两个主要的作用，逻辑块寻址和垃圾回收。

4.2逻辑块映射

逻辑块映射将来自主机空间的逻辑块地址（LBA）转换为物理NAND闪存空间的物理块地址（PBA）。为了访问速度，这个映射表保存在SSD的RAM中，并保存在闪存中以防电源故障。当SSD启动后，这个表从闪存中读出并在SSD的RAM中重建[1, 5]。

一个比较简单的方法是使用页级映射来将主机的所有逻辑页映射为物理页。这个映射方法提供了很大的灵活性，然而主要的缺点是映射表需要大量的内存，这会显著地增加生产成本。一个解决方案是使用块级映射不再对页，而是对块进行映射。假设一个SSD硬盘每个块有256个页。这表示块级映射需要的内存是页级映射的256分之一，这是内存使用的巨大优化。然而这个映射仍然需要保存在硬盘上以防掉电。同时，以防大量小更新的工作负载，无论页是否是满的，全部闪存块都会写入。这会增加写入放大并使得块级映射普遍低效[1, 2]。

页级映射和块级映射的折中其实是在性能和空间之间折中的一个表现。一些研究者试着在两个方面都能够最佳化，得到了称为“hybrid（混合）”的方法[10]。最普遍的是日志块映射，其使用了一种比较像日志结构文件系统的方法。输入的写操作按顺序写入日志块中。当一个日志块满了之后，将其和与其在相同逻辑块编号（LBN）的数据块合并到空块中。只需要维护少量的日志块，且允许以页粒度维护。而块级映射是以块粒度维护的。

下边的图5是对混合日志块FTL的一个简单的陈述，每个块有4个页。FTL处理4个写操作，都是页大小尺寸的写入。逻辑页编号5和9都被映射到LBN（逻辑块编号）=1，而LBN=1关联到物理块#1000。最初，在逻辑块映射表中，LBN=1的所有物理页offset都是null，而日志块#1000同样是完全空的。

第一个写入将b’写到LPN=5，这被日志块映射表解释到LBN=1，即为关联到PBN=1000（日志块#1000）。因此页b’写到块#1000的0号页中。映射用的元数据需要更新，为此，逻辑offset 1（随便举的例子）对应的物理offset从null改为0。

写入操作继续而映射元数据随之更新，当日志块#1000完全填满，将其和对应为相同的逻辑块的数据块（本例中是#3000）合并。这个数据可以从数据块映射表中读取，此表将逻辑块映射为物理块。合并操作的结果数据被写到新的空块中，本例中为#9000。当这个工作做完了，块#1000和#3000可以被擦除成为空块，而块#9000成为一个数据块。数据块映射表中LBN=1的元数据则从一开始的#3000改为新的数据块#9000.

一个值得注意的很重要的事情是，四个写操作只集中在两个LPN中。逻辑块方法在合并的过程中隐藏了b’和d’操作，直接使用更加新的b”和d”版本，使其能够更好的降低写入放大。最后，如果读命令请求一个最新更新但还没合并到数据块中的页，这个页将会在日志块中读取，否者将会在数据块中找到。这就是如图5中所示，读操作即需要读取日志块映射表又需要读取数据块映射表的原因。

图5：混合日志块FTL

日志块FTL可以进行优化，其最值得注意的是切换合并，有时候也叫做“交换合并”。假设逻辑块中所有地址都立马写满了，这表示这些地址的所有新数据都将写到一个像样的日志块中。既然这个日志块包含的数据是一整个逻辑块的数据，那么将其和数据块合并到新的空块中是没有意义的，因为保存合并结果的空块中的数据就是日志块中的数据。只更新数据块映射表中的元数据并将数据块映射表中的数据块切换为日志块将会更快，这就是切换合并。

很多论文都讨论日志块映射方案，这些论文导致了一系列的改进，例如FAST（Fully Associative Sector Translation 完全关联扇区转换）、superblock mapping（超块映射）、以及flexible group mapping（灵活组映射）。同样还有其他的映射方案，例如Mitsubishi（三菱）算法和SSR。下面两篇论文是学习更多关于FTL和映射方案的很好的开始点

• “A Survey of Flash Translation Layer“, Chung et al., 2009 [9]
• “A Reconfigurable FTL (Flash Translation Layer) Architecture for NAND Flash-Based Applications“, Park et al., 2008 [10]

闪存转换层

闪存转换层是SSD控制器的一个组件，它将来自主机的逻辑块地址（LBA）映射为硬盘上的物理块地址（PBA）。大部分最新的硬盘使用了一种叫做“混合日志块映射”的技术或者其衍生技术，其工作方式比较像日志结构文件系统。这种技术可以将随机写入当做序列写入处理。

4.3 关于行业状态的注记.

在2014年2月2日，Wikipedia [64]上列出了70个SSD的生产商，有意义的是，只有11个主控的生产商[65]。在这11个主控生产商之中，只有4个是“captive（自给自足的）”，即仅对它们自己的产品使用自己的主控（譬如Intel和三星）；而其他的7个是“independent（独立的）”，即他们把自己的主控卖给其他的硬盘生产商。这些数字表示，这7个公司生产固态硬盘市场上90%的主控。

我没有这90%中，关于哪个主控生产商卖给哪个硬盘生产商的数据吗，但是根据帕雷托法则（二八定律或80/20法则——译注），我赌只有两三家主控制造商分享了大部分的蛋糕。直接结论是，来自非自给自足厂家的SSD，因其本质上使用相同的主控或至少其主控使用相同的全局设计和底层思想，其行为会及其相似。

映射方案作为主控的一部分是SSD十分重要的组件，因为其往往完全定义了硬盘的表现。这就解释了为什么在有如此多竞争的产业中，SSD主控生产商不分享其FTL实现的细节。因此，即使有大量的公共可用的关于FTL算法的研究，但仍然不清楚主控生产商使用了多少研究，以及某个牌子和型号具体实现了什么。

这篇文章[3]的作者声称通过分析工作负载，他们可以对硬盘的映射策略进行反向工程。除非芯片中的二进制代码本身被反向工程，我自己还是不太认同这种方法。因为没有办法完全确认某个硬盘中映射策略真正做了什么。并且预测一个特定的工作负载下映射的行为更难。

因为有很大量的不同映射策略，而对市场上所有可用固件进行反向工程所花费的时间的量值得考虑。然后，即使获得了所有可能的映射政策的源代码，你能拿来干啥？新产品的系统需求经常导致全面改进，使用未标明和内部易变的硬件组件。因此，只为一个映射政策进行优化是不值当的，因为这个优化的方案可能在其他所有映射政策表现很差。某人想只对一种映射政策进行优化的唯一原因是他在为已经保证使用一致硬件的嵌入式系统进行开发。

综上所述，我得说知道某一个SSD具体使用的是哪一个映射政策并不重要。唯一重要的事情是知道映射政策是LBA和PBA之间的转换层，而其很像混合日志块或其衍生算法的实现。因此，写入大小至少是NAND闪存块大小的数据片将会更加效率，因为对于FTL来说，更新映射及其元数据的开支是最小化的。

4.4 垃圾回收

如我在4.1和4.2节中所说，页不能被复写。如果页中的数据必须更新，新版本必须写到空页中，而保存之前版本数据的页被标记为stale。当块被stale页充满后，其需要在能够再写入之前进行擦除。

垃圾回收

SSD控制器中的垃圾回收进程确保“stale”的页被擦除并变为“free”状态，使得进来的写入命令可以访问这个页。

如第一节中所说，擦除命令需要1500-3500 μs，写入命令需要250-1500 μs。因为擦除比写入需要更高的延迟，额外的擦除步骤导致一个延迟使得写入更慢。因此，一些控制器实现了后台垃圾回收进程，或者被称为闲置垃圾回收，其充分利用空闲时间并经常在后台运行以回收stale页并确保将来的前台操作具有不足够的空页来实现最高性能[1]。其他的实现使用并行垃圾回收方法，其在来自主机的写入操作的同时，以并行方式进行垃圾回收操作。

遇到写入工作负载重到垃圾回收需要在主机来了命令之后实时运行的情况并非罕见。在这种情况下，本应运行在后台的垃圾回收进程可能会干预到前台命令[1]。TRIM命令和预留空间是减少这种影响的很好的方法，具体细节将在6.1和6.2节介绍。

后台操作可能影响前台操作

诸如垃圾回收后台操作可能会对来自主机的前台操作造成负面影响，尤其是在持续的小随机写入的工作负载下。

块需要移动的一个不太重要的原因是read disturb（读取扰乱）。读取可能改变临近单元的状态，因此需要再一定数量的读取之后移动块数据[14]。

数据改变率是一个很重要的影响因素。有些数据很少变化，称为冷数据或者静态数据，而其他一些数据更新的很频繁，称为热数据或者动态数据。如果一个页一部分储存冷数据，另一部分储存热数据，这样冷数据会随着热数据一起在垃圾回收以损耗均衡的过程中拷贝，冷数据的存在增加了写入放大。这可以通过将冷数据从热数据之中分离出来，存储到另外的页中来避免。缺点是这样会使保存冷数据的页更少擦除，因此必须将保存冷数据和热数据的块经常交换以确保损耗均衡。

因为数据的热度是在应用级确定的，FTL没法知道一个页中有多少冷数据和热数据。改进SSD性能的一个办法是尽可能将冷热数据分到不同的页中，使垃圾回收的工作更简单。

分开冷热数据

热数据是经常改变的数据，而冷数据是不经常改变的数据。如果一些热数据和冷数据一起保存到同一个页中，冷数据会随着热数据的读-改-写操作一起复制很多次，并在为了损耗均衡进行垃圾回收过程中一起移动。尽可能的将冷热数据分到不同的页中是垃圾回收的工作更简单

缓存热数据

极其热的数据应该尽可能多的缓存，并尽可能的少的写入到硬盘中。

以较大的量废除旧数据

当一些数据不再需要或者需要删除的时候，最好等其它的数据一起，在一个操作中废除一大批数据。这会使垃圾回收进程一次处理更大的区域而最小化内部碎片。

为SSD编程（3）：页、块和闪存转换层