基于时间戳的FTL实现的连续数据恢复方法

袁 芳，刘 伟，宋贺伦，张耀辉

（1.中国科学院大学 纳米技术与纳米仿生研究所，北京100049；2.中国科学院 苏州纳米技术与纳米仿生研究所 系统集成部，江苏 苏州215123）

0 引 言

为了保证存储信息的安全，很多研究者提出连续数据保护 （continuous data protection，CDP）方法。固态硬盘（solid state drive，SSD）是采用半导体存储介质进行数据存储和读取的一种存储设备。它因为数据存取速度快、体积小、功耗小、噪音低、发热量小、抗震能力好、不易损坏等优点而备受关注。要实现CDP，需要记录数据的每次更新信息，这些信息将占用大量额外的存储空间，虽然很多研究者着力于研究怎么分散这些存储空间，但又会对设备的性能造成影响。在SSD 中，由于闪存的固有特性，不存在严格意义的覆盖写，SSD 不允许直接向一块已经写入数据的区域再写入数据。如果要达到覆盖写的效果，必须首先执行一次擦除操作，将数据块的原有数据进行擦除，然后再写入新的数据。这些未被擦除的数据恰巧可以用来实现CDP，基于此点出发，本文提出应用在SSD 上的CDP方法，它很好地解决了由于数据的变化信息而占用存储空间的问题，并且由于不需要记录数据的更新信息，其对硬盘的性能影响非常小。

1 研究背景和思路

CDP技术在很多领域都有广泛应用，如电力企业数据中心建设、医院信息系统数据保护［1］等等。典型的连续时间保护方法的实现可以基于数据块层、文件层和应用层。基于数据块的连续时间数据保护方法直接在物理存储设备上运行，需要将所有更改过的数据块按时间顺序保存下来；它与应用的相关性比较小 （与文件系统，设备无关）。基于文件级的连续数据保护方法工作在文件系统上，可以跟踪文件系统中文件数据或元数据的改变，及时备份这些变动信息，并记录发生改变的时间。基于应用层的连续时间数据保护是在受保护的应用程序中直接插入并运行连续时间数据保护功能程序代码，它能实现与应用程序的无缝整合，确保应用程序的数据在连续数据保护过程中的一致性，管理灵活，用户容易部署和实施。但是上诉实现方法均需要大量额外的存储空间来保存数据的改变。数据块级别的连续时间数据保护因为与应用的相关性小，成为很多研究者研究的目标。传统磁盘因为是 “原地更新”，旧数据会被新数据覆盖，为了可以恢复任意时间点的数据，需要在数据更新时备份数据的变化。备份这些数据需要占用大量的存储空间。很多研究者着力于研究怎样最大限度的降低这种空间浪费，并且能够在故障发生时尽快的恢复数据。NPCDP［2］将邻近时间点恢复划分为4 种类型，给出一种用“位表”标记差异数据块、把多余数据剔除、缺少数据写入的 “差异算法”，减少了数据读写、开销，提高了恢复效率。MM－CDP［3］设计了3 种元数据管理方法，包括简单的基于MySQL 数据库的实现的DIR－MySQL、OPTMySQL和根据应用特点设计的META－CDP，前两种随着恢复数据的增加，所需的恢复时间增加，而后一种恢复时间增加很小，效率要高很多。TH－CDP［4］采用日志结构，并把数据块的每次更新信息存储在原始磁盘上。HSTIM［5］旨在提高连续数据保护的响应时间。VDISK［6］是另外一个可靠的数据块级别保护的系统，它通过一个用户级别的工具来驱动和解释变化数据，并将它记录进一个只读盘中，同时它对标准的文件系统也提供文件粒度的保护。

