龍運(yùn)波，唐聃

（1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041；2.中國(guó)科學(xué)院大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，北京 100049；3.成都信息工程大學(xué) 軟件工程學(xué)院，成都 610225）

0 引言

隨著信息產(chǎn)業(yè)的迅猛發(fā)展和普及，數(shù)據(jù)存儲(chǔ)量呈爆炸式增長(zhǎng)，國(guó)際數(shù)據(jù)公司預(yù)測(cè)到2025 年全球數(shù)據(jù)將增至175 ZB［1］。數(shù)據(jù)作為生產(chǎn)要素之一，已經(jīng)被正式納入國(guó)家所定義的要素市場(chǎng)化配置中，保障數(shù)據(jù)的可靠性和可用性具有重要意義，因此數(shù)據(jù)存儲(chǔ)技術(shù)已成為現(xiàn)代信息產(chǎn)業(yè)架構(gòu)中不可或缺的底層基座。在新興技術(shù)的驅(qū)動(dòng)下，存儲(chǔ)主要面對(duì)的應(yīng)用已經(jīng)從數(shù)據(jù)庫(kù)、文件、流媒體等傳統(tǒng)應(yīng)用轉(zhuǎn)向云計(jì)算、大數(shù)據(jù)和人工智能等大規(guī)模數(shù)據(jù)應(yīng)用場(chǎng)景，因此在存儲(chǔ)效率、容錯(cuò)能力之外也給存儲(chǔ)系統(tǒng)的即時(shí)訪問(wèn)性能提出了新的挑戰(zhàn)。面對(duì)眾多復(fù)雜的應(yīng)用場(chǎng)景，大型分布式存儲(chǔ)的訪問(wèn)效率至關(guān)重要。存儲(chǔ)系統(tǒng)的訪問(wèn)效率受諸多因素影響，最重要的原因在于負(fù)載不均導(dǎo)致的資源競(jìng)爭(zhēng)［2］。例如互聯(lián)網(wǎng)中資源分布和訪問(wèn)呈現(xiàn)Zipf 定律，即少數(shù)流行度比較高的數(shù)據(jù)資源常常占據(jù)大部分的訪問(wèn)量，造成相應(yīng)存儲(chǔ)服務(wù)器的工作負(fù)荷遠(yuǎn)高于其他節(jié)點(diǎn)。另一方面，由于應(yīng)急突發(fā)性事件而引發(fā)的系統(tǒng)大量并發(fā)訪問(wèn)，也會(huì)造成某些數(shù)據(jù)訪問(wèn)量劇增，使存儲(chǔ)系統(tǒng)中訪問(wèn)熱度偏移，從而嚴(yán)重影響存儲(chǔ)系統(tǒng)的訪問(wèn)性能。因此如何高效地避免因節(jié)點(diǎn)的集中訪問(wèn)造成的負(fù)載不均，是分布式存儲(chǔ)亟待解決的問(wèn)題。

分布式存儲(chǔ)中傳統(tǒng)的負(fù)載均衡方法主要分為靜態(tài)負(fù)載均衡和動(dòng)態(tài)負(fù)載均衡。靜態(tài)負(fù)載均衡指在系統(tǒng)設(shè)計(jì)之初對(duì)數(shù)據(jù)的訪問(wèn)規(guī)律進(jìn)行先驗(yàn)分析，預(yù)先設(shè)定負(fù)載策略，避免出現(xiàn)負(fù)載不均的問(wèn)題，主要方法有節(jié)點(diǎn)空間劃分法［3］、多Hash法［4-5］。但由于數(shù)據(jù)應(yīng)用場(chǎng)景的日益豐富，動(dòng)態(tài)變化的訪問(wèn)負(fù)載難以預(yù)見(jiàn)，因此復(fù)雜場(chǎng)景需要?jiǎng)討B(tài)地均衡系統(tǒng)負(fù)載。動(dòng)態(tài)負(fù)載均衡指在系統(tǒng)運(yùn)行過(guò)程中，通過(guò)實(shí)時(shí)收集數(shù)據(jù)的訪問(wèn)特征和節(jié)點(diǎn)信息，動(dòng)態(tài)調(diào)控出現(xiàn)的各種負(fù)載不均問(wèn)題，其中應(yīng)用最廣泛的有動(dòng)態(tài)副本法［6-7］和虛擬節(jié)點(diǎn)算法［8-9］。動(dòng)態(tài)副本法主要針對(duì)存儲(chǔ)系統(tǒng)中冷熱數(shù)據(jù)資源訪問(wèn)不均的問(wèn)題，通過(guò)增加熱數(shù)據(jù)的副本數(shù)量，將數(shù)據(jù)的訪問(wèn)請(qǐng)求分散到多個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)熱點(diǎn)降溫。不同動(dòng)態(tài)副本算法之間的主要區(qū)別在于副本放置節(jié)點(diǎn)的選擇不同。文獻(xiàn)［6］中提出了一種樹(shù)型副本放置策略，過(guò)熱節(jié)點(diǎn)利用相鄰節(jié)點(diǎn)建立一棵虛擬平衡樹(shù)，樹(shù)的同一層節(jié)點(diǎn)共同存儲(chǔ)一個(gè)完整的數(shù)據(jù)副本。通過(guò)這種分散的副本放置策略，利用最少的副本數(shù)量實(shí)現(xiàn)負(fù)載均衡。虛擬節(jié)點(diǎn)算法主要針對(duì)因服務(wù)器配置不同而引起的存儲(chǔ)負(fù)載不均問(wèn)題，將物理服務(wù)器虛擬為多個(gè)相同配置的虛擬節(jié)點(diǎn)，并將它隨機(jī)分布避免因資源分布不均導(dǎo)致的存儲(chǔ)負(fù)載失衡問(wèn)題，同時(shí)可以靈活刪除和添加虛擬節(jié)點(diǎn)以實(shí)現(xiàn)存儲(chǔ)系統(tǒng)的負(fù)載轉(zhuǎn)移。文獻(xiàn)［10］中基于虛擬節(jié)點(diǎn)的一致性哈希提出了一種動(dòng)態(tài)負(fù)載均衡方法，通過(guò)動(dòng)態(tài)收集和分析數(shù)據(jù)訪問(wèn)情況以均衡調(diào)度節(jié)點(diǎn)間的負(fù)載。無(wú)論是上述的靜態(tài)負(fù)載均衡還是動(dòng)態(tài)負(fù)載均衡，通?；诙喔北救哂嗉夹g(shù)，針對(duì)數(shù)據(jù)的訪問(wèn)負(fù)載，預(yù)先或?qū)崟r(shí)設(shè)置數(shù)據(jù)資源的副本數(shù)量和放置規(guī)則來(lái)提供多種訪問(wèn)方式，以實(shí)現(xiàn)負(fù)載均衡。然而這種方式在均衡負(fù)載的同時(shí)，存儲(chǔ)系統(tǒng)的空間利用率大打折扣，同時(shí)頻繁地創(chuàng)建、遷移、刪除數(shù)據(jù)副本也會(huì)給網(wǎng)絡(luò)帶寬帶來(lái)巨大壓力。

