馬東，邵維專

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

0 引言

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

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

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

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

1 背景與問題分析

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

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

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

2 基于修改頻率的目錄分級存儲算法

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

2.1 冷熱目錄劃分

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

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

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

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

（2）熱度衰減算法

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

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

表1 熱度衰減策略分類表

2.2 目錄壓縮

（1）節(jié)點替換

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

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

（2）子樹序列化

考慮到NameNode元數(shù)據(jù)的組織形式，本文將目錄和該目錄下文件和子目錄的關(guān)系抽離單獨保存，使用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ù)存儲策略

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

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

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

2.4 目錄遍歷算法

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

圖2 目錄遍歷算法

2.5 子樹的合并策略

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

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

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

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

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

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

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

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

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

子樹合并策略如下：

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

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

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

3 結(jié)果與分析

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

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

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

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

4 結(jié)語

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

[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é)報,2016,27(12):3192-3207.

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

[5]陳濤,肖儂,劉芳.對象存儲系統(tǒng)中自適應(yīng)的元數(shù)據(jù)負(fù)載均衡機(jī)制[J].軟件學(xué)報,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的分級存儲功能設(shè)計與實現(xiàn)[D].華中科技大學(xué),2016.