虽然上述这些应用在硬盘上的方法都旨在解决因为CDP而带来的各种问题，但却没有考虑硬盘的存储介质的特性。对于SSD 来说，在闪存中由于特殊的数据复写机制，旧的数据被擦除之前仍旧逗留在闪存中，在旧数据未被垃圾回收 （garbage collection，GC）［7］之前，它代表的恰恰就是CDP需要保存的历史数据。另外闪存的读写单位为页，这与我们的操作系统读写数据单位不同。而为了不加重操作系统的负担，SSD 采用软件的方式建立上层系统和闪存的联系，这就是闪存地址映射层 （flash translation layer，FTL）［8］。当文件系统发送指令要写入或者更新一个特定的逻辑页时，FTL实际上是把数据写入到一个不同的空闲物理页，并更新映射信息，最后把这个页上包含的 “旧数据”标记为 “无效”。想要恢复某个时刻的数据，需要满足两个条件，一是该时刻的数据依然存在闪存中，二是FTL 中映射信息表中此数据的物理地址为该时刻该数据存储的位置。因此为了实现连续数据保护，在确保数据存在的前提下，还要恢复FTL中的映射信息。本文就是基于SSD 的这种天然特性出发提出的利用其使用过程中的残留数据进行的连续数据保护方法。为了提高硬盘的性能，FTL 的相关信息存储在以DRAM 为介质的内存中。BVSSD［9］提出的基于SSD 的连续时间数据保护方法，在内存中记录FTL中映射信息的每次变化。虽然它是利用了SSD 的介质特性，但需要在内存中记录数据更新所引起的映射信息的改变，相对来说也占用了额外的DRAM 空间。本文提出的方法中，在映射信息表中加入时间戳，映射信息直接与时间相关，不需要在DRAM 中开辟额外空间记录每次映射关系的改变。BVSSD 中受DRAM 空间的限制，可以保存的FTL的变化信息有限，这样就导致数据可恢复时间短，本文通过使可以恢复的时间始终保持在一个稳定的区间。

2 设计方案介绍

SSD 中数据在逻辑和物理层的管理结构如图1 所示。主要包括两个部分，闪存地址映射层和数据存储层。用户端向硬盘中写数据时，地址映射层为该逻辑地址分配物理地址。首先在DRAM 中记录此逻辑地址对应的物理地址和写入时间，然后将数据写入闪存的该物理地址处，并同时将该数据写入时间记录在FLASH 的该物理地址对应的OOB区域中。用户提出恢复申请前需要知道硬盘可以恢复的时间范围，即为恢复窗口，此时间存储在图1中的NOR FLASH 中。在垃圾回收时，本方案的垃圾回收策略确保那些在恢复窗口内的数据不被回收。当用户告知硬盘想要恢复的时间点，硬盘即还原此时间点时的地址映射层中的映射信息，如此即可完成数据的恢复。

2.1 闪存地址映射层

地址映射采用页映射［10］，包括逻辑页和物理页一一对应的映射表、标识每个物理页有效性的位图和其它一些控制信息表格。映射表中每条映射信息包括逻辑地址、物理地址和写入时间，因为每次数据的读写都需要访问映射表，为了可以快速操作映射表，把它存储于DRAM 中。位图所占空间大小为若干个字节，其中每一个Bit代表物理空间中的一个物理页，当某一Bit位为1时表示它对应的物理页是有效页，否则为0时表示该物理页是无效页。其它控制信息是指为地址分配提供辅助作用的一些标识信息，如：记录每个Block中有效页的个数的表格等。主机端进行读操作时，硬盘根据地址映射表中该逻辑地址对应的物理地址进行读取。主机端进行写操作时，FTL 会新分配一个物理页来写入数据，这个物理页的物理地址和当前写入时间会更新到映射表中。由于加入了时间戳标记，映射信息表中映射信息与时间直接相关，反映的是时间点上的映射信息。

图1 数据管理的结构

2.2 物理存储区

包括基于NAND FLASH 的存储区和基于NOR FLASH 的存储区。在NAND FLASH 区管理中，将若干个数据页组合成一个可以擦除的数据块，数据块的大小取决于闪存的物理结构。每个数据页包含数据区 （Data Zone）和带外区 （OOB Zone），数据区存储用户的数据，此数据页中数据的写入时间值和数据校验信息存储在OOB 区中。OOB是FLASH 中为了存放每个数据页的校验数据 （ECC）和其它一些控制信息的，对用户不可见，在Flash颗粒出厂时就预留的，可以在其中添加一些控制信息来提升性能或者添加功能，本文中在其中记录每个数据页的写入时间。Nor Flash区中包含若干个扇区单元，扇区是擦除操作得最小单位，它包含若干个Byte，Byte是读写操作的最小单位。当要写数据到Nor Flash中时，可以指定任意的物理地址。当要读取其中的数据时，可以读取指定地指处的某个Byte。当执行擦除操作时，必须擦除一个扇区，擦除成功的扇区可以再次用来存储数据。

