吳陽(yáng)++馮徑

摘 要：針對(duì)氣象水文應(yīng)用中，大量常規(guī)觀探測(cè)報(bào)文批量訪問(wèn)出現(xiàn)的低效問(wèn)題，研究文件存儲(chǔ)特性，定量分析了目錄級(jí)數(shù)和文件數(shù)量對(duì)訪問(wèn)性能的影響，發(fā)現(xiàn)文件數(shù)相對(duì)于文件大小，對(duì)于系統(tǒng)的訪問(wèn)效率影響更大，當(dāng)單個(gè)目錄下文件數(shù)目過(guò)大時(shí)，文件存取延時(shí)較大，嚴(yán)重影響用戶體驗(yàn)與服務(wù)性能。根據(jù)NTFS下的實(shí)驗(yàn)數(shù)據(jù)，設(shè)計(jì)了一種高效的目錄組織方法，優(yōu)化用戶態(tài)文件存儲(chǔ)管理算法。實(shí)驗(yàn)表明，優(yōu)化后的文件目錄結(jié)構(gòu)和組織形式，能極大地提高批量文件的讀取效率，降低20%—73%的訪問(wèn)延時(shí)，改善網(wǎng)絡(luò)環(huán)境下的大規(guī)模文件接收處理效率。

關(guān)鍵詞：存儲(chǔ)優(yōu)化；讀取效率；目錄結(jié)構(gòu)

中圖分類號(hào)：TP302.7 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計(jì)算等信息與通信技術(shù)的快速發(fā)展，信息系統(tǒng)中的數(shù)據(jù)量呈幾何級(jí)數(shù)增長(zhǎng)。據(jù)統(tǒng)計(jì)，21世紀(jì)后，人類每18個(gè)月產(chǎn)生的數(shù)據(jù)量是之前產(chǎn)生的所有數(shù)據(jù)之和。大量的數(shù)據(jù)一方面為信息的獲取提供了便利，另一方面，也對(duì)數(shù)據(jù)存儲(chǔ)技術(shù)提出了更加嚴(yán)峻的挑戰(zhàn)。

在此背景下，分布式存儲(chǔ)系統(tǒng)應(yīng)運(yùn)而生，它具有海量數(shù)據(jù)存儲(chǔ)、高擴(kuò)展性、高性能、高可靠性、高可用性的特點(diǎn)，成為當(dāng)今存儲(chǔ)研究與應(yīng)用的熱點(diǎn)。然而，文件系統(tǒng)的主要任務(wù)是管理和完成在外存中存取和搜索文件的操作，并提供透明方便、高效安全的外存應(yīng)用接口，核心算法是確定磁盤(pán)或分區(qū)上的文件存儲(chǔ)方法和數(shù)據(jù)結(jié)構(gòu)，即在磁盤(pán)上組織文件的方法。對(duì)于普通計(jì)算機(jī)使用者來(lái)說(shuō)，通常無(wú)法介入文件系統(tǒng)的核心態(tài)進(jìn)行優(yōu)化和改進(jìn)，但可以通過(guò)應(yīng)用程序，研究和設(shè)計(jì)高效的用戶態(tài)文件存儲(chǔ)管理算法，包括負(fù)載均衡、存儲(chǔ)資源分配、文件索引、目錄結(jié)構(gòu)優(yōu)化等，以改善系統(tǒng)訪問(wèn)的總體響應(yīng)時(shí)間。

本文分析了現(xiàn)有主流文件系統(tǒng)的存儲(chǔ)特征，分析了影響文件讀取性能的因素，針對(duì)氣象水文應(yīng)用中，大量常規(guī)觀探測(cè)報(bào)文批量訪問(wèn)出現(xiàn)的低效問(wèn)題，研究文件存儲(chǔ)特性，通過(guò)實(shí)驗(yàn)跟蹤了目錄結(jié)構(gòu)對(duì)讀取效率的影響，給出了一種高效訪問(wèn)文件的方法。

2 文件系統(tǒng)存儲(chǔ)特征分析（The file system storage

characteristics analysis）

文件系統(tǒng)是操作系統(tǒng)的重要組成部分，由與文件管理有關(guān)軟件、被管理文件以及實(shí)施文件管理所需數(shù)據(jù)結(jié)構(gòu)三部分組成，根據(jù)系統(tǒng)運(yùn)行和部署的方式，可分為本地和分布式兩種。

2.1 本地文件系統(tǒng)

