基于糾刪碼的HDFS存儲調度技術

范 濤，劉曉燕

（昆明理工大學信息自動化學院，云南 昆明 650000）

0 引言

HDFS糾刪碼技術指的是糾刪碼算法在 HDFS中的實現，簡稱HDFS EC。糾刪碼技術是一種用于數據恢復的技術。通過糾刪碼（Erasure Code，EC）技術，將原始數據經過一定編碼分成若干較小的數據塊并保存在多個不同的存儲節點中。對于一個(n，k)糾刪碼(n＞k)，原始數據先被等分成k個大小相同的數據塊，再將k個數據塊經過一定編碼生成n個數據塊，并保存在n個不同的存儲節點中，每次只需從n個數據塊中任意獲取k個數據塊并進行解碼即可恢復原始數據。對于任意(ni，ki)糾刪碼(i = 1,2, …)，只需滿足最大距離可分碼（Maximum Distance Separable code，MDS），即可使用糾刪碼對文件進行編碼存儲[1]。它通過在原始數據中加入新的校驗數據，使得各個部分的數據產生關聯性。原始數據塊和校驗數據塊都可以通過現有的數據塊進行恢復，規則如下：（1）如果校驗碼數據塊發生錯誤，通過對原始數據塊進行編碼重新生成。（2）如果原始數據塊發生錯誤，通過校驗數據塊的解碼可以重新生成。它對于HDFS帶來的最大改變是可以使得HDFS不再依靠多副本機制來達到容錯的效果。多副本機制的一個很大弊端在于極大浪費存儲空間，HDFS糾刪碼技術的引入將會極大地改善這個問題。在Hadoop EC的設計中，提出了以下幾點實現目標：（1）存儲空間的節省。（2）靈活的存儲策略，用戶同樣能夠標記文件為 HOT或存儲類型。（3）快速的恢復與轉換，同時在數據恢復的時候，需要盡可能減少網絡帶寬的使用。（4）IO帶寬的節省。（5）Namenode低負載。EC技術在一定程度上會增大Namenode的開銷，因為NameNode需要額外跟蹤校驗塊的信息。在 EC的實現過程中，需要盡可能降低NameNode的負載。這里還有一點需要注意，EC在Hadoop中的實現會直接改變原來的HDFS默認的三副本策略 。EC的數據恢復，主要分3大步驟：1. 根據EC數據恢復的要求，至少保證向最少要求數量的源端節點讀取數據；2. 為目標節點解碼數據；3. 傳輸數據到目標節點。在步驟1中，至少向最少要求數量的源端節點讀取緩沖數據。如果部分源端節點出于損壞狀態或是數據落后狀態，將會選擇下一個源節點。最好的源節點會被記住并用在下一輪的數據恢復過程中、當然也可能在每一輪中被更新[2]。

在HDFS存儲系統中，頻繁使用到的熱數據占整個存儲系統的很少部分，系統存儲的數據大部分為不經常使用的冷數據。HDFS存儲系統的三副本策略可以實現數據的高可用性和容錯，適用于熱數據的存儲。大部分的冷數據，對數據的高可用性、及時性要求較低，副本策略短處暴露得明顯，副本會占用大量的存儲資源并有可能耗光所有存儲空間。為了很好地解決這個問題，提出了HDFS糾刪碼技術，它是三副本策略的一個有力補充，可以較好解決存儲系統資源消耗過多過快的問題。糾刪碼技術把數據編碼成數據塊存放在存儲節點上，需要消耗大量的網絡帶寬去和數據節點交互，在進行編碼、解碼計算時，需要消耗CPU資源、內存資源。這些資源消耗較高的代價，決定糾刪碼只對數據的高可用性、及時性要求較低的冷數據適用。采用了糾刪碼技術來存儲冷數據，可以大大減少HDFS集群中的副本數，并且在數據恢復時，消耗資源少，不會存儲集群造成太大的影響。

1 相關分析

