網絡編碼集群存儲系統基于鎖機制的熱數據重建策略

趙昱帆,鄧玉輝,2

1(暨南大學 信息學院計算機科學系,廣州 510632) 2(中國科學院 計算技術研究所計算機體系結構國家重點實驗室,北京 100190) E-mail:tyhdeng@jnu.edu.cn

1 引 言

數據規模的與日俱增催生出了大數據的概念,而大數據的廣泛應用必須依賴于分布式存儲的技術[4].在分布式文件系統中,如GFS[2]和WAS[1],邏輯上完整的數據、存儲和計算資源被分布在不同的物理節點.伴隨著存儲系統規模的不斷增長,節點失效成為了一個越來越普遍的問題[2].存儲系統中應用了不同的冗余機制來避免由節點失效導致的數據的永久性丟失.目前廣泛應用的冗余機制有副本機制[14]、RAID編碼機制以及糾刪碼機制[2,4].網絡編碼的冗余機制跟傳統的副本機制相比,在保障系統可靠性的前提下大大減少了存儲開銷.然而當發生節點失效時,網絡編碼機制則需要消耗數倍于副本機制的網絡帶寬來重建失效數據.當系統處于節點失效的退化模式時,仍要同時服務于重建數據流和用戶訪問數據流.本文的研究針對減少處于退化模式的系統中的兩種數據流之間的I/O爭用,使重建性能和用戶訪問性能得以提升.

有很多之前的研究都致力于在系統失效模式下平衡系統的可靠性和響應性能.這些研究工作主要有以下幾類.一些研究通過減緩用戶訪問和數據重建之間的I/O競爭,從而提升系統性能和重建性能.例如,文章[6]基于RAID編碼的存儲系統提出了一種改進的數據重建機制PRO.PRO改變了原有的數據重建的順序,使得用戶訪問最頻繁的數據得以優先重建,使用戶可以提前從替換節點中訪問已被重建的失效數據,從而減少了兩種數據流在存活節點中的I/O競爭.文章[9]提出了HDFR重建方法,將基于用戶訪問模式的數據重建應用在部署于單機環境中的NCFS[3]分布式網絡編碼文件系統.上述兩個工作將兩種數據流在存活節點中的讀讀爭用轉換為替換節點的讀寫爭用,即替換節點中重建數據流的寫操作和用戶訪問數據流的讀操作發生I/O爭用.

還有一些研究通過減少數據重建過程消耗的網絡帶寬來提升重建性能.例如,文章[5]提出對于通用的基于異或操作的糾刪碼而言,使用枚舉法找到一種最小數據讀方案是一個NP難問題.因此他們設計出了一種新的旋轉Reed-Solomon編碼,這種編碼相較于大多數常見的網絡編碼實現了最小數據讀.文章[7]針對基于[5]中提到的糾刪碼的枚舉重建策略提出了一種替代的重建策略,這種重建策略采用了爬山算法實現在單點失效的場景下時在多項式時間內查找較少數據讀的方案.

總而言之,以上研究工作大多沒有從考慮I/O負載的角度來實現快速重建.而以上考慮到I/O負載的研究[6,9]通過將用戶更多的訪問重定向到替換節點來減少磁盤I/O爭用,然而這個過程中忽略了一些網絡通信協議如AOE中的寫性能比讀性能差[11,12],這將導致替換節點的讀性能削弱,甚至導致重建性能和系統響應性能的降低,并且只適用于單節點失效場景.

基于網絡編碼的分布式文件系統NCFS,我們提出了基于鎖機制的熱數據重建策略(LHDFR),并將其應用于真實的分布式實驗環境中.鎖機制的熱數據重建策略是基于上述熱數據重建,即根據I/O負載特征優先重建用戶訪問最頻繁的區域.但我們考慮以保障系統可靠性為前提,使用戶數據流和重建數據流在存活節點的讀讀爭用與替換節點中的讀寫爭用均衡,對替換節點加鎖,重建數據流有優先獲得鎖的權利,對替換節點進行排他地批量寫入操作,得到讀鎖的用戶可以從替換節點中直接訪問重建好的數據,而未得到讀鎖的用戶則從存活節點中讀取數倍數據來解碼出需要訪問的數據.這使得用戶數據流和重建數據流之間因I/O等待導致的讀寫延遲盡可能減小.我們基于真實的分布式環境搭建了NCFS分布式文件系統,并基于該分布式系統分別測試了傳統順序的數據重建(TR)、熱數據重建(HDFR)以及基于鎖機制的熱數據重建策略(LHDFR)中的系統響應性能和重建性能.最后我們對實驗結果進行了評估分析.