糾刪碼的出現(xiàn)為分布式存儲(chǔ)的負(fù)載均衡提供了更多可能。糾刪碼主要用于存儲(chǔ)容錯(cuò)，以基于最大距離可分（Maximum-Distance-Separable，MDS）碼的分布式存儲(chǔ)系統(tǒng)為例，（n，k）-MDS 碼將一份源文件切分成k個(gè)源數(shù)據(jù)塊，編碼成n個(gè)存儲(chǔ)數(shù)據(jù)塊（當(dāng)中有n-k個(gè)冗余的校驗(yàn)數(shù)據(jù)塊），然后將這n個(gè)存儲(chǔ)數(shù)據(jù)塊分別存放于n個(gè)節(jié)點(diǎn)中，于是其中任意k個(gè)數(shù)據(jù)塊可以通過(guò)譯碼恢復(fù)得到源文件。文獻(xiàn)［11］中注意到糾刪碼除了容錯(cuò)能力，還能以更小的代價(jià)代替多副本策略來(lái)高效地提高存儲(chǔ)系統(tǒng)訪問(wèn)性能。文獻(xiàn)［12］中結(jié)合隊(duì)列理論和糾刪碼，利用（n，2）-MDS 碼對(duì)數(shù)據(jù)進(jìn)行編碼，并結(jié)合Bloking-one Scheduling 算法均衡節(jié)點(diǎn)訪問(wèn)負(fù)載，以提高數(shù)據(jù)的訪問(wèn)效率。文獻(xiàn)［13］中將隨機(jī)線性網(wǎng)絡(luò)編碼應(yīng)用于存儲(chǔ)系統(tǒng)，通過(guò)阻塞算法均衡訪問(wèn)負(fù)載，降低數(shù)據(jù)的訪問(wèn)延時(shí)。文獻(xiàn)［14］中基于（n，k）-MDS 碼提出了（n，k）-fork-join 模型，將訪問(wèn)請(qǐng)求分為n份發(fā)給n個(gè)服務(wù)器，取任意k個(gè)服務(wù)器的響應(yīng)數(shù)據(jù)即可完成訪問(wèn)，以此提高網(wǎng)絡(luò)分布式存儲(chǔ)中的文件下載速度。此后，許多研究致力于通過(guò)糾刪碼提高存儲(chǔ)系統(tǒng)的訪問(wèn)效率［15-19］，但由于編碼后的數(shù)據(jù)被分為n個(gè)數(shù)據(jù)塊，通常需要至少k個(gè)數(shù)據(jù)塊才能獲取一份文件的完整數(shù)據(jù)，當(dāng)多任務(wù)訪問(wèn)一個(gè)數(shù)據(jù)時(shí)還須合理使用隊(duì)列理論或調(diào)度策略處理訪問(wèn)請(qǐng)求的排隊(duì)，計(jì)算量和通信帶寬的代價(jià)高昂。

近年來(lái)局部修復(fù)碼（Local Repair Code，LRC）、再生碼（Regenerating Code，RC）的研究頗受關(guān)注，它們主要針對(duì)存儲(chǔ)系統(tǒng)中局部零星節(jié)點(diǎn)數(shù)據(jù)失效頻率較高的情況，以提升傳統(tǒng)糾刪碼的修復(fù)效率［20-21］。其中局部修復(fù)碼的突出優(yōu)點(diǎn)是只需要較少節(jié)點(diǎn)就能恢復(fù)某個(gè)失效數(shù)據(jù)塊，很大程度上降低了修復(fù)開(kāi)銷(xiāo)，所以近年來(lái)在存儲(chǔ)容錯(cuò)的應(yīng)用中備受關(guān)注。例如文獻(xiàn)［22-23］中利用有理函數(shù)域和橢圓曲線構(gòu)造了一類(lèi)碼長(zhǎng)與運(yùn)算域大小呈線性關(guān)系的局部修復(fù)碼；文獻(xiàn)［24-27］中提出能夠糾正多個(gè)刪除錯(cuò)的一類(lèi)（r，δ）局部修復(fù)碼。研究碼長(zhǎng)擴(kuò)展更自由、局部修復(fù)能力更強(qiáng)的局部修復(fù)碼是國(guó)內(nèi)外學(xué)者們進(jìn)一步追求的目標(biāo)。除了應(yīng)用于存儲(chǔ)系統(tǒng)的高效容災(zāi)，一類(lèi)特殊的局部修復(fù)碼還可以在存儲(chǔ)系統(tǒng)的負(fù)載均衡上發(fā)揮有效作用，本文將它稱(chēng)為具有（r，t）-并行訪問(wèn)性能的LRC。該碼類(lèi)的一個(gè)非常重要的特性是具有（r，t）-availability 性能，即n個(gè)編碼數(shù)據(jù)塊中的任一個(gè)數(shù)據(jù)塊都能由t組不相交的修復(fù)集重構(gòu)，且每組集合至多有r個(gè)碼符，r?k。局部修復(fù)碼的方法為每個(gè)數(shù)據(jù)塊提供了t種平行的訪問(wèn)方式供選擇，每種訪問(wèn)方式相較于傳統(tǒng)糾刪碼都大幅節(jié)省了計(jì)算成本和修復(fù)帶寬。該特性來(lái)源于文獻(xiàn)［28］，需要將局部修復(fù)碼的碼率和最小漢明距離適當(dāng)折中。然而，并非所有的局部修復(fù)碼都適用于負(fù)載均衡的應(yīng)用場(chǎng)景，只有如文獻(xiàn)［28-34］的（r，t）局部修復(fù)碼，才能在負(fù)載均衡的應(yīng)用上表現(xiàn)出更加高效的性能。在這些理論研究中，Wang等［28］首次為局部修復(fù)碼引入了（r，t）-availability 的概念，Rawat等［29］在此基礎(chǔ)上取得了較大突破，將具有（r，t）-availability 性質(zhì)的局部修復(fù)碼定義為（n，k，r，t）-LRC，同時(shí)將它的性能參數(shù)t由2 推廣到了t≥2 的一般情形，使局部修復(fù)碼具有更靈活的并行局部修復(fù)能力，也正是這項(xiàng)工作使該類(lèi)局部修復(fù)碼能夠成為本文實(shí)現(xiàn)負(fù)載均衡的核心與關(guān)鍵。Hao等［31］利用低密度校驗(yàn)碼在二元域上構(gòu)造了該類(lèi)局部修復(fù)碼，Balaji等［32］也基于二元域給出了碼長(zhǎng)為（r+1）g的（n，k，r，t）-LRC，Zhang等［33］將它推廣為更一般的情況，使碼長(zhǎng)不再局限于r+1 的指數(shù)倍，但參數(shù)t≤r，限制較為嚴(yán)重。還有一些理論研究［35-36］關(guān)注于該碼類(lèi)的碼距、碼率及碼長(zhǎng)上界。事實(shí)上，（n，k，r，t）-LRC 只是局部修復(fù)碼的一小類(lèi)分支，且大多仍是在存儲(chǔ)容錯(cuò)的應(yīng)用場(chǎng)景下進(jìn)行理論研究，關(guān)注存儲(chǔ)系統(tǒng)中負(fù)載均衡的側(cè)面應(yīng)用尚不多，只有一些研究［37-42］利用局部修復(fù)碼來(lái)提高存儲(chǔ)系統(tǒng)中的文件下載速度。文獻(xiàn)［41-42］中提出局部修復(fù)碼在應(yīng)用于高頻訪問(wèn)場(chǎng)景下的存儲(chǔ)系統(tǒng)時(shí)，它的訪問(wèn)效率相較于糾刪碼和多副本策略提升較大。但這些研究主要依賴(lài)隊(duì)列理論實(shí)現(xiàn)，局限于隊(duì)列中任務(wù)分配等技術(shù)細(xì)節(jié)問(wèn)題，較少關(guān)注到（n，k，r，t）-LRC本身在訪問(wèn)負(fù)載均衡應(yīng)用中的巨大潛力。

