Data centers commonly use erasure codes to maintain high data reliability with lower storage overhead than replication. However, recycling invalid data blocks caused by deletion and update operations is challenging in erasure-coded data centers. Erasure codes organize data blocks into stripes, and we cannot directly delete invalid data blocks like replication to ensure the redundancy of the remaining valid blocks within a stripe. When considering the recycling issues in data centers, existing studies still need to address the following problems: ignoring heavy cross-rack traffic and the load imbalance problem during recycling, and incurring high disk seeks that affect writing performance after recycling. This paper presents the first systematic study on data re cycling in erasure-coded data centers and proposes a Cross rack Aware Recycle (CARecycle) technique. The key idea is migrating valid data blocks from certain stripes to rewrite invalid ones in others, thereby releasing the invalid blocks for certain stripes. Specifically, CARecycle first carefully examines the block distribution for each stripe and generates an efficient recycle solution for migrating and releasing, with the primary objective of reducing cross-rack traffic and disk seek load of nodes. Due to the rewriting of invalid data blocks, parity blocks in multiple stripes need to be updated concurrently. Thus, it further batch processes multiple stripes and selectively arranges appropriate stripes into a batch to achieve uniform cross-rack traffic load distribution. In addition, CARecycle can be extended to adapt to different erasure codes and boost recycling in heterogeneous network environments. Large-scale simulations and Amazon EC2 experiments show that CARecycle can reduce up to 33.8% cross rack traffic and 28.64%-59.64% recycle time while incurring low disk seek, compared to a state-of-the-art recycling technique.

Compared to DRAM, persistent memory (PM) offers higher density and persistence but encounters more severe reliability challenges. Erasure coding is widely adopted to enhance reliability with minimal space overhead. Unfortunately, applying erasure coding to PM introduces significant additional latency. Previous work to mitigate coding latency has primarily focused on optimizing computational efficiency. Instead, we reveal that the main performance bottleneck is high memory latency due to inefficient hardware prefetchers, rather than computation. We further observe that the prefetching inefficiency mainly results from: (i) too wide or narrow coding stripes, (ii) small block sizes, and (iii) high concurrency.

Erasure coding is widely adopted to maintain data reliability, yet it introduces a significant update penalty. We analyze real-world traces and observe several challenges that are not addressed by existing studies, which thereby restricts the performance gains. We propose FastUpdate, an efficient multi-stripe updates framework that assists existing update schemes for fast updates. FastUpdate comprises three key designs: (i) it perceives the update locality and carefully merges multiple update requests accessing the same stripe to reduce the incurred network traffic; (ii) it abstracts the existing update schemes into collector selection and tree construction, greedily generates the update solution for each stripe to balance the transmission load across nodes; (iii) it dynamically schedules appropriate stripes to update in heterogeneous and dynamic networks to fully saturate the bandwidth resources. Comprehensive evaluations verify the effectiveness of FastUpdate on Alibaba ECS. It can increase the update throughput by 16.15%-88.71% for various update schemes.

Erasure codes(EC) have been widely adopted to provide high data reliability with low storage costs in clusters. Due to the deletion and out-of-place update operations, some data blocks are invalid, which unfortunately arouses the tediousgarbage collection(GC) problem. Several limitations still plague existing designs: substantial network traffic, unbalanced traffic load, and low read/write performance after GC. This paper proposes FastGC, a fast garbage collection method that merges the old stripes into a new stripe and reclaims invalid blocks. FastGC quickly generates an efficient merge solution by stripe grouping and bit sequences operations to minimize network traffic and maintains data block distributions of the same stripe to ensure read performance. It carefully allocates the storage space for new stripes during merging to eliminate the discontinuous free spaces that affect write performance. Furthermore, to accelerate the parity updates after merging, FastGC greedily schedules the transmission links for multi-stripe updates to balance the traffic load across nodes and adopts a maximum flow algorithm to saturate the bandwidth utilization. Comprehensive evaluation results show via simulations and Alibaba ECS experiments that FastGC can significantly reduce 10.36%-81.22% of the network traffic and 34.25%-72.36% of the GC time while maintaining read/write performance after GC.

A significant drawback of erasure-coding is suffering from the expensive update traffic. The analysis of real-world-production traces shows that partial updates, including partial-block-updates and partial-stripe-updates, are both common. Existing schemes cannot work adequately for partial updates. Raid-based scheme coordinates multiple updated entire blocks to update parity, yet it incurs significant network traffic for partial-block-updates. Delta-based scheme transmits the updated parts and independently updates parity, yet it cannot share computed-delta parts for partial-stripe-updates. We propose CoRD, which optimally combines Raid-based and Delta-based schemes to minimize the update traffic. It exploits the offset address intersections between multiple updated blocks and only transmits the updated parts to coordinate in parity updates. CoRD further address cross-block update scenarios by flipping some dedicated blocks to improve the performance. Comprehensive evaluations verify the effectiveness of CoRD for the latest traces, with the update traffic reduction of 37.02%-87.19% and the performance improvement of 36.54%-231.92% compared to state-of-the-art.