本文剩余部分的組織結構如下.在第二部分中介紹了網絡編碼、數據重建以及NCFS文件系統相關背景知識.在第三部分中具體介紹了加鎖的數據重建模型.在第四部分中給出了傳統數據重建、基于熱數據重建和本文基于鎖機制的數據重建的實驗結果對比和評估分析.最后在第五部分中我們給出了結論.

2 背景知識

2.1 常見的網絡編碼及其優缺點

全副本的冗余機制將原始數據的幾個副本存儲到不同的物理節點中,一旦發生節點失效,系統可以通過從任意存活節點中下載丟失數據的備份來實現數據的快速重建,在這個過程中的重建時間和重建帶寬都是最優的.然而,全副本機制導致了很高的存儲開銷.接下來介紹一下常見的網絡編碼及其特點.

RAID5編碼[3]:RAID5編碼是一種可以容忍單節點失效的MDS編碼.RAID5采用了條帶式的結構.我們用k(k=n-1)來定義RAID5,這意味著在每一個條帶中都有一個校驗塊.我們可以通過n個節點中的任意k個重建出整個原始數據.

RAID6編碼[3]:RAID6編碼是用k(k=n-2)來定義可以容忍雙節點失效的RAID編碼.每個條帶中都有k份原始數據和2個線性無關的編碼塊,下載n個節點中的任意k個節點的數據都可以重建出失效數據.

Reed-Solomon編碼(RS 編碼)[8]:RS編碼是用(m,k)來定義,可以容忍不多于k個節點的失效.RS編碼也采用了條帶式的結構.調整RS編碼的參數可以改變系統的容錯能力,也就是說可以使用更少的存儲資源實現跟全副本機制相近的可靠性.

相較與全副本機制,RAID5、RAID6、RS編碼機制通過生成額外的校驗數據來提高系統的存儲效率.在重建過程中,我們可以通過下載同一條帶中的剩余k份數據來計算出丟失的數據.然而這種方式會大大增加重建帶寬,也會極大延長系統重建時間.由于系統在重建過程窗口很可能會發生二次節點失效,因此系統重建性能對于保障整個系統的可靠性和可用性意義重大.

2.2 NCFS分布式文件系統

NCFS分布式文件系統(Network-Coding-Based Distributed File System)[3]是一個構建在FUSE上的開源分布式文件系統.我們把熱數據重建算法和加鎖的熱數據重建算法應用在NCFS文件系統中.在存儲節點(存儲節點可以是普通的個人電腦、云存儲服務器、磁盤等等)中NCFS扮演了連接器和控制器的角色,即通過一個千兆交換機和AOE(ATA over Ethernet)協議控制對所有存儲節點的訪問操作.下面介紹一下NCFS的層次結構.NCFS由文件系統層、重建工具層、編碼層、緩存層以及存儲層5層構成.文件系統層主要處理一些針對文件的操作.重建工具提供了在節點失效場景中適用于不同編碼機制的重建方法.編碼層提供了多種編碼的冗余機制,例如RAID5、RAID6、Reed-Solomon編碼等等.最后,存儲層直接跟各個存儲節點進行交互.

2.3 重建策略

接下來介紹兩種重建機制,一種是NCFS文件系統提供的傳統重建機制TR,另一種是[6]提出的基于I/O負載的熱數據重建HDFR.在傳統的重建策略中.失效節點的數據被順序地重建到替換節點中.在失效節點重建完成之前,當用戶訪問失效節點中的數據時,需要從存活節點中訪問數倍的數據并進行解碼操作直到重建完成.重建過程中,重建進程順序訪問存活節點每次解碼出下一個失效塊,緊接著將其順序寫入替換節點.由于重建是順序執行的,而用戶訪問大致遵循80/20規則,因此在傳統重建機制中,重建數據流和用戶數據流在存活節點發生頻繁的磁盤I/O爭用,嚴重影響了重建性能和系統響應性能.

圖1 熱數據重建過程Fig.1 Reconstruction process of HDFR

如圖1所示,在基于I/O負載的熱數據重建中,用戶訪問最頻繁的數據區域被優先重建到替換節點中.用戶在訪問失效節點數據時,若對應區域已完成重建,則可以直接訪問替換節點中的數據,否則也會執行解碼操作.在重建過程中,重建進程選擇當前最熱區域,在分配的若干時間片內,依然順序重建該區域中的失效數據塊,每次解碼出一塊就將其寫入替換節點.因此這個過程中替換節點同時服務于重建數據流的寫操作和用戶數據流的讀操作.

3 基于鎖機制的熱數據重建模型

3.1 核心思想