本文利用局部修復(fù)碼中（r，t）-availability 性能所帶來(lái)的（r，t）-并行訪問(wèn)性能為分布式存儲(chǔ)系統(tǒng)的文件（數(shù)據(jù)）訪問(wèn)提供一種負(fù)載均衡的方法。主要包括：1）數(shù)據(jù)塊之間訪問(wèn)熱度的負(fù)載均衡以應(yīng)對(duì)因數(shù)據(jù)熱點(diǎn)偏移造成的負(fù)載不均；2）各存儲(chǔ)節(jié)點(diǎn)間的負(fù)載均衡以提升系統(tǒng)的整體性能。本文給出了局部修復(fù)碼（n，k，r，t）-LRC 的三種針對(duì)性的（顯式）構(gòu)造，該負(fù)載均衡方法相較于其他基于糾刪碼或多副本的方法能夠以更小的代價(jià)達(dá)到了更好的負(fù)載均衡效果。

1 預(yù)備知識(shí)

本文的 負(fù)載均 衡方法 主要基 于（n，k，r，t）-LRC 的（r，t）-availability 性能進(jìn)行設(shè)計(jì)，因此本章首先對(duì)背景知識(shí)及所需的方法工具進(jìn)行介紹。

1.1 （n，k，r，t）-LRC的概念及性質(zhì)

（n，k，r，t）-LRC 是一類(lèi)特殊的局部修復(fù)碼，最早由Rawat等［29］給出。假設(shè)有信息向量m=(m1，m2，…，mk)，利用（n，k，r，t）-LRC 對(duì)它編碼，得到編碼向量c=(c1，c2，…，cn)。本文稱(chēng)c（ii∈[n]）為碼字符號(hào)，其中：ci∈m為信息符號(hào)；[n]代表｛1，2，…，n｝的整數(shù)集合，全文的［t］、［k］、［t］、［b］、［c］等都表示為對(duì)應(yīng)的整數(shù)集合。（n，k，r，t）-LRC 應(yīng)滿足以下性質(zhì)：

1）對(duì)于每個(gè)信息符號(hào)ci∈m，都存在t個(gè)不相交的子集Г1(i)，Г2(i)，…，Гt(i) ?[n]{i}，以Гj（i）為索引的碼符cГj(i)可以構(gòu)成ci的函數(shù)式。

2）每個(gè)子集的元素個(gè)數(shù)|Гj(i)|≤r，j∈[t]，i∈[k]。

3）任意兩個(gè)子集的元素都不相交，即對(duì)于任意i∈[k]，j≠l∈[k]，都有Гj(i) ∩Гl(i)=?。

基于以上定義的（n，k，r，t）-LRC 具有（r，t）-availability 性能，本文稱(chēng)之為（r，t）-并行訪問(wèn)性能：對(duì)于任意信息符號(hào)，都存在t個(gè)不相交的集合可以分別構(gòu)成函數(shù)式進(jìn)行重構(gòu)，且每個(gè)集合至多包含r個(gè)其他碼符。將函數(shù)式用于分布式存儲(chǔ)，能夠?yàn)榫幋a后的每一個(gè)數(shù)據(jù)塊提供t+1 種訪問(wèn)方式，以實(shí)現(xiàn)分布式存儲(chǔ)中數(shù)據(jù)塊之間訪問(wèn)熱度的負(fù)載均衡。

1.2 平衡不完全區(qū)組設(shè)計(jì)

本文基于平衡不完全區(qū)組設(shè)計(jì)（Balanced Incomplete Block Design，BIBD）給出了三個(gè)（n，k，r，t）-LRC 的構(gòu)造方法。其中BIBD 是組合數(shù)學(xué)中一類(lèi)特殊的區(qū)組設(shè)計(jì)。

定義1設(shè)X=(x1，x2，…，xk)是一個(gè)包含k個(gè)元素的有限集合；?=(B1，B2，…，Bb)是X的一族子集，稱(chēng)Bi為區(qū)組（blocks）。當(dāng)滿足以下兩個(gè)條件時(shí)，稱(chēng)(X，?)為一個(gè)（k，b，r，c，λ）-BIBD。

1）|X|=k，|? |=b，且對(duì)于所有的i∈[b]，|Bi|=r。

2）每一對(duì)(x，y) ?X恰好包含于λ個(gè)區(qū)組中。

當(dāng)? 可以被劃分為c個(gè)平行類(lèi)（parallel classes），則稱(chēng)(X，?)是可解的，其中一個(gè)平行類(lèi)指? 中多個(gè)不相交的區(qū)組構(gòu)成的子集，且這些區(qū)組的并集為X。

定義2定義一個(gè)可解平衡不完全區(qū)組設(shè)計(jì)（Resolvable Balanced Incomplete Block Design，RBIBD）(X，?)為（k，b，r，c，λ）-RBIBD，? 可以被劃分為c個(gè)平行類(lèi)ε1，ε2，…，εc??。其中：i∈[c]；j∈[k]；|B∈ε∶ixj∈B|=1，即在一個(gè)平行類(lèi)中，所有元素是唯一的。在RBIBD 中，參數(shù)需要滿足r|k。

可以用一個(gè)k×b維的關(guān)聯(lián)矩陣M表示一個(gè)區(qū)組設(shè)計(jì)(X，?)，M的行對(duì)應(yīng)元素x1，x2，…，xk的索引，M的列對(duì)應(yīng)區(qū)組B1，B2，…，Bb的索引，則M中的元素mij定義如下：

根據(jù)關(guān)聯(lián)矩陣的定義以及BIBD 的構(gòu)造屬性可知，（k，b，r，c，λ）-BIBD 的關(guān)聯(lián)矩陣M的行重為c，列重為r，且任意兩列中對(duì)應(yīng)行索引相同的1 的個(gè)數(shù)至多是1 個(gè)。

一個(gè)（k，b，r，c，λ）-RBIBD 的關(guān)聯(lián)矩陣M包含c組列向量集合M1，M2，…，Mc，它們的支撐構(gòu)成集合[k]的t個(gè)不同劃分，每組包含個(gè)列向量。顯然M1，M2，…，Mc可以表示該RBIBD的c個(gè)平行類(lèi)。

1.3 GF（2）上的隨機(jī)矩陣及其性質(zhì)