More and more storage systems use erasure code to tolerate faults. It takes pieces of data blocks as input and encodes a small number of parity blocks as output, where these blocks form a stripe. When reconsidering the recovery problem in the multi-stripe level and heterogeneous network clusters, quickly generating an efficient multi-stripe recovery solution that reduces recovery time remains a challenging and time-consuming task. Previous works either use a greedy algorithm that may fall into the local optimal and have low recovery performance or a meta-heuristic algorithm with a long running time and low solution generation efficiency. In this article, we propose a Stripe-schedule Aware Repair (SARepair) technique for multi-stripe recovery in heterogeneous erasure-coded clusters based on Reed–Solomon code. By carefully examining the metadata of blocks, SARepair intelligently adjusts the recovery solution for each stripe and obtains another multi-stripe solution with less recovery time in a computationally efficient manner. It then tolerates worse solutions to overcome the local optimal and uses a rollback mechanism to adjust search regions to reduce recovery time further. Moreover, instead of reading blocks sequentially from each node, SARepair also selectively schedules the reading order for each block to reduce the memory overhead. We extend SARepair to address the full-node recovery and adapt to the LRC code. We prototype SARepair and show via both simulations and Amazon EC2 experiments that the recovery performance can be improved by up to 59.97% over a state-of-the-art recovery approach while keeping running time and memory overhead low.

Modern clustered storage systems have commonly used erasure coding to maintain data durability against failures, yet it introduces significant update overhead for partial updates (e.g., only part of a block is updated). Recent studies propose the append-commit and buffer-logging techniques, which append multiple updated data to buffer-log and cache the corresponding old data from disk into memory, to reduce the update costs when committing the updates to parity. However, caching the entire old data block will introduce additional disk reads and memory overhead because caching the old part that not be updated, caching the partial old data block will incur the significant disk seeks for frequent partial updates. Our real-cloud experiments show that the unbalanced disk I/O may cause the bottleneck for updating, which is unfortunately overlooked by existing studies.This paper proposes LASC, a locality-aware speculative cache scheme for partial updates. LASC perceives the update locality of a data block from an update request stream within a period and speculatively caches the old data from the disk. It caches the entire old data block with high update locality to reduce the disk seeks. For a series of update requests to the same data block, LASC only performs one disk seek. Otherwise, it caches the old partial data to migrate the disk reads and memory overhead. We evaluate LASC via trace-driven simulations and Alibaba ECS experiments for two of the largest and latest public block-level I/O traces and show that LASC can effectively balance the disk I/O and improve the update performance while keeping memory overhead low.

A significant drawback of erasure codes is suffering from the expensive update overhead, and all parity blocks are regenerated once any update of one data block for consistency. Existing update techniques either neglect the multi-block updates scenario under update-intensive workloads or do not consider how to minimize the update cost in heterogeneous clusters. This paper presents the first systematic study on multi-block updates in heterogeneous clusters. We formulate the problem as a cost-based routing optimization model and propose a novelMulti-block Double Tree Update(MDTUpdate) technique. The key idea is to construct a double tree structure for multiple updated data blocks and all parity blocks, which avoids the congested link bottleneck. To reduce the update costs effectively, we exploit a hybrid update scheme that combines the data-delta and parity-delta schemes under the double tree structure. To accelerate the tree construction, we design a time-efficient greedy algorithm that timely determines the transmission route via perceiving the cost discrepancy among nodes while avoiding exhaustive enumeration. We further prove that our algorithm is optimal in minimizing the update costs. The experiments show that MDTUpdate can improve the update performance by up to 83.23% over the existing techniques while incurring extremely lightweight running overhead.

Large-scale storage systems have introduced erasure codes to guarantee high data reliability, yet inevitably at the expense of high repair costs. In practice, storage nodes are usually divided into different racks, and data blocks in nodes are organized into multiple stripes independently manipulated by erasure code. Due to the scarcity and heterogeneity of the cross-rack bandwidth, the cross-rack transmission dominates the entire repair costs. When erasure code is deployed in rack architectures, existing repair techniques are limited in different aspects: neglecting the heterogeneous cross-rack bandwidth, less consideration for multi-stripe failure, and no special treatment on repair-link scheduling. In this paper, we present CMRepair, aCross-rack Multi-stripe Repairtechnique that aims to reduce the repair time for multi-stripes failure repair in heterogeneous erasure-coded clusters. CMRepair first carefully chooses the nodes for reading/repairing blocks and searches for the multi-stripe repair solution. It adopts different algorithms to adjust the solution, including the Computation Time Priority (CTP) algorithm based on the greedy idea and the Repair Time Priority (RTP) algorithm based on the meta-heuristics idea. Furthermore, CMRepair selectively schedules the execution orders of cross-rack links, with the primary objective of saturating the unused upload/download bandwidth resources and avoiding network congestion. The experiments show that CMRepair with the CTP algorithm can reduce 27.59%-58.12% of the repair time while only introducing negligible computation overhead, and CMRepair with the RTP algorithm can reduce 33.52%-97.75% of the repair time in an acceptable computation time, over existing repair techniques.