NTFS（New Technology File System）、FAT（File Allocation Table）、EXT（Extended File System）是當(dāng)今最為廣泛使用的文件系統(tǒng)，主要管理本地文件。NTFS和FAT多在WINDOWS操作系統(tǒng)中使用，EXT多在LINUX操作系統(tǒng)中使用。其中，NTFS文件系統(tǒng)所有的數(shù)據(jù)，包括系統(tǒng)信息，如引導(dǎo)程序、記錄整個(gè)卷的分配狀態(tài)位圖和用于文件定位和恢復(fù)的數(shù)據(jù)結(jié)構(gòu)等都以文件的形式存在，而且文件和目錄是以數(shù)據(jù)庫(kù)進(jìn)行組織的。

NTFS卷中的任何一個(gè)文件均由位于MFT表中的文件記錄來(lái)完全描述，主控文件表MFT是NTFS中最重要的系統(tǒng)文件，它是一個(gè)關(guān)系數(shù)據(jù)庫(kù)，由文件記錄的數(shù)組組成，磁盤(pán)卷上的每一個(gè)文件都有一個(gè)文件記錄[1]。

記錄描述文件的第一個(gè)記錄稱為基本文件記錄，如果一個(gè)文件無(wú)法被一個(gè)基本文件記錄完全描述，系統(tǒng)會(huì)在MFT表中繼續(xù)為該文件分配一個(gè)或多個(gè)文件記錄，這些文件記錄稱為擴(kuò)展文件記錄。

NTFS文件系統(tǒng)中文件夾與它所包含的文件或文件夾的關(guān)系是通過(guò)索引來(lái)建立的，一個(gè)文件夾下文件的索引在父文件夾MFT記錄的0X90屬性或數(shù)據(jù)運(yùn)行中，一個(gè)文件夾下所有文件的索引構(gòu)成一個(gè)B+樹(shù)的結(jié)構(gòu)，這種結(jié)構(gòu)適合快速查找。

三種典型文件系統(tǒng)的存儲(chǔ)特性比較如表1所示，從中可見(jiàn)，NTFS的所有復(fù)雜度最小，支持的操作系統(tǒng)最多，也是目前應(yīng)用最廣泛的本地文件存儲(chǔ)系統(tǒng)，因此本文的實(shí)驗(yàn)部分主要針對(duì)NTFS進(jìn)行了研究。

表1 文件系統(tǒng)存儲(chǔ)特性

Tab.1 File system storage characteristics

屬性 NTFS FAT32 EXT2

簇大小 0.5kB至4kB 4kB至16kB 4kB

最大大小上限 2TB 4GB 2GB

最大分區(qū) 2TB 128GB 4TB

索引結(jié)構(gòu) B+樹(shù) 鏈?zhǔn)?鏈?zhǔn)?/p>

索引復(fù)雜度 O（logN） O（N） O（N）

支持系統(tǒng) WINDOWS 2000、

WINDOWS XP DOS、WINDOWS 95

不支持 LINUX

2.2 分布式文件系統(tǒng)

分布式文件系統(tǒng)DSF（Distributed File System）是指文件系統(tǒng)管理的物理存儲(chǔ)資源不一定直接連接在本地節(jié)點(diǎn)上，而是通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)與節(jié)點(diǎn)相連。HDFS是當(dāng)今最為廣泛使用的分布式文件系統(tǒng)，它被設(shè)計(jì)成適合運(yùn)行在通用硬件是一個(gè)高度容錯(cuò)性的系統(tǒng)，能提供高吞吐量的數(shù)據(jù)訪問(wèn)，非常適合大規(guī)模數(shù)據(jù)集上的應(yīng)用[2]。

HDFS主從式的架構(gòu)極大地簡(jiǎn)化了分布式文件系統(tǒng)的結(jié)構(gòu)，文件系統(tǒng)所能容納的文件數(shù)目取決于控制節(jié)點(diǎn)的內(nèi)存大小[3]。這就導(dǎo)致了HDFS對(duì)海量小文件支持不理想，雖然已有技術(shù)通過(guò)小文件合并來(lái)經(jīng)行優(yōu)化[4]，但這一瓶頸始終限制了其在海量小文件存儲(chǔ)中的應(yīng)用。因此HDFS在海量小文件存儲(chǔ)應(yīng)用效率還不是很高。

3 文件存取效率分析（File access efficiency analysis）

3.1 影響存取效率的因素

