Erasure Coding for Cloud Storage Systems: A Survey

In the current era of cloud computing, data stored in the cloud is being generated at a tremendous speed, and thus the cloud storage system has become one of the key components in cloud computing. By storing a substantial amount of data in commodity disks inside the data center that hosts the cloud, the cloud storage system must consider one question very carefully： how do we store data reliably with a high efficiency in terms of both storage overhead and data integrity？ Though it is easy to store replicated data to tolerate a certain amount of data losses, it suffers from a very low storage efficiency. Conventional erasure coding techniques, such as Reed-Solomon codes, are able to achieve a much lower storage cost with the same level of tolerance against disk failures. However, it incurs much higher repair costs, not to mention an even higher access latency. In this sense, designing new coding techniques for cloud storage systems has gained a significant amount of attention in both academia and the industry. In this paper, we examine the existing results of coding techniques for cloud storage systems. Specifically, we present these coding techniques into two categories： regenerating codes and locally repairable codes. These two kinds of codes meet the requirements of cloud storage along two different axes： optimizing bandwidth and I/O overhead. We present an overview of recent advances in these two categories of coding techniques. Moreover, we introduce the main ideas of some specific coding techniques at a high level, and discuss their motivations and performance.

A reliable and energy-efficient storage system with erasure coding cache

In modern energy-saving replication storage systems, a primary group of disks is always powered up to serve incoming requests while other disks are often spun down to save energy during slack periods. However, since new writes cannot be immediately synchronized into all disks, system reliability is degraded. In this paper, we develop a high-reliability and energy-efficient replication storage system, named RERAID, based on RAID10. RERAID employs part of the free space in the primary disk group and uses erasure coding to construct a code cache at the front end to absorb new writes. Since code cache supports failure recovery of two or more disks by using erasure coding, RERAID guarantees a reliability comparable with that of the RAID10 storage system. In addition, we develop an algorithm, called erasure coding write （ECW）, to buffer many small random writes into a few large writes, which are then written to the code cache in a parallel fashion sequentially to improve the write performance. Experimental results show that RERAID significantly improves write performance and saves more energy than existing solutions.

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

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 pipe-line 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.

A Fault Detection Mechanism in Erasure-Code Byzantine Fault-Tolerance Quorum

Fault-tolerance is increasingly significant for large-scale storage systems in which Byzantine failure of storage nodes may happen. Traditional Byzantine Quorum systems that tolerate Byzantine failures by using replication have two main limitations： low space-efficiency and static quorum variables. We propose an Erasure-code Byzantine Fault-tolerance Quorum that can provide high reliability with far lower storage overhead than replication by adopting erasure code as redundancy scheme. Through read/write operations of clients and diagnose operation of supervisor, our Quorum system can detect Byzantine nodes, and dynamically adjust system size and fault threshold. Simulation results show that our method improves performance for the Quorum with relatively small quorums.

Research of Methods for Lost Data Reconstruction in Erasure Codes over Binary Fields

In the process of encoding and decoding,erasure codes over binary fields,which just need AND operations and XOR operations and therefore have a high computational efficiency,are widely used in various fields of information technology.A matrix decoding method is proposed in this paper.The method is a universal data reconstruction scheme for erasure codes over binary fields.Besides a pre-judgment that whether errors can be recovered,the method can rebuild sectors of loss data on a fault-tolerant storage system constructed by erasure codes for disk errors.Data reconstruction process of the new method has simple and clear steps,so it is beneficial for implementation of computer codes.And more,it can be applied to other non-binary fields easily,so it is expected that the method has an extensive application in the future.

CLEC:Combination Locality Based Erasure Code for Permissioned Blockchain Storage

Building a new decentralized domain name system based on blockchain technology is helping to solve problems,such as load imbalance and over-dependence on the trust of the central node.However,in the existing blockchain storage system,the storage overhead is very high due to its fullreplication data storage mechanism.The total storage consumption for each block is up to O(n)with n nodes.Erasure code applied to blockchains can significantly reduce the storage overhead,but also greatly lower the read performance.In this study,we propose a novel coding scheme for blockchain storage,Combination Locality based Erasure Code for Permissioned blockchain storage(CLEC).CLEC uses erasure code,parity locality,and topology locality in blockchain storage,greatly reducing reading latency and repair time.In CLEC,the storage consumption per block can be reduced to O(1),and the repair penalty can also be lowered to O(1).Experiments in an open-source permissioned blockchain Tendermint show that CLEC has a maximum repair speed of 6 times and a read speed of nearly 1.7 times with storage overhead of only 1.17 times compared to the current work,a great improvement in reading performance and repair performance with slightly increased storage overhead via implementation.

