通过差值和压缩减少SSD的擦除次数*

2019-01-17郭云格陈明宇蒋德钧

计算机与生活 2019年1期

郭云格，陈明宇，蒋德钧

1.中国科学院计算技术研究所，北京 100190

2.中国科学院大学，北京 100049

1 引言

固态硬盘（solid state drives，SSD），具有读写速度快、防震抗摔、低功耗、无噪音、工作温度范围大、轻便等机械硬盘不具有的优点。SSD在接口规范和定义、读写功能及使用方法上与普通硬盘完全相同。因此，最近几年SSD被越来越多地应用于数据中心服务器、存储系统等多种领域。

类似于一次写入型存储器，SSD在进行写之前必须进行擦除操作。频繁的擦除操作会严重影响SSD寿命和性能：首先，擦除操作会损耗存储单元，导致SSD无法可靠地保存数据。当擦除次数达到上限时，SSD将无法继续使用。此外，擦除操作可能导致的写入放大会增加写和读请求的响应时间，严重影响SSD的性能[1-2]。

为了减少SSD的擦除次数，可以采用一次写入型存储器编码WOM（write-once memory codes）[3]，但是由于编码的长度大于数据本身的长度，需要占用额外的存储空间，在SSD的设计中并没有被广泛采用。近年来提出的Reusable SSD[4]利用SSD每个物理页的额外空间实现二次写，但是需要占用大量的额外空间。随着SSD使用时间的增长，需要保存校验位的额外空间越来越多，这种方法将不再适用。

为了在减少SSD擦除次数同时提升空间利用率，本文针对数据库中的数据更新场景设计了一种对SSD进行二次写（对写过的SSD物理页进行二次写入）的方法，即基于差值和压缩的二次写（second write based on difference and compression，SWBOCAD）。最后本文使用tpcc基准测试程序对所提的编码方式进行了评测。评测结果表明，和Reusable SSD[4]相比，在数据更新量较小的应用场景中，SWBOCAD能够减少SSD 50%的擦除次数。

本文的主要贡献如下：

（1）提出利用物理页中的可写位和WOM编码实现对一个SSD物理页的二次写；

（2）提出利用压缩进一步提升二次写的可能性。

本文的组织结构：第2章介绍本文的工作背景；第3章介绍SWBOCAD的设计与实现；第4章对本文提出的方法进行评测；第5章介绍与本文相关的工作；第6章为总结。

2 工作背景

2.1 基于NAND Flash的SSD

SSD一般采用NAND Flash作为内部的存储介质。根据存储元件的不同，可以将SSD分为SLC（single-level cell）、MLC（multi-level cell）、TLC（triplelevel cell）三种。三种存储元件的每个存储单元（cell）分别可以存储1 bit、2 bit、3 bit的信息。存储单元通过电压的高低来表示不同的数据。存储元件的基本结构如图1所示。

Fig.1 Storage cell structure图1 存储单元结构图

在对一个闪存单元编程的时候，电压加到控制栅极（control gate）上，形成一个电场，让电子穿过硅氧化物栅栏，达到浮动栅极（floating gate）。穿越过程完成后，控制栅极上的电压会立刻降回零，硅氧化物就扮演了一个绝缘层的角色。单元的擦除过程类似，只不过电压加在硅基底（P-well）上。

在SSD内部，存储单元被组织成块（block），即擦除的基本单位。一个块通常包括256～2 048个页（page），页大小通常为2～16 KB，页是读写的基本单位。在芯片内部，块又被分成若干个平面（plane），每个平面分开管理，可以独立地进行各种操作[5-6]。图2是Micron的芯片内部结构图[7]。

每个页都配有额外区域，主要用来保存ECC编码（error correction codes）[2,5]，其大小通常为页面大小的5%～12.5%[6,8]。随着SSD使用时间的增长，需要保存ECC的空间也会增加[2,9-10]。