本文編碼的構(gòu)造需要使用GF（2）上的隨機(jī)矩陣以及它的重要性質(zhì)。

定義3設(shè)GF（2）上的矩陣Rn×k，n＞k＞0，若其中各元素取值相互獨(dú)立，且滿足取“0”的概率為p，取“1”的概率為1 -p。當(dāng)p∈(0，1) 時(shí)，稱(chēng)它為隨機(jī)矩陣；當(dāng)p=0.5 時(shí)，稱(chēng)它為均勻隨機(jī)矩陣。

文獻(xiàn)［43］給出了定理1、2，并證明了它們的正確性。

定理1GF（2）上的隨 機(jī)矩陣Rn×k列滿秩 的概率 如式（2）所示，其中δ=n-k。

定理2設(shè)有GF（2）上列滿秩的生成矩陣Gn×（kn＞k＞0）和校驗(yàn)矩陣Hn×n（m=n-k）。若Gn×k中刪除任意t（t＜min{k，m}）行仍然列滿秩，則Hn×n中對(duì)應(yīng)t行線性無(wú)關(guān)。

推論1 根據(jù)定理1 和定理2，給定一個(gè)二元域上的隨機(jī)矩陣Rn×k，可以構(gòu)造一個(gè)具有高概率容錯(cuò)能力的糾刪碼，以P的概率容n-k-δ個(gè)刪除錯(cuò)，本文稱(chēng)它為近似δ-MDS 碼。

證明 定理2 指出，若生成矩陣Gn×k刪除任意t=n-k-δ行仍列滿秩，則校驗(yàn)矩陣Hn×n中對(duì)應(yīng)t行線性無(wú)關(guān)，即譯碼矩陣存在唯一解。因此，校驗(yàn)矩陣成功譯碼的概率等于生成矩陣的滿秩概率。而根據(jù)定理1，利用GF（2）上的隨機(jī)高矩陣作為生成矩陣，它滿秩的概率如式（2）所示，當(dāng)隨機(jī)矩陣的分布概率p=0.5 時(shí)，滿秩概率；當(dāng)δ＞20時(shí)，隨機(jī)矩陣的滿秩概率P＞1 -10-7。這意味著該編碼的高概率譯碼能力可用于分布式存儲(chǔ)系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行編碼。

文獻(xiàn)［43］中基于二元域上隨機(jī)矩陣的優(yōu)良性質(zhì)提出了隨機(jī)陣列碼。本文將用它給出（n，k，r，t）-LRC 的一種構(gòu)造方案，選擇隨機(jī)陣列碼作為構(gòu)造基礎(chǔ)，主要考慮到以下優(yōu)勢(shì)：1）隨機(jī)陣列碼的參數(shù)不受有限域規(guī)模的限制，為存儲(chǔ)系統(tǒng)提供的容錯(cuò)能力也可根據(jù)容錯(cuò)需求擴(kuò)展。2）隨機(jī)陣列碼的編譯碼基于二元域的異或運(yùn)算，文獻(xiàn)［43］中通過(guò)實(shí)驗(yàn)證明了它相較于里所（Reed Solomon，RS）碼、柯西里所（Cauchy Reed Solomon，CRS）碼等MDS 碼具有更高的編譯碼速率，尤其是在大規(guī)模構(gòu)造中表現(xiàn)良好。其中CRS 碼的編譯碼雖然也可以采用異或運(yùn)算，但由于它的本質(zhì)是將GF（2w）域中的元素映射為二元域中的比特矩陣，在編碼過(guò)程中，生成矩陣的規(guī)模相較于隨機(jī)陣列碼增大了w2倍，相應(yīng)的異或運(yùn)算次數(shù)也會(huì)成倍增加，導(dǎo)致編譯碼效率降低，且效率差距在大規(guī)模編碼中會(huì)愈加明顯。3）根據(jù)推論1，隨著規(guī)模的增長(zhǎng)，隨機(jī)陣列碼的存儲(chǔ)效率趨近于MDS 碼，有較高的存儲(chǔ)空間利用率。

2 構(gòu)造（n，k，r，t）-LRC

本章給出了（n，k，r，t）-LRC 的顯式構(gòu)造方法，其中使用了前面介紹的（k，b，c，r，λ）-RBIBD和GF（2）上的隨機(jī)矩陣。

早在文獻(xiàn)［29，34］中就曾利用（k，b，c，r，λ）-RBIBD 構(gòu)造局部修復(fù)碼的局部修復(fù)組，但沒(méi)有提到（k，b，c，r，λ）-RBIBD的顯式構(gòu)造方法。而在一些專(zhuān)門(mén)針對(duì)BIBD 的研究［44］中，大多采用 正交拉丁方（Multiple Orthogonal Latin Squares，MOLS）或有限射影平面進(jìn)行構(gòu)造，這些方法復(fù)雜且沒(méi)有程序化的實(shí)現(xiàn)方法。因此本文提出一種RBIBD 的顯式構(gòu)造算法。

2.1 （k，b，c，r，λ）-RBIBD的構(gòu)造算法

根據(jù)（k，b，c，r，λ）-RBIBD 的定義及性質(zhì)，可以采用向量篩選的辦法在列重為r的k維列向量全集Ω中篩選向量，使篩選得到的向量集合滿足以下條件：

1）任意兩個(gè)向量至多有一個(gè)1 的位置相同；

2）向量集合可以劃分為c個(gè)不相交的子集，子集中所有向量的并恰好是一個(gè)元素全1 的向量。

根據(jù)以上分析，給出（k，b，c，r，λ）-RBIBD 的構(gòu)造算法。

算法1 能夠顯式地構(gòu)造一個(gè)（k，b，c，r，λ）-RBIBD，雖然參數(shù)c的取值有限，但本文的目的是將它應(yīng)用于局部修復(fù)碼構(gòu)造局部校驗(yàn)列，為數(shù)據(jù)塊提供（r，t）-并行訪問(wèn)性能，一般只需要少量平行類(lèi)就能滿足數(shù)據(jù)塊對(duì)并行讀取能力的要求。

例1設(shè)X={1，2，…，15}，利用算 法1 可以構(gòu) 造一個(gè)（15，15，3，3，1）-RBIBD 的關(guān)聯(lián)矩陣M如式（3）所示，對(duì)應(yīng)的RBIBD 如表1 所示，其中：b=15 個(gè)不同的三元組集合表示區(qū)組，任意兩個(gè)元素恰好只出現(xiàn)在λ=1 個(gè)區(qū)組中，這些區(qū)組可以分為3 個(gè)平行類(lèi)ε1、ε、ε3，每個(gè)平行類(lèi)中的區(qū)組都是集合X的劃分。

表1 一個(gè)（15，15，3，3，1）-RBIBD的例子Tab.1 An example of（15，15，3，3，1）-RBIBD

2.2 （n，k，r，t）-LRC的構(gòu)造方法

基于算法1 給出的（k，b，c，r，λ）-RBIBD，本文面向分布式存儲(chǔ)數(shù)據(jù)塊訪問(wèn)負(fù)載均衡給出了三個(gè)（n，k，r，t）-LRC 的構(gòu)造方法。

2.2.1 構(gòu)造方法1