不同的文件系統(tǒng)采用不同的索引方式進(jìn)行文件定位。在NTFS文件系統(tǒng)中，定位文件步驟由圖1所示。endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設(shè)文件系統(tǒng)定位時(shí)間為T(mén)1，與文件系統(tǒng)本身有關(guān)；遍歷B+樹(shù)時(shí)間為T(mén)2，與B+樹(shù)的結(jié)構(gòu)有關(guān)；磁盤(pán)的控制及訪問(wèn)時(shí)間為T(mén)3，與計(jì)算機(jī)的硬件性能有關(guān)。一個(gè)文件的讀取時(shí)間為T(mén)S，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優(yōu)化方法

在文件系統(tǒng)與計(jì)算機(jī)硬件條件固定的情況下，B+樹(shù)的結(jié)構(gòu)對(duì)文件的存取效率影響至關(guān)重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關(guān)鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個(gè)文件的MFT記錄大小為1kB，當(dāng)父目錄下的文件不斷增加而生成新的索引項(xiàng)，父目錄MFT記錄沒(méi)有足夠的空間存放時(shí)，會(huì)按照B+樹(shù)的節(jié)點(diǎn)分裂規(guī)則進(jìn)行分裂，產(chǎn)生了兩層的B+目錄結(jié)構(gòu)。當(dāng)文件夾下的文件數(shù)量一直增加到一個(gè)臨界點(diǎn)，兩層的B+樹(shù)目錄不足以存放所有的索引項(xiàng)時(shí)，B+樹(shù)第二層的一些節(jié)點(diǎn)會(huì)根據(jù)B+樹(shù)的分裂規(guī)則分離出葉子節(jié)點(diǎn)，自身變成非葉子節(jié)點(diǎn)，此時(shí)變成了三層B+樹(shù)結(jié)構(gòu)[5]。

樹(shù)的深度對(duì)檢索的效率有著極為關(guān)鍵的影響，理論上，B+樹(shù)的層數(shù)越大，檢索文件的所需的遍歷時(shí)間將越長(zhǎng)，但定量的分析未見(jiàn)文件報(bào)道。不同的文件數(shù)量下系統(tǒng)中目錄會(huì)產(chǎn)生不同的樹(shù)結(jié)構(gòu)，從而對(duì)對(duì)文件的檢索效率產(chǎn)生影響：

第一層B+樹(shù)存放的索引項(xiàng)數(shù)目為：30

第二層B+樹(shù)存放的索引項(xiàng)數(shù)目為：900

第三層B+樹(shù)存放的索引項(xiàng)數(shù)目為：27930

4 實(shí)驗(yàn)及分析（Experiment and analysis）

在第3節(jié)中，已討論了讀取效率的影響因素，式（1）中T1與文件系統(tǒng)本身有關(guān)，視為定量，為了減少對(duì)T2的影響，在實(shí)驗(yàn)中將文件進(jìn)行連續(xù)的寫(xiě)入以控制T3。因此，通過(guò)測(cè)量TS，便可間接得到目錄組織結(jié)構(gòu)對(duì)T2的影響。

結(jié)合氣象水文應(yīng)用中，常規(guī)觀探測(cè)報(bào)文特點(diǎn)，本文對(duì)小文件在計(jì)算機(jī)中的組織形式對(duì)檢索效率的影響進(jìn)行了實(shí)驗(yàn)。將大量的小文件連續(xù)寫(xiě)入計(jì)算機(jī)，將其組織在不同的目錄結(jié)構(gòu)中，編程實(shí)現(xiàn)了對(duì)每個(gè)文件的遍歷，遍歷完成后自動(dòng)記錄時(shí)間。

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

操作系統(tǒng)：Microsoft Windows Server 2003；計(jì)算機(jī)系統(tǒng)配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統(tǒng)：NTFS；實(shí)驗(yàn)分區(qū)容量：30GB。

三層B+樹(shù)目錄結(jié)構(gòu)可以存放27930個(gè)索引項(xiàng)，滿足一個(gè)超大文件夾下文件數(shù)量的要求。當(dāng)索引項(xiàng)超過(guò)27930時(shí)，會(huì)產(chǎn)生四層B+樹(shù)結(jié)構(gòu)。因此分別設(shè)計(jì)了文件數(shù)為10000和100000的文件檢索實(shí)驗(yàn)，代表了三層與四層B+樹(shù)的結(jié)構(gòu)，也覆蓋了一般大目錄應(yīng)用的條件。

4.2 實(shí)驗(yàn)分析

