An efficient data layout scheme for better I/O balancing in RAID-6 storage systems

XIE Ping; HUANG Jian-zhong; DAI Er-wei; CAO Qiang; XIE Chang-sheng

doi:10.1631/FITEE.1400362

Your Location：

Home >

Browse articles >

An efficient data layout scheme for better I/O balancing in RAID-6 storage systems

Computer & Automation | Updated：2022-06-06

- An efficient data layout scheme for better I/O balancing in RAID-6 storage systems
- 一种负载平衡的RAID-6存储方案
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 5, Pages: 335-345(2015)
- Affiliations：
  
  1.Wuhan National Laboratory for OptoElectronics, Huazhong University of Science & Technology, Wuhan 430074, China
  2.Computer College, Qinghai Normal University, Xining 810008, China
- Author bio：
  
  [ "Ping XIE, E-mail: xieping@qhnu.edu.cn" ]
  Jian-zhong HUANG, E-mail: hjzh@hust.edu.cn
  [ "Qiang CAO, E-mail: caoqiang@hust.edu.cn" ]
  [ "Chang-sheng XIE, E-mail: cs_xie@hust.edu.cn" ]
- Funds：
- DOI：10.1631/FITEE.1400362
  CLC： TP311
- Received：23 October 2014，
  
  Revised：2015-04-21，
  
  Published：2015-05
