NTFS 文件系统空间回收方法的研究

齐婵颖，李战怀，张 晓，丰文雄，张瑞杰

(西北工业大学计算机学院，西安 710129)

1 概述

云存储在工业和学术界一直是一个热点［1］。虚拟化技术中的自动精简配置技术已广泛应用于云存储中来实现动态资源分配功能［2］。该技术提供的是运行时空间，可以显著减少已分配但未使用的存储空间。自动精简配置扩展了存储管理功能，可以用较小的物理容量为操作系统提供超大容量的虚拟存储空间［3］。然而该技术会造成在应用释放申请的空间后，存储系统难以及时回收这些被释放的空间，且存在回写缓存造成的数据不一致问题。

在SAN 环境下，若要存储设备能有效回收主机文件系统所释放的空间，则必须使存储设备能感知主机文件系统对存储空间的释放行为。目前的主要文件系统在空间回收中均需要额外占用存储资源，配合完成回收。

针对空闲空间的回收问题，目前国内外主要研究有如下3 类:(1)Flash 文件系统的研究与设计中提出一种碎片回收技术，通过搬移那些状态为OUTUSE 的块，擦除状态为INVALID 的块来实现回收。该方法需要维护一张无效数据块-正常使用块对应表，该表是项目数为保留块数的一个数组［4］。这种方法需要额外的存储空间，存储效率较低。(2)垃圾回收:存储设备在经过一段时间的分配使用后，会出现空闲区和文件碎片，可能导致系统空间不够用，JFFS2 文件系统采用建立内核线程的方法来实现垃圾回收。首先重写块的全部数据，然后再擦除整个块［5］。JFFS2 是一种典型的日志文件系统，以节点的方式管理整个文件系统上的数据。而NTFS通过簇位示图存储数据，该方法不适合NTFS 文件系统。(3)文件的删除和反删除技术:当文件被用户或应用程序删除时，文件并没有立即从HDFS 删除掉，而是被临时存入/trash 目录中，存留一段可配置的时间长度。在此时间过期前可以实现反删除，恢复文件。当预留时间结束，HDFS 会自动释放与该文件相关的数据块，完成删除操作［6］。这种方法需要额外的存储空间，当删除大量文件时，会耗费较多的系统资源，而且很难对频繁的删除操作做出及时的响应。

上述方法都存在不同程度的弊端，在释放空间前，都需要占用额外的空间。而本文提出的SAN 环境下基于NTFS 文件系统簇位示图的空间智能回收方法，不需要占用额外的空间，可以实现实时的空间回收，极大提高存储利用率。该技术无需对每台应用主机附加额外的功能;在存储端实现空间回收不但可靠性较高，而且对应用的影响较小。

本文采用如下方法实现SAN 环境下NTFS 文件系统中空闲空间的回收:由存储端识别主机文件系统类型，若为NTFS，则检测关键区域元数据，确定主机文件系统中的闲置存储单元，根据映射关系确定其闲置的TP 页数据，系统在进行数据一致性确认之后，周期性地启动回收线程，进行空闲空间的智能回收［7］。

2 功能结构和基本原理

最基本的自动精简配置按需分配给服务器的是资源池中的页面而不是最初的存储空间［8］。本文提出的ThinPro iSCSI Server 是一种具有自动精简配置功能的存储服务软件。它通过容量虚拟和地址映射，可以实现基于一个较小容量的块设备或文件系统，对外提供多个可设置为较大容量的逻辑单元(LU)。

ThinPro iSCSI Server 向外提供的服务是在配置文件中预先设置的，每一组磁盘服务称为一个target(目标端)，ThinPro iSCSI Server 可以同时向外提供多个target 并分别设置不同的权限。Initiator(客户端)为发起服务端，向目标端target 发起iscsi 服务请求。图1 为iSCSI 服务端向外提供磁盘服务的整体结构示意图。

在传统的iSCSI 服务端，磁盘服务分为磁盘加载模块、容量虚拟模块、设备虚拟模块、地址映射模块、容量扩充模块以及I/O Trace 模块。本文对传统服务端进行改进，增加了空间回收模块，使其具有对上层应用不再使用的空闲存储空间进行回收的功能。

图1 iSCSI 整体结构

