謝 磊 吳建華 廖卓凡 羅 可

(長沙理工大學計算機與通信工程學院 湖南 長沙 410004)

0 引 言

Hadoop[1-2]是一種對分析大數(shù)據(jù)的MapReduce模型的實現(xiàn)框架，憑借其開源、高效、高擴展性、低成本、高可靠的特性在互聯(lián)網(wǎng)領域得到了廣泛的利用。受Google文件系統(tǒng)啟發(fā)而形成的Hadoop分布式文件系統(tǒng)HDFS[3]是Hadoop 底層基礎框架的存儲部分，由一個管理文件系統(tǒng)命名空間的命名節(jié)點(NameNode)和若干個數(shù)據(jù)節(jié)點(DataNode)組成。在這種主從結構分布式文件系統(tǒng)中，命名節(jié)點作為主節(jié)點負責管理整個文件系統(tǒng)的目錄樹，并在集群中提供集中式服務，而數(shù)據(jù)節(jié)點作為從節(jié)點負責數(shù)據(jù)的存儲，配合名字節(jié)點工作。

HDFS從啟動到正常運行期間，命名節(jié)點需要處理客戶端、數(shù)據(jù)節(jié)點、第二命名節(jié)點的大量請求，創(chuàng)建并維護文件系統(tǒng)目錄樹。現(xiàn)階段的HDFS只有單一的命名節(jié)點，而隨著HDFS數(shù)據(jù)量不斷增長，HDFS中數(shù)據(jù)節(jié)點不斷增多，命名節(jié)點的性能將是整個HDFS的瓶頸。因此，需要降低NameNode的負載。

1 相關工作

解決HDFS命名節(jié)點性能問題的主要方法分為兩種，一種是增加命名節(jié)點的數(shù)量，另一種是在數(shù)據(jù)節(jié)點建立緩存，減少數(shù)據(jù)節(jié)點與命名節(jié)點交互次數(shù)和訪問磁盤次數(shù)。

饒磊等[7]利用一個superNameNode節(jié)點和多個NameNode節(jié)點組成一個小型的分布式NameNode系統(tǒng)作為HDFS的主節(jié)點，superNamenode節(jié)點負責管理所有 NameNode節(jié)點，監(jiān)控所有Namenode狀態(tài)并作出處理。李寬[8]利用多個NameNode并在這多個Namenode中選取一個Leader節(jié)點和一個SecondaryLeader節(jié)點組成一個NameNode集群作為整個HDFS的主節(jié)點。其中Leader節(jié)點根據(jù)選舉制、終生制、世襲制原則從NameNode中選舉出來。集群中的所有NameNode節(jié)點都是對等的，它們一起為HDFS提供服務。Leader節(jié)點負責監(jiān)控NameNode集群的工作狀態(tài)、處理集群中的節(jié)點故障。HDFS的HDFS Federation[9]使用多個相互獨立的NameNode節(jié)點使得命名服務水平拓展。在HDFS Federation中的NameNode之間是聯(lián)盟關系，它們之間相互獨立且不需要相互協(xié)調(diào)。趙婧等[10]等提出了一種在HDFS數(shù)據(jù)節(jié)點上增加本地緩存的解決方案，實現(xiàn)了HDFS數(shù)據(jù)節(jié)點的本地緩存。

增加命名節(jié)點的數(shù)量需要通過某種選舉機制選舉一個主命名節(jié)點，并建立命名節(jié)點群，這將使整個HDFS系統(tǒng)復雜化，并影響系統(tǒng)的穩(wěn)定性。而在數(shù)據(jù)節(jié)點建立緩存不能從根本上降低NameNode負載。

本文針對該現(xiàn)象提出一種利用LRFU[4-5]緩存替換算法在 HDFS 客戶端建立本地緩存[6]的解決方案。當用戶請求文件時，如果HDFS客戶端已緩存該文件的元數(shù)據(jù)，則不必請求NameNode，直接從緩存中讀取。由于客戶端實現(xiàn)了NameNode部分功能，所以從功能上講，每個HDFS客戶端也是一個NameNode。

