颜好, 胡万宝, 陈子星

(安庆师范大学数学与计算科学学院, 安庆 246133)

1 引言

传统的大型存储体系依赖于通过块复制来提供系统的可靠性, 复制的缺点是存储开销大. 擦除编码技术以相当小的存储开销实现了更高的数据可靠性, 局部恢复码(LRC码) 是擦除编码的一种, 它极大地提高了分布式存储系统的可靠性和有效性[1].

虽然现代存储系统允许几个符号丢失的情况出现, 但到目前为止, 一个符号丢失的情况更常见, 因此系统应重点设计一个符号丢失的精确恢复. 在系统中一个符号丢失的精确恢复效率, 可以通过三个不同的指标来量化, 每个指标都与不同的存储系统和应用相关, 已经有许多论文在这三个指标下考虑精确恢复问题, 即读取位的数量[2]、恢复带宽[3-6]、局部化参数r(参与恢复过程符号的个数), 关注的是局部化参数r[7-8]. 对于一个局部恢复码, 如果一个符号丢失, 可以通过至多r个符号来恢复. 局部恢复码的精确定义如下[9]:

定义1.1设C是Fq上的[n,k]线性码,如果对于每个i ∈{1,2,··· ,n},存在r个元素的子集Ii ⊆{1,2,··· ,n}{i}和一个函数φi:Frq →Fq使得对于每个码字x ∈C有xi=φi(xj1,xj2,··· ,xjr), 其中j1

如果C是(n,k,r) LRC 码, 则C的最小距离满足

若(1) 式成立, 称C是距离最优的(n,k,r) LRC 码. 当r=k时, (1) 式是著名的singleton 界. 若等式成立, 即

则称码C是MDS 码. 每个坐标重复两次得到的长度为2k的线性码是局部化参数为1的LRC 码. 另外, 整个码字可以通过接收除丢失符号之外的k个符号来确定, 因此局部化参数1≤r ≤k[10]. 文献[7] 构造了一族最优的(n,k,r) LRC 码, 与传统的MDS 码一样, 在这族LRC 码中, 码长……