馬東，邵維專

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，傳統(tǒng)的文件系統(tǒng)已經(jīng)無(wú)法應(yīng)對(duì)新時(shí)代下的大數(shù)據(jù)存儲(chǔ)的挑戰(zhàn)，分布式文件系統(tǒng)以其高可靠性、高性能以及強(qiáng)大的可擴(kuò)展性逐漸得到廣泛的使用。在主流的分布式文件系統(tǒng)中，大都采用元數(shù)據(jù)和文件數(shù)據(jù)分離的策略，將元數(shù)據(jù)信息存放在單獨(dú)的服務(wù)器上，元數(shù)據(jù)服務(wù)器作為整個(gè)分布式文件系統(tǒng)的管理節(jié)點(diǎn)，為應(yīng)用提供文件系統(tǒng)目錄視圖和數(shù)據(jù)定位服務(wù)。

作為大數(shù)據(jù)平臺(tái)Hadoop的存儲(chǔ)核心，HDFS以其良好的設(shè)計(jì)和性能逐漸成為大數(shù)據(jù)處理方向的一個(gè)標(biāo)準(zhǔn)，Hadoop2.0引入主備模式，使用StandBy NameNode作為Active NameNode的熱備節(jié)點(diǎn)，由于整個(gè)文件系統(tǒng)的元數(shù)據(jù)全部存放在NameNode的內(nèi)存中，當(dāng)使用主備模式對(duì)NameNode進(jìn)行同步備份時(shí)備份服務(wù)器需要與主NameNode同等配置，但是備份服務(wù)器并不對(duì)外提供讀寫服務(wù)，只是將同步應(yīng)用Active NameNode的日志信息,文獻(xiàn)表明，在一個(gè)常規(guī)的HDFS分布式文件系統(tǒng)中，元數(shù)據(jù)寫操作僅占據(jù)所有元數(shù)據(jù)操作的5%左右，因此本文提出了一個(gè)StandBy NameNode元數(shù)據(jù)分級(jí)存儲(chǔ)策略，將寫操作較少的目錄的元數(shù)據(jù)信息序列

HDFS由元數(shù)據(jù)管理節(jié)點(diǎn)NameNode和數(shù)據(jù)節(jié)點(diǎn)DataNode組成，NameNode負(fù)責(zé)管理整個(gè)分布式文件系統(tǒng)的元數(shù)據(jù)信息，包括目錄樹以及各個(gè)數(shù)據(jù)塊對(duì)應(yīng)的存儲(chǔ)信息，所有的存儲(chǔ)數(shù)據(jù)分散到DataNode上，當(dāng)需要訪問文件時(shí)，應(yīng)用首先需要訪問NameNode獲得文件的存儲(chǔ)信息，再訪問DataNode獲取文件數(shù)據(jù)。

我們把NameNode管理的文件系統(tǒng)目錄樹稱之為第一關(guān)系鏈，將NameNode中數(shù)據(jù)塊與對(duì)應(yīng)的DataNode的關(guān)系稱之為第二關(guān)系鏈，HDFS使用FsIm?age以及EditLog文件中保存第一關(guān)系鏈的數(shù)據(jù)信息，第二關(guān)系鏈的建立依賴于NameNode啟動(dòng)時(shí)由各個(gè)DataNode節(jié)點(diǎn)匯報(bào)得到。在一個(gè)小型的HDFS文件系統(tǒng)中，有10M文件，0.3M目錄以及13M數(shù)據(jù)塊，元數(shù)據(jù)占用了約9G內(nèi)存?；酱疟P，這樣在保持主備完全同步的情況下可以極大降低StandBy NameNode內(nèi)存的使用率。

1 背景與問題分析

1.1 HDFS 元數(shù)據(jù)管理策略

1.2 元數(shù)據(jù)訪問特性