將1萬(wàn)個(gè)147kB的小文件平均存儲(chǔ)在N個(gè)目錄中，并統(tǒng)計(jì)其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬(wàn)個(gè)文件時(shí)的檢索效率走勢(shì)，統(tǒng)計(jì)其結(jié)果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)目錄數(shù)在[20，50]之間時(shí)，總體檢索時(shí)間處于一個(gè)最小值的區(qū)間，因?yàn)锽+樹(shù)在此區(qū)間內(nèi)目錄結(jié)構(gòu)的查找效率已達(dá)到最優(yōu)，因此要將目錄數(shù)控制在此范圍內(nèi)才能達(dá)到最優(yōu)的檢索效率。

通過(guò)算法人為設(shè)置最大目錄數(shù)，從而改變系統(tǒng)的默認(rèn)。將目錄改進(jìn)后與目錄改進(jìn)前的時(shí)間作對(duì)比，得到圖3和圖4。

將本文的方法與普通方法對(duì)比可得，1萬(wàn)個(gè)文件時(shí)，性能提升了20%，10萬(wàn)個(gè)文件時(shí)，性能提升了71.3%。

綜上所述，改進(jìn)后的目錄在文件讀取上的效率有明顯，特別是在文件數(shù)目較多時(shí)，性能有顯著的提升。

圖3 1萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.3 Delay contrast of 10000 files

圖4 10萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.4 Delay contrast of 100000 files

5 結(jié)論（Conclusion）

本文針對(duì)大量文件訪問(wèn)時(shí)出現(xiàn)的性能下降問(wèn)題，對(duì)常用的文件系統(tǒng)的存儲(chǔ)方法進(jìn)行研究，發(fā)現(xiàn)不論是集中式存儲(chǔ)還是分布式存儲(chǔ)，最終的讀取效率與本地?cái)?shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)有很大關(guān)系。在基于文件名檢索的文件系統(tǒng)中，文件數(shù)相對(duì)于文件大小，對(duì)于系統(tǒng)的訪問(wèn)效率影響更大。因?yàn)?，其名字空間的管理隨文件數(shù)量的變化形成數(shù)據(jù)結(jié)構(gòu)上的量變到質(zhì)變，這種變化使得不同操作系統(tǒng)隱含了最佳的目錄數(shù)和單個(gè)目錄下存放的文件數(shù)。據(jù)此，以最常用的NTFS文件為對(duì)象，通過(guò)實(shí)驗(yàn)，定量分析了不同數(shù)量目錄和文件的讀取效率和變化趨勢(shì)，得出了一種簡(jiǎn)單易行的優(yōu)化方法，有效改善了海量文件存儲(chǔ)訪問(wèn)的響應(yīng)時(shí)間，特別是存在大量小文件的情形。研究結(jié)果對(duì)于提高某些應(yīng)用系統(tǒng)性能，特別是自動(dòng)文件保存和緩沖，如氣象水文觀探測(cè)報(bào)文的接收處理和批量數(shù)據(jù)交換等，有重要的工程指導(dǎo)意義。下一步將結(jié)合具體應(yīng)用案例，將本文提出的優(yōu)化存儲(chǔ)方法在不同文件系統(tǒng)中進(jìn)行檢驗(yàn)，并與分布式環(huán)境下的負(fù)載均衡和備份服務(wù)相結(jié)合。

參考文獻(xiàn)（References）

[1] 尤晉元，史美林.Windows操作系統(tǒng)原理[M].北京：機(jī)械工業(yè)

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲(chǔ)和讀取的方

法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優(yōu)化的小文件存儲(chǔ)訪問(wèn)策略的研究[J].

計(jì)算機(jī)研究與發(fā)展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹(shù)大目錄結(jié)構(gòu)動(dòng)態(tài)解析[J].計(jì)算機(jī)工程

與設(shè)計(jì)，2013，34（4）：1376-1382.

作者簡(jiǎn)介：

吳 陽(yáng)（1989-），男，碩士，學(xué)生.研究領(lǐng)域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領(lǐng)域：系統(tǒng)集成與應(yīng)用.endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設(shè)文件系統(tǒng)定位時(shí)間為T(mén)1，與文件系統(tǒng)本身有關(guān)；遍歷B+樹(shù)時(shí)間為T(mén)2，與B+樹(shù)的結(jié)構(gòu)有關(guān)；磁盤(pán)的控制及訪問(wèn)時(shí)間為T(mén)3，與計(jì)算機(jī)的硬件性能有關(guān)。一個(gè)文件的讀取時(shí)間為T(mén)S，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優(yōu)化方法

