王 慧 郭明陽 董歡慶 許 魯

(*中國科學院計算技術(shù)研究所 北京 100190)(**中國科學院大學 北京 100049)

?

BW-RAID系統(tǒng)的分布式異步版本識別機制①

王 慧②***郭明陽*董歡慶*許 魯*

(*中國科學院計算技術(shù)研究所 北京 100190)(**中國科學院大學 北京 100049)

為解決BW-RAID系統(tǒng)中數(shù)據(jù)冗余模式從鏡像向RAID4轉(zhuǎn)換時的節(jié)點間緩存數(shù)據(jù)版本識別問題，提出了一種分布式異步版本識別機制。該版本識別機制在鏡像卷中的一個邏輯塊被更新時，為其生成一個新版本；在冗余模式轉(zhuǎn)換時，通過比較鏡像節(jié)點間的版本判定某一邏輯塊在兩個鏡像節(jié)點緩存的數(shù)據(jù)是否一致，如果數(shù)據(jù)一致將其遷移到數(shù)據(jù)存儲卷，否則暫存入鏡像節(jié)點各自的磁盤緩存以保證系統(tǒng)的冗余一致性。實驗表明，該機制在系統(tǒng)正常、降級、故障恢復狀態(tài)下均能準確、有效識別一致數(shù)據(jù)；順序?qū)懺u測中存儲負載小于1%，平均帶寬提升最高達25.43%；Open-mail負載重播評測中存儲負載低于40%，應(yīng)用重播結(jié)束時寫更新數(shù)據(jù)均完成冗余模式轉(zhuǎn)換，實現(xiàn)了提高空間利用率的目標。

網(wǎng)絡(luò)RAID， 數(shù)據(jù)一致性， 分布式異步版本， 泛化時間戳， 版本識別

0 引 言

RAID是廉價磁盤冗余陣列(redundant array of inexpensive disk)，是存儲系統(tǒng)的基礎(chǔ)和關(guān)鍵部件。RAID技術(shù)大大提高了存儲系統(tǒng)的存儲容量、可靠性和性價比。藍鯨分布式集群BW-RAID(Blue Whale network RAID)[1]采用鏡像與糾刪碼協(xié)作的系統(tǒng)架構(gòu)，其優(yōu)勢在于既能發(fā)揮較高的讀寫性能又節(jié)省存儲空間。在工業(yè)界類似的混合冗余架構(gòu)被廣泛應(yīng)用，比如，EMC-Isilon[1，2]、Panasas[3]均實現(xiàn)了對小文件使用副本冗余，對大文件使用parity保證可靠性；HDFS-DiskReduce[4]則實現(xiàn)了應(yīng)用寫三副本，異步轉(zhuǎn)為糾刪碼冗余方式保存。上述系統(tǒng)中混合冗余機制均是文件系統(tǒng)級的實現(xiàn)，BW-RAID則是在通用塊層實現(xiàn)了混合冗余。

BW-RAID采用Mirror與RAID4混合的冗余方式容忍單點故障。集群中的存儲資源劃分為若干冗余組(RAID-set)，每個RAID-set實現(xiàn)對數(shù)據(jù)的冗余存儲。一個RAID-set覆蓋多個數(shù)據(jù)卷和一個校驗卷，其中包括兩類功能節(jié)點，即數(shù)據(jù)存儲節(jié)點(data node, DN)和校驗存儲節(jié)點(parity node, PN)；一個數(shù)據(jù)卷的寫更新數(shù)據(jù)首先存儲在由DN和PN的緩存組成的鏡像中，PN的后臺線程異步地對冷數(shù)據(jù)進行集中RAID4計算，并將完成冗余計算的數(shù)據(jù)存儲到DN的數(shù)據(jù)卷，將校驗碼更新到PN的校驗卷，實現(xiàn)數(shù)據(jù)冗余模式轉(zhuǎn)換。針對冗余模式轉(zhuǎn)換過程中如何解決鏡像中的緩存數(shù)據(jù)一致性問題，本文提出了一種分布式異步版本識別機制，以保證冗余組一致。

1 背 景