現(xiàn)有的分布式文件系統(tǒng)往往采用元數(shù)據(jù)和數(shù)據(jù)的分離存儲(chǔ)，元數(shù)據(jù)訪問與典型的數(shù)據(jù)訪問不同，元數(shù)據(jù)往往較小，因此通常使用將元數(shù)據(jù)存放在內(nèi)存中。大量研究表明，當(dāng)數(shù)據(jù)剛被存放到存儲(chǔ)系統(tǒng)中時(shí)，對(duì)數(shù)據(jù)的修改和訪問會(huì)十分頻繁，但是隨著時(shí)間的推移，這些數(shù)據(jù)的訪問頻率會(huì)越來(lái)越低，甚至不再被訪問，這些數(shù)據(jù)往往占總數(shù)據(jù)量的80%以上。文獻(xiàn)[1]指出文件系統(tǒng)的變化具有顯著的空間局部性，在其對(duì)兩個(gè)企業(yè)級(jí)網(wǎng)絡(luò)文件服務(wù)器三個(gè)月的日志分析顯示，超過92%的元數(shù)據(jù)變化簇集在低于10%的目錄中;文獻(xiàn)[2]統(tǒng)計(jì)了Spotify的HDFS集群的元數(shù)據(jù)操作，指出在Hadoop典型應(yīng)用產(chǎn)生的負(fù)載中，寫操作約占所有元數(shù)據(jù)操作的5%;基于此，本文提出了一種StandBy NameNode上元數(shù)據(jù)分級(jí)存儲(chǔ)算法。

2 基于修改頻率的目錄分級(jí)存儲(chǔ)算法

NameNode作為HDFS的核心，使用主備模式保證HDFS的高可用，并在主備機(jī)上應(yīng)用相同的日志序列保證Active NameNode和StandBy NameNode的一致性,Active NameNode處理集群的讀寫請(qǐng)求，StandBy Na?meNode同步應(yīng)用寫操作的日志，考慮到大數(shù)據(jù)應(yīng)用的特點(diǎn)和元數(shù)據(jù)變化的局部性，僅在StandBy NameNode內(nèi)存中存放修改熱度較高的目錄，將熱度較低的目錄序列化后存儲(chǔ)在本地。

2.1 冷熱目錄劃分

本文在HDFS的INodeDirectory結(jié)構(gòu)中添加了int editIndicator作為目錄修改熱度值，考慮到文件系統(tǒng)目錄的修改特征，建立了一個(gè)層級(jí)的衰減模型。本文定義editIndicator的第0~1bit存儲(chǔ)熱度衰減標(biāo)識(shí)，使用第2~31位記錄當(dāng)前目錄的熱度值，將第2位作為該目錄的w位，同樣，衰減標(biāo)識(shí)為01，10，11的w位分別為ed?itIndicator的第 23，15，7位，當(dāng)目錄被修改時(shí)，會(huì)將路徑上目錄對(duì)應(yīng)的w位置1。

圖1 熱度字段存儲(chǔ)結(jié)構(gòu)

（1）衰減標(biāo)識(shí)

目錄的熱度衰減分為四個(gè)級(jí)別，當(dāng)目錄被創(chuàng)建時(shí)，級(jí)別設(shè)置為0，即衰減標(biāo)識(shí)置為00，并設(shè)置當(dāng)前級(jí)別的W位為1，當(dāng)目錄被壓縮線程訪問時(shí)，會(huì)根據(jù)當(dāng)前的衰減標(biāo)識(shí)適用對(duì)應(yīng)的衰減算法并降低當(dāng)前的目錄熱度，熱度低于閾值后序列化和存儲(chǔ)該目錄。在需要加載目錄樹時(shí)，提升INodeLinked節(jié)點(diǎn)到被修改目錄路徑上目錄的熱度衰減級(jí)別。

（2）熱度衰減算法

老化算法：當(dāng)壓縮線程訪問該目錄時(shí)，將該目錄的熱度衰減一半。

遞減算法：當(dāng)壓縮線程訪問該目錄時(shí)，將該目錄的熱度降低1。

表1 熱度衰減策略分類表

2.2 目錄壓縮

（1）節(jié)點(diǎn)替換

當(dāng)存在子樹的熱度過低時(shí)，使用INodeLinked節(jié)點(diǎn)替換該子樹根節(jié)點(diǎn)，然后將子樹序列化，INodeLinked保存了該子樹的序列化信息，其結(jié)構(gòu)定義如下:

其中filePath為保存該子樹信息的文件存儲(chǔ)路徑。

（2）子樹序列化

考慮到NameNode元數(shù)據(jù)的組織形式，本文將目錄和該目錄下文件和子目錄的關(guān)系抽離單獨(dú)保存，使用DirEntry序列化目錄與該目錄下文件和子目錄的映射關(guān)系，其結(jié)構(gòu)如下：

HDFS NameNode使用INodeMap保存所有目錄和文件的元數(shù)據(jù)。HDFS中文件(INodeFile)和目錄（IN?odeDirectory）都是INode的子類，因此定義了INode?Common用以序列化文件和目錄信息。INodeCommon

數(shù)據(jù)結(jié)構(gòu)如下：

2.3 數(shù)據(jù)存儲(chǔ)策略

本文使用INodeLinked保存子樹的序列化信息，然后將子樹元數(shù)據(jù)信息存儲(chǔ)到文件中,文件的結(jié)構(gòu)如表2所示。

表2 文件存儲(chǔ)結(jié)構(gòu)

其中，treeId為子樹Id，INodeMapSection存放所有的INode信息，DirEntrySection存放所有的DirEntry信息，在序列化子樹或目錄時(shí)采用預(yù)分配空間的方法，每個(gè)文件預(yù)分配256KB大小，其中16KB作為DirEntry?Section,，其余空間作為INodeMapSection，為防止過多的文件創(chuàng)建，使FILE_MIN_INODE_COUNT限制每個(gè)文件最少需要保存的INode個(gè)數(shù)。當(dāng)需要從文件加載子樹時(shí)，首先加載INodeMapSection，將其INode放入InodeMap中，然后加載DirEntrySection重建目錄子樹。

2.4 目錄遍歷算法

每隔時(shí)間T或者內(nèi)存使用量達(dá)到一定閾值時(shí)啟動(dòng)壓縮線程遍歷目錄樹，將熱度較低的目錄序列化存儲(chǔ)到本地，算法流程如圖2所示。

圖2 目錄遍歷算法

2.5 子樹的合并策略

定義1兄弟節(jié)點(diǎn):目錄或子樹根節(jié)點(diǎn)所在的父目錄包含的其他子目錄稱為該目錄的兄弟節(jié)點(diǎn)。

定義2可序列化:當(dāng)一個(gè)子樹或目錄的熱度低于某一設(shè)定的閾值，則稱該子樹或目錄是可序列化的。

定義3可合并的：如果一個(gè)INodeLinked節(jié)點(diǎn)的剩余空間可以存放可序列化的兄弟節(jié)點(diǎn)或父節(jié)點(diǎn)的信息，則稱該INodeLinked節(jié)點(diǎn)是可合并的。

定義4最小序列化條件:當(dāng)需要序列化的目錄或子樹的INode數(shù)量大于FILE_MIN_INODE_COUNT，則稱該子樹或目錄滿足最小序列化條件。

定義5孤立節(jié)點(diǎn)：若一個(gè)子樹或目錄滿足最小序列化條件，且父目錄是非可序列化的以及不存在可序列化的兄弟節(jié)點(diǎn)或者可合并的INodeLinked兄弟節(jié)點(diǎn)，則稱之為孤立節(jié)點(diǎn)。

定義6不可約減節(jié)點(diǎn)：如果某一個(gè)可序列化目錄或子樹包含的所有INodeLinked節(jié)點(diǎn)均滿足1）存在兄弟節(jié)點(diǎn)，該節(jié)點(diǎn)與兄弟節(jié)點(diǎn)是不可合并的，2）不存在兄弟節(jié)點(diǎn)，該節(jié)點(diǎn)與父目錄時(shí)不可合并的，則稱該目錄或子樹時(shí)不可約減節(jié)點(diǎn)。

若當(dāng)前目錄或子樹是孤立節(jié)點(diǎn)，根據(jù)其INode個(gè)數(shù)分配存儲(chǔ)空間，空間分配策略如下：

（1）若當(dāng)前子樹INode個(gè)數(shù)count小于1024，則分配256KB空間，DirEntrySection占用16KB