在文件系統(tǒng)與計(jì)算機(jī)硬件條件固定的情況下，B+樹(shù)的結(jié)構(gòu)對(duì)文件的存取效率影響至關(guān)重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關(guān)鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個(gè)文件的MFT記錄大小為1kB，當(dāng)父目錄下的文件不斷增加而生成新的索引項(xiàng)，父目錄MFT記錄沒(méi)有足夠的空間存放時(shí)，會(huì)按照B+樹(shù)的節(jié)點(diǎn)分裂規(guī)則進(jìn)行分裂，產(chǎn)生了兩層的B+目錄結(jié)構(gòu)。當(dāng)文件夾下的文件數(shù)量一直增加到一個(gè)臨界點(diǎn)，兩層的B+樹(shù)目錄不足以存放所有的索引項(xiàng)時(shí)，B+樹(shù)第二層的一些節(jié)點(diǎn)會(huì)根據(jù)B+樹(shù)的分裂規(guī)則分離出葉子節(jié)點(diǎn)，自身變成非葉子節(jié)點(diǎn)，此時(shí)變成了三層B+樹(shù)結(jié)構(gòu)[5]。

樹(shù)的深度對(duì)檢索的效率有著極為關(guān)鍵的影響，理論上，B+樹(shù)的層數(shù)越大，檢索文件的所需的遍歷時(shí)間將越長(zhǎng)，但定量的分析未見(jiàn)文件報(bào)道。不同的文件數(shù)量下系統(tǒng)中目錄會(huì)產(chǎn)生不同的樹(shù)結(jié)構(gòu)，從而對(duì)對(duì)文件的檢索效率產(chǎn)生影響：

第一層B+樹(shù)存放的索引項(xiàng)數(shù)目為：30

第二層B+樹(shù)存放的索引項(xiàng)數(shù)目為：900

第三層B+樹(shù)存放的索引項(xiàng)數(shù)目為：27930

4 實(shí)驗(yàn)及分析（Experiment and analysis）

在第3節(jié)中，已討論了讀取效率的影響因素，式（1）中T1與文件系統(tǒng)本身有關(guān)，視為定量，為了減少對(duì)T2的影響，在實(shí)驗(yàn)中將文件進(jìn)行連續(xù)的寫(xiě)入以控制T3。因此，通過(guò)測(cè)量TS，便可間接得到目錄組織結(jié)構(gòu)對(duì)T2的影響。

結(jié)合氣象水文應(yīng)用中，常規(guī)觀探測(cè)報(bào)文特點(diǎn)，本文對(duì)小文件在計(jì)算機(jī)中的組織形式對(duì)檢索效率的影響進(jìn)行了實(shí)驗(yàn)。將大量的小文件連續(xù)寫(xiě)入計(jì)算機(jī)，將其組織在不同的目錄結(jié)構(gòu)中，編程實(shí)現(xiàn)了對(duì)每個(gè)文件的遍歷，遍歷完成后自動(dòng)記錄時(shí)間。

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

操作系統(tǒng)：Microsoft Windows Server 2003；計(jì)算機(jī)系統(tǒng)配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統(tǒng)：NTFS；實(shí)驗(yàn)分區(qū)容量：30GB。

三層B+樹(shù)目錄結(jié)構(gòu)可以存放27930個(gè)索引項(xiàng)，滿足一個(gè)超大文件夾下文件數(shù)量的要求。當(dāng)索引項(xiàng)超過(guò)27930時(shí)，會(huì)產(chǎn)生四層B+樹(shù)結(jié)構(gòu)。因此分別設(shè)計(jì)了文件數(shù)為10000和100000的文件檢索實(shí)驗(yàn)，代表了三層與四層B+樹(shù)的結(jié)構(gòu)，也覆蓋了一般大目錄應(yīng)用的條件。

4.2 實(shí)驗(yàn)分析

將1萬(wàn)個(gè)147kB的小文件平均存儲(chǔ)在N個(gè)目錄中，并統(tǒng)計(jì)其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬(wàn)個(gè)文件時(shí)的檢索效率走勢(shì)，統(tǒng)計(jì)其結(jié)果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)目錄數(shù)在[20，50]之間時(shí)，總體檢索時(shí)間處于一個(gè)最小值的區(qū)間，因?yàn)锽+樹(shù)在此區(qū)間內(nèi)目錄結(jié)構(gòu)的查找效率已達(dá)到最優(yōu)，因此要將目錄數(shù)控制在此范圍內(nèi)才能達(dá)到最優(yōu)的檢索效率。