通過(guò)算法1 構(gòu)造一個(gè)（k，b，c，r，λ）-RBIBD 的關(guān)聯(lián)矩陣M，設(shè)M1，M2，…，Mt為M的t組列向量集合，表示RBIBD的t個(gè)平行類(lèi)。可以通過(guò)如下方式構(gòu)造一個(gè)

-LRC 的生成矩陣G。

1）生成矩陣G的前k列由單位矩陣Ik×k構(gòu)成；

2）在（k，b，c，r，λ）-RBIBD 的關(guān)聯(lián)矩陣M中選取t組向量集合M1，M2，…，Mt，每組列向量集合包含個(gè)列向量。G的后列由M1，M2，…，Mt構(gòu)成，使G=[Ik×k|M1，M2，…，Mt]。

例2 根據(jù)方法1，可以構(gòu)造一個(gè)（25，15，3，2）-LRC，碼字的生成矩陣G=[I15×15|M1，M2]，M1、M2取例1中M的前10列。設(shè)信息向量m=（m1，m2，…，m15），則碼字c=（m1，m2，…，m15，l1，l2，…，l10）=mG，其中：（l1，l2，…，l10）為t·k/r=2×15/3=10個(gè)局部校驗(yàn)符號(hào)，給信息向量m中的每個(gè)符號(hào)提供（3，2）-并行訪問(wèn)性能。例如m1可以直接獲取，也可以選擇{m4，m11，l1}或{m3，m6，l7}兩組碼符組成的函數(shù)式通過(guò)計(jì)算進(jìn)行訪問(wèn)。

顯然方法1 給出的（n，k，r，t）-LRC 具有（r，t）-并行訪問(wèn)性能，但由于大規(guī)模分布式存儲(chǔ)需要一定的容錯(cuò)能力保證數(shù)據(jù)可靠性，本文在方法1 的基礎(chǔ)上給出方法2 及方法3。

2.2.2 構(gòu)造方法2

給定一個(gè)（k，b，c，r，λ）-RBIBD 的關(guān)聯(lián)矩陣M，給定一個(gè)（N+t，k）-RS 碼的生成矩陣，可以通過(guò)如下方式構(gòu)造一個(gè)（n=N+t·k/r，k，r，t）-LRC 的生成矩陣G。

1）生成矩陣G的前N列由的前N列構(gòu)成；

2）根據(jù)Mi的支撐，將的第N+i列劃分成k/r列，使每一個(gè)列向量的列重為r，其中：i∈[t]。將劃分所得的向量作為G的后t·k/r列。

在方法2 的生成矩陣G中，前k列對(duì)應(yīng)碼字的信息符號(hào)，第k+1～N列對(duì)應(yīng)碼字的全局校驗(yàn)，最后k·t/r列對(duì)應(yīng)碼字的局部校驗(yàn)。方法2 借鑒了文獻(xiàn)［29］中Construction1 的構(gòu)造思路，不同之處在于本文給出了其中（k，b，c，r，λ）-RBIBD 的詳細(xì)構(gòu)造方法。

例3 基于GF（26）給定一個(gè)（22，15）-RS 碼的生成矩陣如式（4）所示，其中的前15 列為單位矩陣，第16～22 列為范德蒙矩陣。根據(jù)方法2，將的最后t=2 列如圖1 所示劃分成t·k/r=2×15/3=10 列作為 局部校驗(yàn)列，得到一 個(gè)（30，15，3，2）-LRC 的生成矩陣G。這些局部校驗(yàn)列為編碼后的每個(gè)信息符號(hào)提供了（3，2）-并行訪問(wèn)性能。

圖1 例3中生成矩陣G的構(gòu)造過(guò)程Fig.1 Construction procedure for generated matrix G in example 3

方法2 給出的（n，k，r，t）-LRC 仍然具有（r，t）-并行訪問(wèn)性能，相較于方法1，它的優(yōu)勢(shì)在于擁有一定的容錯(cuò)能力。

定理3當(dāng)r|t，且存在一個(gè)（k，b，c，r，λ）-RBIBD，其中：c≥t，它的關(guān)聯(lián)矩陣M可由算法1 給出，那么方法2 給出的（n=N+t·k/r，k，r，t）-LRC 能夠修復(fù)個(gè)刪除錯(cuò)。最小漢明距離為：

證明 對(duì)于（N+t，k）-RS 碼，它的最小漢明距離滿足dmin(c)=N-k+t+1，在方法2 中，G的后t·k/r列向量總是能夠通過(guò)線性變換重構(gòu)中的t列，與前N列一起構(gòu)成RS 碼的生成矩陣，因此方法2 給出的（n=N+t·k/r，k，r，t）-LRC 滿足，即式（5）。

方法2 給出的（n，k，r，t）-LRC 具有（r，t）-并行訪問(wèn)性能，同時(shí)達(dá)到了（n，k，r，t）-LRC 的最小漢明距離上界，但由于方法2 基于RS 碼構(gòu)造，因此需要與RS 碼保持同一有限域大小。事實(shí)上，方法2 的（n，k，r，t）-LRC 只適用于中小規(guī)模的存儲(chǔ)系統(tǒng)，因?yàn)殡S著碼長(zhǎng)n的增大，有限域?qū)⒕€性增長(zhǎng)，在大規(guī)模有限域上的矩陣運(yùn)算效率低下。針對(duì)這個(gè)問(wèn)題，本文提出了方法3 以適用大規(guī)模存儲(chǔ)系統(tǒng)的負(fù)載均衡。

2.2.3 構(gòu)造方法3

根據(jù)定義3 構(gòu)造一個(gè)GF（2）上的滿秩隨機(jī)矩陣RN×k，利用初等行變換將RN×k變換為上單位陣的形式，使：

給定一個(gè)（N，k，δ）-隨機(jī)編 碼的生成矩陣=RT=[Ik×k|Dk×m]，以及（k，b，c，r，λ）-RBIBD 的關(guān)聯(lián)矩陣M，可以通過(guò)如下方式構(gòu)造一個(gè)（n=N+k·t/r，k，r，t）-LRC 的生成矩陣G。

1）生成矩陣G的前N列由的前N列構(gòu)成；

2）選取（k，b，c，r，λ）-RBIBD的t個(gè)平行類(lèi)，即在關(guān)聯(lián)矩陣M中選取t組列向量集合M1，M2，…，Mt，每組列向量集合包含k/r個(gè)列向量。G的后t·k/r列由M1，M2，…，Mt構(gòu)成，使G=[Ik×k|Dk×m|M1，M2，…，Mt]。

同方法2 一樣，在方法3 的生成矩陣G中，前k列對(duì)應(yīng)碼字的信息符號(hào)，第k+1 到第N列對(duì)應(yīng)碼字的全局校驗(yàn)，最后t·k/r列對(duì)應(yīng)碼字的局部校驗(yàn)。顯然這些局部校驗(yàn)列為碼字中的每個(gè)信息符號(hào)提供了（r，t）-并行訪問(wèn)性能，同時(shí)方法3 繼承了GF（2）上隨機(jī)陣列碼的容錯(cuò)能力及高效的編譯碼速率。