RAID-set的最小寬度為2，包括兩個數(shù)據(jù)卷和一個校驗卷，覆蓋兩個DN節(jié)點和一個PN節(jié)點，布局見圖 1(a)。為減少不必要的網(wǎng)絡(luò)數(shù)據(jù)傳輸和磁盤IO，RAID-set在進行冗余模式轉(zhuǎn)換時PN冗余計算和DN數(shù)據(jù)遷移均引用各自緩存中的數(shù)據(jù)副本，但此時正在進行轉(zhuǎn)換的邏輯塊在DN與PN緩存中的數(shù)據(jù)對象若不一致將導致RAID4的數(shù)據(jù)與校驗不一致，即影響RAID-set的冗余一致性。然而在分布式環(huán)境中由于存在網(wǎng)絡(luò)延遲、節(jié)點間獨立請求調(diào)度等因素，互為鏡像的緩存中數(shù)據(jù)不一致的現(xiàn)象難以避免。比如圖1(b)所示情形，DV1中的邏輯塊B在DN1緩存中已更新為[B:V2]，然而遠程寫被阻塞，PN緩存中仍為[B:V1]，此時若對邏輯塊B進行冗余模式轉(zhuǎn)換導致RAID4不一致。因此緩存數(shù)據(jù)一致性感知(或數(shù)據(jù)對象一致性識別)是保證冗余一致性的關(guān)鍵。解決數(shù)據(jù)對象一致性識別問題的常用方法有以下幾種：

圖1 RAID-set結(jié)構(gòu)及冗余一致性問題

(1) 內(nèi)存字符比較： Linux系統(tǒng)中的cmp工具、CMSD系統(tǒng)[5]等使用此方法比較數(shù)據(jù)一致性，該方法的不足是，將數(shù)據(jù)加載到內(nèi)存增加了磁盤IO，在分布式環(huán)境中需要將數(shù)據(jù)傳輸?shù)綀?zhí)行比較的節(jié)點又有網(wǎng)絡(luò)開銷。

(2) 數(shù)據(jù)指紋比較：采用SHA-1、MD-5等算法計算數(shù)據(jù)對象的數(shù)據(jù)指紋，使用數(shù)據(jù)指紋索引數(shù)據(jù)內(nèi)容，可以實現(xiàn)一致性確定，比如文件系統(tǒng)中的冗余數(shù)據(jù)識別[6-14]、內(nèi)存尋址系統(tǒng)[15]、版本管理系統(tǒng)GIT[16]等均使用該方法，其優(yōu)點是精確度高，但是數(shù)據(jù)指紋計算的時間開銷、維護的空間開銷都較高。

(3) 數(shù)據(jù)版本識別：(a)物理時間戳，通過比較數(shù)據(jù)對象產(chǎn)生的物理時間戳識別其一致性，其優(yōu)點是時間由操作系統(tǒng)維護的，無需單獨的模塊支持，該方法在理論上可行，然而在分布式環(huán)境中要求各節(jié)點的時間須完全同步，難以實現(xiàn)；(b)邏輯時間版本，其本質(zhì)是請求序列號，通過比較版本判斷數(shù)據(jù)更新發(fā)生的序列關(guān)系確定一致性，該方法可以不依賴于物理時間。比如版本管理系統(tǒng)SVN[17]，使用自增量作為其版本，Lamport timestamp[18]通過記錄更新操作發(fā)生的偏序關(guān)系判斷節(jié)點間的數(shù)據(jù)更新一致性，Dynamo[19]采用了該類算法解決并發(fā)訪問中的數(shù)據(jù)一致性問題。邏輯時間版本方式易于實現(xiàn)，其最顯著的特點是節(jié)點間數(shù)據(jù)同步時需要同時同步其版本號，目前通用塊層成熟的傳輸協(xié)議(如Iscsi)不支持該功能。(c)物理時間與邏輯時間結(jié)合的版本，每隔固定時間更新并同步節(jié)點間的全局邏輯時間，各節(jié)點在全局邏輯版本為基礎(chǔ)獨立更新本地邏輯時間，該方法允許節(jié)點間存在合理的時鐘偏移，這可以降低時鐘同步開銷，并且邏輯時間同步及更新與數(shù)據(jù)同步可以解耦，WACE[20]使用了該方法解決緩存集群中的緩存一致性問題。

上述方法難以滿足BW-RAID對數(shù)據(jù)對象一致性識別的要求，為此，本文提出了一種分布式異步版本識別機制解決該問題，該版本機制支持物理時間與邏輯時間結(jié)合的實現(xiàn)方式。

2 分布式異步版本識別

2.1 概念

主節(jié)點(master serving node, MSN)：緩存鏡像中接收客戶端請求的存儲節(jié)點，正常情況下默認是數(shù)據(jù)節(jié)點(DN)。

從節(jié)點(slave serving node, SSN)：緩存鏡像中接收鏡像寫請求的存儲節(jié)點，正常狀態(tài)下默認是校驗節(jié)點(PN)。

關(guān)聯(lián)請求：主節(jié)點寫請求和從節(jié)點與之對應(yīng)的鏡像寫請求為一對關(guān)聯(lián)請求。

2.2 基于精確時間的版本識別

2.2.1 精確時間版本定義