由于SSD在写之前必须擦除，如果在不改变数据存储位置的条件下对数据进行原地更新（in-place update），会造成巨大的开销。因此，SSD的数据更新操作通常采用异地更新的方式（out-of-place update）：在收到一个逻辑页的更新请求时，之前其对应的物理页会被标记为无效页，新的数据会被写到一个新分配的未写过的物理页中。这就需要建立一个映射表来保存逻辑页和物理页的映射关系，这是闪存转换层（flash transfer layer，FTL）的主要工作。

虽然有很多工作尝试改进垃圾回收的时机和策略[11]，利用缓存来尽量减小写入放大的倍数[12]，平衡各个块的擦除次数来延长SSD的寿命[13]，但是垃圾回收仍然是影响SSD性能和使用寿命的一个重要因素。

2.2 WOM编码

WOM编码在1982年第一次被Rivest和Shamir提出[3]，表1是WOM编码的一种。假设每一位只能从0变为1，无法从1变为0。

Table 1 WOM codes表1 WOM编码

这种方式用3位编码来表示2位的数据。以数据01为例，第一次写的时候用010来表示；当进行第二次写的时候，如果数据还是01，则保持编码不变，即010；如果数据变为00，则用编码111；如果数据变为10，则用编码011；如果数据变为11，则用编码110。可以看到，第一次写的编码010总能够被第二次写的编码111、011、110完全覆盖。通过这种编码，原来只能写一次的存储介质就能进行二次写。

当然，表1只是WOM编码中的一种，有很多其他的编码方式。但是无论采用哪种编码方式，编码的长度总是长于数据的长度。如果在SSD中采用WOM，以表1的编码为例，只有2/3的实际空间被用来存储数据；每次数据传输也都需要额外传输更多的数据。

Fig.2 Micron NAND flash chip internal structure图2 镁光NAND闪存芯片内部结构图

3 设计与实现

通常情况下，新写一个SSD页时，写入数据有1有0。根据SSD擦除机制，SSD擦除一个数据块时将块内所有位置为1。因此，SSD在写入数据时只将bit值为1的位置为0，即实际只写入0，并不写入1。由于实际写入数据时有0有1，因此，一个物理页写过一次后，通常有些位仍然处于可写的状态（programable），本文将这种物理页称为可二次写页，对这些物理页仍然可写的位再次执行写操作，称之为二次写。本文利用上述可二次写入的物理页中仍然可以写入的位保存新数据，从而提高这些可二次写页的利用率，进而减少物理页的擦除次数。

因此，为了实现基于物理页的二次写操作，对于逻辑页的更新操作，本文不像传统的SSD设计，为逻辑页分配一个新的物理页进行写入，而是将待写入的数据和该逻辑页对应的原来物理页的数据进行对比（按位异或），得到一个差值信息。对于一个已写入一次的物理页而言，其中可写位的数量可能并没有太多，因此，本文利用上述差值信息判断待写入数据是否可以以二次写入的方式进行保存。如果差值并不大，则保存差值这个信息到写过的物理页中；如果差值很大，则延用传统的SSD异地更新机制，分配一个新的物理页保存新数据。

为了进一步减少所需的可写位，充分利用写过的物理页，本文将差值信息进行压缩，然后进行编码，再将编码写入到可重写的页中。之后，将可重写页的页号等二次写的信息保存到原来物理页的额外空间中。

图3所示为驱动软件与SSD控制器的交互示意图。其中，SSD控制器接收驱动发来的读写请求，再向Flash芯片发送相应命令进行读写操作。

Fig.3 System structure图3 系统结构图

本文提出的方法可以实现在SSD控制器中，写入操作的数据差值和压缩过程都在SSD控制器中实现；读取操作的数据解压和还原操作也在SSD控制器中实现。

3.1 写操作

写操作的主要流程如图4所示，当控制器接收到驱动的某个逻辑页的写请求时，首先根据映射表判断该逻辑页是否已经有物理页与之相对应。