定理4當(dāng)r|t，且存在一個(gè)（k，b，c，r，λ）-RBIBD，其中：c≥t。它的關(guān)聯(lián)矩陣M可由算法1 給出，那么方法3 給出的（n=N+k·t/r，k，r，t）-LRC 能夠以的概率修復(fù)n-k-k·t/r+t-δ個(gè)刪除錯(cuò)。

3 基于（n，k，r，t）-LRC的負(fù)載均衡方法

第2 章給出了三個(gè)（n，k，r，t）-LRC 的構(gòu)造方法，本章將它們應(yīng)用于分布式存儲(chǔ)，以實(shí)現(xiàn)數(shù)據(jù)塊間訪問(wèn)熱度及存儲(chǔ)節(jié)點(diǎn)間的負(fù)載均衡。

3.1 數(shù)據(jù)塊間訪問(wèn)熱度的負(fù)載均衡

在分布式存儲(chǔ)中，一個(gè)完整數(shù)據(jù)將被劃分為k個(gè)數(shù)據(jù)塊進(jìn)行存儲(chǔ)。針對(duì)不規(guī)模的存儲(chǔ)系統(tǒng)，本文選取相應(yīng)的（n，k，r，t）-LRC 對(duì)數(shù)據(jù)塊進(jìn)行編碼，編碼過(guò)程可以表示為：m1×k×Gk×n=c1×n。其中：信息向量m1×k表示原始數(shù)據(jù)塊向量；碼字c1×n表示編碼數(shù)據(jù)塊向量。由于復(fù)雜的數(shù)據(jù)應(yīng)用場(chǎng)景，數(shù)據(jù)塊之間的訪問(wèn)熱度負(fù)載不均成為常態(tài)，某些數(shù)據(jù)塊過(guò)高的訪問(wèn)熱度成為訪問(wèn)效率的瓶頸。因此，本文首先基于（n，k，r，t）-LRC 的（r，t）-并行訪問(wèn)性能給出了一個(gè)熱數(shù)據(jù)訪問(wèn)算法以降低熱數(shù)據(jù)的訪問(wèn)壓力。

例4 設(shè)數(shù)據(jù)塊m=(m1，m2，…，m15)，利用方法1 給出的（25，15，3，2）-LRC 進(jìn)行編 碼，得到編 碼數(shù)據(jù) 塊向量c=(m1，m2，…，m15，l1，l2，…，l10)。其中l(wèi)1，l2，…，l10為局部校驗(yàn)塊，根據(jù)生成矩陣G可得局部校驗(yàn)塊的生成式如表2 所示，構(gòu)成兩組不相交的修復(fù)集。假設(shè)數(shù)據(jù)塊m1的訪問(wèn)熱度過(guò)高，根據(jù)算法2，可以得到t=2 組索引集合Г1=｛4，11，16｝，Г2=｛3，6，22｝，對(duì)應(yīng)的兩組編碼塊向量為mГ1=(m4，m11，l1)，mГ2=(m3，m6，l7)。由生成矩陣G進(jìn)行譯碼可得m1的兩個(gè)譯碼公式如式（7）、（8）所示，根據(jù)算法2 的步驟6），動(dòng)態(tài)選擇其中之一作為m1的訪問(wèn)方式，即可分散多個(gè)請(qǐng)求對(duì)于m1的訪問(wèn)負(fù)載，實(shí)現(xiàn)數(shù)據(jù)塊間的負(fù)載均衡。

表2 例4中局部校驗(yàn)塊的生成式Tab.2 Generation formulas of local parity blocks in example 4

3.2 分布式存儲(chǔ)節(jié)點(diǎn)間的負(fù)載均衡

分布式存儲(chǔ)中節(jié)點(diǎn)間的負(fù)載不均也是影響性能的重要因素，通?？梢允褂煤侠淼臄?shù)據(jù)布局及遷移策略來(lái)均衡節(jié)點(diǎn)負(fù)載。為了避免頻繁的數(shù)據(jù)遷移影響存儲(chǔ)系統(tǒng)的整體性能，本文結(jié)合熱數(shù)據(jù)訪問(wèn)算法，通過(guò)合理的數(shù)據(jù)布局達(dá)到更優(yōu)的負(fù)載均衡效果。

小規(guī)模分布式存儲(chǔ)可以采用方法1 的（n，k，r，t）-LRC 對(duì)數(shù)據(jù)編碼，為了在均衡節(jié)點(diǎn)負(fù)載的同時(shí)也能發(fā)揮存儲(chǔ)系統(tǒng)的局部修復(fù)性能，將編碼數(shù)據(jù)塊如圖2 所示布局于存儲(chǔ)系統(tǒng)中，稱(chēng)其為縱式布局：

1）首先在編碼數(shù)據(jù)塊中任選一個(gè)修復(fù)集，將數(shù)據(jù)塊及局部校驗(yàn)塊按照修復(fù)集中的分組方式縱式存儲(chǔ)于各節(jié)點(diǎn)中，如例4 中，選擇修復(fù)集1，則原始數(shù)據(jù)塊將按照該修復(fù)集分組存儲(chǔ)于各存儲(chǔ)節(jié)點(diǎn)，對(duì)應(yīng)的局部校驗(yàn)塊l1，l2，…，l5負(fù)責(zé)各自節(jié)點(diǎn)內(nèi)的局部修復(fù)。

2）為實(shí)現(xiàn)節(jié)點(diǎn)間的負(fù)載均衡，將其余修復(fù)集的局部校驗(yàn)塊與關(guān)聯(lián)數(shù)據(jù)塊錯(cuò)位存儲(chǔ)。如例4，修復(fù)集2 中，局部校驗(yàn)塊l6與數(shù)據(jù)塊m2、m10、m12相關(guān)聯(lián)，它們分別存儲(chǔ)于D3、D4、D5，那么l6要與它們錯(cuò)位存儲(chǔ)，就只能存儲(chǔ)在D1或D2中。于是按照這個(gè)規(guī)則，l6，l7，…，l10的存儲(chǔ)布局如圖2 所示。

圖2 一個(gè)（25，15，3，2）-LRC的編碼數(shù)據(jù)布局Fig.2 Encoded data layout of a（25，15，3，2）-LRC

縱式存儲(chǔ)布局有以下兩點(diǎn)優(yōu)勢(shì)：

1）實(shí)現(xiàn)存儲(chǔ)節(jié)點(diǎn)間的負(fù)載均衡。在例4 中，假設(shè)數(shù)據(jù)塊m1的訪問(wèn)熱度過(guò)高，可以選擇式（7）或式（8）兩種方式對(duì)m1進(jìn)行訪問(wèn)。而結(jié)合圖2 可以看出，利用式（8）進(jìn)行訪問(wèn)，訪問(wèn)請(qǐng)求可以被分散到D2～D4節(jié)點(diǎn)，使節(jié)點(diǎn)之間負(fù)載均衡。

2）當(dāng)節(jié)點(diǎn)內(nèi)數(shù)據(jù)塊發(fā)生刪除錯(cuò)時(shí)，可以利用某一修復(fù)集在節(jié)點(diǎn)內(nèi)進(jìn)行修復(fù)，節(jié)省了跨節(jié)點(diǎn)修復(fù)的數(shù)據(jù)訪問(wèn)開(kāi)銷(xiāo)，進(jìn)一步提升系統(tǒng)性能。