假設(shè)系統(tǒng)開始運行時主、從節(jié)點時間同步，主節(jié)點串行的接收對一個數(shù)據(jù)卷中同一邏輯塊地址的寫更新。我們對同一邏輯地址的寫請求按發(fā)生次序使用自然數(shù)編號，主、從節(jié)點的請求分別表示為Qi(i=1,2,3,…), qj(j=1,2,3,…)。

根據(jù)同步鏡像特點則有：

推論1：主節(jié)點寫請求Qi與從節(jié)點訪問相同地址的寫請求qj為關(guān)聯(lián)請求的充要條件是i=j。

識別關(guān)聯(lián)請求的關(guān)鍵是探尋i=j的充分條件。由數(shù)理邏輯可知：

i=j?i+1>j&&j+1>i

(1)

只需要探尋i+1≤j‖j+1≤i的必要條件。由此結(jié)合訪問某邏輯地址的當前寫請求與其后繼寫請求的時間屬性，我們給出了寫請求版本定義，該版本同樣是寫請求所包含數(shù)據(jù)對象的版本。

定義1：存儲節(jié)點上一個邏輯數(shù)據(jù)卷中的任意邏輯塊B，在當前節(jié)點對其數(shù)據(jù)進行更新的寫請求Qi的版本表示為：

(1) Ai：Qi在當前節(jié)點發(fā)生的精確系統(tǒng)時間；

(2) Ci：Qi在當前節(jié)點完成的精確系統(tǒng)時間；

(3) Ai+1：寫請求Qi+1在當前節(jié)點發(fā)生的精確系統(tǒng)時間。

2.2.2 精確時間版本識別

假設(shè)主、從節(jié)點訪問相同邏輯塊B的任意兩個寫請求，Qi:<(Ai，Ci，Ai+1>, qj:< aj，cj，aj+1>，我們以Qi與qj為參照論證關(guān)聯(lián)請求版本識別方法。論證分為三步：論證i+1≤j的必要條件；論證j+1≤i的必要條件；論證i=j的充分條件。

(1) i+1≤j的必要條件：

i+1≤j時，Qi+1，Qj，qj在主、從節(jié)點的邏輯時序如圖 2(a)。參數(shù)說明：[d]為網(wǎng)絡(luò)傳輸延遲；[δ]為DN與PN當前時鐘誤差；[Δm]為寫緩存時間。

圖2 關(guān)聯(lián)請求邏輯時序

由時序圖可得推導式：

(2)

即 Ai+1

(2) j+1≤i的必要條件：

j+1≤i時，Qi，qi，qj+1在主、從節(jié)點的邏輯時序如圖 2(b)，則有推導式：

(3)

即aj+1

由式(1)、(2)得推導式：

(i+1≤j)‖(j+1≤i)?(Ai+1

(aj+1

(4)

即(Ai+1

(3) i=j的充分條件：

式(4)的逆否命題成立，即有

(j+1)>i?i=j

(5)

由此得：定理1：(Ai+1≥cj+δ)&&(aj+1≥Ci+δ)?i=j

□

證畢。

2.2.3 節(jié)點故障恢復

首先，定理1的前提是一個數(shù)據(jù)卷中同一邏輯地址的寫請求串行地進入存儲節(jié)點，通過調(diào)研dm-raid1、md-raid1等常用的鏡像實現(xiàn)方式，我們發(fā)現(xiàn)在鏡像恢復過程中會阻塞對正在恢復的邏輯地址的應(yīng)用寫更新，直到該邏輯地址恢復完成，即對于同一邏輯地址數(shù)據(jù)恢復請求與應(yīng)用寫請求是串行的。其次，鏡像恢復時將恢復窗口內(nèi)地址的最新版本數(shù)據(jù)同步到接替節(jié)點。最后，新節(jié)點接入后集群恢復以RAID-set為單元并發(fā)執(zhí)行。我們以一個RAID-set中的數(shù)據(jù)節(jié)點恢復和校驗節(jié)點恢復為例分別論證。

(1) 數(shù)據(jù)節(jié)點恢復

證明：

(6)

上述推導式結(jié)合時序圖可得：

(7)

2) DN′1的恢復數(shù)據(jù)不會誤判為PN的任意新版本數(shù)據(jù)(即i

i

(8)

3) 結(jié)論:綜合DN恢復時的兩種情況則有i≠j?iAi+1)||Ci+δ>aj+1。

證畢?！?/p>

圖3 DN′恢復的請求時序圖

(2) 校驗節(jié)點恢復

假設(shè)RAID-set中PN故障(見圖 1)，接替節(jié)點為PN′，恢復開始是PN′與兩個DN時鐘均同步；DV1卷中的任意邏輯塊B，在DN1有寫請求Qi: ，在PN′有恢復請求qj:；Qi與qj對應(yīng)不同的數(shù)據(jù)對象。

證明：

1) PN′的恢復數(shù)據(jù)不會誤判為DN1的任意舊版本數(shù)據(jù)(即j>i)。

假設(shè)DN1在Tr時刻恢復邏輯塊B數(shù)據(jù)到PN′，PN′的恢復請求qj:對應(yīng)恢復時刻的最新數(shù)據(jù)，在DN1與qj對應(yīng)的應(yīng)用寫請求Qj:較Qi晚到達存儲節(jié)點。邏輯時序關(guān)系見圖4(a)，則有推導式：

Ai+1≤Aji)