本文提出的方法只对有物理页对应的情况所做的操作进行了修改（图4中虚线框部分），下面对其中的几个主要步骤进行详细说明，以一个大小为128 bit的页面数据为例，原数据和新数据如表2所示。

Table 2 Example data表2 示例数据

3.1.1 获取差值

在接收到一个逻辑页的更新请求时，先根据映射表从SSD中读出与该逻辑页对应的物理页的数据，然后将新的数据和原来的数据进行比较，本文采用的是按位异或操作。如果异或的结果中只有少量的位是1，表明该逻辑页的新数据和旧数据相比变化较小，即更新的数据量较小，可以采用保存差值的方法来保存更新的逻辑页。

表2中原数据和新数据做异或后的结果转化为十六进制为1000000E000000000000C0000000000C。

为了减少保存差值信息所需的可写位的数量，在获取到差值信息后，由于新写入的数据和原来的数据相差较小，差值信息中绝大部分位都是0，只有少量的位是1，因此对差值进行压缩。压缩可以使用任何已有的压缩方法，本文直接采用Linux下的zip工具。由于表2中数据较少，直接采用哈夫曼编码来进行压缩，结果为0011 1111 1000 1111 1111 1111 0111 1111 1111 01，共38 bit。

Fig.4 Write process flowchart图4 写操作流程图

3.1.2 差值编码

差值压缩后，为了在可重写页上写入压缩后的数据，需要对其进行编码。

为了利用页面中已有的01或10，可以用01表示0，10表示1。对于可重写页中无法利用的01和10，将其填充为11，作为无效数据。

表2中数据进行压缩后用上述编码结果为01011010 10101010 10010101 10101010 10101010 10101010 01101010 10101010 10101010 0110。

针对可重写页中可写位的数量，可以根据可写位的数量采用相应的编码长度，例如用3 bit编码表示2 bit数据，用4 bit编码表示3 bit数据。

3.1.3 数据写入

对于编码后的数据，选取包含足够数量的可写位的可重写页。可按照可重写页中可写位的数量大小对可重写页进行排序，选择可写位的数量与编码后的数据长度相匹配的可重写页。可重写页指该页面已经被无效掉，但发现其中还有大量的可写位，没有进行擦除操作的页。

首先验证可重写页中剩余可写位的数量足够写入请求数据，然后按3.2节中编码方法将数据写入，并将可重写页的索引信息（页号）、编码方式（可用一个数字代表一种编码）等二次写信息存入原来物理页的额外空间中。

选择下述的可重写页来写入编码后的数据（不包括额外空间的内容）：

写入编码后的数据后，该可重写页的内容变为（灰色部分为改变的bit）：

3.2 读操作

数据读取首先根据映射表从原来的物理页中读取数据（这个物理页并不会作为废弃页进行回收），并从其额外空间中读取二次写的信息（可重写页的索引信息和编码方式），然后根据二次写的页号从可重写页中读取压缩后的差值数据，根据编码方式解压出差值数据，然后与旧数据进行异或操作，恢复出新的数据。

读操作的流程图如图5所示，其中，虚线框中是本文方法对传统的SSD控制器所做的补充。

Fig.5 Read process flowchart图5 读操作流程图

4 实验评测

下面对本文提出的二次写的方法进行评测。4.1节介绍测试平台及评测系统；4.2节介绍差值数据和压缩的测试；4.3节介绍可重写页的获取；4.4节测试差值写入的过程；4.5节是对测试结果的分析。

4.1 测试平台及评测系统

为了获取真实应用的数据，实验采用MySQL-tpcc[14]工具加载一个数据库，使用其中的一个大小为3 GB左右的表作为监测对象，表中大约有3 000万条记录。然后进行数据库的更新操作，记录数据更新导致的数据变化，具体步骤如下：

（1）对数据表进行300万（记录总数的10%）次更新操作，更新操作每次随机选择一条记录，然后随机选择6个非主键属性中的一个进行更新。

（2）对数据表做快照，保存其数据。

按照上述步骤循环几次，即可得到数据表的多个快照文件。