在本文中，HDFS存儲系統采用如圖 1所示架構。在HDFS存儲系統中，用戶向代理節點提出數據請求，代理節點接受請求，并把客戶的請求放入請求隊列中，調度器對用戶請求進行調度，把用戶請求映射到適當的任務隊列。本文只關注 get操作的用戶請求，即文件獲取操作。糾刪碼(n，k)糾刪碼(n＞k)恢復一個文件至少需要k個數據塊。每個任務是利用一個線程與源端數據塊存儲節點建立 TCP連接并下載k個目標數據塊的任務，將下載的數據保存在代理節點的存儲緩沖池中[4]。一個線程定期掃描數據，比如對數據塊和校驗塊做 crc校驗，如果發現有數據塊或者校驗塊失效，則重新對數據進行選擇。當k個任務都完成后，代理節點進行解碼操作并恢復文件，最后將恢復好的文件返回給用戶。代理節點每消耗一個線程與存儲節點進行TCP連接進行數據下載直至任務完成，但代理節點內可用線程數固定，當可用線程數用盡時，剩余任務則需要等待任務完成并出現新的可用線程，代理節點對等待隊列中的任務進行調度，新任務才開始工作。本文的系統架構增加了一個監控節點，它實時收集每個存儲節點的性能負載信息，為代理節點提供調度依據。

圖1 HDFS存儲系統架構Fig.1 HDFS storage system architecture

2 節點信息分析

2.1 性能指標分析

本文在如圖1所示的云存儲系統架構中，設置了一個性能檢測節點，每經過Δt時間間隔，采集云存儲系統中各個存儲節點的性能指標信息并保存。通過實時跟蹤一些具有代表性的性能指標信息（如表1所示），來分析其對調度產生的影響大小。這樣單獨設置一個性能檢測節點，可以減小對代理節點的干擾，使文件獲取的時延得到降低，并且性能檢測節點的通信開銷對系統負載影響很小。

本文為了驗證上述指標對文件獲取的平均時延的影響，在存儲節點中單獨部署了兩個應用，分別用于提高存儲節點的CPU利用率和內存利用率。實驗發現隨著CPU利用率和內存利用率的變化，文件平均下載時延變化不大。通過對多個節點的負載信息進行分析，發現文件平均下載時延也不會隨著CPU利用率、內存利用率、throughput_recv、disk_percent、disk_write等指標變化而變化。由此可以推斷出 CPU利用率和內存利用率 throughput_recv、disk_percent、disk_write等指標對文件獲取的平均時延基本沒有影響。

表1 性能指標信息Tab.1 performance index information

由數據傳輸時延=發送時延+傳播時延+等待時延公式可知，當要發送的數據較多、吞吐量升高時，發送端口能力一定，導致更多數據等待發送，等待時延增加。節點負載較重，吞吐量升高會導致數據丟包率升高，更多數據需要超時重傳，增加數據傳輸時延。通過實驗研究發現，數據獲取時延曲線隨著throughput_send曲線的變化而發生一定變化，可以推斷文件獲取時延與吞吐量之間存在一定的關系。存儲系統從從存儲節點磁盤讀取數據塊，然后發送到代理節點，假設每次磁盤讀操作讀取的數據大小相同，為d字節，那么在理想情況下，只要發送速度足夠快，throughput_send = disk_read* d，可以看出每秒發送的字節數和每秒讀取次數存在線性關系，所以本文使用吞吐量作為調度依據而不使用每秒磁盤讀操作[6]。HDFS存儲系統中存在各種異構系統，各存儲節點的磁盤 I/O速率和可靠性差異較大，在實際的應用場景中，磁盤 I/O速率比較低的存儲節點和可靠性比較低的存儲節點往往成為影響整個存儲系統數據讀寫性能的瓶頸，如果僅僅用吞吐量（throughput_send）作為存儲負載的判定條件，則其數據的讀寫效率必然受到限制。

過負載節點：在每個監測周期(Δt)內計算每個存儲節點的負載率Li和系統平均負載Lavg，當某個節點的Li超過Lavg時則視為出現了過載節點。高負載可能造成高時延，節點過載導致較高的丟包率，用戶獲取數據時延的不穩定。

2.2 過負載節點判斷

（1）計算系統中所有節點的數據總量DN。設分布式系統中第 i個節點的存儲數據量為 DNi，共有n個節點，則該系統數據總量為：

（2）設第i個節點中磁盤的讀寫速率為DRi，則磁盤平均讀寫速率DR為：

（3）近似計算節點的的可靠性 Ri設定磁盤出廠未使用時其可靠性為100%，當達到硬件的使用壽命時，其可靠性為50%，當達到2倍的硬件壽命時，其可靠性為0%。其中，Tlife表示磁盤壽命（一般為3萬小時)，Ti表示磁盤已經使用時間。則第 i個節點可靠性為：

（4）設第i個節點中磁盤在可靠的情況下讀寫數據所需時間為DTi，則

（5）讀寫第i個節點的數據時，可能出現讀寫成功和讀寫失敗兩種情況，將該節點的可靠性視為讀寫成功的概率，則可以計算出第 i個節點的平均讀寫時間，因此綜合考慮磁盤可靠和不可靠兩種情況，定義節點平均讀寫時間：