2 HDFS客戶端本地緩存解決方案架構

HDFS客戶端本地緩存解決方案主要由緩存模塊、離線日志分析模塊、定時器三部分組成。如圖1所示。

圖1 HDFS客戶端緩存架構

緩存模塊是本方案的主要模塊，離線日志分析模塊和定時器服務于緩存模塊。緩存模塊負責緩存的建立、緩存更新、緩存命中等。離線日志分析使用Hadoop中的MapReduce通過分析歷史文件，更新緩存模塊中部分參數(shù)，達到優(yōu)化緩存模塊的目的。定時器記錄緩存文件緩存時間，當緩存時間達到臨界值時，將其從緩存數(shù)據(jù)結構中刪除，以保證緩存文件的有效性。

3 文件讀取與緩存

3.1 HDFS文件讀取部分源碼分析

文件在數(shù)據(jù)節(jié)點中是以塊(Block)的形式存儲的，一方面簡化了HDFS存儲子系統(tǒng)，使HDFS可以存儲比存儲節(jié)點單一磁盤大的文件。另一方面，使HDFS方便容錯，有利于數(shù)據(jù)復制[11]。命名節(jié)點中維護著HDFS中兩層重要的關系：每個文件對應的數(shù)據(jù)塊及這些數(shù)據(jù)塊對用的數(shù)據(jù)節(jié)點。命名節(jié)點啟動后，讀取命名空間鏡像(FSImage)并加載編輯日志(FSEdit)到內(nèi)存獲得HDFS某時刻的第一層關系。啟動數(shù)據(jù)節(jié)點時，數(shù)據(jù)節(jié)點需要和命名節(jié)點握手、注冊、上報管理的數(shù)據(jù)塊信息以建立HDFS中的第二層關系。啟動之后，數(shù)據(jù)節(jié)點不斷地向命名節(jié)點發(fā)送心跳(Heartbeat)，維護這層關系，向命名節(jié)點上報塊信息并獲取指令。

HDFS向用戶應用提供如Java API、類Shell命令等多種接口，這樣用戶就可以像操作本地文件系統(tǒng)一樣操作HDFS。當用戶需要讀取HDFS文件時，會在HDFS客戶端(DFSClient)調(diào)用open()方法打開要讀取的文件，該方法返回一個DFSInputStream對象，然后就可以通過這個對象的read()方法讀取HDFS文件。DFSInputStream類的構造方法最終會調(diào)用NameNode的遠程方法getBlockLocations()向命名節(jié)點請求文件的數(shù)據(jù)塊信息，命名節(jié)點返回文件從指定位置起配置項{dfs.read.prefecth.size}個數(shù)據(jù)塊信息，客戶端將此信息保存在變量locatedBlocks中。在DFSInputStream類中，用pos成員變量保存“下一個”要數(shù)據(jù)字節(jié)在文件中的位置以支持HDFS文件隨機讀。當用DFSInputStream對象的read()方法讀取文件的時候，首先會調(diào)用blockSeekTo()方法查找pos所指文件位置所在的數(shù)據(jù)塊，如果pos所指的數(shù)據(jù)塊的信息在變量locatedBlocks中，則在本地讀取。反之，則需要再次調(diào)用NameNode遠程方法getBlockLocations()向命名節(jié)點請求數(shù)據(jù)塊信息，并將此數(shù)據(jù)塊信息插入到locatedBlocks變量中。當客戶端獲取到數(shù)據(jù)塊信息后，讀取此信息，請求數(shù)據(jù)節(jié)點，讀取數(shù)據(jù)塊。每次從數(shù)據(jù)節(jié)點讀取輸入緩沖區(qū)大小數(shù)據(jù)，并更新pos的值，根據(jù)pos的值判斷是否需要請求其他數(shù)據(jù)節(jié)點和調(diào)用遠程NameNode方法getBlockLocations()獲得其他數(shù)據(jù)塊信息。輸入緩沖區(qū)大小的值由配置項由{io.file.buffer.size}決定。這樣，當HDFS文件讀取完畢后，pos指向文件的末尾，locatedBlocks變量中保存了文件所有數(shù)據(jù)塊的信息。

