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

（1.四川大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，成都 610200；2.成都云祺科技有限公司，成都 610041）

0 引言

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

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

1 NTFS系統(tǒng)結(jié)構(gòu)

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

圖1 NTFS系統(tǒng)結(jié)構(gòu)

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

NTFS中的每個(gè)文件都有一個(gè)或多個(gè)文件記錄來(lái)記錄文件數(shù)據(jù)的位置以及文件的其他信息，$MFT文件是NTFS中所有文件記錄的集合。每個(gè)文件記錄都有其序號(hào)，又稱文件記錄號(hào)。文件記錄號(hào)從0開(kāi)始，第0號(hào)文件記錄是基本文件記錄，是整個(gè)文件記錄自身的文件記錄，通過(guò)解析基本文件記錄可以獲取全部文件記錄在磁盤(pán)上的位置。

文件記錄由文件記錄頭和屬性列表組成。文件記錄頭保存文件記錄大小等一些基本信息并指向?qū)傩粤斜碇械娜肟?；屬性列表由一個(gè)個(gè)屬性組成，屬性是保存文件特征信息的數(shù)據(jù)結(jié)構(gòu)，例如要獲得文件數(shù)據(jù)在磁盤(pán)上的位置，需要查找文件記錄中的80屬性。常見(jiàn)屬性的描述如下。

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

b）80屬性：數(shù)據(jù)文件專用，存放或指向文件數(shù)據(jù)。

c）90屬性：目錄文件專用，存放目錄項(xiàng)。

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

e）B0屬性：位圖屬性?；疚募涗浿?，B0屬性用于記錄每個(gè)文件記錄的使用情況；在目錄文件的文件記錄中，B0屬性用于記錄每個(gè)索引節(jié)點(diǎn)的使用情況。

2 海量小文件讀寫(xiě)方法

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

圖2 NTFS海量小文件讀寫(xiě)方法結(jié)構(gòu)

2.1 采集模塊

采集模塊具有四個(gè)功能。

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

表1 $Boot偏移量含義

（2）定位文件記錄。定位是預(yù)讀的前提。$Boot文件中偏移量為0x30的數(shù)據(jù)為$MFT起始簇號(hào)，采集模塊據(jù)此訪問(wèn)$MFT起始位置，也就是基本文件記錄。通過(guò)解析基本文件記錄的80屬性，定位整個(gè)$MFT文件在磁盤(pán)上的位置。

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

（4）預(yù)讀文件數(shù)據(jù)。該功能的實(shí)現(xiàn)方法與預(yù)讀文件記錄相同，一次性預(yù)讀大段數(shù)據(jù)，從而降低讀取次數(shù)，減少開(kāi)銷。

2.2 定位模塊

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

（1）小索引。當(dāng)目錄下文件數(shù)量比較小時(shí)（一般是7個(gè)以下），文件名直接存放在目錄文件記錄的90屬性中。一般情況下，90屬性后無(wú)A0和B0屬性。

（2）單索引節(jié)點(diǎn)。文件數(shù)量增多（一般為8～20個(gè)），90屬性無(wú)法存放全部的文件名。此時(shí)文件名會(huì)存放在一個(gè)索引節(jié)點(diǎn)中，90屬性只存放索引節(jié)點(diǎn)號(hào)，索引節(jié)點(diǎn)的數(shù)據(jù)運(yùn)行列表（可以指向某個(gè)位置的數(shù)據(jù)）存放在A0屬性中。

（3）多索引節(jié)點(diǎn)。文件數(shù)量再次增多（一般為20～200個(gè)），一個(gè)索引節(jié)點(diǎn)無(wú)法存放全部的文件名，此時(shí)NTFS系統(tǒng)會(huì)再申請(qǐng)新的索引節(jié)點(diǎn)，多個(gè)索引節(jié)點(diǎn)共同存放文件名。此時(shí)90屬性存放部分文件名和索引節(jié)點(diǎn)號(hào)，索引節(jié)點(diǎn)的數(shù)據(jù)運(yùn)行列表存放在A0屬性中。

（4）多級(jí)索引節(jié)點(diǎn)。文件數(shù)量非常大（一般為200個(gè)以上），90屬性無(wú)法存放所有的索引節(jié)點(diǎn)號(hào)，此時(shí)NTFS系統(tǒng)會(huì)用一個(gè)新索引節(jié)點(diǎn)存放索引節(jié)點(diǎn)號(hào)和文件名。90屬性存放索引節(jié)點(diǎn)號(hào)和部分文件名，A0屬性存放多個(gè)索引節(jié)點(diǎn)的數(shù)據(jù)運(yùn)行列表。此時(shí)的目錄結(jié)構(gòu)為B-樹(shù)。

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

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

圖3 定位模塊流程圖

2.3 提取模塊

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

2.4 寫(xiě)入模塊

寫(xiě)入模塊的流程如圖4所示。寫(xiě)入模塊接收寫(xiě)隊(duì)列中依次出隊(duì)的文件記錄號(hào)，若對(duì)應(yīng)的文件記錄已被采集模塊采集，可直接從內(nèi)存中訪問(wèn)；若未被采集，由采集模塊將整段文件記錄讀入內(nèi)存。寫(xiě)入模塊解析文件記錄的80屬性得到文件數(shù)據(jù)在磁盤(pán)上的偏移，通過(guò)采集模塊實(shí)現(xiàn)數(shù)據(jù)的預(yù)讀后，向NTFS發(fā)送寫(xiě)命令將該數(shù)據(jù)寫(xiě)入指定文件中。

圖4 寫(xiě)入模塊流程

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

3 實(shí)驗(yàn)與評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

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

表2 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)內(nèi)容

本文設(shè)計(jì)了一組對(duì)比實(shí)驗(yàn)，給定幾個(gè)目錄，先獲取目錄下所有文件的信息，再讀取每個(gè)文件的數(shù)據(jù)，寫(xiě)入到指定文件中。與本文方法對(duì)比的是系統(tǒng)調(diào)用，通過(guò)opendir、readdir和stat獲取文件列表信息，通過(guò)C標(biāo)準(zhǔn)庫(kù)函數(shù)fopen、fread、fwrite和fclose實(shí)現(xiàn)文件數(shù)據(jù)的讀寫(xiě)。本實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)為獲取文件列表信息時(shí)間和讀寫(xiě)文件時(shí)間。

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

圖5 獲取文件列表速率

圖6 讀寫(xiě)文件速率

表3 海量小文件對(duì)比實(shí)驗(yàn)數(shù)據(jù)

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

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

4 結(jié)語(yǔ)

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