该空间回收机制使得存储系统可以检测到上层应用所释放的存储空间，并解除与物理存储空间的映射关系，从而使该空间可以被再次分配给任一应用，降低了发生过量提交的可能［9］，同时推迟了预警和扩容的时间，提高了存储利用率。空间回收模块适时地配合其他模块，组成一个有机体，使自动精简配置向用户提供一个有效、可用并具有较好性能的存储服务。图2 为ThinPro iSCSI Server 各个模块间的关系。

图2 ThinPro iSCSI Server 内部功能模块

3 NTFS 文件系统空闲空间检测识别

3.1 NTFS 文件系统识别

主引导扇区MBR(Master Boot Record)是系统运行时加载到内存中的第一块扇区［10］。在MBR 中每个分区记录占用16 个字节，MBR 中最多包含4 个分区的信息，而这4 个分区称为主分区;不在MBR 中的分区信息称为扩展分区。第一个扩展分区的位置信息在MBR 中最后一个分区记录中表示。

NTFS 文件系统识别依据MBR 中每条分区记录的第4 个字节内容进行判定。该条记录可以识别出分区本身是文件系统类型(FAT 或者NTFS)或者分区是否为扩展分区(即该记录指向扩展分区信息所在扇区)，用同样的方法也可识别出扩展分区的文件系统类型。

3.2 NTFS 文件系统簇位示图的检测识别

当用户将硬盘的一个分区格式化为NTFS 分区时，就建立了一个NTFS 文件系统结构。NTFS 文件系统的元数据内容保存在元文件$MFT(Master File Table 主文件表)中，指示了文件的关键属性信息，甚至包括文件内容。

在NTFS 文件系统中，所有重要的元数据均以文件的形式存放，NTFS 文件系统的元数据结构如图3所示。

图3 NTFS 文件系统元数据结构

NTFS 文件系统是以簇为单位对磁盘空间和文件的存储进行管理。元文件$Bitmap(簇位示图)描述了文件系统中簇的分配情况，在其数据属性(80H属性)中，以一个位代表一个簇是否被分配(0:未分配;1:已分配)。通过检查$Bitmap 元文件中的所有位，可以得到该文件系统的空间使用情况。$Bitmap 元文件的读取方法为:

(1)确定NTFS 分区每个簇所占扇区数，在DBR(主分区的引导扇区)中0x0D(16 进制偏移字节)处，1 个字节;每个扇区的字节数在DBR 中0x0B 处，2 个字节。

(2)确定$MFT 的首簇:在DBR 中0x30 处，8 个字节。

(3)计算$Bitmap 条目位置:将前2 步结果相乘得$MFT 首扇区，加上12($MFT 为第0 个文件，$Bitmap 为第6 号文件，每个文件记录一般占2 个扇区)。

(4)读取$Bitmap 条目位置处2 个扇区。

(5)从这2 个扇区0x30 处开始找80H 属性:读8 个字节，前4 个为属性，如果小于80 继续，后4 个为此属性所占字节(若为0，直接后移)，一直到找到80 属性。30 属性是文件名，正好确定此文件是否确定是$Bitmap。

(6)从80 属性开始处向后偏移0x40 字节，此为本文件存放位置，其中，80H 属性的第1 个未命名数据流也就是文件真正的数据，由Run List(簇流表)记录数据属性，由Data Run(数据流)记录其属性体，即文件数据的具体地址。

(7)此字节低4 位为簇数字节数，高4 位为首簇字节数［11］。

(8)从Data Run 的下一个字节开始，依次提取出Data Run 所占用的簇数和Data Run 的起始簇号，分别计算出$Bitmap 的起始偏移地址和结束偏移地址。

3.3 空闲TP 页区间的检测识别

主文件表$MFT 记录了包括$Bitmap 在内所有文件的基本信息。读取起始扇区数据可以定位$MFT，检索$MFT 即可查出$Bitmap 的文件记录，继而定位$Bitmap 文件位置。检测文件系统的所有闲置簇，把得到的所有闲置簇区间映射到TP 页的地址空间，进而计算出存储系统中对应的闲置TP 页页号。将Thin LUN(精简逻辑单元号)从0 开始编址其地址空间，划分为大小相等的TP 页，TP 页大小可以在配置文件中设置。每个逻辑单元都包含一个逻辑卷，该逻辑卷可以格式化为任意文件系统。在本文中，将其格式化为NTFS 文件系统，将簇偏移地址设定为cluster_offset。

