一種面向NTFS的海量小文件高速讀寫方法

彭涵鈞，黃傳波，涂 磊，胡曉勤

（1.四川大學網絡空間安全學院，成都 610200；2.成都云祺科技有限公司，成都 610041）

0 引言

隨著信息技術的不斷發(fā)展，社交平臺、電商等數據密集型應用的普及，數據量呈爆炸式增長。其中，最常用的數據為圖片、日志和電子郵件等小于1MB的小文件。目前的文件系統(tǒng)大多是針對大文件設計，其元數據管理機制、數據存儲機制以及緩存機制在處理小文件時效率會大幅下降，海量小文件問題已成為工業(yè)界和學術界共同的難題。

目前，學者主要針對HDFS等分布式文件系統(tǒng)的海量小文件讀寫性能進行了優(yōu)化，并沒有很好的方法解決本地文件系統(tǒng)上的海量小文件問題。NTFS是Windows環(huán)境下主流的本地文件系統(tǒng)，在Windows 2000及以上版本的操作系統(tǒng)中，分區(qū)文件系統(tǒng)默認格式化為NTFS。因其具有安全性高、可靠性強、高效、文件碎片少等特點，已經取代了Windows98的FAT32文件系統(tǒng)。本文提出了一種面向NTFS的海量小文件高速讀寫方法。

1 NTFS系統(tǒng)結構

NTFS系統(tǒng)結構如圖1所示，其主要結構為卷，一個NTFS卷由文件組成，文件分為元文件和用戶文件。其中，元文件是隱藏的系統(tǒng)文件，用戶不能直接對元文件進行訪問，是NTFS文件系統(tǒng)中最重要的部分。除根目錄外，元文件的文件名均以“$”符號開頭。除$Boot文件固定在第0簇外，NTFS中其他文件的位置都是不固定的。在本文提出的方法中，主要對$Boot和$MFT進行了解析。

圖1 NTFS系統(tǒng)結構

$Boot文件是用于系統(tǒng)啟動的元文件，該文件的數據流指向卷的啟動扇區(qū)，包含有卷大小、簇大小、扇區(qū)大小等文件系統(tǒng)基本信息，其位置固定在卷中的第0簇。

NTFS中的每個文件都有一個或多個文件記錄來記錄文件數據的位置以及文件的其他信息，$MFT文件是NTFS中所有文件記錄的集合。每個文件記錄都有其序號，又稱文件記錄號。文件記錄號從0開始，第0號文件記錄是基本文件記錄，是整個文件記錄自身的文件記錄，通過解析基本文件記錄可以獲取全部文件記錄在磁盤上的位置。

文件記錄由文件記錄頭和屬性列表組成。文件記錄頭保存文件記錄大小等一些基本信息并指向屬性列表中的入口；屬性列表由一個個屬性組成，屬性是保存文件特征信息的數據結構，例如要獲得文件數據在磁盤上的位置，需要查找文件記錄中的80屬性。常見屬性的描述如下。

a）30屬性：存放文件名。

b）80屬性：數據文件專用，存放或指向文件數據。

c）90屬性：目錄文件專用，存放目錄項。

d）A0屬性：目錄文件專用，90屬性的擴展屬性，存放索引節(jié)點的位置。

e）B0屬性：位圖屬性。基本文件記錄中，B0屬性用于記錄每個文件記錄的使用情況；在目錄文件的文件記錄中，B0屬性用于記錄每個索引節(jié)點的使用情況。

2 海量小文件讀寫方法

本文提出的NTFS海量小文件讀寫方法由采集模塊、定位模塊、提取模塊和寫入模塊四部分組成。采集模塊讀磁盤獲取其他模塊所需的數據后，定位模塊根據目錄路徑定位目錄的文件記錄，提取模塊通過解析文件記錄指向的目錄項結構得到目錄下的文件列表并將每個文件的文件記錄號推入寫隊列，隊列中每個文件記錄號出隊后進入寫入模塊，寫入模塊訪問內存中采集模塊預讀的數據，向文件系統(tǒng)發(fā)送寫指令，將數據寫入指定位置。方法的模塊結構如圖2所示，采集模塊、定位模塊、提取模塊模擬了NTFS的讀操作，最后由寫入模塊通過系統(tǒng)調用實現寫操作。

圖2 NTFS海量小文件讀寫方法結構

2.1 采集模塊

采集模塊具有四個功能。