對(duì)于中大規(guī)模的存儲(chǔ)系統(tǒng)，可以使用方法2 或方法3 給出的（n，k，r，t）-LRC 對(duì)數(shù)據(jù)進(jìn)行編碼，提供負(fù)載均衡、局部修復(fù)，及較好的容錯(cuò)能力，對(duì)其編碼數(shù)據(jù)使用橫縱聯(lián)合布局：

1）首先仍然對(duì)局部校驗(yàn)塊采用縱式布局方案，最大化節(jié)點(diǎn)間的負(fù)載均衡效果和存儲(chǔ)系統(tǒng)的局部修復(fù)性能，如例5中，給出l1，l2，…，l10的存儲(chǔ)布局如圖3 所示。

2）將全局校驗(yàn)塊單獨(dú)存儲(chǔ)于一個(gè)節(jié)點(diǎn)，稱(chēng)它為校驗(yàn)節(jié)點(diǎn)，如例5，校驗(yàn)節(jié)點(diǎn)D6存儲(chǔ)了所有的全局校驗(yàn)塊p1，p2，…，p5。

例5 假設(shè)數(shù)據(jù)塊m=(m1，m2，…，m15)，利用方法2 給出的（30，15，3，2）-LRC 進(jìn)行編碼，得到編碼數(shù)據(jù)塊向量c=（m1，m2，…，m15，p1，p2，…，p5，l1，l2，…，l10），其中：p1，p2，…，p5為全局校驗(yàn)塊；l1，l2，…，l10為局部校驗(yàn)塊，生成式如表3 所示，構(gòu)成兩個(gè)不相交的修復(fù)集。編碼數(shù)據(jù)塊的橫縱聯(lián)合布局如圖3 所示，以發(fā)揮存儲(chǔ)系統(tǒng)的負(fù)載均衡和局部修復(fù)性能。

圖3 一個(gè)（30，15，3，2）-LRC的編碼數(shù)據(jù)布局Fig.3 Encoded data layout of a（30，15，3，2）-LRC

表3 例5中局部校驗(yàn)塊的生成式Tab.3 Generation formulas of local parity blocks in example 5

該存儲(chǔ)系統(tǒng)具有縱式布局的兩個(gè)優(yōu)勢(shì)——節(jié)點(diǎn)間的負(fù)載均衡及節(jié)點(diǎn)內(nèi)高效的局部修復(fù)性能。另外，全局校驗(yàn)塊保障了存儲(chǔ)系統(tǒng)不俗的容錯(cuò)能力，以采用方法2 中（n，k，r，t）-LRC 進(jìn)行編碼的存儲(chǔ)系統(tǒng)為例，能夠修復(fù)任意n-k-k·t/r+t個(gè)刪除錯(cuò)，例5 中的存儲(chǔ)系統(tǒng)可以容任意7 個(gè)數(shù)據(jù)塊的刪除錯(cuò)。

4 實(shí)驗(yàn)與結(jié)果分析

本文基于（n，k，r，t）-LRC 給出了一種適用于分布式存儲(chǔ)的負(fù)載均衡方法，本章將展開(kāi)具體實(shí)驗(yàn)。除此之外，還會(huì)從負(fù)載均衡代價(jià)、存儲(chǔ)性能、擴(kuò)展性能等多個(gè)維度與同類(lèi)研究進(jìn)行對(duì)比分析。

4.1 負(fù)載均衡能力分析

實(shí)驗(yàn)方案：本文生成k=30 個(gè)數(shù)據(jù)塊，編號(hào)為（1，2，…，k），分別利用方法1 給出的（n=40，k=30，r=3，t=1）-LRC，（n=50，k=30，r=3，t=2）-LRC，（n=60，k=30，r=3，t=3）-LRC 進(jìn)行編碼，并模擬用戶(hù)對(duì)這些數(shù)據(jù)塊進(jìn)行T次隨機(jī)訪問(wèn)。以此設(shè)計(jì)兩組對(duì)比實(shí)驗(yàn)，分別限定數(shù)據(jù)的隨機(jī)訪問(wèn)范圍為[ 1，k/2 ]，模擬真實(shí)存儲(chǔ)系統(tǒng)中數(shù)據(jù)塊訪問(wèn)負(fù)載不均的情形。定義各數(shù)據(jù)塊間訪問(wèn)次數(shù)的標(biāo)準(zhǔn)差S為負(fù)載均衡度，用于衡量負(fù)載均衡表現(xiàn)，標(biāo)準(zhǔn)差越小，負(fù)載均衡表現(xiàn)越佳。

實(shí)驗(yàn)假設(shè)數(shù)據(jù)塊的訪問(wèn)次數(shù)為數(shù)據(jù)塊熱度，當(dāng)數(shù)據(jù)塊熱度（訪問(wèn)次數(shù)）時(shí)，通過(guò)算法2 實(shí)現(xiàn)數(shù)據(jù)塊間的訪問(wèn)負(fù)載均衡。

1）情形1，限定數(shù)據(jù)的隨機(jī)訪問(wèn)范圍為[ 1，k/2 ]，它的數(shù)據(jù)塊訪問(wèn)負(fù)載分布如圖4（a）所示，訪問(wèn)負(fù)載集中在[ 1，k/2]這些數(shù)據(jù)塊之間，負(fù)載均衡度S≈20.3。分別基于（n=40，k=30，r=3，t=1）-LRC、（n=50，k=30，r=3，t=2）-LRC 和（n=60，k=30，r=3，t=3）-LRC 使用算法2 均衡各數(shù)據(jù)塊間的訪問(wèn)負(fù)載，得到訪問(wèn)負(fù)載分布如圖4（b）～（d）所示。隨著修復(fù)集數(shù)量t的增多，負(fù)載均衡度逐漸降低，分別為：S1≈14.1、S2≈10.4、S3≈5.2，可以看到算法2 表現(xiàn)出了優(yōu)秀的負(fù)載均衡性能。

圖4 情形1下的數(shù)據(jù)訪問(wèn)負(fù)載分布圖Fig.4 Load distribution diagram of data blocks in case 1

2）情形2，更極端的情況，本文限定數(shù)據(jù)的隨機(jī)訪問(wèn)范圍為[ 1，]，數(shù)據(jù)塊訪問(wèn)負(fù)載分布如圖5（a）所示，訪問(wèn)負(fù)載集中在[ 1，]這些數(shù)據(jù)塊之間，此時(shí)的負(fù)載均衡度S≈36.5。分別基于方法1 給出的（n=40，k=30，r=3，t=1）-LRC、（n=50，k=30，r=3，t=2）-LRC、（n=60，k=30，r=3，t=3）-LRC 使用算法2 均衡各數(shù)據(jù)塊間的訪問(wèn)負(fù)載，均衡后的訪問(wèn)負(fù)載分布如圖5（b）～（d）所示，對(duì)應(yīng)的負(fù)載均衡度分別為S1≈25.5、S2≈17.8、S3≈14.3。

