| In the big data age, the information technology industry has shifted its focus to storage from computing, making mass storage a trend. Distributed storage systems, deployed over clusters of commodity servers, are widely used for mass data storage because of their low cost and high scalability. Due to the low availability of distributed storage nodes, ensuring high data reliability has become a crucial problem. In order to ensure data reliability, systems must adopt certain data fault-tolerant techniques. As a fault-tolerant technique with high reliability and low storage space consumption, erasure codes can significantly improve distributed storage systems’ data reliability and reduce their costs. However, the heavy network load and poor efficiency of data repair for erasure codes seriously hinder their wide use in distributed storage systems. To tackle such problems, this thesis studies low network load data repair techniques and rapid data repair techniques for erasure codes. The main contributions obtained are as follows:The traditional metric of network load generated by data repair is the amount of data transmitted, which ignores the data transmission distance and can’t accurately measure the impact of data repair on network. For this problem, a network topology based network load metric called network cost is proposed. Network cost defines the network load of data transmission as the product of the amount of data transmitted and the transmission distance of data, which more accurately describes the network resources occupied by data transmission and its impact on network performance. Experimental results show that the network cost of data transmission can reflect the data transmission impact on network performance more accurately than the amount of data transmitted. Therefore, network cost is a better metric of network load.In order to reduce the data repair network cost for erasure codes, a network topology based tree-structured data repair techniques called NTree is proposed. NTree builds a tree structure(repair tree) with minimum total distance according to the network topology to minimize the transmission distance of data during repair, which reduces the network cost. Moreover, an algorithm named OpTree is also proposed to select providers. OpTree can quickly make an optimal selection and generate the optimal repair tree at the same time, further reducing the network cost. Simulation results show that, compared to starstructured data repair method, NTree can reduce the network cost by 20%- 45%.Targeting at accelerating the data repair process for erasure codes to improve degraded reads performance, a network topology based line-structured data repair technique called NLine is proposed. Analysis into the repair process of NTree shows that data repair speed is inversely proportional to the maximum in degree of the repair tree. NLine organizes all the nodes involved in data repair into a line structure(repair path) according to network topology. Since the maximum in degree of line structure is only 1, NLine achieves the highest data repair speed. In order to minimize the network cost of NLine, an approximate optimal repair path planning algorithm named OpLine is presented. A large number of simulation results show that NLine is able to repair 5 times as quick as NTree and 2 times as quick as star-structured data repair method, with a network cost very close to that of NTree.Based on above theoretical research results, a data repair prototype system for erasure codes called ECRepair is designed and implemented. Fully following the design principle of the separation of mechanism and policy, ECRepair not only supports network topology based tree-structured data repair technique NTree and network topology based line-structured data repair technique NLine but also can be easily extended to support other tree-structured data repair techniques. Besides, ECRepair applies to all linear erasure codes. The results of thorough experiments in ECRepair show that among network topology based tree-structured data repair technique NTree, network topology based line-structured data repair technique NLine and star-structured data repair method, NTree has the lowest network cost and highest parallel repair speed, and NLine has the highest serial repair speed and the best degraded reads performance, which further validates the theoretical analysis and simulation results. |