（2）若當(dāng)前子樹INode個(gè)數(shù)count大于1024,則分配((count-1)/1024+1)*256K空間，DirEntrySection占用((count-1）/1024+1）*16K

子樹合并策略如下：

（1）對(duì)cdl隊(duì)列中的目錄進(jìn)行約減：若該目錄子樹存在INodeLinked節(jié)點(diǎn)，則INodeLinked節(jié)點(diǎn)合并其兄弟節(jié)點(diǎn)以及父節(jié)點(diǎn)，直至該目錄子樹成為不可約減節(jié)點(diǎn)或INodeLinked節(jié)點(diǎn)，若該節(jié)點(diǎn)約減后成為IN?odeLinked節(jié)點(diǎn)，則將其加入existLinked隊(duì)列。

（2）將existLinked中節(jié)點(diǎn)與cdl隊(duì)列中的約減后的目錄進(jìn)行合并，直至cdl中沒有可以并入existLinked的目錄。

（3）將cdl剩余的目錄子樹合并作為孤立節(jié)點(diǎn)，按照空間分配策略分配存儲(chǔ)空間。

3 結(jié)果與分析

本文使用三臺(tái)虛擬機(jī)搭建了測(cè)試集群，其中兩臺(tái)作為Active NameNode和StandBy NameNode，配置為1核CPU，2G內(nèi)存，20G硬盤,三臺(tái)虛擬機(jī)均配置為Jour?nalNode和DataNode，NameNode中JVM內(nèi)存配置為-Xms256M-Xmx1024M，使用測(cè)試程序隨機(jī)創(chuàng)建了約400萬(wàn)空文件，并隨機(jī)標(biāo)記約20%的目錄為熱點(diǎn)目錄，本文設(shè)定 FILE_MIN_INODE_COUNT為 20，同時(shí)在

參考文獻(xiàn)：StandBy NameNode啟動(dòng)壓縮線程。

由圖3可以看出，在啟動(dòng)壓縮線程之后，StandBy NameNode的堆內(nèi)存使用明顯降低。

圖3 主備NameNode堆內(nèi)存使用

4 結(jié)語(yǔ)

本文針對(duì)StandBy NameNode內(nèi)存占用高但是活躍元數(shù)據(jù)比例很低的問題，研究了HDFS元數(shù)據(jù)管理策略，提出了一種分級(jí)熱度衰減策略，實(shí)現(xiàn)了StandBy NameNode元數(shù)據(jù)的分級(jí)存儲(chǔ)算法，將StandBy Na?meNode的非活躍元數(shù)據(jù)壓縮存儲(chǔ)到本地，大大降低了其內(nèi)存使用，同時(shí)使用初步的實(shí)驗(yàn)驗(yàn)證了算法的有效性。

[1]劉立坤.海量文件系統(tǒng)元數(shù)據(jù)查詢方法與技術(shù)[D].清華大學(xué),2011.

[2]Niazi S,Ismail M,Grohsschmiedt S,et al.HopsFS:Scaling Hierarchical File System Metadata Using NewSQL Databases[J]，2017.

[3]孫耀,劉杰,葉丹,等.分布式文件系統(tǒng)元數(shù)據(jù)服務(wù)的負(fù)載均衡框架[J].軟件學(xué)報(bào),2016,27(12):3192-3207.

[4]李靜.基于訪問熱度分類的元數(shù)據(jù)副本技術(shù)研究[D].華中科技大學(xué),2016.

[5]陳濤,肖儂,劉芳.對(duì)象存儲(chǔ)系統(tǒng)中自適應(yīng)的元數(shù)據(jù)負(fù)載均衡機(jī)制[J].軟件學(xué)報(bào),2013(2):331-342.

[6]Haohui Mai,Scaling Out the Namespace Using KV Store.https://issues.apache.org/jira/browse/HDFS-8286.

[7]曾衛(wèi)進(jìn).基于HDFS的分級(jí)存儲(chǔ)功能設(shè)計(jì)與實(shí)現(xiàn)[D].華中科技大學(xué),2016.