[發(fā)明專利]解碼方法和裝置及云存儲(chǔ)方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201410167214.8
• 申請日: 2014-04-23
• 公開（公告）號(hào): CN105007286B
• 公開（公告）日: 2018-12-28
• 發(fā)明（設(shè)計(jì)）人: 孫崎
• 申請（專利權(quán)）人: 蘇寧易購集團(tuán)股份有限公司
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08
• 代理公司: 北京市萬慧達(dá)律師事務(wù)所 11111
• 代理人: 張金芝;楊穎

本發(fā)明提供一種解碼方法和裝置及云存儲(chǔ)方法和系統(tǒng)，屬于云存儲(chǔ)技術(shù)領(lǐng)域。該解碼方法包括：讀取輸入緩沖區(qū)的待解碼數(shù)據(jù)，將讀取到的包括原數(shù)據(jù)分片和校驗(yàn)數(shù)據(jù)分片的待解碼數(shù)據(jù)移送至輸出模塊，并在輸出模塊中對(duì)待解碼數(shù)據(jù)進(jìn)行處理；根據(jù)處理后輸出模塊中原數(shù)據(jù)區(qū)和待解碼區(qū)域中數(shù)據(jù)分片的數(shù)量，選取相應(yīng)的數(shù)據(jù)分片進(jìn)行解碼操作，將解碼操作結(jié)果組合成全部原數(shù)據(jù)。本發(fā)明的技術(shù)方案可以實(shí)現(xiàn)解碼操作和數(shù)據(jù)獲取工作并行進(jìn)行，大大提高了解碼效率。本發(fā)明對(duì)待解碼數(shù)據(jù)的順序沒有要求，包含原數(shù)據(jù)和校驗(yàn)數(shù)據(jù)的待解碼數(shù)據(jù)，可以任意順序在輸入緩沖區(qū)內(nèi)得到處理。

技術(shù)領(lǐng)域

本發(fā)明涉及云存儲(chǔ)技術(shù)領(lǐng)域，具體涉及一種解碼方法和裝置及云存儲(chǔ)方法和系統(tǒng)。

背景技術(shù)

云存儲(chǔ)是指通過集群應(yīng)用、網(wǎng)絡(luò)技術(shù)或分布式文件系統(tǒng)等功能，將網(wǎng)絡(luò)中大量各種不同類型的存儲(chǔ)設(shè)備通過應(yīng)用軟件集合起來協(xié)同工作，共同對(duì)外提供數(shù)據(jù)存儲(chǔ)和業(yè)務(wù)訪問功能的一個(gè)系統(tǒng)。在云存儲(chǔ)系統(tǒng)中，文件一般被分片保存在多個(gè)云存儲(chǔ)服務(wù)器中。此外，在數(shù)據(jù)通訊時(shí)，需要通訊的數(shù)據(jù)也會(huì)被分為多個(gè)分片，逐片傳送給對(duì)方。

在數(shù)據(jù)存儲(chǔ)和通訊時(shí)，為了解決可靠性的問題，可采用糾刪碼(Erasure Codes，簡稱為EC)技術(shù)，將文件進(jìn)行編碼，分為若干個(gè)原始數(shù)據(jù)分片和校驗(yàn)分片，分別進(jìn)行存儲(chǔ)或通訊。里德-所羅門(Reed-Solomon，簡稱為RS)糾刪碼是一種常用的EC技術(shù)，它將原始文件編碼后，分為大小相同的m個(gè)原始數(shù)據(jù)分片和n個(gè)校驗(yàn)分片，分別進(jìn)行存儲(chǔ)或通訊。對(duì)于文件存儲(chǔ)或者通訊接收方，只要獲得其中任意m個(gè)分片，即可通過解碼方式恢復(fù)原文件或者數(shù)據(jù)，因此可以抗n個(gè)分片損壞或者丟失，大大提高了系統(tǒng)的可靠性。對(duì)于計(jì)算機(jī)文件存儲(chǔ)，糾刪碼系統(tǒng)的存儲(chǔ)空間利用率為m/(m+n)，遠(yuǎn)遠(yuǎn)高于副本存儲(chǔ)方式，因此，RS糾刪碼通過使用計(jì)算能力換取存儲(chǔ)能力，顯著降低了存儲(chǔ)成本和運(yùn)維成本。

