基于糾刪碼的云存儲(chǔ)數(shù)據(jù)可靠性保障

王芳芳

摘要摘要：云存儲(chǔ)系統(tǒng)由于其系統(tǒng)復(fù)雜性和業(yè)務(wù)特征，使數(shù)據(jù)可靠性受到嚴(yán)重挑戰(zhàn)。針對(duì)云計(jì)算環(huán)境下帶數(shù)據(jù)去重的云存儲(chǔ)系統(tǒng)的內(nèi)部數(shù)據(jù)保護(hù)問題，提出一種基于糾刪碼的數(shù)據(jù)可靠性保障機(jī)制，采用多種糾刪編碼算法及配置方法對(duì)去重?cái)?shù)據(jù)塊進(jìn)行編碼保護(hù)。該機(jī)制具有良好的綜合性能與可擴(kuò)展性。

關(guān)鍵詞關(guān)鍵詞：云存儲(chǔ)；數(shù)據(jù)可靠性；糾刪碼；數(shù)據(jù)去重

DOIDOI：10.11907/rjdk.1431041

中圖分類號(hào)：TP309.2

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）004013702

0引言

云存儲(chǔ)是云計(jì)算服務(wù)商提供的一種IaaS模式的基礎(chǔ)服務(wù)，其通過硬件集群、高速內(nèi)聯(lián)網(wǎng)絡(luò)以及分布式文件系統(tǒng)等資源和技術(shù)，將大量設(shè)備中的存儲(chǔ)資源整合成一個(gè)整體，共同對(duì)外提供基于網(wǎng)絡(luò)的數(shù)據(jù)存取服務(wù)。它的業(yè)務(wù)特點(diǎn)是向外界提供統(tǒng)一、透明的數(shù)據(jù)操作接口，將所有的分布式存儲(chǔ)細(xì)節(jié)都封裝在系統(tǒng)內(nèi)部[1]。

目前多數(shù)云存儲(chǔ)系統(tǒng)（網(wǎng)盤、云空間等）為控制系統(tǒng)規(guī)模，降低系統(tǒng)建設(shè)和管理成本，均采用了數(shù)據(jù)去重技術(shù)來壓縮數(shù)據(jù)量。鑒于其它種類云存儲(chǔ)系統(tǒng)的數(shù)據(jù)保護(hù)要求較為簡單，現(xiàn)有機(jī)制已經(jīng)能夠很好地滿足需要。因此，本文針對(duì)這種帶數(shù)據(jù)去重的云存儲(chǔ)系統(tǒng)，對(duì)如何保障其內(nèi)部數(shù)據(jù)可靠性進(jìn)行了研究。

針對(duì)去重系統(tǒng)的數(shù)據(jù)可靠性保障，傳統(tǒng)做法包括使用更加可靠的底層存儲(chǔ)設(shè)施（如RAID陣列），以及對(duì)重要的數(shù)據(jù)塊保留更多副本[2]。前者部署方便，對(duì)上層透明，但是容錯(cuò)能力差、恢復(fù)過程慢；后者容錯(cuò)能力強(qiáng)、恢復(fù)過程快，但空間占用多、帶寬消耗量大、成本高。因此，這兩種技術(shù)僅對(duì)小規(guī)模存儲(chǔ)系統(tǒng)以及數(shù)據(jù)量不太大的核心業(yè)務(wù)較為實(shí)用。對(duì)于云存儲(chǔ)這種大規(guī)模分布式存儲(chǔ)系統(tǒng)而言，由于其節(jié)點(diǎn)數(shù)量和數(shù)據(jù)規(guī)模極其龐大，如果每個(gè)節(jié)點(diǎn)都采用高端設(shè)備，或者系統(tǒng)整體采用復(fù)制冗余機(jī)制，均會(huì)導(dǎo)致整體成本的極大增長，使建設(shè)和使用這類系統(tǒng)變得難以承受，從而失去實(shí)用性[3]。相對(duì)于各類本地存儲(chǔ)系統(tǒng)，云存儲(chǔ)系統(tǒng)內(nèi)部的數(shù)據(jù)重要性高但活躍度較低，因此有條件在系統(tǒng)內(nèi)使用較為復(fù)雜的糾刪碼來保護(hù)數(shù)據(jù)，以便在存儲(chǔ)成本和可靠性間達(dá)到更好的平衡。為此，本文采用多種不同的糾刪碼算法及配置方法對(duì)去重?cái)?shù)據(jù)塊進(jìn)行靜態(tài)編碼，并提出了基于糾刪碼的云存儲(chǔ)系統(tǒng)數(shù)據(jù)可靠性保障機(jī)制（Reliability Guarantee Mechanism for Deduplication Cloud Storage，RGMDCS）。