通過(guò)算法人為設(shè)置最大目錄數(shù)，從而改變系統(tǒng)的默認(rèn)。將目錄改進(jìn)后與目錄改進(jìn)前的時(shí)間作對(duì)比，得到圖3和圖4。

將本文的方法與普通方法對(duì)比可得，1萬(wàn)個(gè)文件時(shí)，性能提升了20%，10萬(wàn)個(gè)文件時(shí)，性能提升了71.3%。

綜上所述，改進(jìn)后的目錄在文件讀取上的效率有明顯，特別是在文件數(shù)目較多時(shí)，性能有顯著的提升。

圖3 1萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.3 Delay contrast of 10000 files

圖4 10萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.4 Delay contrast of 100000 files

5 結(jié)論（Conclusion）

本文針對(duì)大量文件訪問(wèn)時(shí)出現(xiàn)的性能下降問(wèn)題，對(duì)常用的文件系統(tǒng)的存儲(chǔ)方法進(jìn)行研究，發(fā)現(xiàn)不論是集中式存儲(chǔ)還是分布式存儲(chǔ)，最終的讀取效率與本地?cái)?shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)有很大關(guān)系。在基于文件名檢索的文件系統(tǒng)中，文件數(shù)相對(duì)于文件大小，對(duì)于系統(tǒng)的訪問(wèn)效率影響更大。因?yàn)?，其名字空間的管理隨文件數(shù)量的變化形成數(shù)據(jù)結(jié)構(gòu)上的量變到質(zhì)變，這種變化使得不同操作系統(tǒng)隱含了最佳的目錄數(shù)和單個(gè)目錄下存放的文件數(shù)。據(jù)此，以最常用的NTFS文件為對(duì)象，通過(guò)實(shí)驗(yàn)，定量分析了不同數(shù)量目錄和文件的讀取效率和變化趨勢(shì)，得出了一種簡(jiǎn)單易行的優(yōu)化方法，有效改善了海量文件存儲(chǔ)訪問(wèn)的響應(yīng)時(shí)間，特別是存在大量小文件的情形。研究結(jié)果對(duì)于提高某些應(yīng)用系統(tǒng)性能，特別是自動(dòng)文件保存和緩沖，如氣象水文觀探測(cè)報(bào)文的接收處理和批量數(shù)據(jù)交換等，有重要的工程指導(dǎo)意義。下一步將結(jié)合具體應(yīng)用案例，將本文提出的優(yōu)化存儲(chǔ)方法在不同文件系統(tǒng)中進(jìn)行檢驗(yàn)，并與分布式環(huán)境下的負(fù)載均衡和備份服務(wù)相結(jié)合。

參考文獻(xiàn)（References）

[1] 尤晉元，史美林.Windows操作系統(tǒng)原理[M].北京：機(jī)械工業(yè)

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲(chǔ)和讀取的方

法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優(yōu)化的小文件存儲(chǔ)訪問(wèn)策略的研究[J].

計(jì)算機(jī)研究與發(fā)展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹(shù)大目錄結(jié)構(gòu)動(dòng)態(tài)解析[J].計(jì)算機(jī)工程

與設(shè)計(jì)，2013，34（4）：1376-1382.

作者簡(jiǎn)介：

吳 陽(yáng)（1989-），男，碩士，學(xué)生.研究領(lǐng)域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領(lǐng)域：系統(tǒng)集成與應(yīng)用.endprint

圖1 NTFS的文件定位步驟

Fig.1 NTFS file access process

設(shè)文件系統(tǒng)定位時(shí)間為T(mén)1，與文件系統(tǒng)本身有關(guān)；遍歷B+樹(shù)時(shí)間為T(mén)2，與B+樹(shù)的結(jié)構(gòu)有關(guān)；磁盤(pán)的控制及訪問(wèn)時(shí)間為T(mén)3，與計(jì)算機(jī)的硬件性能有關(guān)。一個(gè)文件的讀取時(shí)間為T(mén)S，則

TS= T1+ T2+T3 （1）

3.2 讀取效率優(yōu)化方法

在文件系統(tǒng)與計(jì)算機(jī)硬件條件固定的情況下，B+樹(shù)的結(jié)構(gòu)對(duì)文件的存取效率影響至關(guān)重要。因此，如何減少公式（1）中T2是提高文件檢索效率的關(guān)鍵。