（1）采集文件系統(tǒng)基本信息。采集模塊通過讀起始扇區(qū)，解析$Boot文件的結構，獲取文件系統(tǒng)基本信息。$Boot文件中部分偏移量的含義如表1所示。其中，每個扇區(qū)的字節(jié)數、每個簇的扇區(qū)數、每個文件記錄的簇數和每個索引記錄的簇數是文件系統(tǒng)存儲單元的基本信息，對這部分信息的采集是模擬文件系統(tǒng)讀操作的必要條件。

表1 $Boot偏移量含義

（2）定位文件記錄。定位是預讀的前提。$Boot文件中偏移量為0x30的數據為$MFT起始簇號，采集模塊據此訪問$MFT起始位置，也就是基本文件記錄。通過解析基本文件記錄的80屬性，定位整個$MFT文件在磁盤上的位置。

（3）預讀文件記錄。寫入模塊接收寫隊列中的文件記錄號后需要讀取對應的文件記錄，單個文件記錄的大小通常為1 KB，通過預讀機制可以大幅提升后續(xù)文件記錄的訪問效率。采集模塊定位文件記錄后，將文件記錄拆分成若干個段。在寫入模塊需要訪問文件記錄時，從磁盤中將其所在的整個文件記錄段讀入內存，在接收到段內其他文件記錄號時，寫入模塊可以直接訪問文件記錄。采集模塊在內存中開辟若干塊的空間用于存放文件記錄段，并采用LRU（least recently used，最近最少使用）算法實現文件記錄段的置換。每個文件記錄段維護一個計時器，每當寫入模塊處理完一個文件記錄號后，其所在的文件記錄段計時器不變，內存中其他文件記錄段的計時器加1，當需要進行置換時，優(yōu)先置換計時器值大的文件記錄段。此外，當一個文件記錄段內的全部文件記錄被訪問過后，釋放該部分內存。

（4）預讀文件數據。該功能的實現方法與預讀文件記錄相同，一次性預讀大段數據，從而降低讀取次數，減少開銷。

2.2 定位模塊

定位模塊的功能是根據給定的目錄路徑，定位目錄的文件記錄。根據目錄量級的不同，NTFS存放目錄項的方式也不同，隨著目錄下文件數量的增多可分為以下4種情況，分別是小索引、單索引節(jié)點、多索引節(jié)點、多級索引節(jié)點，后三種索引節(jié)點統(tǒng)稱為大索引。

（1）小索引。當目錄下文件數量比較小時（一般是7個以下），文件名直接存放在目錄文件記錄的90屬性中。一般情況下，90屬性后無A0和B0屬性。

（2）單索引節(jié)點。文件數量增多（一般為8～20個），90屬性無法存放全部的文件名。此時文件名會存放在一個索引節(jié)點中，90屬性只存放索引節(jié)點號，索引節(jié)點的數據運行列表（可以指向某個位置的數據）存放在A0屬性中。

（3）多索引節(jié)點。文件數量再次增多（一般為20～200個），一個索引節(jié)點無法存放全部的文件名，此時NTFS系統(tǒng)會再申請新的索引節(jié)點，多個索引節(jié)點共同存放文件名。此時90屬性存放部分文件名和索引節(jié)點號，索引節(jié)點的數據運行列表存放在A0屬性中。

（4）多級索引節(jié)點。文件數量非常大（一般為200個以上），90屬性無法存放所有的索引節(jié)點號，此時NTFS系統(tǒng)會用一個新索引節(jié)點存放索引節(jié)點號和文件名。90屬性存放索引節(jié)點號和部分文件名，A0屬性存放多個索引節(jié)點的數據運行列表。此時的目錄結構為B-樹。

綜上所述，小索引的目錄項一定只存放在90屬性中，3種大索引的目錄項一定存放在A0屬性中，而90屬性可能存放部分目錄項。無論是大索引還是小索引，90屬性都可能存放需要的文件名，因此先解析90屬性，未匹配到需要的文件名時，判斷目錄為大索引還是小索引，如為大索引，無需考慮索引節(jié)點的結構，只需解析A0屬性，遍歷其指向的所有索引節(jié)點即可。如為小索引，說明未能找到所需的文件名。

定位模塊從根目錄開始，循環(huán)獲取下一級目錄的文件記錄號，根目錄的文件記錄號固定為5，即元文件“.”。定位模塊流程如圖3所示。

圖3 定位模塊流程圖

2.3 提取模塊