本文利用此特點，在HDFS讀取文件后，如果locatedBlocks變量中保存了文件完整的數(shù)據(jù)塊信息，則將此信息緩存在HDFS客戶端。當客戶端下次需要訪問此文件時，不必從命名節(jié)點那里請求數(shù)據(jù)塊信息，而直接從本地讀取。不僅降低了命名節(jié)點的負載，而且提高了文件的訪問效率。

3.2 HDFS客戶端建立本地緩存后文件讀取步驟

HDFS客戶端建立緩存后，文件讀取步驟如下：

步驟1HDFS客戶端通過java API 、C、類Shell等接口接收到用戶讀取文件請求。并查看所請求的文件是否已緩存，若已緩存，則向命名節(jié)點取得文件的訪問權。得到文件訪問權后，向命名節(jié)點查詢文件塊信息有無變更。若無變更，則直接將緩存的文件對應的數(shù)據(jù)節(jié)點信息賦值給locatedBlocks變量，進行步驟3。若文件塊信息變更或文件沒有緩存進行步驟2。

步驟2HDFS客戶端向命名節(jié)點獲取文件的訪問權并調(diào)用getBlockLocations()獲得部分文件對應的數(shù)據(jù)節(jié)點信息，更新locatedBlocks變量。

步驟3讀取變量pos當前的值，若pos的值不位于變量locatedBlocks中所有的數(shù)據(jù)塊中時，轉向步驟2。否則，從變量locatedBlocks中選擇合適的數(shù)據(jù)節(jié)點，建立連接，并轉向步驟4。

步驟4從連接的數(shù)據(jù)節(jié)點不斷讀取配置項{io.file.buffer.size}個字節(jié)數(shù)據(jù)到內(nèi)存，并更新pos變量。當變量pos的值超出該節(jié)點所存儲的數(shù)據(jù)塊時，若其值不小于文件的長度時，轉向步驟5，否則轉向步驟3。

步驟5根據(jù)LRUF緩存替換策略，更新緩存模塊。如圖2所示。

圖2 文件讀取流程

3.3 LRUF緩存替換策略

LFU(Least Frequently Used)[12]和LRU(Least Recently Used)[13-14]是兩種最常用的緩存替換策略[15]。LFU是基于“如果一個數(shù)據(jù)在最近一段時間內(nèi)使用次數(shù)很少，那么在將來一段時間內(nèi)被使用的可能性也很小”的思路，而LRU的核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”。在這兩種看起來毫無關聯(lián)的策略之間卻存在著LFU和LRU分別是極端值的緩存替換策略，這就是LRFU(Least Recently/Frequently Used)緩存替換策略。LRFU通過用一個控制參數(shù) 靈活地權衡LFU和LRU在替換策略中的比重。 的變化范圍是0到1。一方面，如果 越接近0，LRFU 緩存替換策略就越靠近LFU緩存替換策略。最終當 等于0時，LRFU 緩存替換策略就是簡單的LFU緩存替換策略。另一方面，如果 越接近1，LRFU 緩存替換策略就越靠近LRU緩存替換策略。最終當 等于1時，LRFU 緩存替換策略就退化到LRU緩存替換策略。文獻[6] 證明了該緩存替換策略的可行性。

在HDFS中，用戶可以根據(jù)分析HDFS歷史文件訪問日志、HDFS特殊應用場景等來確定 的取值。

3.4 HDFS客戶端本地緩存模塊設計

在客戶端緩存模塊中用LocatedBlocksWithCRF類代表HDFS文件。該類的UML類圖如圖3所示。

圖3 LocatedBlocksWithCRF UML類圖

該類主要有三個私有屬性：該文件絕對路徑src,此屬性唯一區(qū)分一個HDFS文件、該文件的數(shù)據(jù)塊信息blks和一個緩存模塊分配給每個文件的值CRF(Combined Recency and Frequency), 緩存模塊用這個值來度量該文件將來被訪問的可能性。另外，屬性last記錄此文件上次被訪問時經(jīng)歷過了多少個單位時間(一個單位時間對應一次訪問)。