LHDFR重建模型在熱數據重建策略的基礎上根據由AOE網絡通信協議構建了SAN集群系統.AOE是比iSCSI更加廉價、更輕量、更安全且性能更優的存儲區域網絡技術,在AOE中發起主機可以訪問目標主機共享出來的磁盤空間.本文基于AOE中寫延遲大于讀延遲的特性提升了系統響應性能和數據重建性能,并且結合網絡編碼的條帶式分布和磁盤的空間局部性原理將針對單節點失效的熱數據重建應用于雙節點失效以及多盤失效場景中.接下來我們將逐一闡述這兩個創新點.

第一點,由于進行磁盤同步寫以及磁盤讀的預期機制,AOE中磁盤平均寫延遲大于讀延遲的特性,我們把替換節點中的I/O讀寫爭用轉換為存活節點中的I/O讀讀爭用.我們這里討論兩種場景下的I/O讀寫時間.第一種情況是用戶對失效數據塊只執行解碼操作,以RAID5(4,3)編碼為例,用戶會讀取三個數據塊來解碼出一個失效數據塊.由于,本文所用重建策略采用串行方法訪問所有存儲節點,所以這樣一個解碼操作的系統響應時間為:

Tresponse=Tread1+Tread2+Tread3+Tdecode

(1)

以上公式(1)中的系統響應時間由分別讀取三個數據塊的時間Tread1、Tread2、Tread3以及對三個數據塊進行解碼計算的時間Tdecode構成.如果對熱數據中的失效數據塊進行解碼操作,那么基于磁盤的緩存和預取機制讀取三個熱數據塊往往并不需要觸發磁盤I/O.這個場景中重建數據流在替換節點進行一次寫操作所需要的時間是:

Twite=Tqueue+Tservice

(2)

在第二種情況是用戶對替換節點中已重建好的數據進行直接訪問,用戶讀取這樣一個失效數據塊所需要的系統響應時間為:

(3)

針對用戶訪問的熱數據而言,利用文中所述網絡編碼的條帶式結構,可知空間局部性表現為熱數據傾向于分布于鄰近的若干條帶中.因此我們針對在替換節點中已經重建完成的熱數據重新思考公式(1)和(3)中的兩種響應時間.這里我們假設熱數據已經存在于工作節點緩存中的概率為prbuf,那么從磁盤訪問數據的概率為1-prbuf.那么公式(1)中的平均響應時間可以表達為以下形式:

(4)

很顯然熱數據往往在存在于緩存中所以prbuf的值往往比較大.假設訪問替換節點的用戶請求有pwrite的概率剛好在等待一個同步寫操作,那么公式(3)中的平均響應時間可以表達為以下形式:

(5)

由于替換節點為寫密集型設備,那么pdiskwrite概率比較大.那么我們假設極端情況,工作節點存在所訪問數據的緩存并且替換節點目前正在服務于寫操作.那么公式(4)中的響應時間大約為3Trbuf,公式(5)中的響應時間大約為Tdiskwrite+Trbuf.很顯然磁盤同步寫操作的時間開銷遠遠大于訪問緩存的時間開銷.所以面臨替換節點的讀寫爭用問題時,我們傾向于訪問工作節點來提升響應性能.

第二點,我們基于網絡編碼的條帶式分布特性將只適用于單節點失效的熱數據重建,應用在了適用于雙節點失效以及多節點失效的場景中.根據上文中RAID5、RAID6以及RS編碼的結構,可以看出順序的數據流或者文件傾向于分布在同一條帶或者鄰近的條帶中,所以我們將同一個熱區的劃分應用在所有的替換節點中.因此重建流程中的每次重建所有失效節點的同一熱區,這種策略適用于各種條帶式分布的網絡編碼存儲系統中的多節點失效場景.

3.2 LHDFR模型概覽

本文基于真實集群環境中的分布式文件系統NCFS提出了基于鎖機制的熱數據重建模型.如圖2所示該重建模型中主要分為三個模塊,即用戶模塊、跟蹤模塊以及重建模塊.其中用戶模塊中采用了齊夫定律來模擬符合80/20規則的用戶訪問;我們將磁盤均勻劃分為幾十個區域,每個區域由順序鄰近的條帶組成,跟蹤模塊記錄用戶對每個區域的訪問頻次,并且定期刷新統計數據;重建模塊每次選取最熱的訪問區域,對該區域內的失效數據進行順序重建,當某熱數據區域重建完成后,用戶可從替換節點中直接訪問該區域中的數據,以此來減少解碼過程中成倍的帶寬開銷以及存活節點中的磁盤讀讀爭用的問題.

圖2 LHDFR模型工作流程Fig.2 Working procedure of LHDFR