2.3 垃圾回收机制 （GC）

数据存储在NAND FLASH 中，写入单位为数据页，也即是地址映射层中的物理页地址。因为固态硬盘不支持“原地更新”操作，若一个物理地址空间中已经写入数据，当希望再次写入此地址空间时，首先要擦除其中的数据，也即是 （写前擦除）。由于闪存的擦除单位是 “块”，因此需要当整个块达到一定条件后，才会进行擦除。当硬盘空间不足时，为了保证硬盘的正常读写性能，需要擦除一些数据块。选择哪些数据块，何时进行擦除以及块中数据如何处理也即是GC［10］机制需要考虑的问题。

假定一个数据块被选作擦除，首先需要将此数据块中有效的页搬移到别的数据块中，然后擦除此数据块，以用作后续数据的写入。为了减少搬移操作的负担，尽量选取那些其中有效数据比较少的数据块，另外，考虑到数据保护，FTL用位图来代表硬盘中哪些数据页是有效的，位图中每一位来标识每个数据页的有效性，这样可以灵活的控制数据页，对于那些CDP需要保护的数据，在擦除前也需要搬移到新的数据块中，以备数据恢复时使用。这一点与一般SSD 的GC机制是不同的，一般SSD 的GC 机制会将这些历史数据都删除，不会进行搬移。因为数据搬移引起的写操作和用户端的数据写不同，它在硬盘中记录数据页的写入时间时，记录的是从该页中读出的时间值，此时间值是最初用户数据写入硬盘时记录的写入时间。

2.4 恢复窗口

恢复窗口 （recovery window）指的是硬盘的CDP可以恢复的最远时刻，从当前时刻到恢复窗口的这段时间的数据可以恢复。因为本文利用残留在硬盘中未被回收的数据来实现数据保护，但是一些数据可能因为硬盘空间不足而被回收。因此可以恢复的时间窗口是会变化的。硬盘需要告知用户哪些时间的数据仍然可以恢复，这就需要恢复窗口的概念。

因为垃圾回收时会擦除一些数据页，这些数据页中的数据不能再恢复，这会造成恢复窗口的改变。为了能实时告知用户最新的恢复窗口，需要记录它的每次变化。如果恢复窗口用数据页中数据的写入时间来表示，它会频繁更新，会占用存储空间，也会对硬盘的性能造成一定的影响。本文中恢复窗口用数据块的标识来表示，因为垃圾回收的单位为数据块，当由于数据块被回收而引起恢复窗口改变时才进行更新，这大大降低了更新的频率。另外，更新窗口值时只需要计算数据块的标识号，不需要再读取Flash中的数据页，减小了对硬盘性能的影响。在NOR FLASH中，仅使用其中的小部分空间来记录数据块标识，这里用其中的两个扇区来记录。每个数据块标识占4个Byte，每个扇区可以记录若干个块标识，当一个扇区剩余的空间不够存下一个标识时，则在新的扇区中继续写，为了安全性，不让一个块标识跨越两个扇区。考虑到数据块的标识对用户不可见，当用户需要恢复窗口值时，通过记录的最新的数据块标识，读取OOB 中记录的此数据块的第一个数据页中的数据写入时间，此时间值也既是硬盘可恢复的最远时刻。

由于本文的GC 策略，SSD 始终能保存的数据量几乎可以达到其容量的大小，比如一天写入20GB 的数据，那一个60G 大的盘可以恢复的时间可达3天。

2.5 数据恢复过程

例如：要回退到T 时刻，具体恢复过程如下：

（1）用户通过应用程序向硬盘发送获取时间窗口的命令，硬盘在接收到命令后，从NOR FLASH 中读取记录的最新的数据块标识，读取此标识数据块中数据页的OOB区中记录的时间值，此时间值即为硬盘可以恢复的最远时间窗口点，通过应用程序将此时间值告知用户。

