一類(lèi)最優(yōu)局部修復(fù)碼的構(gòu)造

蔣靜 王金玉

摘 ? 要：有多個(gè)互不相交修復(fù)集合的局部修復(fù)碼是一類(lèi)很重要的能應(yīng)用于提高分布式存儲(chǔ)系統(tǒng)修復(fù)效率的碼。本文利用多種組合結(jié)構(gòu)，如填充、平衡不完全區(qū)組設(shè)計(jì)等，構(gòu)造了參數(shù)較小的最優(yōu)局部修復(fù)碼，其中每一個(gè)修復(fù)集合至多包含4個(gè)元素且恰有一個(gè)是校驗(yàn)元。

關(guān)鍵詞：局部修復(fù)碼 ?分布式存儲(chǔ)系統(tǒng) ?填充 ?平衡不完全區(qū)組設(shè)計(jì)

中圖分類(lèi)號(hào)：TN911 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1674-098X（2019）02（a）-0088-05

在大數(shù)據(jù)環(huán)境下，分布式存儲(chǔ)系統(tǒng)被應(yīng)用于海量數(shù)據(jù)的存儲(chǔ)。在分布式存儲(chǔ)系統(tǒng)中，原始數(shù)據(jù)被分成k個(gè)等大小的片段，然后被編碼成n個(gè)片段存儲(chǔ)在n個(gè)不同的節(jié)點(diǎn)中，使得當(dāng)要修復(fù)1個(gè)節(jié)點(diǎn)時(shí)，我們只需連接其中部分節(jié)點(diǎn)。根據(jù)實(shí)際需求選用特定的編碼是分布式存儲(chǔ)的一項(xiàng)關(guān)鍵技術(shù)，其中用到的局部修復(fù)碼是近幾年非常熱門(mén)的一個(gè)研究方向。最近，Cai等[1]在假設(shè)每個(gè)節(jié)點(diǎn)有多個(gè)修復(fù)集合，且每一個(gè)修復(fù)集合只包含一個(gè)校驗(yàn)元的前提下，利用組合結(jié)構(gòu)填充（packing）構(gòu)造了一些最優(yōu)局部修復(fù)碼的無(wú)窮類(lèi)。本文基于文獻(xiàn)[1]的結(jié)果，利用多種組合結(jié)構(gòu)構(gòu)造了若干最優(yōu)局部修復(fù)碼。

1 ?相關(guān)概念

1.1 局部修復(fù)碼

定理1的證明：由推論1-4和引理7-8可知，存在一個(gè)（δ-1）-正則（k，R，1）-填充，其中（k，δ-1，R）的值為表1中列出的值。由引理1可知，存在一個(gè)擁有局部信息（r，δ，1）c的最優(yōu)對(duì)稱(chēng)碼。

2 ?結(jié)語(yǔ)

本文基于文獻(xiàn)[1]的結(jié)果，構(gòu)造了當(dāng)k（δ-1）≡0，3（mod 4）且k≤20時(shí)，擁有局部信息（4，δ，1）c的最優(yōu)對(duì)稱(chēng)碼。本文方法也可以用于構(gòu)造k>21時(shí)的最優(yōu)局部修復(fù)碼，但這樣的局部修復(fù)碼結(jié)構(gòu)較復(fù)雜、相應(yīng)的構(gòu)造也更加困難，需要對(duì)構(gòu)造方法做進(jìn)一步地改進(jìn)。

參考文獻(xiàn)

[1] Cai H， Cheng M， Fan C， et al. Optimal Locally Repairable Systematic Codes Based on Packings[J]. IEEE Transactions on Communications， 2019， 67（1）： 39-49.

[2] Huang C， Chen M， Li J. Pyramid Codes： Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems[J]. ACM Transactions on Storage， 2013， 9（1）：3.

[3] Wang A， Zhang Z. Repair Locality with Multiple Erasure Tolerance[J]. IEEE Transactions on Information Theory， 2014， 60（11）： 6979-6987.

[4] Rawat A S， Papailopoulos D S， Dimakis A G， et al. ?Locality and Availability in Distributed Storage[J]. IEEE Transactions on Information Theory， 2016， 62（8）： 4481-4493.

[5] Chung H， Kumar P V. Optical Orthogonal Codes-New Bounds and an Optimal Construction [J]. IEEE Transactions on Information Theory， ?1990， 36（4）： 866-873.

[6] Yin J. Some Combinatorial Constructions for Optical Orthogonal Codes[J]. Discrete Mathematics， 1998， 185（1-3）： 201-219.

[7] Colbourn C J， ? Dinitz J H. Handbook of Combinatorial Designs[M]， Chapman & Hall/CRC， vol. 42， 2006.