基于结构化因子图的高效可重构局部修复码研究

Data have become an important resource of enterprise and society concern. How to provide reliable, efficient and security data storage service via using unreliable storage node has become a hot topic in the literature of distributed storage systems. Although the employment of locally repairable codes (LRCs) can greatly improve the performance of data storage systems, how to construct LRCs with excellent performance under the scenario, where the characteristic of data is dynamically change become "cold" and "hot", faces technical challenges. By exploiting the factor graph characteristics, this project will focus on the following research topics: 1) Establish a relationship between the parameters of factor graph and the structure of LRCs, further learn the impacts of factor graph parameters on the performance of LRCs; 2) Research and derive functional relation among average locality, availability and minimum distance of code under the constraint of structured factor graph; 3) Propose an algorithm for designing and optimizing structured factor graph subject to complicated constraints, and finally construct a class of reconfigurable LRCs; 4) Analyze the effect of trapping sets on the Markov model of distributed storage based on error correction codes, extend the evaluation function of mean-time-to-data-loss (MTTDL). This project will enrich and develop the theory and technology of LRCs for distributed data storage systems.

数据已经成为企业和社会关注的重要资源。如何在不可靠的存储节点上提供可靠、高效、安全的数据存储服务，是目前分布式存储领域一个热点课题。局部修复码的引入大大改善了分布式存储系统性能，但在数据“冷”“热”不均衡及动态变化场景下如何设计、构造性能优异的局部修复码是当前面临的一个难题。本课题拟基于结构化因子图开展以下几方面的研究：1）建立因子图与局部修复码之间的参数映射关系，明确因子图各参数对局部修复码性能的影响；2）研究推导结构化因子图约束下的局部修复码的平均修复局部度、平均修复可用度与极小码距之间的函数关系；3）提出在复杂约束条件下结构化因子图的设计及优化算法，构造一类高效可重构局部修复码；4）分析译码停止集对基于容错编码存储系统的马尔科夫状态模型的影响，扩展分布式存储系统数据丢失平均时延评估关系式。本课题的研究将对丰富和发展局部修复码相关理论及技术具有非常重要的意义。

随着物联网、云计算、大数据的发展和应用，以“数据为中心，存储为中心”已经成为重要发展趋势。大规模分布式存储系统以其海量存储能力、高吞吐量、高可用性和低成本的突出优势被广泛使用，但随着存储节点、存储容量、存储开销的不断增加，如何在复杂存储应用环境下，有效控制存储开销、修复带宽的同时提升存储的可靠性，成为当前面临的一个主要挑战。.本项目从差错控制编码的角度出发，开展局部修复码设计构造、性能分析、修复策略，以及综合测试等方面的系统深入研究，具体研究成果包括：1）部署了Ceph分布式存储系统、搭建了分布式存储算法仿真、硬件测试环境，并对分布式存储节点的失效机制和修复策略进行了验证分析；2）基于packings，提出了一种修复集大小达到4的局部修复码设计构造方法，联合LDPC码的校验矩阵特性，对该码的性能特性进行了系统分析；3）提出一种构造在特定商环上，具有多个校验列的MDS阵列码称为GEBR码，并针对该类型码设计了一种基于LU分解的GEBR码解码算法，同时给出了该类型码的最小距离界；4）针对机架集群环境和“冷”“热”数据应用需求，提出了一种将（n, k, r, t, d）局部修复码的n个节点放到k个集群中放置策略，有效降低了修复开销。.在该项目的支持下，本课题组发表期刊论文13篇，其中SCI期刊论文12篇，EI会议论文6篇；申请发明专利7件,授权4件；培养硕士研究生9人，引进培养青年教师2人、博士后1人。