（2）用户根据获取的时间窗口，告知硬盘需要回退的时间点T；将它写入到NOR FLASH 中，硬盘根据NOR FLASH 中的记录信息来确定是否需要进行恢复过程。

（3）因为回退后会照成硬盘中数据状态的变化，为了保证数据的正确性，在进行回退前对硬盘进行安全关机。

（4）硬盘上电，开始恢复。首先查看NOR FLASH 中是否有回退时间T，如果有，则用户提出了恢复请求。由于地址映射层反映的是某一时刻硬盘中的数据的地址映射情况，要恢复某一时刻的数据，需要将此时刻的硬盘中数据所在的地址更新到地址映射层中。

（5）扫描OBB中每个数据页的写入时间。在扫描过程中，其中的数据页中的数据有两种情况，或者是由于GC造成的数据搬移时写入的，或者是HOST 端写入的。对于其中扫描到的因搬移而写入的页，查看其中记录的写入数据的时间戳，如果时间戳大于映射表中该条映射信息中记录的时间戳，则修改映射表。对于其中扫描到的每一个HOST 端写入的页，查看其中记录的写入数据的时间戳，如果时间戳大于映射表中该条映射信息中记录的时间戳，并且小于要恢复的时间点T，则修改映射信息。

（6）扫描完成后，映射信息都已经恢复完成，备份映射信息，以防止掉电。

（7）擦除NOR FLASH 中的回退时间T，恢复完成。

数据恢复流程如图2所示。

图2 数据恢复流程

3 测试结果分析

选择Intel L84A 颗 粒，共64 G 大 小 的Flash 颗 粒，DRAM 为64 MB，通过SATA 对硬盘进行数据读写操作。在上述条件下进行硬盘数据恢复的功能性测试和性能测试，并与未添加连续数据保护的硬盘做了测试对比，同时对其它实现连续数据保护的策略进行了对比分析。

为了更加直观的观察每个恢复点的硬盘数据状态，编写了应用程序，将需要写入硬盘的数据设定为写入硬盘时的精确到秒级的系统时间。测试发现当硬盘完成恢复点的恢复时，其中数据状态可以准确达到恢复点时的数据状态，误差仅在2～3s之内。另外，在任意时间往硬盘中写入文件或者文件夹，当需要恢复到任意时间点时，可以直观地看出这些文件和文件夹在硬盘中的状态。如图3所示：在T1时刻，硬盘中只有之前写入的文件夹，在T2时刻，硬盘中有文件夹和新写入的Word文档，在T3时刻硬盘中有文件夹、Word文档和新写入的TXT 文档。在Now 时刻，用户发现错误，想要硬盘的状态恢复到T 时刻，硬盘完成恢复操作后，硬盘中的只有之前写入的文件夹和Word文档。

图3 实现结果

因为并不需要记录每次数据的变化引起的映射信息的变化，所以并不需要占用大量额外的内存空间，表1中为内存主要占用情况。其中除了地址映射表外，还包括记录数据页有效性的位图表以及记录每个数据块中有效页个数的表格。

在设定需要恢复的时间点后，硬盘中的数据会恢复到恢复点的状态。在恢复的过程中所占用的时间主要是FLASH 中的块扫描、块排序。恢复时间见表2。在最好的情况下，FTL的最新备份可用，在最坏的情况下，最新备份不能用，需要扫描更多的数据页，从表中数据可以看出，即使最差情况恢复时间也是相当短的。

表2 恢复时间

对硬盘的性能进行了测试，对添加此功能和不添加此功能的SSD 分别做了测试，其中图4中pattern1为Sequential Read；pattern2 为Sequential Write；pattern3 为Random Read；pattern4为Random Write；pattern5为Random Read，4KB，Queue depth 1；pattern6为Random Write，4 KB，Queue depth 1；pattern7 为Random Read，4 KB，Queue depth 32；pattern8为Random Write，4KB，Queue depth 32；从图中可以看出，在添加了CDP 的情况下，并未对SSD 的性能造成明显影响。

