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.