?Ai+1

?Ai+1

(9)

即有j>i?Ai+1

2) PN′的恢復數(shù)據(jù)不會誤判為DN1的任意新版本數(shù)據(jù)(即j

根據(jù)鏡像恢復邏輯在邏輯塊B恢復時刻DN1的最新更新對應(yīng)Qj，而Qi為恢復完成后到達的某一應(yīng)用寫請求，邏輯時序見圖4(b)，有推導式：

aj+1≤ai(∵j

?aj+1≤ci-Δm(∵ai=ci-Δm)

?aj+1≤Ci-Δm-d?δ(∵ci=Ci-d?δ)

?aj+1

(10)

圖4 PN節(jié)點恢復請求時序圖

即有j

3) 結(jié)論：綜合PN恢復時的兩種情景則有i≠j?iAi+1)||Ci+δ>aj+1。

證畢?！?/p>

(3) 結(jié)論

綜合集群故障恢復時RAID-set中DN恢復與PN恢復兩種情況，對于任意兩個數(shù)據(jù)對象不一致的恢復寫請求與應(yīng)用寫請求均滿足推導式：

i≠j?iAi+1)‖Ci+δ>aj+1

(11)

由此證明集群恢復過程中新節(jié)點的鏡像恢復請求不會誤判為正常服務(wù)節(jié)點的任一不相關(guān)聯(lián)的寫請求。進而根據(jù)數(shù)理邏輯則可知集群恢復狀態(tài)下定理1同樣成立。

2.3 應(yīng)用局限性

定理1表明通過比較鏡像節(jié)點間請求的精確物理時間戳來識別關(guān)聯(lián)請求的方法理論上可行，實際應(yīng)用中仍存在以下局限性：

局限1：保證數(shù)據(jù)與版本一致須將數(shù)據(jù)更新與版本更新綁定，當緩存數(shù)據(jù)合并時，精確物理時間版本合并違背定義1語義。

局限2：定義1與定理1依賴于后繼應(yīng)用寫請求到達的精確物理時間，因而版本識別須在后繼寫請求發(fā)生之后進行，否則請求版本不完整。

針對上述兩方面局限性，本文提出了泛化時間戳版本理論。

2.4 基于泛化時間戳的版本機制

2.4.1 泛化時間戳版本定義

2.4.2 泛化時間戳版本識別

證明：

假設(shè)Qi, qj的精確物理時間屬性分別為(Ai, Ci, Ai+1)，(aj, cj, aj+1)，由定義2，則有

因此有

證畢?！?/p>

2.5 應(yīng)用局限性解決

2.5.1 版本合并方法

基于定義2提出了版本合并方法解決局限1，使得存儲層數(shù)據(jù)合并時，新舊版本同時合并。版本合并須保證定理2適用，須滿足兩個條件：

(1) 合并后版本是新數(shù)據(jù)的合法泛化時間版本，即符合定義2語義。

(2) Ai對應(yīng)同一邏輯塊寫請求Qi-1的后繼寫請求的泛化發(fā)生時間。

版本合并方法：假設(shè)任意邏輯塊B當前版本為，后繼寫請求版本為，邏輯塊B數(shù)據(jù)合并時，兩個版本項按如下規(guī)則合并：{Ai=MIN(Ai, Ai+1); Ci+1=MAX(Ci, Ci+1);Ai+2=Ai+2;}< Ai, Ci+1, Ai+2>作為新版本覆蓋舊版本。

證明：

假設(shè)兩個待合并的泛化時間版本對應(yīng)的精確時間版本分別為和，根據(jù)定義2則有Ai≤ai≤ai+1, Ci+1≥ci+1, Ai+2≤ai+2，再根據(jù)推論2可得是合并后數(shù)據(jù)的合法版本。

版本合并前，Ai是Qi-1后繼寫請求的泛化發(fā)生時間，每次版本合并均保留Ai，即新版本可以保證當前版本中請求到達時間為Qi-1的后繼寫請求的泛化到達時間。

因此新版本符合定理2適用的兩個條件。

證畢。□

2.5.2 后繼寫請求時間擴展

推理1：假設(shè)任意邏輯塊B的某一版本，若進行版本比較時Ai+1=NULL，則取Ai+1=SYScurrent.。

