蔣靜 王金玉

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

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

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

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

1 ?相關(guān)概念

1.1 局部修復(fù)碼

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

2 ?結(jié)語

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

參考文獻(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.