将不同的快照文件进行比较，获取快照文件之间的差值数据。再对差值数据进行压缩，尝试将压缩后的差值数据写入到原来的文件中，从而减少擦除次数。

4.2 差值数据及压缩测试

获取到数据表的多个快照文件后，首先按照页面大小为8 KB对文件进行切分；接着比较对应的文件，即将文件进行按位异或操作，得到页面更新前后的差值数据；然后将差值数据进行压缩，统计差值数据的压缩率。

实验共获得5个快照文件，差值数据通过相邻的快照文件进行按位异或操作得到，接着采用zip工具对差值数据进行压缩，发现绝大部分的差值数据的压缩率能够达到90%以上，只有少数的差值数据压缩率在90%以下。为了表述方便，下文的差值文件指的是包含差值数据的文件。

具体的统计结果即处于各个压缩率的文件数量所占文件总数的具体比例，如图6所示。图中（1）代表压缩率小于等于80%以下，（2）代表压缩率在81%～85%之间，（3）代表压缩率在86%～90%之间，（4）代表压缩率在91%～95%之间，（5）代表压缩率在96%～100%之间。从图6中可以看出90%的差值文件压缩率都在90%以上。

Fig.6 Percentages of files with different compression rates after 3 million times update(Cfor compression rate)图6 300万次更新后不同压缩率文件的占比（C代表压缩率）

对于间隔的快照文件进行异或操作，即第1个快照文件与第3个快照文件做差值，第2个快照文件与第4个快照文件做差值，第3个快照文件与第5个快照文件做差值，得到的为进行600万次更新操作后得到的文件的差值。各种压缩率文件所占的比例如图6所示。

图7中（1）～（5）的含义和图6相同，从图中可以看出，进行600万次更新操作后86%的差值文件的压缩率仍大于90%。

Fig.7 Percentages of files with different compression rates after 6 million times update(Cfor compression rate)图7 600万次更新后不同压缩率文件的占比（C代表压缩率）

因此，压缩后的差值文件大小低于文件自身大小的10%，可见数据库类应用的更新操作，产生的数据变化量非常小，通过保存更新前后数据的差值来保存更新后的数据可以大大减少所需的存储空间，为本文提出的SSD二次写的方法提供了可能。

4.3 可重写页的获取

根据第一次写过的页中的可写位的数量，判断该页能否用于二次写，即是否是可重写页。如果可写位的数量过低，则不满足写入压缩文件的需要，无法用于二次写。

在本实验中，切分快照文件产生的页面文件都可以视为第一次写的页，本文假定在写的过程中，存储单元只能从1变为0，不能从0变为1，则其中为1的位的数量，即为可写位的数量。

分析5个快照文件中为1的位，得到图8所示的统计结果。可以看到，对于每个快照文件，可写位的平均数量都处于27%～28%之间，能够满足写入压缩后的差值数据的要求。

Fig.8 Percentage of writable bits in snapshot file图8 快照文件中可写位的比例

事实上，如果在写数据之前可以提前感知所写的数据中0位的数量远大于1位的数量，则可以将所写数据按位取反后再进行写入，从而使物理页在第一次写后仍有很大一部分处于可写状态。

在传统的SSD设计中，垃圾回收操作会在物理页无效以后直接将其擦除，并不会利用其中的可写位，本文利用这些可写位来实现SSD的二次写。

4.4 差值写入测试

基于4.2节和4.3节所得实验数据，进行差值写入测试。选取可重写页，尝试进行二次写入的操作。实验步骤如下：

（1）任意选择一个快照文件切分后产生的页面文件作为可重写页；

（2）任意选择压缩后的文件，按照3.2节中所述方式进行编码；

（3）判断编码后的文件能否写入可重写页中。

本文共进行了4次实验，由于实验中的可重写页面数量较多（1 570 816×4），为了证明本文方法确实可行，每次从切分快照文件所得的页面文件中任意选择一个作为可重写页，对于每一个压缩后的差值文件，尝试将其写入可重写页中。