以NTFS為例，目錄中，文件索引放在父目錄的MFT記錄的0X90屬性中。一個(gè)文件的MFT記錄大小為1kB，當(dāng)父目錄下的文件不斷增加而生成新的索引項(xiàng)，父目錄MFT記錄沒(méi)有足夠的空間存放時(shí)，會(huì)按照B+樹(shù)的節(jié)點(diǎn)分裂規(guī)則進(jìn)行分裂，產(chǎn)生了兩層的B+目錄結(jié)構(gòu)。當(dāng)文件夾下的文件數(shù)量一直增加到一個(gè)臨界點(diǎn)，兩層的B+樹(shù)目錄不足以存放所有的索引項(xiàng)時(shí)，B+樹(shù)第二層的一些節(jié)點(diǎn)會(huì)根據(jù)B+樹(shù)的分裂規(guī)則分離出葉子節(jié)點(diǎn)，自身變成非葉子節(jié)點(diǎn)，此時(shí)變成了三層B+樹(shù)結(jié)構(gòu)[5]。

樹(shù)的深度對(duì)檢索的效率有著極為關(guān)鍵的影響，理論上，B+樹(shù)的層數(shù)越大，檢索文件的所需的遍歷時(shí)間將越長(zhǎng)，但定量的分析未見(jiàn)文件報(bào)道。不同的文件數(shù)量下系統(tǒng)中目錄會(huì)產(chǎn)生不同的樹(shù)結(jié)構(gòu)，從而對(duì)對(duì)文件的檢索效率產(chǎn)生影響：

第一層B+樹(shù)存放的索引項(xiàng)數(shù)目為：30

第二層B+樹(shù)存放的索引項(xiàng)數(shù)目為：900

第三層B+樹(shù)存放的索引項(xiàng)數(shù)目為：27930

4 實(shí)驗(yàn)及分析（Experiment and analysis）

在第3節(jié)中，已討論了讀取效率的影響因素，式（1）中T1與文件系統(tǒng)本身有關(guān)，視為定量，為了減少對(duì)T2的影響，在實(shí)驗(yàn)中將文件進(jìn)行連續(xù)的寫(xiě)入以控制T3。因此，通過(guò)測(cè)量TS，便可間接得到目錄組織結(jié)構(gòu)對(duì)T2的影響。

結(jié)合氣象水文應(yīng)用中，常規(guī)觀探測(cè)報(bào)文特點(diǎn)，本文對(duì)小文件在計(jì)算機(jī)中的組織形式對(duì)檢索效率的影響進(jìn)行了實(shí)驗(yàn)。將大量的小文件連續(xù)寫(xiě)入計(jì)算機(jī)，將其組織在不同的目錄結(jié)構(gòu)中，編程實(shí)現(xiàn)了對(duì)每個(gè)文件的遍歷，遍歷完成后自動(dòng)記錄時(shí)間。

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

操作系統(tǒng)：Microsoft Windows Server 2003；計(jì)算機(jī)系統(tǒng)配置：CPU為Intel（R）、Xeon（R）、1.86GHz，RAM為2.00GB；文件系統(tǒng)：NTFS；實(shí)驗(yàn)分區(qū)容量：30GB。

三層B+樹(shù)目錄結(jié)構(gòu)可以存放27930個(gè)索引項(xiàng)，滿足一個(gè)超大文件夾下文件數(shù)量的要求。當(dāng)索引項(xiàng)超過(guò)27930時(shí)，會(huì)產(chǎn)生四層B+樹(shù)結(jié)構(gòu)。因此分別設(shè)計(jì)了文件數(shù)為10000和100000的文件檢索實(shí)驗(yàn)，代表了三層與四層B+樹(shù)的結(jié)構(gòu)，也覆蓋了一般大目錄應(yīng)用的條件。

4.2 實(shí)驗(yàn)分析

將1萬(wàn)個(gè)147kB的小文件平均存儲(chǔ)在N個(gè)目錄中，并統(tǒng)計(jì)其檢索速度，N的值為5、10、20、50、100、200、500、1000。用同樣的方法，我們還研究了10萬(wàn)個(gè)文件時(shí)的檢索效率走勢(shì)，統(tǒng)計(jì)其結(jié)果如圖2所示。

圖2 文件檢索效率

Fig.2 File retrieval efficiency