More and more commodity storage systems use erasure code to tolerate faults. When reconsidering the recovery problem in a multi-stripe level and heterogeneous network for the erasure-coded cluster, efficiently generating an optimal multi-stripe recovery solution that reduces recovery time remains a challenging and time-consuming task. Previous works either use a greedy algorithm that may fall into the local-optimal and has low performance or use a meta-heuristic algorithm with a long search time and low efficiency.In this paper, we propose a Stripe-schedule Aware Repair (SARepair) technique for multi-stripe recovery in heterogeneous erasure-coded clusters. By carefully examining the metadata of blocks, SARepair intelligently adjusts the recovery solution for each stripe and obtains another multi-stripe solution with less recovery time in a computationally efficient manner. It then tolerates worse solutions to overcome the local-optimal and uses a rollback mechanism to adjust search regions to further reduce recovery time. Moreover, instead of reading blocks sequentially from each node, SARepair also selectively schedules the reading order for each block to reduce the memory overhead. We prototype SARepair and show via both simulations and Amazon EC2 experiments that the recovery time can be reduced by up to 68% over a state-of-the-art recovery approach while keeping time complexity and memory overhead low.

Large-scale distributed storage systems have introduced erasure code to guarantee high data reliability, yet inevitably at the expense of high repair costs. In practice, storage nodes are usually divided into different racks, and data blocks in storage nodes are often organized into multiple stripes independently manipulated by erasure code. Due to the scarcity and heterogeneity of the cross-rack bandwidth, the cross-rack network transmission dominates the entire repair costs. We argue that when erasure code is deployed in a rack architecture, existing repair techniques are limited in different aspects: neglecting the heterogeneous cross-rack bandwidth, less consideration for multi-stripe failure, no special treatment on repair link scheduling, and only targeting specific erasure code constructions.

Erasure codes offer a storage-efficient redundancy mechanism for maintaining data availability guarantees in storage clusters, yet also incur high network traffic consumption and recovery time in failure repair. Extensive research has been carried out to reduce the recovery time. However, previous works either target specific erasure code constructions which are not commonly used in today’s distributed storage clusters or neglect the heterogeneous bandwidth property in real network environments. Since erasure-coded clusters are typically composed of multi-node with heterogeneous bandwidth and accessed in parallel, the whole recovery time is mainly restricted by the low-bandwidth links. In this article, we propose SMFRepair, a single-node multi-level forwarding repair technique that is designed to improve the performance in heterogeneous networks based on Reed-Solomon codes for general fault tolerance. SMFRepair carefully selects the helper nodes and uses idle nodes to bypass low-bandwidth links. Idle nodes have sufficient and unused network bandwidth. It also pipelines the repair links that are optimized by idle nodes. Furthermore, a multi-node scheduling repair technique, called MSRepair, is proposed. MSRepair carefully schedules the multi-node repair link to saturate the most unoccupied bandwidth and transfers data from as large-bandwidth links as possible, with the primary objective of minimizing the recovery time. Large-scale simulation and Amazon EC2 real experiments show that compared to state-of-the-art repair techniques, SMFRepair can accelerate the single-node recovery by up to 47.69%, and MSRepair can reduce the multi-node recovery time by 33.78%$\sim$67.53%.

Erasure codes offer a storage-efficient redundancy mechanism for maintaining data availability guarantees in storage clusters, yet also incur high network traffic consumption and recovery time in failure repair. Exiting studies aim to reduce the recovery time in the heterogeneous network. However, the recovery time is always limited by the link with the low bandwidth between nodes, due to bandwidth heterogeneity. Recently, Bai et al. proposed a parallel pipeline tree technique, called PPT, to reduce recovery time by utilizing a special bandwidth gap to bypass the low-bandwidth link. But we find that PPT’s gap-based bypassing method will cause network congestion and competition. In this paper, we propose SMFRepair, a single-node multi-level forwarding repair technique that uses idle nodes to bypass low-bandwidth links without incurring network congestion and competition. Furthermore, a multi-node scheduling repair technique, called MSRepair, is proposed. MSRepair finds a recovery solution that schedules the parallel repair of multi-node and transfers data from as large-bandwidth links as possible, with the primary objective of minimizing the recovery time. Large-scale Mininet simulation and Amazon EC2 real experiments show that compared to state-of-the-art repair techniques, the single-node recovery time can be reduced by up to 36.65%, and the multi-node recovery time can be reduced by up to 55.10%.