Research On Optimization Of Erasure Code Based On FR Code

With the rapid advances in computer technology, the explosive growth of computer data forces people to put forward higher requirements to storage system. Distributed storage system is proving the best option because of its low price and excellent performance. Cloud storage technology, which derived from Distributed storage system, is adopt by the major IT companies and fully commercialized. However, the unreliability of network storage node make the system to use a large amount of storage space for storing redundant data and to do the high-frequency node repair when the node failure. This is a serious waste of limited network bandwidth and storage resources, and reduce the quality of storage services.Therefore, Distributed storage systems not only need to ensure that multi-node fault tolerance,but need to reduce consumption during the repair network. To this end, a variety of fault-tolerant coding techniques, in particular reproduction code, to obtain in-depth study.Paper [1] proposed a Fractional Repetition code. FR code not required the calculation in the repair process and have better storage capacity than the Minimum Bandwidth Regenetating code. It can achieve the theoretical minimum bandwidth consumption in one-failure repair.However, existing constructures of FR Code often depend on the particular structures in combination, applied only to a limited parameter case. Under normal parameters, how to construct optimal storage capacity FR coding is considered to be an openning question.In this paper, based on the FR code in distributed storage system, we present a method to gives data distribution policy in any parameters. The data distribution policy make the number of connections reaches the theoretical minimum in recovering data. The main work in the following aspects.(1) In order to find the optimal coding matrix FR Code, this paper presents traversal search the optimal encoding matrix based on the Young tableau. First, we change the FR Code to Boolean matrix, then use the one-to-one correspondence between Young tableau and Boolean matrix realize the corresponding between FRC coding matrix and Young tableau. At last we use the special nature of Young tableau to pruning the search space. The proposed algorithm can complete traversal the coding matrix set of FRC code in any parameters. And the pruning optimization of algorithm can reduce more than 95% of the search term.Experiments show better results of the algorithm.(2) On the basis of Boolean matrix description of FR Code, this paper presents a tabu search algorithm based on Boolean matrix exchange operation. According to the characteristic of FR Code structure, this paper studies the relationship between the distribution of one in coding matrix and the storage capacity of FR Code, propose and prove the sufficient condition theorem for FRC code storage capacity and coding matrix. On this basis, we propose a tabu search algorithm using C4 ring count as heuristic criterion. Algorithm can construct the FRCcoding matrix with current optimal storage capacity in any parameters. Meanwhile, this paper presents a faster lap count C4 matrix method reduces the time complexity of the algorithm.Experiments show that the algorithm with different encoding matrix for the initial search node can get beter coding matrix with basically same storage capacity. And the storage capacity of results in algorithm is closer to the upper bound.