3.3 主要模塊

下面主要描述一下上圖中的用戶模塊和重建模塊.用戶模塊的實現如算法1所示.用戶模塊一共生成了n個訪問請求,每個請求訪問一個數據塊.首先我們隨機生成需要訪問的磁盤號,并根據齊夫定律生成需要訪問的熱區號i(每個磁盤被均勻劃分為等大的熱區).然后我們再隨機訪問熱區i中的某一塊數據,并把訪問的偏移地址以一定規律映射到磁盤地址中.如果用戶需要訪問的磁盤未失效,那么直接發起磁盤讀操作.如果用戶訪問的是失效磁盤,但所訪問的熱區已經修復并且替換節點并未上鎖,那么可以直接從替換節點中訪問請求數據塊.但如果用戶訪問的失效磁盤中的熱區未重建完成或者替換節點已被重建模塊上鎖,那么用戶只能進行解碼操作,從存活節點中解碼出請求數據塊.這個過程中,用戶每訪問一次失效磁盤中的某一熱區,該熱區的訪問頻次加一.

算法1.用戶模塊算法1 for n>0 do2 generate req_disk randomly;3 generate hotzone number i;// 根據齊夫定律生成需要訪問的熱區號4 generate zone_of fset randomly;//隨機生熱區i中訪問的偏移地址5 mapping zone_of fset to disk of fset;//將訪問的偏移地址映射到磁盤地址6 if req_disk is aalive then7 diskread(req_disk,disk_of fset);8 else if hotzone[i]is recovered && trylockreq_disk then //熱區i已修復并且對替換節點加鎖成功9 diskread(req_disk,disk_of fset);//從替換節點中直接訪問10 if hotzone[i]is not recovered then11 hotzone[i].time++;12 else13 decode(req_disk,true_of fset);//從存活節點中解碼出訪問數據14 hotzone[i].time++;15 n--;

算法2.LHDFR算法1 while tracker send hotzone i do //跟蹤模塊發美術字最熱區號i給重建進程2 set reconstruct_size to m blocks untilhotzone[i]is recovered;3 calculate disk_offset using mapping;4 reconstruct_end=disk_of fset+reconstruct_size;5 num=0;6 while num=zone_size then20 hotzone[i].flag=1;// hotzone[i]已重建完成21 return 0;

圖2中的重建模塊的實現如算法2中所示.重建模塊從跟蹤模塊中接收目前訪問最熱的熱區號,重建模塊默認順序重建熱區中若干個數據塊直至整個熱區被重建完成.接下來把整個重建過程分成了兩個步.第1步,依次重建所有失效磁盤的同一熱區中的塊到緩存中.第2步,在用戶某次訪問之后獲得所有替換節點的寫鎖,將恢復到緩存中的數據批量寫入替換節點中,寫入完成后釋放替換節點的鎖,再次開放對用戶的直接訪問.

4 實驗評估和分析

4.1 實驗環境及說明

我們的實驗是在基于網絡編碼的分布式文件系統NCFS中進行.NCFS支持多種網絡編碼例如RAID5、RAID6、RS編碼等等.在整個NCFS系統中,我們一共部署了6個存儲服務器作為物理節點,這6個服務器通過AOE協議經由NCFS主服務器來調度訪問磁盤空間.其中每臺服務器的實驗環境如表1中所示.我們在該環境中測試了TR、HDFR以及LHDFR三種重建方式在不同節點數目以及不同編碼機制下的系統響應性能和重建性能.在本文的實驗中,我們預設每個物理存儲節點的存儲容量為1GB,用戶對系統的訪問次數為300,000次.本次實驗中我們統計的系統響應時間滿足公式(6),即響應時間由解碼和讀磁盤時間組成,系統重建時間滿足公式(7),即重建總時間由解碼、讀磁盤和寫磁盤時間三部分構成.

Tresponse=Tdecode+Tread

(6)

Trecover=Tdecode+Tread+Twrite

(7)

表1 實驗環境Table 1 Experiment environment

4.2 單節點失效及分析