分析實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)目錄數(shù)在[20，50]之間時(shí)，總體檢索時(shí)間處于一個(gè)最小值的區(qū)間，因?yàn)锽+樹(shù)在此區(qū)間內(nèi)目錄結(jié)構(gòu)的查找效率已達(dá)到最優(yōu)，因此要將目錄數(shù)控制在此范圍內(nèi)才能達(dá)到最優(yōu)的檢索效率。

通過(guò)算法人為設(shè)置最大目錄數(shù)，從而改變系統(tǒng)的默認(rèn)。將目錄改進(jìn)后與目錄改進(jìn)前的時(shí)間作對(duì)比，得到圖3和圖4。

將本文的方法與普通方法對(duì)比可得，1萬(wàn)個(gè)文件時(shí)，性能提升了20%，10萬(wàn)個(gè)文件時(shí)，性能提升了71.3%。

綜上所述，改進(jìn)后的目錄在文件讀取上的效率有明顯，特別是在文件數(shù)目較多時(shí)，性能有顯著的提升。

圖3 1萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.3 Delay contrast of 10000 files

圖4 10萬(wàn)個(gè)文件的檢索時(shí)延對(duì)比

Fig.4 Delay contrast of 100000 files

5 結(jié)論（Conclusion）

本文針對(duì)大量文件訪問(wèn)時(shí)出現(xiàn)的性能下降問(wèn)題，對(duì)常用的文件系統(tǒng)的存儲(chǔ)方法進(jìn)行研究，發(fā)現(xiàn)不論是集中式存儲(chǔ)還是分布式存儲(chǔ)，最終的讀取效率與本地?cái)?shù)據(jù)文件的存儲(chǔ)結(jié)構(gòu)有很大關(guān)系。在基于文件名檢索的文件系統(tǒng)中，文件數(shù)相對(duì)于文件大小，對(duì)于系統(tǒng)的訪問(wèn)效率影響更大。因?yàn)椋涿挚臻g的管理隨文件數(shù)量的變化形成數(shù)據(jù)結(jié)構(gòu)上的量變到質(zhì)變，這種變化使得不同操作系統(tǒng)隱含了最佳的目錄數(shù)和單個(gè)目錄下存放的文件數(shù)。據(jù)此，以最常用的NTFS文件為對(duì)象，通過(guò)實(shí)驗(yàn)，定量分析了不同數(shù)量目錄和文件的讀取效率和變化趨勢(shì)，得出了一種簡(jiǎn)單易行的優(yōu)化方法，有效改善了海量文件存儲(chǔ)訪問(wèn)的響應(yīng)時(shí)間，特別是存在大量小文件的情形。研究結(jié)果對(duì)于提高某些應(yīng)用系統(tǒng)性能，特別是自動(dòng)文件保存和緩沖，如氣象水文觀探測(cè)報(bào)文的接收處理和批量數(shù)據(jù)交換等，有重要的工程指導(dǎo)意義。下一步將結(jié)合具體應(yīng)用案例，將本文提出的優(yōu)化存儲(chǔ)方法在不同文件系統(tǒng)中進(jìn)行檢驗(yàn)，并與分布式環(huán)境下的負(fù)載均衡和備份服務(wù)相結(jié)合。

參考文獻(xiàn)（References）

[1] 尤晉元，史美林.Windows操作系統(tǒng)原理[M].北京：機(jī)械工業(yè)

出版社，2001.

[2] 張春明，芮建武，何婷婷.一種Hadoop小文件存儲(chǔ)和讀取的方

法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（11）：95-100.

[3] 趙躍龍，等.一種性能優(yōu)化的小文件存儲(chǔ)訪問(wèn)策略的研究[J].

計(jì)算機(jī)研究與發(fā)展，2012，49（7）：1579-1586.

[4] Bo Dong，etc.A Novel Approach to Improving the Efficiency

of Storing and Accessing Small Files on Hadoop：a Case Study by

PowerPoint Files. 2010 IEEE International Conference on

Services Computing[R].

[5] 吳偉民，等.NTFS B+樹(shù)大目錄結(jié)構(gòu)動(dòng)態(tài)解析[J].計(jì)算機(jī)工程

與設(shè)計(jì)，2013，34（4）：1376-1382.

作者簡(jiǎn)介：

吳 陽(yáng)（1989-），男，碩士，學(xué)生.研究領(lǐng)域：信息與通信工程.

馮 徑（1952-），女，博士，教授.研究領(lǐng)域：系統(tǒng)集成與應(yīng)用.endprint