The Optimization Of Data Layouts In Fault-Tolerant Storage Systems With Erasure Coding

Failures in large-scale storage systems have become commonplace today,and therefore erasure codes are widely deployed in storage systems to provide fault tol-erance with low storage overhead.However,the data layouts of erasure-coded storage systems,i.e.,the mapping between blocks and storage devices,are closely related to the scalability,reliability,and recovery performance of the fault-tolerant storage sys-tems.This dissertation carries out a research from the perspective of data layouts in three aspects:scaling(i.e.,block remapping)algorithm design,reliability improvement scheme,and efficient failure recovery strategy.The main contributions are listed as follows:·This dissertation proposes an efficient scaling scheme,called Parity Decluster-ing Scaling(PDS),to scale up disk arrays with parity declustered data layout.PDS employs balanced incomplete block designs to define the data migration.It preserves parity declustered data layout and a uniform distribution of data/parity blocks after scaling while requiring only the minimal data migration.Experimen-tal results show that PDS can effectively reduce scaling time and user response time during scaling.·This dissertation proposes a fault tolerance improvement scheme based on the data migration of the PDS scaling scheme to support PDS to improve the reliabil-ity of disk arrays.PDS improves fault tolerance by allocating more parity blocks into stripes and employs balanced incomplete block designs to define the loca-tions of the new added blocks in the scaled disk array.It achieves parity declus-tered data layout and a uniform distribution of data/parity blocks after improving reliability.Experimental results show that PDS with improving reliability can still effectively shorten scaling time and user response time during scaling.·This dissertation proposes a data layout scheme,called Deterministic Data Dis-tribution(D3),for efficient failure recovery in erasure-coded distributed storage systems.D3 employs orthogonal arrays to define a deterministic data distribution of blocks to racks and storage nodes.It not only uniformly distributes data/parity blocks among nodes,but also balances the repair traffic among racks and nodes for single node failure recovery.Furthermore,D3 also minimizes the cross-rack repair traffic for data layouts against a single rack failure.Experimental results show that D3 can significantly speed up single node failure recovery.