徐光伟 史春红 冯向阳 罗 辛 石秀金 韩松桦 李 玮

(东华大学计算机科学与技术学院 上海 201620)(gwxu@dhu.edu.cn)

互联网发展带来的数据爆炸性增长，对数据存储提出了巨大挑战.企业和个人采用云存储提供的在线外包存储以获取价格低廉的海量数据存储空间.这种外包存储的最基本要求是要保证数据的可用性.目前常用的方法是通过数据备份来保证数据可用性，如多副本[1](multiple-replica)存储，通过对原始数据进行备份，一旦数据发生损坏或丢失时，可利用备份数据进行恢复.

为提高云存储的利用率和数据可用性，常采用擦除码(erasure codes)技术[2]，其中纠删码reed-solomon是一种应用广泛的擦除码[3].利用纠删码计算编码块进行冗余存储，可在相同的存储空间下获得高的数据可用性.与多副本复制相比，纠删码在相同的存储开销下提高了数据存储的可靠性[4].目前有许多改进的纠删码方法，如纠双错的极大距离可分码(maximum distance separable, MDS)[5]、EVENODD(efficient encoding on double disk failures)[6]、X-code[7]、RDP(row-diagonal parity) 码[8]、自由码(liberation code)[9]等.然而，基于纠删码的方法尽管节省了数据存储空间，但损坏数据恢复时，常因文件解码需要下载与原文件大小相同的编码块，造成大量的通信和计算开销.基于网络编码(network coding)技术[10]应用到数据备份时，通过对数据块之间的线性编码来生成数据块.损坏数据恢复时，无需解码原文件，只需下载一定量的数据块即可通过线性计算恢复原数据，从而降低了计算和通信开销.但这种方法在数据译码时，一旦数据块的编码系数存在线性相关性会导致译码失败……