基于条带配对合并算法的局部可修复码冗余度转换机制

Stripe Matching and Merging Algorithm-based Redundancy Transition for Locally Repairable Codes

相比传统的多副本技术,纠删码是一种以高修复代价换取低存储开销的数据冗余机制。局部可修复码是一类具有低修复代价的纠删码,被广泛应用在大数据存储系统中。为了应对动态变化的工作负载和存储介质动态改变的故障率,现代存储系统需要对纠删码数据进行冗余度转换,以调节数据访问性能和可靠性。设计了一种基于条带配对合并的局部可修复码冗余度转换方法,通过选择特定位置的条带进行配对合并,实现了冗余度转换与数据布局的解耦合;进一步通过设计代价量化方法与最优化模型,降低了冗余度转换的网络通信开销。相比设计数据布局的算法,所提算法有与其近似的性能,但对数据布局无限制,可级联迭代地多次运行。实验结果表明,在两种冗余度转换设置下,所提算法均近似于理论最优值,相比随机布局的朴素算法,网络流量分别降低了27.74%和27.47%,耗时分别缩短了39.10%和22.32%。

Compared with traditional replication technique,erasure coding is another data redundancy mechanism with lower space overhead at the cost of high repair cost.Locally repairable code is a special kind of erasure code with low repair cost,which is widely deployed in big data storage systems.In order to accommodate itself to dynamic workload and varying failure rate of sto-rage media,modern storage systems make better trade off between access performance and reliability for erasure coded data by means of redundancy transitions.A redundancy transition method,which selectively matches and merges stripes of specific layout,decouples data placement and redundancy transition,is proposed.Furthermore,it reduces the cross-rack network traffic by designing cost quantification and optimization model.In contrast to those algorithms that designing data placement,the proposed algorithm has almost the same performance but eliminates the constraints on data layout and can be run iteratively.Experiment results show that under the two common transition setups,compared with naive approach of random layout,the proposed algorithm approximates the theoretical optimum,mitigates network traffic by 27.74%and 27.47%,and shortens transition time by 39.10%and 22.32%respectively.