每次实验都会对差值文件1～4压缩后的3 GB/8 KB×4=1 570 816个文件进行二次写测试。对于4个可重写页，二次写失败的统计结果如图9所示。

Fig.9 Failure times of write twice图9 二次写的失败次数

其中，可重写页1的失败次数最小，所占比例为36 743/1 570 816=2.34%；可重写页2二次写全部失败；可重写页3失败次数和4接近，分别为58 529和59 958，所占比例分别为3.73%和3.82%。相应地，可重写页1中1 bit即可写位的比例最高，为28.78%；可重写页2中可写位的比例为5.98%，不满足二次写的要求，因此全部失败；可重写页3和4中可写位的比例较为接近，分别为23.99%和22.65%。

正如4.3节中所说，如果所写数据中1 bit（可写位）的数量较少，可以将数据按位取反后写入。因此，对于本文方法，可以认为所有的写过一次的页面都可以作为进行二次写的可重写页，且写入成功的概率为96%。

对于压缩率大于97%的差值文件，本文进行了进一步的实验：对每个快照文件切分后所得的页面文件（可重写页）进行两次写入操作，写入的内容为两个压缩率大于97%的差值文件；如果第一个差值文件成功写入可重写页，则记录下写入第一个差值文件后可重写页的相关信息，再尝试写入第二个差值文件。

实验结果表明，有22.41%的可重写页能够写入两个压缩后的差值文件。

对于压缩率在95%以上的差值文件，更详细的统计如图10所示。

Fig.10 Percentages of files with above 95%compression rate(Cfor compression rate)图10 压缩率在95%以上的文件所占比例（C代表压缩率）

图10中（1）～（4）分别代表压缩率在96%、97%、98%、99%的差值文件所占的比例。从图中可以看出，压缩率在97%以上的比例为65%。

4.5 测试结果分析

4.2节中差值数据的压缩结果表明数据库的更新操作导致的相应的文件内容的变化十分微小，在这类应用中，可以采用本文方法。

无论哪种应用，在其对SSD进行写入操作后，依然存在大量的可写位。本文提出的二次写的方法可以利用传统SSD设计无法利用的可写位，在响应相同的写操作的情况下，大大减少SSD的擦除次数，延长SSD的使用寿命。

4.4节的测试结果则表明，对于一个8 KB大小的页面，如果压缩率能够达到90%以上，即压缩后的文件小于其自身大小的10%，并且页面中所含的可写位的数量在30%左右，则压缩后的文件能够成功写入到页面中的概率为96%。

表3对比了本文提出的方法与Reusable SSD[4]（表中简称ReSSD）对SSD擦除次数的影响。

Table 3 Comparison between this paper and Reusable SSD表3 本文方法与Reusable SSD的比较

Reusable SSD主要思想是利用两个写过一次的物理页和其额外空间来编码一个新的逻辑页，实现物理页的二次写。具体实现为将一个逻辑页通过2.1个物理页来表示，表示成功的概率为95%；如果第一次表示尝试没有成功，进行第二次尝试。成功的概率为1-(1-0.95)×(1-0.95)=99.75%。

在收到一个写逻辑页的请求时，选择两个写过一次且被无效掉的物理页，通过编码将逻辑页的数据写到这两个物理页和其额外空间（每页的额外空间需要写入5%的数据），实现物理页的二次写。读取数据时，读出相应的两个物理页的内容，根据编码恢复出原来的数据。

Reusable SSD需要占用大量的页面的额外空间，因此随着SSD的使用，用于保证其稳定性的校验码越来越多，需要的额外空间越来越大，Reusable SSD将无法继续应用。因此只适用于SSD寿命的前30%；本文方法只占用十分少的额外空间来保存二次写的信息。以8 KB的页面为例，假设SSD的容量为512 GB，则包含226个页面，本文方法需要4×8 bit的空间来保存可重写页的索引。而对于8 KB大小的页面，通常含有448 Byte[7]的额外空间，本文方法只需占用其中的4 Byte。