1960年，里德(I.S.Reed)和所羅門(G.Solomon)提出了一種構(gòu)造糾刪碼的方法，使用該方法的糾刪碼被稱作Reed-Solomon碼，簡稱RS碼?；赗S編碼技術(shù)構(gòu)造的糾刪碼則稱作RS糾刪碼。一個(gè)(n，k)糾刪碼是把k個(gè)源數(shù)據(jù)編碼為n(n>k)個(gè)數(shù)據(jù)，使得用這n個(gè)數(shù)據(jù)中任意k個(gè)數(shù)據(jù)均可重構(gòu)原來的k個(gè)源數(shù)據(jù)。采用m個(gè)分片和n個(gè)校驗(yàn)分片的糾刪碼體制就是(m+n，m)糾刪碼。

RS糾刪碼的實(shí)現(xiàn)技術(shù)關(guān)鍵是尋找一個(gè)生成矩陣G，該矩陣中任意k列均線性無關(guān)。RS編碼技術(shù)中，生成矩陣可以是范德蒙矩陣和柯西矩陣。使用范德蒙矩陣生成的編碼叫范德蒙碼(Vandermond Code)，使用柯西矩陣生成的編碼叫柯西碼(Cauchy Code)。其編碼原理是：原始數(shù)據(jù)D[D1，D2，..Dm]乘以生成矩陣G，產(chǎn)生m個(gè)原始數(shù)據(jù)D[D1，D2，..Dm]和n個(gè)校驗(yàn)數(shù)據(jù)P[P1，P2，…，Pn]。解碼原理是：在m+n個(gè)原始數(shù)據(jù)和校驗(yàn)數(shù)據(jù)中任意獲得m個(gè)數(shù)據(jù)，組成待解碼數(shù)據(jù)D'，例如[D1，…Di,P1..Pj]。在生成矩陣中去掉n個(gè)未出現(xiàn)數(shù)據(jù)對(duì)應(yīng)的那一列，組成一個(gè)新的生成矩陣G，然后計(jì)算G的逆矩陣G'，最后D'*G'＝D。為了使矩陣運(yùn)算的結(jié)果保持在實(shí)數(shù)域，運(yùn)算改為限定在伽羅瓦(Galois)域G(2^8)或者G(2^16)進(jìn)行。具體運(yùn)算流程和特性，早已被研究透徹，在相關(guān)數(shù)學(xué)書籍和刊物上可以查到，因此在此不再贅述。

但是，無論范德蒙矩陣和柯西矩陣的RS糾刪碼體制的系統(tǒng)，在解碼上都有一個(gè)共同的缺點(diǎn)，即通過D'*G'＝D才能計(jì)算出D，因此只有收齊任意的m個(gè)分片后，如果其中含有校驗(yàn)分片，對(duì)應(yīng)的解碼生成矩陣G'和待解碼數(shù)據(jù)D'才能確定，系統(tǒng)才能開始解碼。在系統(tǒng)收到第m個(gè)分片前，即使知道該分片的編號(hào)，能夠獲得對(duì)應(yīng)解碼生成矩陣G'，但由于待解碼數(shù)據(jù)D'＝[D1，…Di,P1..Pj]，其中至少丟掉了一個(gè)分片數(shù)據(jù)，因此不能確定D'。只有獲得第m個(gè)分片后，D'才能最終確定，系統(tǒng)才能開始解碼，因此系統(tǒng)解碼性能受制于任意m個(gè)分片中最慢的那個(gè)。在現(xiàn)有系統(tǒng)中，網(wǎng)絡(luò)傳輸模塊和解碼計(jì)算模塊是串行的，在收齊第m個(gè)分片前，網(wǎng)絡(luò)傳輸模塊在工作，而解碼計(jì)算模塊空閑；開始解碼后，解碼計(jì)算模塊工作而網(wǎng)絡(luò)傳輸模塊空閑，降低了系統(tǒng)性能。