通过实时监控元文件$Bitmap，若发现连续全0区间，记录其起始0 位为cluster_no，0 的个数为cluster_cnt。从而得到区间(cluster_no，cluster_cnt)，即为NTFS 文件系统的一个空闲区间。磁盘加载模块记录了0 号簇的偏移地址以及簇大小，TP 页大小是在配置文件中预先设置的，用N 号簇的偏移地址除以TP 页大小就可以得到N 号簇对应的物理TP 页号。以此类推，用闲置簇区间可计算出对应的嫌疑TP 页物理区间。区间(clr_no，clr_cnt)对应的候选起始TP 页页号Pstart及终止TP 页页号Pend计算分别为:

通过计算，区间(cluster_no，cluster_cnt)对应的可回收闲置TP 页区间就是(Pstart，Pend– Pstart)，即从Pstart页号开始的连续(Pend–Pstart)个TP 页。

4 回收策略

频繁地检测簇位示图，会产生过多无用的I/O操作，影响系统性能。部分解决方案采用由存储管理员指定一检测周期，周期性地全盘检测并回收闲置空间，以平衡回收效率和系统I/O 性能。然而，用户应用的数据访问模式多种多样且随时间不断变化，该方法难以针对每种应用不同时刻的数据访问模式及时地调整回收策略。

本文优化了上述回收策略:当上层应用对数据进行操作时，NTFS 文件系统会自动修改其簇位示图。因此，实时监控$Bitmap 区域的数据，计算出可能空闲的TP 页区间，存入检测队列。考虑到缓存的存在，对嫌疑TP 页区间要进行再次确认，在适当时机回收确定的空闲区间，对应基本处理流程如图4所示。

图4 系统I/O 处理基本流程

本文采取的回收触发条件为:若检测队列中存在可能闲置的TP 页区间则触发回收。

5 数据一致性

5.1 缓存一致性问题

常用cache 算法有回写和透写2 种［12］。其中，透写缓存必须修改所有存在的数据实例，或者保证丢弃所有原数据的拷贝;而回写缓存一旦数据写到缓存中，就会发送写请求已完成信号，而把数据写到非易失性存储介质上的实际操作将会延迟进行。

为了给应用提供更快的响应，文件系统对其元数据和文件实体数据I/O 均采用回写缓存机制，这样可以有效提高系统性能，但却造成了潜在的数据丢失问题。SAN 环境下，存储设备无法感知到用户主机缓存的存在，在存储端直接读取的用户数据可能是过时的数据，不能反映主机文件系统的最新空间使用情况。由于主机缓存所造成的数据一致性问题，使得系统在存储端很难根据读取的文件系统元数据有效识别闲置空间。因为在存储端看到的闲置空间很可能在主机的缓存中已经被标识为已分配。此时，若贸然进行回收操作，很可能会破坏新写入的数据，造成严重后果。

5.2 数据一致性确认方法

为了避免缓存机制造成的数据不一致问题，需要在空间回收前再次确认数据一致性，基本流程如图5 所示。

图5 回收线程中数据一致性确认基本流程

在任意时刻，当检测队列中有待检测区间时，按顺序取出检测区间。先计算出当前检测区间A 对应的嫌疑TP 页区间B，若该嫌疑区间为空集，则顺序对下一检测区间进行操作。否则，延迟时间T，计算与之前区间A 相关的区间A1 对应的嫌疑TP 页区间B1，若不为空集，且区间(B∩B1)不为空集，则区间(B∩B1)对应的TP 页确定可以回收，且更新检测队列。否则，说明该区域已经被再次操作。此时，查看检测队列中是否还有区间，继续如上操作。

在满足回收触发条件之后，系统唤醒回收线程。回收线程读取检测队列中的待检测区间，针对待处理的当前区间进行闲置空间的判定。若其满足闲置空间的条件，则使用上述方法进行数据一致性确认:读取写I/O 区间表计算其与当前区间的交集区间，当前区间中不在此交集区间的TP 页确认为当前闲置的区间，可进行回收，否则执行延迟确认。其中，延迟的数据一致性通过Linux 动态定时器触发延迟确认，确认过程由系统工作队列的event 线程执行。

6 实验与分析

6.1 实验环境

针对本文所述的NTFS 文件系统中基于簇位示图的空间回收方法，扩展了一个Linux 内核模块，应用自动精简配置技术，实现了基于iSCSI 协议的存储服务，针对NTFS 文件系统的空间进行了检测，并实现了自动回收。拓扑结构如图6 所示。实验平台如表1 所示。

图6 软件应用平台拓扑示意图

表1 实验环境说明