1糾刪碼選取

1.1ReedSolomon編碼

ReedSolomon編碼（下稱RS編碼）是目前使用最廣泛的糾刪碼之一。RS編碼同時(shí)具有MDS屬性和系統(tǒng)屬性，因此它編碼生成的n個(gè)編碼數(shù)據(jù)片段包含m個(gè)原始數(shù)據(jù)片段以及n-m個(gè)校驗(yàn)數(shù)據(jù)片段，其中任意片段丟失后均可使用任意m個(gè)存留的片段來恢復(fù)。

RS編碼的編碼過程可由式（1）描述：

1.2Tornado編碼

Tornado編碼不具有MDS屬性，但具有系統(tǒng)屬性。Tornado編碼的編解碼操作計(jì)算開銷較小，而且用到的節(jié)點(diǎn)數(shù)目也較少。因此，Tornado編碼比傳統(tǒng)的MDS糾刪碼具有更快的運(yùn)算速度，其數(shù)據(jù)修復(fù)過程需要更小的數(shù)據(jù)傳輸量，非常適合大規(guī)模的分布式存儲(chǔ)系統(tǒng)。

2靜態(tài)密碼策略

2.1設(shè)計(jì)方案

考慮到云存儲(chǔ)系統(tǒng)面對(duì)的數(shù)據(jù)具有復(fù)雜性和多樣性，RGMDCS系統(tǒng)采用了Rabin Fingerprinting算法對(duì)數(shù)據(jù)進(jìn)行變長分塊。然而，相關(guān)研究表明，若使用變長分塊算法對(duì)文件進(jìn)行分塊去重，由于數(shù)據(jù)塊大小不同且都比較?。ㄍǔ閹资止?jié)到幾百KB），在存儲(chǔ)節(jié)點(diǎn)中將數(shù)據(jù)塊直接存儲(chǔ)會(huì)大大增加設(shè)備中的磁盤碎片，導(dǎo)致其訪問效率低下，造成系統(tǒng)性能產(chǎn)生較大程度下降[4]。針對(duì)這一矛盾，RGMDCS將多個(gè)變長的數(shù)據(jù)包打包成較大的定長對(duì)象（Object，一般為幾MB）進(jìn)行存儲(chǔ)和管理，定長對(duì)象的大小根據(jù)不同的應(yīng)用場(chǎng)景和相關(guān)實(shí)踐來配置。數(shù)據(jù)塊（Chunk）是存儲(chǔ)節(jié)點(diǎn)的最小數(shù)據(jù)訪問單元，通過對(duì)應(yīng)的數(shù)據(jù)塊標(biāo)識(shí)符（Chunk ID）進(jìn)行訪問。根據(jù)數(shù)據(jù)塊的不同大小，各個(gè)定長對(duì)象包含不同數(shù)量的數(shù)據(jù)塊。當(dāng)從服務(wù)接口接收到新的數(shù)據(jù)塊時(shí)，存儲(chǔ)節(jié)點(diǎn)先將積攢的變長數(shù)據(jù)塊打包成固定大小的對(duì)象。如果定長對(duì)象當(dāng)前所剩空間不夠放置后續(xù)數(shù)據(jù)塊，則剩余空間填0（Padding），后續(xù)數(shù)據(jù)塊新開一個(gè)對(duì)象繼續(xù)放置。隨后存儲(chǔ)節(jié)點(diǎn)對(duì)這些對(duì)象進(jìn)行分組并用糾刪編碼算法對(duì)分組進(jìn)行編碼，生成編碼對(duì)象組（包含原始對(duì)象和校驗(yàn)對(duì)象），最后將編碼對(duì)象組內(nèi)的所有對(duì)象分布到不同的節(jié)點(diǎn)上存儲(chǔ)。

2.2系統(tǒng)業(yè)務(wù)流程