證明：

假設(shè)Qi+1發(fā)生的精確時間為Anext(Anext或趨于∞)，則有Ai+1≤Anext，因此Ai+1時間符合定義2語義，即該版本合法且定理2適用。

證畢?！?/p>

2.6 小 結(jié)

論證結(jié)果表明，利用物理時間戳版本解決BW-RAID中鏡像節(jié)點間的數(shù)據(jù)版本識別問題是理論可行的，通過對物理時間戳做泛化擴展可以滿足實際系統(tǒng)的需求，基于此形成了基于泛化時間戳的分布式異步版本識別機制。該版本機制優(yōu)點是：(1)易于實現(xiàn)，不需要冗余組內(nèi)的節(jié)點時間保持完全同步，允許節(jié)點間存在合理的時間誤差，時間同步難度和開銷降低。(2)時間復雜度低，其實現(xiàn)的時間復雜度主要是版本生成及更新時檢索版本項的時間消耗，本文的原型系統(tǒng)中將使用基樹(Radix tree)管理版本項，查找操作的時間復雜度為O(h)，h為基樹高度，在64位x86平臺的Linux操作系統(tǒng)中基樹最大高度僅為16。

3 原型實現(xiàn)及評測

3.1 原型系統(tǒng)實現(xiàn)

本文以BW-RAID原型系統(tǒng)為基礎(chǔ)，實現(xiàn)了版本子系統(tǒng)，該系統(tǒng)包括四個功能模塊：(1)組內(nèi)全局版本管理模塊，定時更新全局邏輯版本號，并向組內(nèi)各成員同步全局版本；(2)本地系統(tǒng)版本更新模塊，接收并更新全局邏輯版本號，定時更新本地版本序列號，將全局版本與邏輯版本組合產(chǎn)生節(jié)點當前系統(tǒng)版本；(3)請求版本生成及更新模塊，寫請求到達節(jié)點時為其生成版本，對于已存在舊版本的邏輯塊，執(zhí)行版本合并；(4)版本識別模塊，鎖定待比較邏輯塊版本，并執(zhí)行版本比較；該模塊包含inline和offline兩個版本識別線程；inline線程在校驗節(jié)點執(zhí)行冗余計算時與數(shù)據(jù)卷對應(yīng)的數(shù)據(jù)節(jié)點交換版本，并進行對應(yīng)邏輯塊的版本識別；offline線程對冗余計算時寫入PN暫存的邏輯塊進行后臺識別。

BW-RAID系統(tǒng)中引入分布式異步版本識別機制使得RAID-set冗余模式轉(zhuǎn)換可以與應(yīng)用數(shù)據(jù)更新異步。冗余模式轉(zhuǎn)換過程是先更新校驗碼，然后同時對即將轉(zhuǎn)換的邏輯塊進行版本比較，若版本一致則將DN緩存中的數(shù)據(jù)遷移到數(shù)據(jù)存儲卷；若版本不一致PN的數(shù)據(jù)暫存入本節(jié)點磁盤緩存中，監(jiān)測到一致版本后DN再進行數(shù)據(jù)遷移，并釋放在PN占用的磁盤緩存資源。

本文對配置分布式異步版本識別機制的BW-RAID原型系統(tǒng)進行了評測。測試環(huán)境包括一個客戶端和三個存儲節(jié)點，節(jié)點物理配置見表 1。本文在三個存儲節(jié)點上搭建了只有一個RAID-set的簡易集群，在客戶端為每個數(shù)據(jù)卷配置主、從訪問路徑，可以分別通過DN和PN讀寫數(shù)據(jù)，默認主路徑為活躍路徑；客戶端節(jié)點作為組內(nèi)時鐘服務(wù)器。

表1 硬件環(huán)境配置

3.2 數(shù)據(jù)可用性驗證

數(shù)據(jù)正確性是指BW-RAID系統(tǒng)中配置分布式異步版本識別機制后，客戶端寫入邏輯卷的數(shù)據(jù)與從該卷讀出的數(shù)據(jù)須一致，即可用性。綜合RAID-set的狀態(tài)，可用性包括三方面：(1)客戶端寫入到存儲端的數(shù)據(jù)可用；(2)數(shù)據(jù)節(jié)點故障時數(shù)據(jù)可用；(3)節(jié)點故障恢復完成后，恢復到新節(jié)點的數(shù)據(jù)可用。

測試方法：客戶端將邏輯卷格式化為ext3文件系統(tǒng)并掛載，復制2GB大小的文件和1.5GB大小的目錄(包含3個子目錄)到掛載目錄；分別通過主路徑(master path)和從路徑(slave path)訪問存儲節(jié)點，計算復制文件與源文件的md5校驗值，對比一致性，執(zhí)行diff操作對比復制目錄與源目錄的一致性。通過主、從路徑讀RAID-set中數(shù)據(jù)卷的請求流向見圖 5。