由文獻[6]，文件的CRF值可由式(1)算得:

CRFlast(b)=f(0)+f(tc-LAST(b))×CRFlast(b)

(1)

式中：

(2)

LAST(b),CRFlast(b)分別表示上次訪問文件b時的單位時間次數(shù)和文件b的CRF值。tc表示當前單位時間次數(shù)。結合式 (1) 和式 (2) 可知，f(0)即為當前被訪問，且在此次訪問之前從未被訪問過的文件的CRF值。

圖4 文件緩存替換流程

在每次文件讀取完畢更新緩存系統(tǒng)時，都新建一個LocatedBlocksWithCRF對象，用來緩存被訪問過文件的數(shù)據(jù)塊信息。該對象的src屬性賦值為被訪問文件在HDFS中的絕對路徑，CRF屬性為f(0)，blks為文件被訪問完后DFSInputStream對象的locatedBlocks屬性，last為當前單位時間次數(shù)。用LocatedBlocksWithCRF類的src屬性的比較器查看該文件的數(shù)據(jù)塊信息是否已被緩存。若該文件的數(shù)據(jù)塊信息未被緩存(既不在鏈表中，也不再堆中)，則進行如下步驟：

步驟1替換掉鏈表尾部的一個元素。

步驟2堆頂元素降級到鏈表的首部。

步驟3新塊插入到堆頂部。

步驟4調(diào)整堆，使其滿足小根堆性質。

若該文件的數(shù)據(jù)塊信息位于緩存堆中，則根據(jù)式(1)用緩存LocatedBlocksWithCRF對象的CRF、last和當前時間算出新的CRF值，并用其更新新建的LocatedBlocksWithCRF對象。然后用新建的LocatedBlocksWithCRF對象替換緩存的LocatedBlocksWithCRF對象，并調(diào)整以其作為根的子樹的堆，使其滿足小根堆性質。若該文件的數(shù)據(jù)塊信息位于緩存單鏈表中，則進行如下步驟：

堆頂元素降級到單鏈表首部。刪除單鏈表中的該文件的LocatedBlocksWithCRF對象。根據(jù)式(1)用緩存LocatedBlocksWithCRF對象的CRF、last和當前時間算出新的CRF值，并用其更新新建的LocatedBlocksWithCRF對象。將新建LocatedBlocksWithCRF對象插入到堆頂。調(diào)整堆，使其滿足小根堆性質。

4 日志分析模塊

HDFS客戶端緩存模塊性能取決于由參數(shù)所決定的LFU和LRU在替換策略中的比重是否符合實際文件訪問情況。HDFS運用的場景不同，HDFS客戶端緩存模塊最佳性能對應的值不同。在HDFS運行前，通過參數(shù){io.file.cache.Lambda}來設定的值，不設定則使用系統(tǒng)默認值。在HDFS運行時，通過分析Web日志文件來確定合適的值。

在HDFS客戶端緩存模塊中用Pf(A)表示在LFU緩存替換策略中用戶訪問文件A后再次訪問文件A的概率。計算如公式所示:

(3)

式中：N表示訪問日志中所有文件出現(xiàn)的次數(shù)，Na表示訪問文件A前t時間單位內(nèi)文件A被訪問的次數(shù)，在HDFS客戶端緩存模塊中t為單鏈表的長度與堆大小之和。LFU緩存替換策略用Pf(A)值表示文件A在將來被訪問概率，Pf(A)值越大表示文件A在將來越有可能再次被訪問，文件A越不可能被替換出緩存。

用Pr(A)表示在LRU緩存替換策略中用戶訪問文件A后再次訪問文件A的概率。計算如公式所示：

(4)

式中：T表示訪問日志總單位時間，在數(shù)值上等于所有文件出現(xiàn)的次數(shù)，Ta表示此次訪問文件A距上次訪問文件A的單位時間次數(shù)，t為單鏈表的長度與堆大小之和，當t-Ta小于0，則t-Ta取0。LRU緩存替換策略用Pr(A)值表示文件A在將來被訪問概率，Pr(A)值越大表示文件A在將來越有可能再次被訪問，文件A越不可能被替換出緩存。