下面，首先判断文件系统类型，然后测试缓存一致性，其次测试空间回收效率，最后测试I/O 性能，并探讨其间的关系。

6.2 NTFS 文件系统的判断

文件系统类型有多种，NTFS 文件系统因其诸多优点而被广泛使用。本文主要针对NTFS 文件系统做研究。首先测试文件系统类型是否为NTFS，若为NTFS，则进一步实现回收，若不是NTFS，则不做处理。

设定虚拟磁盘容量为2 TB，启动iSCSI 服务后，当磁盘未初始化时，程序提示信息:The disc has not been initialized!当初始化完成，格式化为NTFS 文件系统类型，此时，程序会加载MBR，识别NTFS 文件系统，并记录其相关信息，留待空间回收模块使用。用磁盘管理查看到测试结果，如图7 所示。

图7 NTFS 文件系统类型识别

6.3 一致性测试缓存

由于主机缓存造成的数据一致性问题，使得系统在存储端很难根据读取的文件系统元数据有效识别闲置空间。

以NTFS 文件系统为例，在写入文件和删除文件时，对$Bitmap 数据的修改往往会迟于部分文件实体数据或目录文件的修改。表2 反映了这种延迟现象，针对Windows 平台下NTFS 文件系统3.1 版本，随机测试在写入和删除不同大小的文件时修改磁盘$Bitmap 操作的延迟时间td，其中该逻辑卷容量为1.1 GB，簇容量为1 024 B。

表2 NTFS 文件系统磁盘$Bitmap 修改延迟时间测试结果

可以看出，由于文件系统的回写缓存机制，使得在写入较小的文件时，$Bitmap 元数据缓存刷新的延迟时间反而较大;而删除文件时，无论文件大小，文件系统写入的数据量基本一致，因此，延迟时间相差不大。

这种由于缓存机制造成的数据不一致，其实质是指示空间分配状况的元数据所反映的存储空间使用情况，与当前实际的空间使用情况不同，未能反映最新空间分配状态。

在NTFS 文件系统中，设T 时刻系统检测存储端元文件$Bitmap 发现闲置区间A1，这只是在主机端$Bitmap 缓存数据最近一次冲洗到存储端之后的空间分配状态;设此缓存冲洗时刻为T1，其中T1 ＜T。若在时刻T2(T1 ＜T2 ＜T)主机端写入文件数据并分配对应存储区间A2 且A1∩A2≠φ，则在时刻T发现的闲置区间A1 实际上是过时的。对区间A1 的回收会导致已经写入的文件数据丢失，造成严重后果。

由此可见，缓存机制确实造成了数据不一致。因此，在回收过程中，维护一个写I/O 区间表，来保证数据的一致性非常必要。

6.4 空间回收效率测试

文件系统的空间回收效率可以用其空间使用量来衡量。分别在配置文件中更改TP 页大小，对系统的空间使用量进行测试，进而探测其空间回收效率。

测试条件:随机生成文件的大小范围为4 KB～1 MB，写入的文件总数为200 个，总的大小为110 889 427 B。

在测试客户主机1 上挂载测试服务器所提供的Thin LUN(可视容量设定为2 TB)，将其格式化为一个NTFS 文件系统，记录此时该Thin LUN 的空间使用量，即为元数据操作空间使用量(图中格式化对应数据值);然后将200 个测试文件写入该逻辑卷并记录其空间使用量(写入数据);接着删除全部测试文件，记录此时的使用量(删除数据)。

图8 反映了文件系统操作各阶段的空间使用量，图9 为回收效率测试曲线。

从图8 可以看出，在设定存储设备和I/O 操作时，TP 页容量决定了系统的空间使用量和空间回收效率。当设定较小的TP 页时，可以回收更多的空闲空间，实现更高效的存储利用率。

图8 Thin LUN 空间使用量测试结果

从图9 看出，当TP 页大小设置在KB 级时，回收效率可达90%以上。当TP 页大小设置为16 MB时，回收效率下降比预期缓慢，是因为回收效率跟多种因素有关，本次实验中，部分空闲元数据区域跟写入文件正好在同一空闲TP 页中，恰好被回收了。

图9 Thin LUN 空间回收效率测试结果

可以看出，针对传统空间回收方法会额外占用系统资源的问题，本文提出的基于簇位示图的空间回收方法较好地实现了空闲空间的自动检测和智能回收，可以满足频繁操作对存储空间的需求，极大提高了存储利用率。与传统回收方法相比，针对频繁的写入操作，本算法节省了额外的开销，具有更高效的存储利用率。