对于一个可重写页写入两个文件的情况，除了需要保存可重写页的索引信息，还要保存写入文件的起始位置和长度信息。以8 KB的页面为例，包含8×8×1 024=216bit，需要2×8 bit的空间来保存起始位置，长度信息也一样。因此，除了可重写页的索引信息所需的4 Byte空间，还需要4 Byte空间来保存起始位置和长度，共8 Byte空间。

与Reusable SSD相比，本文提出的方法能够在一个可重写页中写入两个压缩后的差值文件。4.2节和4.4节中统计结果表明有82%的差值文件压缩率在95%以上，其中的65%压缩率在97%以上，即有82%×65%=53.3%的差值文件可以作为要写入的对象。而4.4节的实验结果表明对于压缩率在97%以上的文件，有22.41%的概率能够写入到可重写页中。因此，本文方法有63.3%×22.41%=14.19%的概率可以在一个可重写页中写入两个差值文件。

Reusable SSD总计减少擦除次数的百分比为：0.997 5×0.33×0.3=9.88%。本文提出的方法总计减少擦除次数的百分比为：0.96×0.5×(2×0.141 9+1-0.141 9)×1=54.81%。

由于本文方法能够有效减少SSD的擦除次数，在响应相同次数的写操作时，能够减少写入放大。但是，在读取数据的过程中，本文方法需要先将数据读出，根据额外空间的内容来判断是否有差值信息与其对应；如果有差值信息存在，还需要读取差值信息所在的物理页，然后再将差值信息解压，从而恢复出新的数据。整个过程中，进行了两次读取操作，一次解压操作；如果不采用本文方法，只需要进行一次读取操作。

在数据写入的过程中，本文方法需要先将原来的数据读出，和新数据进行异或，然后压缩，进而判断能否将其写入无效页中；如果可以，将压缩后的数据进行编码，写入到无效的页中，保存无效页的物理页号到原来页的额外空间，共需要两次读取操作，两次写入操作。如果不采用本文方法，只需进行一次写入操作。

因此，本文方法会对数据读取和写入的性能带来一定的影响。但是，在实际应用中，对于逻辑页的操作一般是连续的，可以将本文方法中的读取操作和写入操作并行，从而减少本文方法对读写性能带来的影响。

需要说明的是，本文的测试集只有3 GB，而目前SSD的容量一般都在256 GB、512 GB，但SSD进行读写的基本单位都是页，本文方法主要对页的读取和写入操作进行改动，实验数据处理也是以页作为基本单位。虽然本文的数据集对于SSD的容量而言太小，但是并不会影响本文实验结果的说服力。

5 相关工作

擦除操作会严重影响SSD的性能，近年来，有很多工作在研究如何减少擦除操作。

这些工作主要分为两大类，一类是通过优化垃圾回收操作，平衡存储单元的损耗，从而延长SSD的使用寿命。例如，Stable Greedy[15]通过逻辑页的更新频率来将逻辑页分为经常更新的热页和不经常更新的冷页，然后将其分别存放到擦除次数较少的块和擦除次数较多的块中，一方面可以减少垃圾回收中的擦除操作，另一方面也能平衡各个存储单元的擦除次数。

一类则是通过WOM编码，对写过的物理页进行重复利用，从而实现二次写，减少擦除次数。但是，基于WOM编码的大部分工作都需要多于逻辑页的空间来存储编码信息[5,16]，而且编码的复杂度较高，还有很高的几率编码失败[17-18]。改进的WOM编码利用页的额外空间来实现二次写，编码实现比较简单，但是仍然有一定的几率失败，而且随着SSD使用时间的增长无法继续发挥作用[4]。

本文方法利用写过物理页的可写位，通过简单的编码实现二次写。针对某些应用中数据更新量较小的特点，采用保存差值的方法来保存新数据。可以作为FTL的一个软件扩展，具有良好的移植性。