[發(fā)明專利]門限矩陣構(gòu)造方法、系統(tǒng)、存儲(chǔ)介質(zhì)、程序、存儲(chǔ)系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202010438776.7
• 申請(qǐng)日: 2020-05-21
• 公開（公告）號(hào): CN111711456A
• 公開（公告）日: 2020-09-25
• 發(fā)明（設(shè)計(jì)）人: 蔡紅亮;耿微;高燕;王珂;羅涵;張海清
• 申請(qǐng)（專利權(quán)）人: 成都信息工程大學(xué)
• 主分類號(hào): H03M13/15
• 分類號(hào): H03M13/15;G06F3/06
• 代理公司: 北京元本知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11308
• 代理人: 王紅霞

本發(fā)明屬于數(shù)據(jù)存儲(chǔ)技術(shù)領(lǐng)域，公開了一種門限矩陣構(gòu)造方法、系統(tǒng)、存儲(chǔ)介質(zhì)、程序、存儲(chǔ)系統(tǒng)，確定門限矩陣參數(shù)(k，n)；構(gòu)造初始矩陣S₀，將維度為2k?2且含有(k?1)個(gè)1和(k?1)個(gè)0的不同列向量組成一個(gè)矩陣，記作S₀；構(gòu)造矩陣擴(kuò)展S_e；抽取形成S_(k，n)，從擴(kuò)展矩陣S_e中任意抽取n行，形成最終的門限矩陣S_(k，n)。系統(tǒng)包括：門限矩陣參數(shù)取定模塊；初始矩陣構(gòu)造模塊；矩陣擴(kuò)展構(gòu)造模塊；門限陣列形成模塊。本發(fā)明與傳統(tǒng)的支持任意編碼方案的RS生成矩陣相比，此門限生成矩陣基于二元域運(yùn)算得到，矩陣運(yùn)算相對(duì)計(jì)算時(shí)間復(fù)雜度低，與陣列碼生成矩陣相比，此生成門限矩陣靈活，不受行列規(guī)模限制。

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

本發(fā)明屬于數(shù)據(jù)存儲(chǔ)技術(shù)領(lǐng)域，尤其涉及一種門限矩陣構(gòu)造方法、系統(tǒng)、存儲(chǔ)介質(zhì)、程序、存儲(chǔ)系統(tǒng)。

背景技術(shù)

目前，隨著存儲(chǔ)系統(tǒng)規(guī)模的不斷增長(zhǎng)，出于經(jīng)濟(jì)成本考慮，大量系統(tǒng)使用數(shù)千甚至數(shù)十萬(wàn)廉價(jià)且可靠性低的磁盤保存大量的數(shù)據(jù)，導(dǎo)致磁盤故障的概率很高，磁盤是當(dāng)前分布式存儲(chǔ)系統(tǒng)中最主要的故障來(lái)源，磁盤故障占所有故障比例接近百分之八十，這對(duì)大型存儲(chǔ)系統(tǒng)的可靠性和數(shù)據(jù)可用性產(chǎn)生了巨大的影響。為了滿足用戶對(duì)高可靠性存儲(chǔ)系統(tǒng)的需求，人們把糾刪碼冗余技術(shù)應(yīng)用到分布式存儲(chǔ)系統(tǒng)中，用于提高存儲(chǔ)系統(tǒng)的可靠性。糾刪碼冗余技術(shù)是通過(guò)特定編碼方法對(duì)原始數(shù)據(jù)進(jìn)行編碼得到冗余數(shù)據(jù)，并將原始數(shù)據(jù)和冗余數(shù)據(jù)按照特定方式存儲(chǔ)在分布式存儲(chǔ)系統(tǒng)中。分布式存儲(chǔ)系統(tǒng)的規(guī)模逐漸擴(kuò)大，降低編碼的計(jì)算復(fù)雜度能有效減少分布式系統(tǒng)編碼過(guò)程的開銷。

