基于Erasure code的分布式存储系统中多重数据丢失的树状并行再生外文翻译资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

武汉理工大学毕业设计（论文）

英文文献翻译

目 录

Tree-Structured Parallel Regeneration for Multiple Data Losses in Distributed Storage Systems Based on Erasure Codes

Tree-Structured Parallel Regeneration for Multiple Data Losses in Distributed Storage Systems Based on Erasure Codes

SUN Weidong, WANG Yijie, PEI Xiaoqiang

National Key Laboratory for Parallel and Distributed Processing, School of Computer, National University of Defense Technology Changsha 410073, China

Abstract: To reduce the time required to complete the regeneration process of erasure codes, we propose a Tree-structured Parallel Regeneration (TPR) scheme for multiple data losses in distributed storage systems. Under the scheme, two algorithms are proposed for the construction of multiple regeneration trees, namely the edge-disjoint algorithm and edge-sharing algorithm. The edge-disjoint algorithm constructs multiple independent trees, and is simple and appropriate for environments where newcomers and their providers are distributed over a large area and have few intersections. The edge-sharing algorithm constructs multiple trees that compete to utilize the bandwidth, and make a better utilization of the bandwidth, although it needs to measure the available band-width and deal with the bandwidth changes; it is therefore difficult to implement in practical systems. The parallel regeneration for multiple data losses of TPR primarily includes two optimizations: firstly, transferring the data through the bandwidth optimized-paths in a pipeline manner; secondly, executing data regeneration over multiple trees in parallel. To evaluate the proposal, we implement an event-based simulator and make a detailed comparison with some popular regeneration methods. The quantitative comparison results show that the use of TPR employing either the edge-disjoint algorithm or edge-sharing algorithm reduces the regeneration time significantly.

Key words: distributed storage system; erasure code; replication; regeneration tree

I. INTRODUCTION

Cloud service providers gather a large number of commodity nodes to build up broad-scale data centers. In such a large system, data losses brought by frequent node departures and hardware failures should be treated as a rule and not an exception, which dramatically degrades the reliability of data in the system. Therefore, replication and erasure codes are widely used as redundant techniques to ensure the data reliability.

However, regeneration is indispensable to redundant techniques as failures may damage redundancy as well and eventually harm the reliability of stored data. During the regeneration process, the system chooses some active nodes (named as providers) to provide data furan idle node (named as newcomer) to reconstruct and store the lost data.

Replication is one of the most common redundant techniques, where m (the redundant factor equals m) identical copies of data object are kept in the system. Any of the replicas can provide services to data users. Another common redundant technique is erasure codes, in which each data object is firstly divided into blocks, and then these blocks are encoded into n (the redundant factor equals m/n)blocks and stored separately in n different storage nodes, where ngt;m. Compared with replication, erasure codes require less storage space. In Refs. [I-2], it is shown that systems employing erasure codes have Mean-Time-to-Failure (MTTF) many orders of magnitude higher than that of the replication. However, when the failure occurs, in the system employing replication, the newcomer only needs to download a replica from one provider; different from replication, newcomer of the system employing erasure codes has to download from at least k providers to regenerate the lost data. Therefore, the regeneration of erasure codes consumes more bandwidth and takes longer time.

In order to reduce the bandwidth consumption of erasure codes, Demakis et al. Propose Regeneration Code, which reduces the total amount of transferred data for regeneration process by accessing more than k providers[3-4]. In the traditional star-structured regeneration, the providers transfer data directly tithe newcomer, and the regeneration time depends on the bottleneck bandwidth between newcomer and providers. Li et al. in Ref. [5]prove that by adopting random linear codes, the bottleneck link can be bypassed by constructing a regeneration tree structure instead of the traditional star structure. Their experiment results further show that tree-structured construction can greatly reduce the regeneration time compared with the star-structured regeneration.

In modern large-scale distributed systems, frequent failures make multiple nodes failed often at the same time. Moreover, the service providers prefer to perform the regeneration with lazy policy so as to reduce the management cost, which means that the regenerations triggered only when the total amount of losses reaches a given threshold. Suppose there are n storage nodes initially, and r nodes failed at a certain time. It is necessary to construct r new nodes to maintain the original redundancy. The most common scheme for constructing multiple newcomers is to regenerate multiple newcomers one by one, such as sequential Star-Structured Regeneration (referred to as and sequential Tree-Structured Regeneration (TSR). To deal with the multiple losses, Hub et al. [6] propose a Mutually Cooperative Recovery (MCR) mechanism, in which all the newcomers repair the lost data cooperatively and simultaneously. But MCR is still based on the star structure, which cannot maximize the utilization of the network bandwidth capacity, and results in slower regeneration process, lower probability of successful regeneration and lower da

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[141416]，资料为PDF文档或Word文档，PDF文档可免费转换为Word