RGMDCS系統(tǒng)的服務(wù)接口接收到客戶提交的待存文件后，其分塊邏輯則會(huì)使用Rabin Fingerprinting算法將文件切割成互不重疊的變長數(shù)據(jù)塊，再使用特定的哈希算法對(duì)數(shù)據(jù)塊內(nèi)容進(jìn)行計(jì)算，用得到的結(jié)果值作為數(shù)據(jù)塊標(biāo)識(shí)符，并將這些標(biāo)識(shí)符傳給業(yè)務(wù)處理模塊。業(yè)務(wù)處理模塊將數(shù)據(jù)塊標(biāo)識(shí)符與元數(shù)據(jù)管理模塊中所有已知數(shù)據(jù)塊的標(biāo)識(shí)符進(jìn)行比較。如果標(biāo)識(shí)符已經(jīng)存在，則該數(shù)據(jù)塊屬于重復(fù)數(shù)據(jù)塊，無需存儲(chǔ)，只需對(duì)其在Chunk_Table中的Chunk_RC屬性加以操作；如果標(biāo)識(shí)符不存在，則該數(shù)據(jù)塊屬于新數(shù)據(jù)塊，業(yè)務(wù)處理模塊將該數(shù)據(jù)塊的初始屬性信息作為一條新記錄保存到元數(shù)據(jù)管理模塊的Chunk_Table中。待積累了一批新數(shù)據(jù)塊之后，業(yè)務(wù)處理模塊詢問資源管理模塊，由資源管理模塊根據(jù)系統(tǒng)當(dāng)前整體情況挑選一個(gè)合適的存儲(chǔ)節(jié)點(diǎn)負(fù)責(zé)這批數(shù)據(jù)塊的存儲(chǔ)操作，業(yè)務(wù)處理模塊最后通知各服務(wù)接口將相應(yīng)的數(shù)據(jù)塊傳輸?shù)皆摴?jié)點(diǎn)。當(dāng)一個(gè)文件的數(shù)據(jù)全部保存完畢之后，業(yè)務(wù)處理模塊將文件的屬性信息及其與數(shù)據(jù)塊的映射關(guān)系保存到元數(shù)據(jù)管理模塊中的File_Table中。

存儲(chǔ)節(jié)點(diǎn)在接收到一批新的數(shù)據(jù)塊后，先將它們打包成定長對(duì)象，隨后根據(jù)編碼管理模塊的指揮，將若干個(gè)定長對(duì)象分成一組，然后執(zhí)行特定的糾刪編碼算法（RS編碼或Tornado編碼），生成若干個(gè)編碼對(duì)象（合稱為一個(gè)編碼對(duì)象組，包含了原始對(duì)象和校驗(yàn)對(duì)象）。隨后，存儲(chǔ)節(jié)點(diǎn)在資源管理模塊的指揮下將編碼對(duì)象組內(nèi)的各個(gè)對(duì)象分散到包括自身在內(nèi)的不同節(jié)點(diǎn)上存儲(chǔ)（每個(gè)節(jié)點(diǎn)最多保存同一個(gè)編碼對(duì)象組中的一個(gè)對(duì)象）。完成此操作后，存儲(chǔ)節(jié)點(diǎn)將數(shù)據(jù)塊與對(duì)象的映射關(guān)系以及對(duì)象的分組、編碼和存儲(chǔ)信息提交到元數(shù)據(jù)管理模塊，由其保存至Object_Group_Table和Group_Table中。

實(shí)際上，在云存儲(chǔ)這種大規(guī)模分布式存儲(chǔ)系統(tǒng)中，某些存儲(chǔ)節(jié)點(diǎn)之間存在著一定關(guān)聯(lián)性，例如相近的物理位置、共享的供電設(shè)施和網(wǎng)絡(luò)鏈路等，導(dǎo)致它們很可能同時(shí)或連續(xù)失效，這樣的節(jié)點(diǎn)集合稱作錯(cuò)誤域。針對(duì)這一情況，RGMDCS的資源管理模塊在為一個(gè)編碼對(duì)象組挑選不同節(jié)點(diǎn)進(jìn)行存儲(chǔ)時(shí)，會(huì)挑選分布在不同機(jī)柜、不同供電及網(wǎng)絡(luò)區(qū)域的那些節(jié)點(diǎn)，以降低某個(gè)錯(cuò)誤域內(nèi)多個(gè)節(jié)點(diǎn)同時(shí)或連續(xù)失效對(duì)數(shù)據(jù)造成的損失。此外，對(duì)于同一個(gè)或同一批文件所屬的新數(shù)據(jù)塊，其打包并分組編碼生成的編碼對(duì)象組會(huì)被資源管理模塊盡可能地調(diào)度到同一組節(jié)點(diǎn)存儲(chǔ)。這樣做可有效地減少文件所依賴的節(jié)點(diǎn)數(shù)，增強(qiáng)了數(shù)據(jù)可靠性。