在HDFS客戶端緩存模塊更新緩存并根據(jù)LRFU緩存替換算法替換出緩存中文件時，比較被替換出文件的Pf值和Pr值大小，若其Pf值較大說明LRU緩存替換策略更適合此場景，LFU緩存替換策略在此場景下的比重應當比LRU緩存替換策略小些。在Pf值大于Pr值1 000此時，將λ值加0.001。反之，在Pf值小于Pr值1 000此時，將λ值減0.001。這樣通過將分析日志得出的結構反饋到值上，提高HDFS客戶端緩存模塊的命中率，使HDFS客戶端緩存模塊具有實時性。

5 實驗與分析

5.1 實驗環(huán)境

本實驗環(huán)境基于4個節(jié)點的Hadoop集群，其中NameNode配置為4 GB內(nèi)存，AMD Athlon(tm) X4 740 Quad 3.20 GHz， 1 TB硬盤。3個dataNode是2 GB內(nèi)存，Intel Core i5-6200U CPU 2.30 GHz，2 TB硬盤。

每個節(jié)點的操作系統(tǒng)都是Centos 7，Hadoop版本2.7.3，Java版本1.8.0，HDFS副本數(shù)為3，HDFS塊大小是32 MB。

實驗中實現(xiàn)了客戶端本地緩存的HDFS的值均取系統(tǒng)默認值，緩存大小均取400個LocatedBlocksWithCRF對象。

5.2 NameNode負載測試

本實驗使用的指標：客戶端調(diào)用遠程方法getBlockLocations()請求NameNode的次數(shù)。在本實驗中，NameNode負載只考慮由訪問文件而請求NameNode的請求量，由于HDFS客戶端和實現(xiàn)了客戶端本地緩存的HDFS均需維護原數(shù)據(jù)，連接數(shù)據(jù)節(jié)點等工作，所以這部分負載不作考慮。

在訪問日志中隨機選取一個時間點作為訪問的起始點，使用HDFS以及實現(xiàn)了客戶端本地緩存的HDFS分別根據(jù)訪問日志分別訪問2 000、4 000、6 000、8 000和10 000個文件，并記錄客戶端調(diào)用遠程方法getBlockLocations()的次數(shù)，結果如圖5所示。

圖5 HDFS與實現(xiàn)了客戶端本地緩存HDFS請求NameNode次數(shù)對比

從圖5中可以看到，HDFS隨著訪問文件的次數(shù)增加，調(diào)用遠程方法getBlockLocations()的次數(shù)呈線性增加。而實現(xiàn)了客戶端本地緩存的HDFS隨著訪問文件次數(shù)的增加，調(diào)用遠程方法getBlockLocations()的次數(shù)開始也會增加，而之后的變化趨勢較為平緩。實驗結果說明了本地緩存的客戶端能明顯減少對NameNode的請求量，從而降低了NameNode的負載。

5.3 緩存命中率測試

為模仿不同的場景，首先使用LRFU緩存替換策略，在訪問日志中選取8個相距較遠的訪問時間作為訪問點，并分別從這些訪問點開始根據(jù)訪問日志訪問2 000個文件，同時記錄從緩存中讀取文件塊信息的文件數(shù)，算出訪問命中率。然后使用LRU和LFU緩存替換策略以相同的方法，分別再次實驗。實驗結果如圖6所示。

圖6 LRFU與LRU、LFU緩存替換策略命中率對比

從圖6中可以看出，LRU和LFU緩存替換策略從不同的訪問點訪問文件的命中率折線具有波動，命中率不如LRFU緩存替換策略高。而LRFU緩存替換策略命中率折現(xiàn)較為平緩。說明LRFU緩存替換策略對不同的場景具有自適應性。

5.4 文件訪問時間測試

在訪問日志中隨機選取一個時間點作為訪問的起始點，使用HDFS以及實現(xiàn)了客戶端本地緩存的HDFS分別根據(jù)訪問日志分別訪問2 000、4 000、6 000、8 000和10 000個文件，記錄每次實驗的訪問時間。實驗結果如圖7所示。