DDUC:an erasure-coded system with decoupled data updating and coding

In distributed storage systems,replication and erasure code(EC)are common methods for data redundancy.Compared with replication,EC has better storage efficiency,but suffers higher overhead in update.Moreover,consistency and reliability problems caused by concurrent updates bring new challenges to applications of EC.Many works focus on optimizing the EC solution,including algorithm optimization,novel data update method,and so on,but lack the solutions for consistency and reliability problems.In this paper,we introduce a storage system that decouples data updating and EC encoding,namely,decoupled data updating and coding(DDUC),and propose a data placement policy that combines replication and parity blocks.For the(N,M)EC system,the data are placed as N groups of M+1 replicas,and redundant data blocks of the same stripe are placed in the parity nodes,so that the parity nodes can autonomously perform local EC encoding.Based on the above policy,a two-phase data update method is implemented in which data are updated in replica mode in phase 1,and the EC encoding is done independently by parity nodes in phase 2.This solves the problem of data reliability degradation caused by concurrent updates while ensuring high concurrency performance.It also uses persistent memory(PMem)hardware features of the byte addressing and eight-byte atomic write to implement a lightweight logging mechanism that improves performance while ensuring data consistency.Experimental results show that the concurrent access performance of the proposed storage system is 1.70–3.73 times that of the state-of-the-art storage system Ceph,and the latency is only 3.4%–5.9%that of Ceph.

AVirtual Cloud Storage Architecture for Enhanced Data Security

The sensitive data stored in the public cloud by privileged users,such as corporate companies and government agencies are highly vulnerable in the hands of cloud providers and hackers.The proposed Virtual Cloud Storage Archi-tecture is primarily concerned with data integrity and confidentiality,as well as availability.To provide confidentiality and availability,thefile to be stored in cloud storage should be encrypted using an auto-generated key and then encoded into distinct chunks.Hashing the encoded chunks ensured thefile integrity,and a newly proposed Circular Shift Chunk Allocation technique was used to determine the order of chunk storage.Thefile could be retrieved by performing the opera-tions in reverse.Using the regenerating code,the model could regenerate the missing and corrupted chunks from the cloud.The proposed architecture adds an extra layer of security while maintaining a reasonable response time and sto-rage capacity.Experimental results analysis show that the proposed model has been tested with storage space and response time for storage and retrieval.The VCSA model consumes 1.5x(150%)storage space.It was found that total storage required for the VCSA model is very low when compared with 2x Replication and completely satisfies the CIA model.The response time VCSA model was tested with different sizedfiles starting from 2 to 16 MB.The response time for storing and retrieving a 2 MBfile is 4.96 and 3.77 s respectively,and for a 16 MBfile,the response times are 11.06 s for storage and 5.6 s for retrieval.

A Fault Tolerance Scheme for Reliable Transfer in Delay Tolerant Networks

Delay Tolerant Network （DTN） is a class of networks that experience frequent and long-duration partitions due to sparse distribution of nodes. It has a broad prospect to new network applications for a better sealability, fault-tolerant, and high performance. In DTNs, path failure occurs frequently, so message transfer is not reliable. Sometimes it is required to change routing even in a very short period, resulting in transmission delay and reception delay. However, some well-known assumptions of traditional networks are no longer true in DTNs. In this paper, we study the problem of path failures in DTNs. The path failure process in DTNs is described when the path appears completely normal, completely failed and partially failed. Traditional approaches based on using precisely known network dynamics have not accounted for message losses. A new fault tolerant scheme to generate redundancy is to use erasure coding and full replication. This can greatly decrease the path failure rate. At last, a traffic DTN model is analyzed. Results reveal the superiority of our scheme in comparison to other present schemes.