圖5 讀請求流向

綜合數(shù)據(jù)可用性所涉及的三方面，進行以下測試：

(1) 冗余組正常狀態(tài)下，從DV1、DV2各自主路徑讀取數(shù)據(jù)，比較一致性；

(2) DN1故障，由DV1卷從路徑讀取數(shù)據(jù)，比較一致性；

(3) DN1故障恢復完成后，由DV1主路徑讀取數(shù)據(jù)，比較一致性；

(4) PN故障恢復完成后，將DV2或者DV1的訪問路徑切換到從路徑讀取數(shù)據(jù)，比較一致性。

對于上述4種測試，復制文件、目錄與源文件、目錄均一致，說明異步版本機制可以保證數(shù)據(jù)可用性，進而達到保證冗余組一致性的目標。

3.3 有效性驗證

有效性評價測試使用基準測試工具FIO進行存儲壓力測試和應(yīng)用負載重播。存儲系統(tǒng)參數(shù)配置見表2。

表2 系統(tǒng)參數(shù)

本節(jié)評測中以sync模式的BW-RAID作為對比基準，其特點是冗余模式時阻塞寫IO保證節(jié)點間緩存同步以解決一致性問題，具體過程是：首先阻塞客戶端對邏輯塊B所在條帶的寫更新，并等待該條帶上所有寫更新完成；然后計算、更新RAID4校驗碼，并進行數(shù)據(jù)遷移。

3.3.1 存儲壓力評測

存儲壓力評測，在邏輯卷上執(zhí)行指定請求粒度的順序?qū)憸y試。測試分別在sync和async兩種模式的BW-RAID中進行，評價指標為校驗節(jié)點的IO負載開銷和系統(tǒng)吞吐量。

(1) 測試方法：在客戶端以direct方式向邏輯卷順序?qū)懭?28GB數(shù)據(jù)，每5秒記錄一次帶寬作為實時帶寬。分別對4kB、64kB、1024kB三種請求粒度進行測試對比。sync模式在校驗存儲節(jié)點不產(chǎn)生IO開銷，只記錄帶寬；對async模式，同時記錄校驗節(jié)點冗余模式轉(zhuǎn)換時寫本地磁盤緩存的IO數(shù)量，及版本比較時鎖定版本導致阻塞的IO數(shù)量。

校驗節(jié)點IO負載(圖6)的結(jié)果表明：(1)三種粒度的順序?qū)憸y試中版本識別率均高于99%，最高達99.69%；(2)由于inline線程中版本比較不一致在PN產(chǎn)生的IO開銷為0.31%～0.85%；async模式下4kB粒度用例中不一致版本比例最高，原因在于緩存資源管理粒度是64kB，同一緩存塊被多次更新，多次被回寫，導致DN與PN緩存的數(shù)據(jù)在某些時刻存在不一致的情況。其它兩個用例中每個緩存塊被寫一次，即只有一個版本，此時不一致版本屬于漏判。冗余計算過程中inline線程不能識別的版本轉(zhuǎn)入后臺識別模式，三個用例的結(jié)果顯示不一致數(shù)據(jù)對象均完成版本識別，遷移到了共享數(shù)據(jù)卷，在PN所占用的磁盤緩存資源也釋放。由此可以得出分布式異步版本識別機制在順序?qū)憫?yīng)用中可以通過版本識別實現(xiàn)識別一致數(shù)據(jù)對象的目標。

圖6 校驗節(jié)點IO負載

(2)結(jié)果分析：

(1)4kB粒度用例，兩種模式實時帶寬接近， async模式平均帶寬比sync模式下降2.70%，其原因是資源管理粒度為64kB，async模式下存儲節(jié)點最多16個請求競爭同一邏輯塊版本執(zhí)行版本合并操作，因此帶寬略有降低(圖7)。

圖7 4kB實時帶寬

(2)64kB粒度用例，async實時帶寬明顯優(yōu)于sync模式，平均帶寬提升25.43%，校驗存儲節(jié)點IO負載僅增加0.31%(圖8)。

圖8 64kB實時帶寬

(3)1024kB粒度用例，async模式實時帶寬抖動明顯，峰值帶寬高于sync模式，通過分析我們發(fā)現(xiàn)此時因版本比較而阻塞的請求數(shù)量明顯上升，分別是4kB和64kB的14倍和17倍，阻塞請求增加導致系統(tǒng)吞吐量不穩(wěn)定(圖9)。

圖9 1024kB實時帶寬

順序?qū)懫骄鶐拰Ρ纫姳?

