局部修复码的三个关键问题研究

Big data has deeply changed the way of our life, work and thinking, one of the core technologies is distributed storage coding. In this project, the problems of locally repairable codes (LRCs) in distributed storage system will be investigated, including construction of optimal LRCs over small fields, proposing a practical bound for LRCs over small fields and deployment of distributed storage system and performance of proposed LRCs and feasibility. First, we consider to investigate the construction of LRCs with better algebraic structure or combinatorial character, analyze its character through finite geometry and graph theory, further determine the character of general LRCs, locality and availablity, then construct optimal LRCs. Secondly, we discuss the reason why existing bounds are impractical, then establish a new relation of code parameters combining the ideas of linear codes and combinatorial property of locality, manage to propose a new bound for LRCs. At last, deploying a cluster system equipped by Hadoop, we will study the performance of LRCs and analyze Mean Time To Data Loss and reliability under the Markov model. The development and the prospective achievements of the project can not only reveal intrinsic rules of LRCs, but also provide theoretical basis for practicality of LRCs.

大数据正深刻改变着人类的生活、工作和思维方式，其核心技术之一是分布式存储编码技术。本项目将研究分布式存储系统中局部修复码（Locally Repairable Code，简称LRC）的相关问题：构造小域上最优LRC、提出实用可行的码界、搭建分布式系统并验证编码方案的性能及可行性等问题。首先，研究小域上具有特殊代数结构或组合特征的LRC构造问题，用有限几何和图论来刻画LRC的特征，进而给出一般LRC的结构特征，确定局部度和可用度，从而构造出参数最优的LRC；其次，分析现有码界难以适用的原因，结合线性码码界的提出思路和局部度的组合特性确立码参数之间新的刻画方式，从而提出普适的LRC码界；最后，搭建一个分布式存储系统，实验验证所构造LRC的性能，借助标准马尔可夫链模型分析编码方案的数据丢失平均时间、系统可靠性等问题。项目的开展和预期成果将揭示LRC的内在规律，为相关编码方案的实用化提供理论依据。

当分布式存储系统中出现坏的节点时，为了确保整个系统的正常运行,需要恢复坏节点中的数据。传统恢复数据的纠删策略增大了网络流量，降低了整个系统的修复效率。局部修复码可以完美地解决这个问题。本项目研究了小域上局部修复码的特征描述、构造方法及最优性判定等问题。首先，分析了d=4的二元LRC的特征，给出其校验矩阵形式，提出了构造距离为4的二元LRC的构造方法；其次，利用分圆陪集理论刻画了三元循环LRC的特征，构造了给定码长的最优三元LRC。同时，基于五元最优码及矩阵变换技巧构造了达到Singleton界的五元LRC。最后，基于特殊几何结构(Cap、Generalized Quadrangles、sunflower、ovoid)的内在性质与LRC之间的联系，构造了距离为6的q元最优LRC和可修复多个节点数据的LRC。通过上述内容的研究揭示了小域上LRC的内在规律，为LRC的应用于实际提供了理论依据，为一般域上构造LRC提供了借鉴。