A novel approach to authenticated group key transfer protocol based on AG codes

Group key management technique is a fundamental building block for secure and reliable group communication systems.In order to successfully achieve this goal, group session key needs to be generated and distributed to all group members in a secure and authenticated manner.The most commonly used method is based on Lagrange interpolating polynomial over the prime field F p={0,1,2,…, p-1}. A novel approach to group key transfer protocol based on a category of algebraic-geometry code is presented over the infinite field GF(2 m). The attractive advantages are obvious. Especially, the non-repeatability, confidentiality, and authentication of group key transfer protocols are obtained easily. Besides, a more generalized and simple mathematical construction model is proposed which also can be applied perfectly to related fields of information security.

NEW METHOD TO RECOVER INTERNET PACKET LOSSES USING(2,1,m)SYSTEMATIC CONVOLUTIONAL CODES

A new method to recover packet losses using (2,1,m) convolutional codes is proposed. The erasure correcting decoding algorithm and the decoding determinant theorem is presented. It is also proved that the codes with optimal distance profile have also optimal delay characteristic. Simulation results show that the proposed method can recover the packet losses more elliciently than RS codes over different decoding delay conditions and thus suits for different packet network delav conditions.

Short Tail:taming tail latency for erasure-code-based in-memory systems

In-memory systems with erasure coding(EC)enabled are widely used to achieve high performance and data availability.However,as the scale of clusters grows,the server-level fail-slow problem is becoming increasingly frequent,which can create long tail latency.The influence of long tail latency is further amplified in EC-based systems due to the synchronous nature of multiple EC sub-operations.In this paper,we propose an EC-enabled in-memory storage system called ShortTail,which can achieve consistent performance and low latency for both reads and writes.First,ShortTail uses a lightweight request monitor to track the performance of each memory node and identify any fail-slow node.Second,ShortTail selectively performs degraded reads and redirected writes to avoid accessing fail-slow nodes.Finally,ShortTail posts an adaptive write strategy to reduce write amplification of small writes.We implement ShortTail on top of Memcached and compare it with two baseline systems.The experimental results show that ShortTail can reduce the P99 tail latency by up to 63.77%;it also brings significant improvements in the median latency and average latency.

SA-RSR:a read-optimal data recovery strategy for XOR-coded distributed storage systems

To ensure the reliability and availability of data,redundancy strategies are always required for distributed storage systems.Erasure coding,one of the representative redundancy strategies,has the advantage of low storage overhead,which facilitates its employment in distributed storage systems.Among the various erasure coding schemes,XOR-based erasure codes are becoming popular due to their high computing speed.When a single-node failure occurs in such coding schemes,a process called data recovery takes place to retrieve the failed node’s lost data from surviving nodes.However,data transmission during the data recovery process usually requires a considerable amount of time.Current research has focused mainly on reducing the amount of data needed for data recovery to reduce the time required for data transmission,but it has encountered problems such as significant complexity and local optima.In this paper,we propose a random search recovery algorithm,named SA-RSR,to speed up single-node failure recovery of XOR-based erasure codes.SA-RSR uses a simulated annealing technique to search for an optimal recovery solution that reads and transmits a minimum amount of data.In addition,this search process can be done in polynomial time.We evaluate SA-RSR with a variety of XOR-based erasure codes in simulations and in a real storage system,Ceph.Experimental results in Ceph show that SA-RSR reduces the amount of data required for recovery by up to 30.0%and improves the performance of data recovery by up to 20.36%compared to the conventional recovery method.

Study on Security Enhancement Technology for Disaster Tolerant System

This paper proposes a security enhancement scheme for disaster tolerant systems based on trusted computing technology which combines with the idea of distributed threshold storage. This scheme takes advantage of a trusted computing platform with a trusted computing module, which has excellent features such as security storage, remote attestation, and so on. These features effectively ensure trustworthiness of the disaster tolerant point. Furthermore, distributed storage based on Erasure code not only disposes the storage problem about a great deal of data, but also preferably avoids one node invalidation, alleviates network load and deals with joint cheat and many other security problems. Consequently, those security enhancement technologies provide mass data with global security protection during the course of disaster tolerance.