图4 带CDP的SSD 与原始SSD 读写性能比较

图5中是和BVSSD 的结果进行的对比，可以看出对不添加数据保护的SSD 的影响，本文的影响明显小。像本文之前提到的，BVSSD 在RAM 中用一个表格来存储FTL 中映射信息的每次改变，因为RAM 空间的限制，当此表格装满时，就把此表格中的信息存储到FLASH 中，然后可以再次使用此表格记录变化的映射信息。因为在硬盘写的过程中，映射信息的变化很频繁，需要不停的在RAM 和FLASH 之间切换，这会对硬盘的写性能造成影响。而本方法则不存在这个问题。

4 结束语

图5 本文和BVSSD 对原始SSD 性能影响

本文提出了一种应用在固态硬盘上的连续数据保护方法，包括历史数据保护和地址映射层的建立和恢复，详细说明了设计的思路和详细实现方法，并对该方法进行了全面的分析。根据固态硬盘的天然特性，利用其中残留数据实现了数据保护，解决了CDP中由于历史数据备份带来的空间浪费问题。在固态硬盘的闪存地址映射层中引入时间戳的概念，有效降低了CDP对硬盘带来的性能影响。另外需要说明的是本文是在特定平台上进行的测试分析，不同的平台差异可能会导致结果略微存在差异。

［1］KONG Guanqing.Continuous data protection applied on hospital data［J］.Computer CD’s Software and Application，2011，15 （3）：50－59 （in Chinese）.［孔冠庆.浅谈连续数据保护解决方案在医院中应用 ［J］.计算机光盘软件与应用，2011，15（3）：50－59.］

［2］HOU Liman.Neighboring point data recovery for CDP based on data gap ［J］.Computer Science，2011，38 （5）：159－164（in Chinese）.［候利曼.基于数据差异的CDP邻近时间点恢复［J］.计算机科学，2011，38 （5）：159－164.］

［3］LI Hongyan.Methods of metadata management in block－level continuous data protection system ［J］.Journal of Computer Applications，2012，32 （8）：2141－2145 （in Chinese）.［李红艳.块级连续数据保护系统元数据管理方法 ［J］.计算机应用，2012，32 （8）：2141－2145.］

［4］Sheng Yonghong，Wang Dongsheng，He Jinyang，et al.THCDP：An efficient block level continuous data protection system［C］／／Proceedings of the 3th International Conference on Networking，Architecture，and Storage，2009.

［5］Sheng Yonghong，Xu Dan，Wang Dongsheng.A High effective indexing and retrieval method providing block－level timely recovery to any poing－in－time ［C］／／Proceeding in the 5th IEEE International Conference on Networking，Architecture，and Storage，2010.

［6］Jake Wires，Michael J Feeley.Secure file system versioning at the block level［C］／／Proceedings of the 2nd ACM SIGOPS／EuroSys European Conference on Computer Systems，2007：203－215.

［7］JI S，Shin D.Locality and duplication－aware collection for flash memory based virtual memory systems［C］／／10th IEEE International Conference on Computer and Information Technology，2010：1764－1771.

［8］QI Xiaoying，TANG Xian，LIANG Zhichao.OAFTL：A high－performance corporation－oriented FLASH translation layer［J］.Computer Research and Development，2011，48 （10）：1918－1926 （in Chinese）. ［綦晓颖，汤显，梁智超.OAFTL：一种面向企业级应用的高效闪存转换层处理策略 ［J］.计算机研究与发展，2011，48 （10）：1918－1926.］

［9］Huang Ping，Zhou Ke，Wang Hua，et al.BVSSD：Build built－in versioning flash－based solid state drives［C］／／Proceeding SYSTOR Proceedings of the 5th Annual International Systems and Storage Conference，2012.

［10］BAI Shi，ZHAO Peng.GFTL：A page group mapping based energy aware flash translation layer［J］.Sciencepaper Online，2011，6 （10）：716－720 （in Chinese） .［白 石， 赵 鹏.GFTL：一种基于页组映射的低能耗闪存转换层 ［J］.中国科技论文在线，2011，6 （10）：716－720］.