提取模塊的功能是提取目錄下所有的目錄項信息。模塊分為三個過程，①通過定位模塊得到的文件記錄號獲取文件記錄。②遍歷目錄項，提取目錄項信息。海量小文件目錄的目錄項通常為多級索引節(jié)點，相對于定位模塊要龐大和復雜的多。③對目錄項排序并推入寫隊列中。通常情況下，連續(xù)生成的小文件在磁盤上的分布也是連續(xù)的。提取模塊按照文件的創(chuàng)建時間對目錄項進行排序，使磁盤上數據的分布順序與入隊順序盡可能的相似，從而提升數據預讀時的命中率。

2.4 寫入模塊

寫入模塊的流程如圖4所示。寫入模塊接收寫隊列中依次出隊的文件記錄號，若對應的文件記錄已被采集模塊采集，可直接從內存中訪問；若未被采集，由采集模塊將整段文件記錄讀入內存。寫入模塊解析文件記錄的80屬性得到文件數據在磁盤上的偏移，通過采集模塊實現數據的預讀后，向NTFS發(fā)送寫命令將該數據寫入指定文件中。

圖4 寫入模塊流程

NTFS中文件數據有兩種存儲方式。當文件非常小時，文件記錄的80屬性為常駐，即數據可以直接存放在80屬性中，寫入模塊直接從80屬性讀取數據；80屬性為非常駐時，屬性中存放指向文件數據的數據運行列表，解析后即可得到數據在磁盤上的偏移。寫入模塊通過屬性頭內偏移量為0x08的字節(jié)判斷其是否常駐，0表示常駐，1表示非常駐。

3 實驗與評估

3.1 實驗環(huán)境

本實驗的實驗環(huán)境如表2所示。文件系統(tǒng)版本為NTFSV3.1，于2001年秋季發(fā)布并用于Win?dows XP及后續(xù)版本，是目前最為常見的NTFS版本。

表2 實驗環(huán)境

3.2 實驗內容

本文設計了一組對比實驗，給定幾個目錄，先獲取目錄下所有文件的信息，再讀取每個文件的數據，寫入到指定文件中。與本文方法對比的是系統(tǒng)調用，通過opendir、readdir和stat獲取文件列表信息，通過C標準庫函數fopen、fread、fwrite和fclose實現文件數據的讀寫。本實驗的評價指標為獲取文件列表信息時間和讀寫文件時間。

本實驗分別對量級為1萬、10萬、100萬、1000萬的小文件目錄進行實驗，目錄下既有數據常駐的小文件，又有存放在其他簇上的“較大”的小文件，其總大小與量級成正比。實驗數據如表3所示，圖5、圖6分別為獲取文件列表速率和讀寫文件速率。

圖5 獲取文件列表速率

圖6 讀寫文件速率

表3 海量小文件對比實驗數據

如圖5所示，在目錄量級較小時，本文提出的方法沒有明顯提升獲取文件列表信息的速率，其原因在于采集模塊和定位模塊會有一定的時間開銷，而這一開銷與目錄量級無關。隨著目錄量級的增大，提取模塊遍歷目錄項的時間開銷占比增大，遍歷時間與目錄量級等比增長，獲取文件列表速率提升并趨于穩(wěn)定，而系統(tǒng)調用的獲取速率隨著量級的增大逐漸降低。因此，在海量小文件的情形下，本文提出的方法能夠提升獲取文件列表信息的速率。

與獲取文件列表信息時相同，讀取文件時，采集模塊實現文件記錄分段有一定的開銷。隨著目錄量級的增大，讀寫文件速率提升。但由于預讀機制的隨機性，當目錄下文件的磁盤分布相對零散時，本實驗的實驗結果可能不與預期結果完全一致。如圖6所示，不同量級目錄的速率沒有呈現逐步提升的趨勢，這是可以接受的。與系統(tǒng)調用讀寫文件速率的對比結果表明，在海量小文件的情形下，本文提出的方法能夠大幅提升讀寫速率。

4 結語

本文提出了一種面向NTFS的海量小文件讀寫方法。該方法對NTFS結構進行解析，提取了文件拷貝時使用的有效元數據；對文件記錄進行解析，獲取了文件屬性從而查找到文件數據或索引節(jié)點的位置；對NTFS目錄項結構進行解析，實現了目錄路徑的分級依次查找；通過遍歷目錄項，獲取了目錄下文件列表信息；通過文件記錄分段和預讀，提升了文件記錄的訪問速率；通過數據的預讀，提升了用戶數據的讀取速率。實驗結果表明，該方法能大幅提升NTFS環(huán)境下海量小文件的讀寫速率。同時，本文并未對采集模塊實現內存置換時的命中率進行深入研究，如果能夠優(yōu)化置換算法，讀寫效率可以進一步提高。