6.5 I/O 性能测试

添加回收功能后，当用户进行每次I/O 操作时，系统都需要使用支持自动精简配置的元数据，由此进行频繁的读取和写入，这样会导致I/O 瓶颈，在提高存储利用率的同时，降低了I/O 性能。在测试客户主机2 上使用Iometer 对目标系统中Thin LUN 的I/O 吞吐量进行测试。其中，Thin LUN 的可视容量设定为2 TB;根据文献［13］中对文件存取模式的分析，设定Iometer 的读操作所占比例为79%。

图10 显示了当传输块大小为4 KB 时，随机I/O与顺序I/O 的吞吐量。从图中可以看出，当块传输大小确定后，顺序I/O 吞吐量大于随机I/O。在顺序工作负载模式下，TP 页大小对I/O 吞吐量影响不大，在随机工作负载模式下，TP 页大小对I/O 吞吐量的影响比较明显。

图10 随机I/O 与顺序I/O 比较

图11 显示了在随机工作负载模式下，当块传输大小分为设置为16 KB、256 KB、1 MB 及16 MB 时，I/O 吞吐量在不同TP 页下的变化。

图11 I/O 性能测试

从图11 可以看出，当TP 页大小设定时，传输块大小越大，I/O 吞吐量越大。此外，TP 页大小对I/O性能也有一定的影响。TP 页越小，回收效率越高，但吞吐量不一定最大。因此，回收效率的提升对I/O性能有一定的影响。

7 结束语

本文采用自动精简配置技术实现了存储资源的按需分配。针对NTFS 文件系统，提出了一种新的基于簇位示图的空闲空间智能回收方法，解决了传统空间回收方法需要占用额外系统资源的问题。同时，针对回写缓存，给出了数据一致性判断方法，确保回收空间的准确性。经实验表明，本文方法可以解决缓存不一致的问题，实现对NTFS 文件系统的自动识别和空闲空间的智能回收，有效推迟容量预警和在线扩容的时间，极大提高了存储利用率。然而，如何在空间利用率和系统性能之间做出平衡和优化，需要进行进一步的实验和研究。

［1］Kamara S，Lauter K.Cryptographic Cloud Storage［C］//Proc.of Conference on Financial Cryptography and Data Security.Berlin，Germany:Springer，2010:136-149.

［2］Wang Lizhe，Laszewski G，Younge A，et al.Cloud Computing:A Perspective Study［J］.New Generation Computing，2010，28(2):137-146.

［3］Veprinsky A，Michael O F，Scharland M J.Data Deduplication Using Thin Provisioning:USA，7822939［P］.2010-10-26.

［4］沈建华，罗悦怿.Flash 文件系统的研究与设计［J］.计算机应用研究，2005，21(12):246-248.

［5］王 健，冯思春，陈良柱.JFFS2 文件系统存储策略研究［J］.微计算机信息，2008，24(8):68-69，83.

［6］朱 珠.基于Hadoop 的海量数据处理模型研究和应用［D］.北京:北京邮电大学，2008.

［7］Foskett S.Monitoring Filesystem Metadata for Thin Provisioning［EB/OL］.(2011-01-03).http://blog.fosketts.net/ 2011/01/03/monitoring-filesystem-metadata-thin-provisioning.

［8］Foskett S.Thin Provisioning in Depth［EB/OL］.(2011-04-01).http://searchstorage.techtarget.com/magazine Content/Thin-provisioning-in-depth.

［9］Hines M R.，Gordon A，Silva M，et al.Applications Know Best:Performance-driven Memory Overcommit with Ginkgo［C］//Proc.of the 3rd International Conference on Cloud Computing Technology and Science.［S.l.］:IEEE Press，2011:130-137.

［10］Fraser C，Cotichini C，Nguyen T C.Security Apparatus and Method:USA，20120275572［P］.2012-11-01.

［11］刘 伟.数据恢复技术深度揭秘［M］.北京:电子工业出版社，2010.

［12］韩朴杰，康慕宁，张 晓.自动精简配置技术中空间回收方法的研究［J］.计算机与现代化，2012，(12):168-173.

［13］Vogels W.File System Usage in Windows NT 4.0［C］//Proc.of the 17th ACM Symposium on Operating Systems Principles.［S.l.］:ACM Press，1999:93-109.