表3 順序?qū)憣Ρ?/p>

3.3.2 應(yīng)用負載重播評測

應(yīng)用負載重播，在async模式下重播應(yīng)用trace驗證版本識別機制的有效性，評測指標：(1)inline線程與offline線程結(jié)合是否可以識別所有版本；(2)inline線程識別的版本比例及校驗存儲節(jié)點數(shù)據(jù)小盤IO負載。

測試方法：在async模式下重播open-mail應(yīng)用中寫請求比例高于50%的1#-3#trace，三個trace中小于8kB的寫請求均比例均高于90%，故在本小節(jié)中選取了4kB的資源管理粒度。

結(jié)果表明三個trace重播完成后，所有數(shù)據(jù)均完成冗余模式轉(zhuǎn)換，即隨著測試的進行版本均可以識別。上述三個應(yīng)用中inline線程不能識別的版本接近40%，那么相對于sync模式PN平均約增加了40%的IO負載(圖10)。

圖10 校驗節(jié)點IO負載

根據(jù)本文版本識別理論，同一邏輯塊重復被寫，并且每次寫間隔小于系統(tǒng)設(shè)置的最小可識別間隔是導致版本不可識別的主要原因。對此我們也分別分析了三個trace的覆蓋寫請求比例及對同一邏輯塊覆蓋寫時間間隔(見表 4)。

表4 覆蓋寫比例

三個trace中均有55%以上的邏輯塊被重復寫，并且覆蓋寫請求比例均高于80%。然而重復寫請求間隔小于配置的可識別間隔(5ms)的比例僅在10%左右，評測結(jié)果與應(yīng)用特點不完全相符。原因在于本文使用了基準測試工具FIO重播，其特點是僅按照請求原有序列模擬IO，并不考慮原有請求實際到達的相對時間，即忽略了應(yīng)用原有請求時間屬性。應(yīng)用重復寫比例高，請求間隔被忽略導致不可識別的版本比例升高。

4 結(jié) 論

本文針對BW-RAID異步冗余計算面臨的冗余一致性問題，以WACE為研究基礎(chǔ)提出了一種分布式節(jié)點數(shù)據(jù)版本識別方法，該方法以泛化分布式時間戳思想為基礎(chǔ)實現(xiàn)了分布式鏡像節(jié)點中同一邏輯塊的數(shù)據(jù)對象一致性比較，其主要特點是：(1)可以轉(zhuǎn)換為物理時間與邏輯時間結(jié)合的版本實現(xiàn)方式；(2)組內(nèi)每個節(jié)點可以獨立維護本節(jié)點系統(tǒng)版本且系統(tǒng)版本更新與IO解耦合，組內(nèi)節(jié)點間版本傳遞開銷降低，適用于Iscsi等通用塊層傳輸協(xié)議；(3)可以通過比較版本確定邏輯塊(或請求)所包含數(shù)據(jù)是否相同，滿足BW-RAID冗余模式轉(zhuǎn)換對數(shù)據(jù)一致性識別的要求。實驗表明，該方法可以有效識別鏡像關(guān)聯(lián)請求，降低組內(nèi)網(wǎng)絡(luò)開銷。

然而應(yīng)用負載評測表明在覆蓋寫密集的應(yīng)用中校驗節(jié)點IO開銷明顯增大，同時隨著系統(tǒng)數(shù)據(jù)容量增大維護版本產(chǎn)生的資源開銷也隨之增加，對于提高版本識別比例、降低版本維護資源開銷等問題需要做進一步的研究及驗證。

[1] 那文武, 柯劍, 朱旭東等. BW-netRAID: 一種后端集中冗余管理的網(wǎng)絡(luò)RAID系統(tǒng). 計算機學報, 2011, 34(5): 912-923

[2] Noble M. EMC Isilon OneFS-A Technical Overview . http://www.emc.com/collateral/hardware/white-papers/: EMC Corporation. 2012

[3] Welch B, Unangst M, Abbasi Z, et al. Scalable performance of the Panasas parallel file system. In: Proceedings of the 6th USENIX Conference on File and Storage Technologies, Berkeley, USA, 2008. 17-33

[4] Fan, B, Tantisiriroj W, Lin X, et al. DiskReduce: RAID for data-intensive scalable computing. In: Proceedings of the 4th Annual Workshop on Petascale Data Storage, New York, USA, 2009. 6-10

[5] 李瑋瑋.BW-RAID系統(tǒng)中數(shù)據(jù)版本管理的研究: [碩士學位論文].北京:中國科學院計算技術(shù)研究所，2011. 9-40

[6] Kulkarni P, Douglis F, LaVoie J, et al. Tracey. Redundancy elimination within large collections of files. In: Proceedings of the General Track:2004 USENIX Annual Technical Conference, Boston, USA, 2004. 59-72