分布式存儲(chǔ)系統(tǒng)中的糾刪碼冗余技術(shù)可分為兩類：第一類Reed-Solomon(RS，里德-所羅門)碼，RS碼門限生成矩陣基于有限域運(yùn)算，(1)RS的譯碼和編碼的時(shí)間絕大多數(shù)是花費(fèi)在有限域上計(jì)算乘法；(2)RS的編碼和譯碼的復(fù)雜度是二次的復(fù)雜度。生成矩陣G的不同，時(shí)間復(fù)雜度有些不同。范德蒙矩陣的編碼時(shí)間復(fù)雜度為O(n²)，譯碼時(shí)間復(fù)雜度高于O(n²)，柯西矩陣的編碼和譯碼時(shí)間均為O(n²)。編碼和解碼的時(shí)間復(fù)雜度高，使得在分布式存儲(chǔ)系統(tǒng)的應(yīng)用受到了較大的限制，RS碼是MDS碼(Maximal Distance Separable，極大距離可分碼：編碼后的消息中任意長(zhǎng)度等于原始消息的子消息都可以解碼得到原始消息的編碼稱為MDS碼)，但是由于RS碼是基于有限域進(jìn)行運(yùn)算，編譯碼時(shí)間復(fù)雜度太高，所以實(shí)際應(yīng)用受限制。第二類陣列糾刪碼，雖然陣列碼編碼和解碼的計(jì)算快速，陣列糾刪碼編碼規(guī)則就是將原始數(shù)據(jù)塊按陣列排放，并按照滿足規(guī)則的校驗(yàn)鏈生成校驗(yàn)數(shù)據(jù)塊，編碼和條帶行列規(guī)模一旦確定，校驗(yàn)鏈確定，只對(duì)應(yīng)唯一的生成矩陣，但是當(dāng)編碼條帶行列規(guī)模大小一旦確定，就對(duì)應(yīng)唯一的生成矩陣，在復(fù)雜的網(wǎng)絡(luò)存儲(chǔ)環(huán)境中缺乏靈活性，常見的陣列碼是MDS碼，但是容錯(cuò)能力有限，只能容忍2個(gè)或3個(gè)存儲(chǔ)節(jié)點(diǎn)故障，無(wú)法滿足龐大存儲(chǔ)系統(tǒng)的需求。

通過(guò)上述分析，現(xiàn)有技術(shù)存在的問(wèn)題及缺陷為：目前的分布式存儲(chǔ)系統(tǒng)中的糾刪碼冗余技術(shù)存在編碼和解碼的時(shí)間復(fù)雜度高，使得在分布式存儲(chǔ)系統(tǒng)的應(yīng)用受到了較大的限制；當(dāng)編碼條帶行列規(guī)模大小一旦確定，就對(duì)應(yīng)唯一的生成矩陣，在復(fù)雜的網(wǎng)絡(luò)存儲(chǔ)環(huán)境中缺乏靈活性。

解決以上問(wèn)題及缺陷的難度為：需要設(shè)計(jì)一種新的碼：既能避免復(fù)雜的有限域上的運(yùn)算，又能滿足MDS性質(zhì)，且容錯(cuò)能力可以按需求設(shè)置。

解決以上問(wèn)題及缺陷的意義為：一種新的編碼方式，基于二元域的簡(jiǎn)單運(yùn)算進(jìn)行編碼，又能滿足MDS性質(zhì)，且容錯(cuò)能力可以按需求設(shè)置，任意長(zhǎng)度大于等于K的子數(shù)據(jù)可以恢復(fù)原始數(shù)據(jù)，任意長(zhǎng)度小于等于K-1的子數(shù)據(jù)無(wú)法恢復(fù)原始數(shù)據(jù)。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)存在的問(wèn)題，本發(fā)明提供了一種門限矩陣構(gòu)造方法、系統(tǒng)、存儲(chǔ)介質(zhì)、程序、存儲(chǔ)系統(tǒng)。

本發(fā)明是這樣實(shí)現(xiàn)的，一種門限矩陣構(gòu)造方法，所述門限矩陣構(gòu)造方法包括：

第一步，確定門限矩陣參數(shù)(k，n)；