2.3數(shù)據(jù)修復(fù)過程

RGMDCS系統(tǒng)采用動(dòng)態(tài)分布式并行修復(fù)機(jī)制：當(dāng)資源管理模塊檢測(cè)到某個(gè)存儲(chǔ)節(jié)點(diǎn)失效時(shí)，從一個(gè)源數(shù)據(jù)管理模塊查詢?cè)摴?jié)點(diǎn)包含的所有對(duì)象信息，然后調(diào)度系統(tǒng)內(nèi)多個(gè)健康節(jié)點(diǎn)同時(shí)開展修復(fù)工作。這樣能夠均衡系統(tǒng)負(fù)載，加快數(shù)據(jù)修復(fù)過程，減少修復(fù)過程中數(shù)據(jù)丟失的可能性，從而進(jìn)一步增強(qiáng)系統(tǒng)的數(shù)據(jù)可靠性。

如圖1所示，當(dāng)存儲(chǔ)節(jié)點(diǎn)SN（a1）失效時(shí)，其所存的對(duì)象<1，1>和<2，n>丟失。為了修復(fù)這兩個(gè)對(duì)象，系統(tǒng)分別隨機(jī)選擇SN（a2）和SN（am）作為修復(fù)的目標(biāo)節(jié)點(diǎn)。SN（a2）和SN（am）收到修復(fù)任務(wù)后，分別從對(duì)象組1和對(duì)象組2中并行地讀取修復(fù)所需要的對(duì)象，然后依靠糾刪編碼算法修復(fù)丟失的對(duì)象并保存在自身中。最后各目標(biāo)節(jié)點(diǎn)通知元數(shù)據(jù)管理模塊更新Group_Table中相應(yīng)的編碼對(duì)象組信息，將新修復(fù)對(duì)象的位置指向自己。

2.4動(dòng)態(tài)負(fù)載均衡

除了保障數(shù)據(jù)可靠性，RGMDCS系統(tǒng)的分布式動(dòng)態(tài)修復(fù)機(jī)制還可以實(shí)現(xiàn)系統(tǒng)的動(dòng)態(tài)負(fù)載均衡。如圖2所示，在SN（a1）節(jié)點(diǎn)發(fā)生超載時(shí)，可以通過糾刪編碼算法由其它輕載節(jié)點(diǎn)上的對(duì)象計(jì)算出該超載節(jié)點(diǎn)上的對(duì)象，進(jìn)而將對(duì)象副本臨時(shí)存放在這些輕載節(jié)點(diǎn)上并對(duì)外提供服務(wù)，從而減輕超載節(jié)點(diǎn)的負(fù)擔(dān)。RGMDCS系統(tǒng)的這種動(dòng)態(tài)負(fù)載均衡操作對(duì)過載節(jié)點(diǎn)完全透明，整個(gè)過程無需其參與。

3結(jié)語

采用靜態(tài)密碼策略的RGMDCS系統(tǒng)是一個(gè)分布式、可擴(kuò)展的系統(tǒng)，其數(shù)據(jù)分塊操作由各服務(wù)接口完成，每個(gè)存儲(chǔ)節(jié)點(diǎn)都可以進(jìn)行數(shù)據(jù)塊的打包、分組、編碼、存儲(chǔ)、讀取、刪除和修復(fù)操作，所以系統(tǒng)的負(fù)載被均衡到各節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)的I/O和計(jì)算資源都可以被充分利用。因此，該方案具有良好的綜合性能和可擴(kuò)展性。

參考文獻(xiàn)參考文獻(xiàn)：

[1]ARMBRUST M，F(xiàn)OX A，GRIFFITH R，et al.A view of cloud computing[J].Communications of the ACM，2010，53（4）：5058.

[2]LIU CHUANYI，LU YINGPING，DU DAVID，et al.ADMAD： applicationdriven metadata aware deduplication archival storage system[C].25th IEEE Conference on Mass Storage System and Technology，2008：2935.

[3]TANNER R.A recursive approach to low complexity codes[J].IEEE Transactions on Information Theory，2006，27（5）：533547.

[4]顧瑜，劉川意，孫林春，等.帶重復(fù)數(shù)據(jù)刪除的大規(guī)模存儲(chǔ)系統(tǒng)可靠性保證[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，50（5）：739744.

責(zé)任編輯（責(zé)任編輯：黃?。?