[7] Policroniades C, Pratt I. Alternatives for detecting redundancy in storage systems data. In: Proceedings of the General Track:2004 USENIX Annual Technical Conference, Boston, USA, 2004. 73-86

[8] Jain N, Dahlin M, Tewari R. TAPER: Tiered approach for eliminating redundancy in replica synchronization. In: Proceedings of the 4th USENIX Conference on File and Storage Technologies, San Francisco, USA, 2005. 281-294

[9] Zhu B, Li K, Patterson H. Avoiding the disk bottleneck in the data domain deduplication file system. In: Proceedings of the 6th USENIX FAST, San Jose, USA, 2008. 69-282

[10] Koller R, Rangaswami R. I/O deduplication: utilizing content similarity to improve I/O performance. In: Proceedings of the 8th USENIX Conference on File and Storage Technologies, San Jose, USA, 2010. 211-224

[11] Ungureanu C, Atkin B, Aranya A, et al. HydraFS: a high-throughput file system for the HYDRAstor content-addressable storage system. In: Proceedings of the 8th USENIX Conference on File and Storage Technologies, San Jose, USA, 2010. 225-238

[12] Kruus E, Ungureanu C, Dubnicki C. Bimodal content defined chunking for backup streams. In: Proceedings of the 8th USENIX Conference on File and Storage Technologies, San Jose, USA, 2010. 239-252

[13] Srinivasan K, Bisson T, Goodson G, et al. iDedup: latency-aware, inline data deduplication for primary storage. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies, San Jose, USA, 2012. 299-312

[14] Lillibridge M, Eshghi K, Bhagwat D. Improving restore speed for backup systems that use inline chunk-based deduplication. In: Proceedings of the 11th USENIX Conference on File and Storage Technologies, San Jose, USA, 2013.183-198

[15] Strzelczak P, Adamczyk E, Herman-Izycka U, et al. Concurrent deletion in a distributed content-addressable storage system with global deduplication. In: Proceedings of the 11th USENIX Conference on File and Storage Technologies, San Jose, USA, 2013. 161-174

[16] Scott C, Liu H. Sgit community book. http: //gitbook. liuhui998.com: Git Community. 2011

[17] Ben C S, Brian W, Fitzpatrick C. Michael Pilato. Svn-book. http://svnbook. red-bean.com:Creative Commons, 2008

[18] Lamport L. Time, clocks, and the ordering of events in a distributed system.CommunicationsoftheACM, 1978,21(7): 558-565

[19] DeCandia G, Hastorun D, Jampani M, et al. Dynamo: amazon’s highly available key-value Store. In: Proceedings of the 21st ACM Symposium on Operating Systems Principles, Stevenson, USA, 2007. 205-220

[20] 司承祥.集中共享存儲環(huán)境中緩存集群的關(guān)鍵技術(shù)研究:[博士學位論文]. 北京：中國科學院計算技術(shù)所，2011. 25-28

Distributed and asynchronous version identification mechanism for BW-RAID system

Wang Hui***, Guo Mingyang*, Dong Huanqing*, Xu Lu*

(*Institute of Computing Technology, Chinese Academy of Science, Beijing 100190)(**University of Chinese Academy of Sciences, Beijing 100049)

To solve the BW-RAID system’s problem of cache data version identification during its data redundant mode conversion from mirror to RAID4, a distributed and asynchronous version identification mechanism is presented. This version identification mechanism generates a new version for a logical block in a mirrored volume when its data are updated, and during the redundant mode conversion, checks whether this logic block’s data cached in two mirroring notes are consistent by comparing the versions between mirroring nodes, and if consistent, makes the data move to the data volume, otherwise stores them to disk caches temporarily to guarantee system redundant consistency. It was proved by experiments that the mechanism can identify consistent data for all blocks in any state, including normal, degraded, and recovery states. The sequential writing tests showed it improved the average bandwidth up to 25.43% with the storage overhead less than 1% compared to cache synchronization mode. The open-mail workloads replay tests showed, the storage loads were less than 40%, and the blocks updated finished redundant conversion as each workload replay ended. The proposed mechanism is essential to guaranteeing redundant consistency while improving storage space utilization in BW-RAID.

network RAID, data consistency, distributed and asynchronous version, time-interval-based timestamp, version identification

10.3772/j.issn.1002-0470.2016.03.003

①863計劃(2013AA013205)和中國科學院重點部署課題(KGZD-EW-103-5(7))資助項目。

2015-10-20)

②女，1981年生，博士生；研究方向：網(wǎng)絡(luò)存儲和分布式系統(tǒng)冗余一致性；聯(lián)系人，E-mail: wanghui@nrchpc.ac.cn(