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

王 慧 郭明陽 董歡慶 許 魯

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

?

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

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

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

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

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

0 引 言

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

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

1 背 景

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

圖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é)點(diǎn)又有網(wǎng)絡(luò)開銷。

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

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

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

2 分布式異步版本識(shí)別

2.1 概念

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

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

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

2.2 基于精確時(shí)間的版本識(shí)別

2.2.1 精確時(shí)間版本定義

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

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

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

識(shí)別關(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é)合訪問某邏輯地址的當(dāng)前寫請求與其后繼寫請求的時(shí)間屬性，我們給出了寫請求版本定義，該版本同樣是寫請求所包含數(shù)據(jù)對象的版本。

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

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

(2) Ci：Qi在當(dāng)前節(jié)點(diǎn)完成的精確系統(tǒng)時(shí)間；

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

2.2.2 精確時(shí)間版本識(shí)別

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

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

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

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

由時(shí)序圖可得推導(dǎo)式：

(2)

即 Ai+1

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

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

(3)

即aj+1

由式(1)、(2)得推導(dǎo)式：

(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é)點(diǎn)故障恢復(fù)

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

(1) 數(shù)據(jù)節(jié)點(diǎn)恢復(fù)

證明：

(6)

上述推導(dǎo)式結(jié)合時(shí)序圖可得：

(7)

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

i

(8)

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

證畢?！?/p>

圖3 DN′恢復(fù)的請求時(shí)序圖

(2) 校驗(yàn)節(jié)點(diǎn)恢復(fù)

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

證明：

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

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

Ai+1≤Aji)

?Ai+1

?Ai+1

(9)

即有j>i?Ai+1

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

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

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é)點(diǎn)恢復(fù)請求時(shí)序圖

即有j

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

證畢?！?/p>

(3) 結(jié)論

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

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

(11)

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

2.3 應(yīng)用局限性

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

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

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

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

2.4 基于泛化時(shí)間戳的版本機(jī)制

2.4.1 泛化時(shí)間戳版本定義

2.4.2 泛化時(shí)間戳版本識(shí)別

證明：

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

因此有

證畢?！?/p>

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

2.5.1 版本合并方法

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

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

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

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

證明：

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

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

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

證畢?！?/p>

2.5.2 后繼寫請求時(shí)間擴(kuò)展

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

證明：

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

證畢?！?/p>

2.6 小 結(jié)

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

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

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

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

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

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

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

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

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

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

圖5 讀請求流向

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

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

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

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

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

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

3.3 有效性驗(yàn)證

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

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

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

3.3.1 存儲(chǔ)壓力評測

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

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

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

圖6 校驗(yàn)節(jié)點(diǎn)IO負(fù)載

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

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

圖7 4kB實(shí)時(shí)帶寬

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

圖8 64kB實(shí)時(shí)帶寬

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

圖9 1024kB實(shí)時(shí)帶寬

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

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

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

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

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

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

圖10 校驗(yàn)節(jié)點(diǎn)IO負(fù)載

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

表4 覆蓋寫比例

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

4 結(jié) 論

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

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

[1] 那文武, 柯劍, 朱旭東等. BW-netRAID: 一種后端集中冗余管理的網(wǎng)絡(luò)RAID系統(tǒng). 計(jì)算機(jī)學(xué)報(bào), 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ù)版本管理的研究: [碩士學(xué)位論文].北京:中國科學(xué)院計(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] 司承祥.集中共享存儲(chǔ)環(huán)境中緩存集群的關(guān)鍵技術(shù)研究:[博士學(xué)位論文]. 北京：中國科學(xué)院計(jì)算技術(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計(jì)劃(2013AA013205)和中國科學(xué)院重點(diǎn)部署課題(KGZD-EW-103-5(7))資助項(xiàng)目。

2015-10-20)

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