- Accepted：
Scan QR Code
XIE Ping, HUANG Jian-zhong, DAI Er-wei, et al. An efficient data layout scheme for better I/O balancing in RAID-6 storage systems[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 335-345.
DOI：

XIE Ping, HUANG Jian-zhong, DAI Er-wei, et al. An efficient data layout scheme for better I/O balancing in RAID-6 storage systems[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(5): 335-345. DOI： 10.1631/FITEE.1400362.

摘要

目的

针对现有垂直RAID-6存储方案中存在不平衡负载的问题，提出一种平衡负载的存储方案，提升RAID存储系统性能。

创新点

基于P-code存储系统，使用一种高效的数据分布方案。该方案能平衡P-code存储系统负载，并提升用户I/O存取性能。

方法

针对P-code存储方案的负载平衡问题，首先分析该存储方案的校验布局和数据分布情况，该编码属于垂直RAID-6编码。校验数据平衡布局于所有磁盘列，从而能平衡数据更新导致的相应校验更新。观察每一条校验链的构建机制发现校验链中的数据块存在不平衡布局的问题，因而提出在不改变数据块原有所在磁盘列的情况下，移动校验链中的数据块使其平衡布局于所有数据行（图4），同时确保P-code存储方案原有的最优属性。

结论

通过对P-code存储方案的布局研究，提出一种平衡负载的存储方案（UPC）。该方案能够有效提升P-code存储系统的存取性能（图5-8）。

Abstract

Among redundant arrays of independent disks (RAID)-6 codes

maximum distance separable (MDS) based RAID-6 codes are popular because they have the optimal storage efficiency. Although vertical MDS codes exhibit better load balancing compared to horizontal MDS codes in partial stripes

an I/O unbalancing problem still exists in some vertical codes. To address this issue

we propose a novel efficient data layout

uniform P-code (UPC)

to support highly balanced I/Os among P-coded disk arrays (i.e.

PC). In UPC

the nonuniformly distributed information symbols in each parity chain of P-code are moved along their columns to other rows

thus enabling the parity chain to keep original parity relationships and tolerate double disk failures. The UPC scheme not only achieves optimal storage efficiency

computational complexity

and update complexity

but also supports better I/O balancing in the context of large-scale storage systems. We also conduct a performance study on reconstruction algorithms using an analytical model. Besides extensive theoretical analysis

comparative performance experiments are conducted by replaying real-world workloads under various configurations. Experimental results illustrate that our UPC scheme significantly outperforms the PC scheme in terms of average user response time. In particular

in the case of a 12-disk array

the UPC scheme can improve the access performance of the RAID-6 storage system by 29.9% compared to the PC scheme.

关键词

Keywords

references

E. Bachmat , Y. Ofek , A. Zakai , 等 . Load Balancing on Disk Array Storage Device . Load Balancing on Disk Array Storage Device. US Patent 6711649 , 2004 .

M. Blaum , R.M. Roth . On lowest density MDS codes . IEEE Trans. Inform. Theory , 1999 . 45 ( 1 ): 46 - 59 . DOI: 10.1109/18.746771 http://doi.org/10.1109/18.746771 .

M. Blaum , J. Brady , J. Bruck , 等 . EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures . IEEE Trans. Comput. , 1995 . 44 ( 2 ): 192 - 202 . DOI: 10.1109/12.364531 http://doi.org/10.1109/12.364531 .

P. Corbett , B. English , A. Goel , 等 . Row-diagonal parity for double disk failure correction . Proc. 3rd USENIX Conf. on File and Storage Technologies , 2004 . p.1 - 14 . .

G.R. Ganger , B.L. Worthington , R.Y. Hou , 等 . Disk subsystem load balancing: disk striping vs . conventional data placement. Proc. 26th Hawaii Int. Conf. on System Sciences , 1993 . p.40 - 49 . DOI: 10.1109/HICSS.1993.270759 http://doi.org/10.1109/HICSS.1993.270759 .

K.M. Greenan , X.Z. Li , J.J. Wylie . Flat XOR-based erasure codes in storage systems: constructions, efficient recovery, and tradeoffs . Proc. IEEE 26th Symp. on Mass Storage Systems and Technologies , 2010 . p.1 - 14 . DOI: 10.1109/MSST.2010.5496983 http://doi.org/10.1109/MSST.2010.5496983 .

J.L. Hafner . WEAVER codes: highly fault tolerant erasure codes for storage systems . Proc. 4th USENIX Conf. on File and Storage Technologies , 2005 . p.16 .

M. Holland , G.A. Gibson . Parity declustering for continuous operation in redundant disk arrays . Proc. 5th Int. Conf. on Architectural Support for Programming Languages and Operating Systems , 1992 . p.23 - 35 . DOI: 10.1145/143365.143383 http://doi.org/10.1145/143365.143383 .

C. Huang , M. Chen , J. Li . Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems . Proc. 6th IEEE Int. Symp. on Network Computing and Applications , 2007 . p.79 - 86 . DOI: 10.1109/NCA.2007.37 http://doi.org/10.1109/NCA.2007.37 .

R.M. Jantz . Method for Host-Based I/O Workload Balancing on Redundant Array Controllers . US Patent 5937428 , 1999 .

C. Jin , H. Jiang , D. Feng , 等 . P-code: a new RAID-6 code with optimal properties . Proc. 23rd Int. Conf. on Supercomputing , 2009 . p.360 - 369 . DOI: 10.1145/1542275.1542326 http://doi.org/10.1145/1542275.1542326 .

O. Khan , R.C. Burns , J.S. Plank , 等 . Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads . Proc. 11th USENIX Conf. on File and Storage Technologies , 2012 . p.20 .

D.A. Patterson , G. Gibson , R.H. Katz . A case for redundant arrays of inexpensive disks (RAID) . Proc. ACM SIGMOD Int. Conf. on Management of Data , 1988 . p.109 - 116 . DOI: 10.1145/50202.50214 http://doi.org/10.1145/50202.50214 .

J.S. Plank , J. Luo , C.D. Schuman , 等 . A performance evaluation and examination of open-source erasure coding libraries for storage . Proc. 8th USENIX Conf. on File and Storage Technologies , 2009 . p.253 - 265 . .

I.S. Reed , G. Solomon . Polynomial codes over certain finite fields . J. Soc. Ind. Appl. Math. , 1960 . 8 ( 2 ): 300 - 304 . DOI: 10.1137/0108018 http://doi.org/10.1137/0108018 .

P. Scheuermann , G. Weikum , P. Zabback . Data partitioning and load balancing in parallel disk systems . VLDB J. , 1998 . 7 ( 1 ): 48 - 66 . DOI: 10.1007/s007780050053 http://doi.org/10.1007/s007780050053 .

B. Schroeder , G.A. Gibson . Disk failures in the real world: what does an MTTF of 1, 000, 000 hours mean to you . Proc. 6th USENIX Conf. on File and Storage Technologies , 2007 . p.1 - 16 . .

S. Wan , Q. Cao , C.S. Xie , 等 . Code-M: a non-MDS erasure code scheme to support fast recovery from up to two-disk failures in storage systems . Proc. IEEE/IFIP Int. Conf. on Dependable Systems and Networks , 2010 . p.51 - 60 . DOI: 10.1109/DSN.2010.5545009 http://doi.org/10.1109/DSN.2010.5545009 .

Z.Y. Wang , A.G. Dimakis , J. Bruck . Rebuilding for array codes in distributed storage systems . Proc. IEEE GLOBECOM Workshops , 2010 . p.1905 - 1909 . DOI: 10.1109/GLOCOMW.2010.5700274 http://doi.org/10.1109/GLOCOMW.2010.5700274 .

S. Wu , H. Jiang , D. Feng , 等 . WorkOut: I/O workload outsourcing for boosting RAID reconstruction performance . Proc. 8th USENIX Conf. on File and Storage Technologies , 2009 . p.239 - 252 . .

L.P. Xiang , Y.L. Xu , J. Lui , 等 . A hybrid approach to failed disk recovery using RAID-6 codes: algorithms and performance evaluation . ACM Trans. Stor. , 2011 . 7 ( 3 ): Article 11 DOI: 10.1145/2027066.2027071 http://doi.org/10.1145/2027066.2027071 .

P. Xie , J.Z. Huang , Q. Cao , 等 . A new non- MDS RAID-6 code to support fast reconstruction and balanced I/Os . Comput. J., in press , 2015 . DOI: 10.1093/comjnl/bxv006 http://doi.org/10.1093/comjnl/bxv006 .

L.H. Xu , J. Bruck . X-code: MDS array codes with optimal encoding . IEEE Trans. Inform. Theory , 1999 . 45 ( 1 ): 272 - 276 . DOI: 10.1109/18.746809 http://doi.org/10.1109/18.746809 .

Y.F. Zhu , P.P.C. Lee , Y.C. Hu , 等 . On the speedup of single-disk failure recovery in XOR-coded storage systems: theory and practice . Proc. IEEE 28th Symp. on Mass Storage Systems and Technologies , 2012a . p.1 - 12 . DOI: 10.1109/MSST.2012.6232371 http://doi.org/10.1109/MSST.2012.6232371 .

Y.F. Zhu , P.P.C. Lee , L.P. Xiang , 等 . A costbased heterogeneous recovery scheme for distributed storage systems with RAID-6 codes . Proc. 42nd Annual IEEE/IFIP Int. Conf. on Dependable Systems and Networks , 2012b . p.1 - 12 . DOI: 10.1109/DSN.2012.6263934 http://doi.org/10.1109/DSN.2012.6263934 .

A.Y. Zomaya , Y.H. Teh . Observations on using genetic algorithms for dynamic load-balancing . IEEE Trans. Parall. Distr. Syst. , 2001 . 12 ( 9 ): 899 - 911 . DOI: 10.1109/71.954620 http://doi.org/10.1109/71.954620 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