其中 DTmax表示節點不可靠情況下讀寫數據所需要的時間。

（6）將第i個節點的數據平均讀寫時間在整個集群中的比重定義為基于讀寫效率的節點負載率Li：

（7）計算系統平均負載Lavg：

通過計算每個節點的負載率Li，計算系統平均負載Lavg，如果Li>Lavg，則說明該存儲節點超載[6]。

在本文中，我們結合單個節點負載率這一指標，初步判斷節點的超載情況，在此基礎上，通過優化現有調度策略，即基于存儲節點吞吐量的負載情況進行調度，設計了一種新的調度算法。

3 改進的調度算法

本文采用單節點存儲負載和磁盤的吞吐量（throughput_send表示）作為調度依據，并以此設計算法。普通動態負載調度算法依據動態運行中數據節點或鏈路的負載情況而采用動態分配存儲節點流量，以實現維護存儲節點吞吐量大致平衡。但這類算法的運行開銷較大，不能帶來較好的效率。而本文的算法不以負載絕對平衡為目的，在綜合考慮整體系統負載和單個節點負載的情況下，選擇最小吞吐量的節點，實現存儲節點負載均衡達到最優化。

在單用戶請求的情況下，當每次有用戶請求到達時，選擇負載最小的一些存儲節點進行下載，比較好處理。然而在多用戶同時請求的情況下，多個請求之間存在關聯性，會使存儲節點的吞吐量發生變化、節點負載加重。本文主要解決多用戶情況下的調度問題。

問題：假設有 p個用戶請求同時到達，獲取 p個文件，用file_list[1, 2, …, p]表示。每個文件分別采用(ni，ki)糾刪碼(i = 1, 2, …, p)。假設所有文件通過編碼后，數據塊全部映射到 q個存儲節點，(MAX(ni)≤q≤Σpi=1ni)。storage[1, 2, …, q]表示每個存儲節點的信息，chunk[1, 2, …, p]表示每個文件對應的數據塊信息。從(n1，n2，…，np)個存儲節點中分別選出(k1，k2，…，kp)個節點，使得所有存儲節點storage[1，2，…，q]的負載程度最優化[7]。

思路：根據類似于最小生成樹中的普里姆算法思想，對每個節點進行存儲負載判定，計算出哪些存儲節點是超負載的，然后每次從超載存儲節點中刪除一個數據塊，由于小數據塊對于吞吐量影響不大，在這里每次刪除最大的數據塊并更新當前節點的負載，重復操作，直到所有數據節點都不超載；再對所有存儲節點按 throughput_send信息進行排序，然后每次從throughput_send最高的存儲節點中刪除一個最大的數據塊，更新節點throughput_send，重復操作，直到所有文件的數據塊數目分別等于k1，k2，…，kp[8]。具體如算法如圖1所示。

4 實驗分析

4.1 實驗環境

為了驗證算法改進的效果，本文搭建了一個多節點的云平臺，采用開源項目OpenStack，使代理節點和所有存儲節點都處于同一個局域網，并配置每個節點使其具有一個千兆網卡。

在云平臺中，申請1臺虛擬機作為性能檢測節點，1臺虛擬機作為代理節點，另外申請20臺虛擬機作為存儲節點，組成一個測試系統。通過糾刪碼對文件進行編碼，并把形成的數據塊放在存儲節點中。本文在代理節點上部署調度算法，并將監測節點與存儲節點之間的交互頻率Δt設為2次/s。代理節點同時擁有L = 40大小的線程池。測試多用戶請求同時到達情況下本文UNION-ALGORITH調度算法的性能。在相同的實驗情況下，將本文的算法UNION-ALGORITH和 FCFS-R算法進行對比，得出相關的結論。FCFS-R：先來先服務策略，對于每個到達的請求，利用冗余線程來進行文件下載任務。

4.2 算法性能

本文以橫坐標表示用戶請求的總次數，縱坐標表示完成所有請求的平均時延。測試10，20，50，100，200，500幾組數據，得到的數據如圖2所示。本文算法避免了單個節點超載，從而影響文件獲取時延，使系統總體調度最優、負載較均衡。從圖 2可以看出，本文提出的UNION-ALGORITH算法比FCFS-R算法降10%～15%數據獲取的平均時延，相比FCFS-R算法降低20%～30%的平均時延。