我們在單節點失效場景中,測試了TR、HDFR和LHDFR三種重建策略在RAID5編碼和RS編碼在不同節點數目中的系統響應性能和重建性能.圖3中顯示了RAID5(4,3)、RAID5(5,4)和RAID5(6,5)三種情況下的系統響應時間和重建時間.從圖3(a)中可以看出,隨著用戶節點數目的增加我們可以發現以下幾個規律.第一,TR重建方法的系統響應時間不斷增加.這是因為隨著節點數目的增多,一個校驗塊由更多節點的數據塊組成,反之當一個節點失效時就需要訪問更多節點的數據塊來進行重建或解碼.第二,HDFR重建方法隨著節點數目增多相對TR重建方法有了更多優勢.這是因為節點數目的增多意味著解碼失效數據的讀操作時間更多,而這個過程中重建數據的寫操作數量不變.第三,LHDFR重建方法相對TR重建方法在響應性能方面的優化程度隨著節點數目越來越大.RAID5(4,3)對比組中LHDFR將響應性能提升了24.6%,RAID5(5,4)中提升了36.2%,RAID5(6,5)中提升了38.1%.第四,與HDFR相比伴隨著節點數目增多LHDFR對響應性能的優化率逐漸減少.這個現象的原因同第一點原因相似,因為隨著解碼開銷的增大,磁盤的讀讀爭用相比讀寫爭用的差異不斷減小.

從圖3(b)中顯示了RAID5編碼系統在單節點失效場景中的系統重建性能.系統重建過程跟用戶訪問過程一樣都包含解碼操作,并且還多了寫磁盤操作.這兩個過程的區別在于,用戶訪問可以根據重建策略HDFR和LHDFR減少需要讀取的數據,但是在重建過程中TR、HDFR以及LHDFR三個方法不會減少重建帶寬的消耗.從圖中可以看出,隨著節點數目的增多TR的重建時間也呈現出不斷增加的趨勢.這是因為重建過程中的解碼過程需要讀取更多數據,這也意味著解碼的計算開銷也更大,加之系統重建過程中的重建帶寬不會減少所以公式(5)中的Tread和Tdecode不斷增大.圖中HDFR隨著節點數目的增多相比TR對重建性能有了一些優化,因為用戶訪問產生的解碼操作會讀取所有存活節點中對應的數據塊,每讀取一次就會跟重建進程的解碼操作在存活節點發生磁盤的讀讀爭用.LHDFR相比HDFR將重建性能優化了58.80%,其中優化了55.45%,優化了64.75%.圖4(a)和圖4(b)跟上圖大致遵循一樣的規律.

圖3 RAID5編碼單節點失效場景Fig.3 RAID5 coding scheme in single node failure scene

圖4 RS編碼單節點失效場景Fig.4 RS coding scheme in single node failure scene

4.3 雙節點失效及分析

我們在雙節點失效場景中,測試了TR、HDFR和LHDFR三種重建策略在RAID6編碼和RS編碼在不同節點數目中的系統響應性能和重建性能.雙節點失效場景相比于單節點失效場景會產生更多的重建帶寬和用戶訪問帶寬.

圖5 RAID6編碼雙節點失效場景Fig.5 RAID6 coding scheme in double nodes failure scene

圖5中顯示了RAID6(4,2)、RAID6(5,3)和RAID6(6,4)三種情況下的系統響應時間和重建時間.從圖5(a)中可以看出,隨著節點數目的增加我們可以發現類似單節點失效場景中的幾個規律.第一,TR重建方法的系統響應時間也不斷增加.第二,HDFR重建方法隨著節點數目增多相對TR重建方法有更多優勢.第三,LHDFR總體而言相比HDFR對系統響應時間優化更多,但隨著節點數目的增多優化率逐漸下降.在RAID6編碼的雙節點失效場景中,LHDFR相較于HDFR在系統響應性能方面優化至27.686%,相較于TR響應性能優化了16.501%.

圖6 RS編碼雙節點失效場景Fig.6 RS coding scheme in double nodes failure scene

圖5(b)中可以看出,圖中隨著節點增多呈現出的變化趨勢同單節點失效的重建場景仍有一下幾點相似.第一,TR重建時間仍不斷增加.第二,HDFR隨著節點數目增多對TR重建性能有了一些優化.第三,LHDFR對重建性能優化率一直保持在較高水平48.015%以上.圖6(a)和圖6(b)跟圖5大致遵循一樣的規律.

5 結 論

本文中我們基于HDFR熱數據重建策略提出了基于鎖機制的熱數據重建策略LHDFR.這種優化的重建策略相比于HDFR在數據重建場景中有更優的系統響應性能和數據重建性能,并且適用于多種編碼以及多節點失效的場景.LHDFR將用戶訪問產生的替換節點中的I/O讀寫爭用轉換為存活節點的解碼操作,用解碼過程中的讀開銷和計算開銷來交換替換節點中I/O爭用以及I/O隊列等待時間.最后我們將LHDFR部署在包含6個節點的NCFS分布式集群環境中,測試了單節點失效場景和雙節點失效場景下LHDFR、HDFR以及TR的系統響應性能和數據重建性能,分別優化至36.2%,59.4%.