圖5 情形2下的數(shù)據(jù)訪問(wèn)負(fù)載分布圖Fig.5 Load distribution diagram of data blocks in case 2

4.2 對(duì)比分析

上述實(shí)驗(yàn)證明了本文基于（n，k，r，t）-LRC 的負(fù)載均衡方法可以有效地應(yīng)用于存儲(chǔ)系統(tǒng)均衡數(shù)據(jù)塊間的訪問(wèn)負(fù)載，且隨著t的增大，負(fù)載均衡能力逐漸增強(qiáng)。相較于同類(lèi)研究，如基于多副本的負(fù)載均衡策略與基于糾刪碼的負(fù)載均衡策略，本文方法的代價(jià)更小、效率更高。

本文方法的核心思想是利用（n，k，r，t）-LRC 的（r，t）-并行訪問(wèn)性能為每個(gè)數(shù)據(jù)塊提供t種不同的訪問(wèn)方式，以此均衡數(shù)據(jù)塊間的訪問(wèn)負(fù)載，執(zhí)行負(fù)載均衡方法僅僅會(huì)增加存儲(chǔ)系統(tǒng)r-1 倍的訪問(wèn)量。而基于（n，k）-MDS 碼的負(fù)載均衡方法，每次觸發(fā)均衡方法都會(huì)激增k-1 倍的訪問(wèn)量。例如，文獻(xiàn)［19］中提出了一種基于（2k，k）-MDS 碼的負(fù)載均衡方法。在情形2 的實(shí)驗(yàn)基礎(chǔ)上，基于（2k，k）-MDS 碼使用算法2 均衡訪問(wèn)負(fù)載，得到實(shí)驗(yàn)結(jié)果如圖6 所示，可以看到索引號(hào)為（k/4，k］的數(shù)據(jù)塊之間增加了大量的訪問(wèn)請(qǐng)求，但原熱點(diǎn)數(shù)據(jù)塊的負(fù)載壓力并沒(méi)有明顯減輕，這正是因?yàn)樵谠搶?shí)驗(yàn)中每執(zhí)行一次負(fù)載均衡都會(huì)激增k-1=29 倍的訪問(wèn)量，代價(jià)巨大。相比之下，圖5（d）中的負(fù)載均衡效果顯著，基于（n，k，r，t）-LRC 每執(zhí)行一次負(fù)載均衡方法只增加r-1=2 倍的訪問(wèn)量。本文方法中的r遠(yuǎn)小于k，實(shí)際應(yīng)用中將極大地節(jié)省網(wǎng)絡(luò)帶寬、減少訪問(wèn)負(fù)載。另一方面，基于（n，k）-MDS碼的負(fù)載均衡方法，普遍存在的問(wèn)題是基于有限域的運(yùn)算復(fù)雜，它的規(guī)模難以擴(kuò)展。針對(duì)這個(gè)問(wèn)題，本文基于方法3 給出的（n，k，r，t）-LRC 結(jié)合了二元域上隨機(jī)陣列碼的優(yōu)良性質(zhì)，可以應(yīng)用于大規(guī)模存儲(chǔ)系統(tǒng)。

圖6 使用MDS碼進(jìn)行實(shí)驗(yàn)的負(fù)載均衡效果Fig.6 Load balancing effect in experiment using MDS code

相較于多副本方式的負(fù)載均衡方法，本文方法更有優(yōu)勢(shì)。一方面數(shù)據(jù)以多副本方式存儲(chǔ)于系統(tǒng)中，存儲(chǔ)效率極低，以三副本為例，它的存儲(chǔ)效率只有33%。另一方面，基于多副本的負(fù)載均衡會(huì)涉及頻繁的數(shù)據(jù)遷移，降低存儲(chǔ)節(jié)點(diǎn)的使用率。本文很好地解決了這些問(wèn)題，利用（n，k，r，t）-LRC將數(shù)據(jù)編碼后進(jìn)行存儲(chǔ)，存儲(chǔ)效率k/n＞50%是常態(tài)；利用局部修復(fù)碼的（r，t）-并行訪問(wèn)性能以及合理的數(shù)據(jù)布局方案，本文的負(fù)載均衡方法有效避免了頻繁的數(shù)據(jù)遷移。

5 結(jié)語(yǔ)

隨著數(shù)據(jù)應(yīng)用場(chǎng)景的日益豐富，面向熱數(shù)據(jù)的分布式存儲(chǔ)對(duì)訪問(wèn)效率提出了更高的要求。針對(duì)存儲(chǔ)系統(tǒng)中熱數(shù)據(jù)訪問(wèn)頻率過(guò)高，導(dǎo)致冷熱數(shù)據(jù)負(fù)載嚴(yán)重失衡的問(wèn)題，本文基于（n，k，r，t）-LRC 提出了一種適用于分布式存儲(chǔ)的負(fù)載均衡方法，以提高存儲(chǔ)系統(tǒng)的訪問(wèn)性能。其中（n，k，r，t）-LRC 是存儲(chǔ)編碼新技術(shù)的前沿課題，本文給出了一種面向分布式存儲(chǔ)負(fù)載均衡應(yīng)用的顯式構(gòu)造方法，利用（n，k，r，t）-LRC 的（r，t）-availability 性質(zhì)，不僅能快速響應(yīng)丟失數(shù)據(jù)塊的修復(fù)請(qǐng)求，進(jìn)行局部修復(fù)，還能夠?yàn)槊總€(gè)數(shù)據(jù)塊提供t+1 種不同的訪問(wèn)方式，以均衡數(shù)據(jù)塊間的訪問(wèn)負(fù)載。相較之下，現(xiàn)有的同類(lèi)研究在實(shí)現(xiàn)負(fù)載均衡時(shí)會(huì)導(dǎo)致訪問(wèn)量激增，額外帶來(lái)大量的網(wǎng)絡(luò)帶寬。而本文方法以更小的代價(jià)達(dá)到了較好的負(fù)載均衡效果，不僅考慮了數(shù)據(jù)塊間的訪問(wèn)負(fù)載均衡，還通過(guò)合理的數(shù)據(jù)布局盡可能均衡了各節(jié)點(diǎn)間的訪問(wèn)負(fù)載。另外，本文方法也可以為后續(xù)更多數(shù)據(jù)存儲(chǔ)應(yīng)用提供思路，如適用于邊緣計(jì)算的存儲(chǔ)系統(tǒng)實(shí)質(zhì)上與本文的核心思想有異曲同工之妙。

盡管如此，本文方法也存在一定的局限性。一方面，由于RBIBD 的生成算法和計(jì)算機(jī)的算力影響，在構(gòu)造（n，k，r，t）-LRC 時(shí)，修復(fù)集的數(shù)量t受到限制，而它對(duì)負(fù)載均衡的效果影響重大，如何在理論范圍內(nèi)構(gòu)造任意規(guī)模、任意參數(shù)的（n，k，r，t）-LRC 是一大挑戰(zhàn)；另一方面，如何設(shè)置參數(shù)t，在負(fù)載均衡效果與存儲(chǔ)效率之前尋找平衡，以最小的代價(jià)達(dá)到理想的效果，值得進(jìn)一步研究。