圖7 HDFS與實現(xiàn)了客戶端本地緩存HDFS文件訪問時間對比

從圖7可以看出，客戶端本地緩存的HDFS速度比HDFS快，證明了實現(xiàn)了客戶端本地緩存的HDFS能提高訪問效率。

6 結 語

本文基于Master/Slave主從構架設計的HDFS中單個NameNode造成的性能瓶頸問題，提出了一種由每個HDFS客戶端在某些功能上充當NameNode，分擔NameNode部分任務的思想。并基于該思想設計實現(xiàn)了在HDFS客戶端中根據(jù)LRFU緩存替換策略建立文件元數(shù)據(jù)緩存，得到如下結論：

1) 該方案減少HDFS客戶端對NameNode請求量，一方面減少分布式系統(tǒng)中網(wǎng)絡流量，另一方面減輕單個NameNode的負載，從而達到優(yōu)化HDFS性能的目的。

2) 該方案對場景具有自適應性。在不同的場景中，HDFS客戶端通過分析文件訪問日志來權衡LFU和LRU在替換策略中的比重，使其更符合當時的場景，保持較高的緩存命中率。

參考文獻

[1] White T. Hadoop:The Definitive Guide[M]． California:O’Reilly Media，inc．，2015:1-4.

[2] Melorose J，Perroy R，Careas S．Hadoop definitive guide[M]．Chicago:Yahoo！Press，2015:1-4.

[3] Honnutagi P S．The Hadoop distributed file system[J]．International Journal of Computer Science & Information Technology，2014，5 (5):6238-6243.

[4] Lee D，Choi J，Kim J H，et al．LRFU:A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies[J]．Computers IEEE Transactions on，2013，50(12):1352-1361.

[5] Bai S，Bai X，Che X，Window‐LRFU:a cache replacement policy subsumes the LRU and window‐LFU policies[J]．Concurrency & Computation Practice & Experience，2016，28(9):2670-2684.

[6] Wang C Y，Huang T E，Huang Y T，et al．An Inter-framework Cache for Diverse Data-Intensive Computing Environments[C]//IEEE International Conference on Smart City/socialcom/sustaincom．IEEE，2016:944-949.

[7] 饒磊，楊凡德，劉東．基于分布式NameNode節(jié)點的HDFS優(yōu)化研究[C]//全國信號和智能信息處理與應用學術會議，2014:450-453.

[8] 李寬．基于HDFS的分布式NameNode節(jié)點模型研究[D]．廣州:華南理工大學，2011.

[9] Aishwarya K，Arvind R A，Sreevatson M C，et al．Efficient prefetching technique for storage of heterogeneous small files in Hadoop Distributed File System Federation[C]//Fifth International Conference on Advanced Computing．IEEE，2014:523-530.

[10] 趙婧，王洪波，程時端．HDFS 數(shù)據(jù)節(jié)點本地緩存的設計與實現(xiàn)[EB/OL].http://www.paper.edu.cn/releasepaper/content/201112-98.

[11] 蔡斌，陳湘萍．Hadoop:技術內(nèi)幕深入解析Hadoop Common和HDFS架構設計與實現(xiàn)原理[M]．北京:機械工業(yè)出版社，2013:218-219.

[12] Einziger G,Friedman R.TinyLFU:A Highly Efficient Cache Admission Policy[C]//Euromicro International Conference on Parallel, Distributed and Network-Based Processing. IEEE, 2014:146-153.

[13] Dan A，Towsley D．An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes[J]．ACM Sigmetrics Performance Evaluation Review，1990，18(1):143-152.

[14] Hai J，Kai H. Efficient LRU Algorithm for Cache Scheduling in a Disk Array System[J]．International Journal of Computers & Applications，2015，22(3):134-139.

[15] Rexha G，Elmazi E，Tafa I．A Comparison of Three Page Replacement Algorithms:FIFO，LRU and Optimal[J]．Epl， 2015，28(7):465-469.