在HDFS存儲系統中，用戶的體驗至關重要，而數據獲取時延的穩定性是決定用戶體驗的重要因素。本文通過分析算法對時延波動的影響，來驗證UNION-ALGORITH算法的性能。根據概率論相關知識，方差越大，表示數據離散程度越高，穩定性越差，因此可以利用方差來體現數據獲取時延的離散程度，D(X) = E{[X-E(X)]2}。實驗使用了糾刪碼(4，2)、(6，3)、(10，4)對文件進行存儲，并在用戶請求服從多用戶請求數據情況下，驗證 UNIONALGORITH算法的穩定性。實驗結果如圖3所示，在不同的糾刪碼編碼方式下，解決多用戶請求同時到達的問題，UNION-ALGORITH算法比 FCFS-R算法的時延方差降低了30%～40%，明顯比FCFS-R算法更有優勢。這說明在長時間內，UNIONALGORITH算法比FCFS-R算法有更穩定的數據獲取時延，不會出現劇烈波動即時延過高或過低的情況，從而帶來更好的用戶體驗。

圖1 多用戶請求調度算法Fig.1 LOAD-ALGORITHM

圖2 用戶請求的平均時延Fig.2 Average delay with multiple user requests

圖3 調度算法對穩定性的影響Fig.3 Effect of scheduling algorithms on stability

根據實驗結果可得出結論，本文提出的調度算法對數據獲取時延的穩定性也有著明顯的改善。

5 結語

本文給出了基于糾刪碼的HDFS存儲調度技術的研究，結合存儲節點的負載情況和節點的吞吐量指標，設計了新的調度算法，達到均衡負載的目的，降低文件獲取的平均時延，以實現最優的資源調用。通過計算單個存儲節點的負載，判斷超載節點，防止出現負載過重節點；通過分析大量存儲節點的相關信息，找出影響文件獲取的平均時延的性能指標，并基于該指標設計了新的調度算法。實驗結果表明，本文提出的調度算法能夠有效降低HDFS存儲系統中用糾刪碼編碼文件獲得的平均時延，達到負載平衡優化的目的，還能夠提高數據獲取的穩定性，給用戶更好的體驗。

[1] 趙勇. 架構大數據——大數據技術及算法解析[M]. 北京:電子工業出版社, 2015: 394-410.ZHAO Y. Big Data Structure—The Technology and Algorithm Analysis of Big Data[M]. Beijing: Publishing House of Electronics Industry, 2015: 394-410.

[2] Apache Software Foundation. Kafka [EB/OL]. [2016-04-11].http://kafka.apache.org/.

[3] Apache Software Foundation. Apache Zookeeper [EB/OL].[2016-04-11]. http://zookeeper.apache.org/.

[4] MICHAEL K, MILLER K W. Big data: new opportunities and new challenges[J]. Computer, 2013, 46(6): 22-24.

[5] 程振東, 欒鐘治, 孟由, 等. 云文件系統中糾刪碼技術的研究與實現[J]. 計算機科學與探索, 2013, 7(4): 315-325.CHENG ZD, LUAN Z Z, MENG Y, et al. Research and implementation on erasure code in cloud file system[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(4):315-325.

[6] BASSAM A A, CHEN W, ZHOU B B, et al. Effects of replica placement algorithms on performance of structured overlay net works[C]//Parallel and Distributed.

[7] 羅象宏, 舒繼武. 存儲系統中的糾刪碼研究綜述[J]. 計算機研究與發展, 2012, 49(1): 1-11.LUO X H, SHU J W. Summary of research for erasure code in storage system[J]. Journal of Computer Research and Development, 2012, 49(1): 1-11.

[8] KOLB L, THOR A, RAHM E. Dedoop: efficient deduplication with Hadoop[J]. Proceedings of the VLDB Endowment,2012, 5(12): 1878-1881.

[9] 蔣海波, 王曉京, 范明鈺, 等. 基于水平糾刪碼的云存儲數據布局方法[J]. 四川大學學報(工程科學版), 2013, 45(2):103-109.JIANG H B, WANG X J, FAN M Y, et al. A data placement based on level array codes in cloud storage[J]. Journal of Sichuan University (Engineering Science Edition), 2013, 45(2):103-109.

[10] Chen Kang, Zheng Wei-min. Cloud computing: System instances and current research[J]. Journal of Software, 2009,20(5): 1337-1348. (in Chinese)

[11] Wei Q S, Veeravalli B, Gong B Z, et al. CDRM: A cost-effective dynamic replication management scheme for cloud storage cluster[C]//Proc of IEEE International Conference on Cluster Computing, 2010: 188-196.

[12] Fu X, Wang R C, Deng S. A dynamic programming based replica placement in data grid[J]. Chinese Journal of Electronics, 2010, 19(4): 699-704.