JZUS - Journal of Zhejiang University SCIENCE

Frontiers of Information Technology & Electronic Engineering 2015 Vol.16 No.5 P.335-345

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

Author(s): Ping Xie, Jian-zhong Huang, Er-wei Dai, Qiang Cao, Chang-sheng Xie
Affiliation(s): Wuhan National Laboratory for OptoElectronics, Huazhong University of Science & Technology, Wuhan 430074, China; more
Corresponding email(s): xieping@qhnu.edu.cn, hjzh@hust.edu.cn, caoqiang@hust.edu.cn, cs_xie@hust.edu.cn
Key Words: RAID-6, Data availability, High performance, I/O balancing

Share this article to： More \|Next Article >>>

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.

一种负载平衡的RAID-6存储方案

目的：针对现有垂直RAID-6存储方案中存在不平衡负载的问题，提出一种平衡负载的存储方案，提升RAID存储系统性能。
创新点：基于P-code存储系统，使用一种高效的数据分布方案。该方案能平衡P-code存储系统负载，并提升用户I/O存取性能。
方法：针对P-code存储方案的负载平衡问题，首先分析该存储方案的校验布局和数据分布情况，该编码属于垂直RAID-6编码。校验数据平衡布局于所有磁盘列，从而能平衡数据更新导致的相应校验更新。观察每一条校验链的构建机制发现校验链中的数据块存在不平衡布局的问题，因而提出在不改变数据块原有所在磁盘列的情况下，移动校验链中的数据块使其平衡布局于所有数据行（图4），同时确保P-code存储方案原有的最优属性。
结论：通过对P-code存储方案的布局研究，提出一种平衡负载的存储方案（UPC）。该方案能够有效提升P-code存储系统的存取性能（图5-8）。

关键词：RAID；数据存取性能；高性能；负载平衡

Reference

[1]Bachmat, E., Ofek, Y., Zakai, A., et al., 2004. Load Balancing on Disk Array Storage Device. US Patent 6711649.

[2]Blaum, M., Roth, R.M., 1999. On lowest density MDS codes. IEEE Trans. Inform. Theory, 45(1):46-59.

[3]Blaum, M., Brady, J., Bruck, J., et al., 1995. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures. IEEE Trans. Comput., 44(2):192-202.

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

[5]Ganger, G.R., Worthington, B.L., Hou, R.Y., et al., 1993. Disk subsystem load balancing: disk striping vs. conventional data placement. Proc. 26th Hawaii Int. Conf. on System Sciences, p.40-49.

[6]Greenan, K.M., Li, X.Z., Wylie, J.J., 2010. Flat XOR-based erasure codes in storage systems: constructions, efficient recovery, and tradeoffs. Proc. IEEE 26th Symp. on Mass Storage Systems and Technologies, p.1-14.

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

[8]Holland, M., Gibson, G.A., 1992. Parity declustering for continuous operation in redundant disk arrays. Proc. 5th Int. Conf. on Architectural Support for Programming Languages and Operating Systems, p.23-35.

[9]Huang, C., Chen, M., Li, J., 2007. 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, p.79-86.

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

[11]Jin, C., Jiang, H., Feng, D., et al., 2009. P-code: a new RAID-6 code with optimal properties. Proc. 23rd Int. Conf. on Supercomputing, p.360-369.

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

[13]Patterson, D.A., Gibson, G., Katz, R.H., 1988. A case for redundant arrays of inexpensive disks (RAID). Proc. ACM SIGMOD Int. Conf. on Management of Data, p.109-116.

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

[15]Reed, I.S., Solomon, G., 1960. Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math., 8(2):300-304.

[16]Scheuermann, P., Weikum, G., Zabback, P., 1998. Data partitioning and load balancing in parallel disk systems. VLDB J., 7(1):48-66.

[17]Schroeder, B., Gibson, G.A., 2007. 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, p.1-16.

[18]Wan, S., Cao, Q., Xie, C.S., et al., 2010. 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, p.51-60.

[19]Wang, Z.Y., Dimakis, A.G., Bruck, J., 2010. Rebuilding for array codes in distributed storage systems. Proc. IEEE GLOBECOM Workshops, p.1905-1909.

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

[21]Xiang, L.P., Xu, Y.L., Lui, J., et al., 2011. A hybrid approach to failed disk recovery using RAID-6 codes: algorithms and performance evaluation. ACM Trans. Stor., 7(3), Article 11.

[22]Xie, P., Huang, J.Z., Cao, Q., et al., 2015. A new non-MDS RAID-6 code to support fast reconstruction and balanced I/Os. Comput. J., in press.

[23]Xu, L.H., Bruck, J., 1999. X-code: MDS array codes with optimal encoding. IEEE Trans. Inform. Theory, 45(1):272-276.

[24]Zhu, Y.F., Lee, P.P.C., Hu, Y.C., et al., 2012a. 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, p.1-12.

[25]Zhu, Y.F., Lee, P.P.C., Xiang, L.P., et al., 2012b. A cost-based heterogeneous recovery scheme for distributed storage systems with RAID-6 codes. Proc. 42nd Annual IEEE/IFIP Int. Conf. on Dependable Systems and Networks, p.1-12.

[26]Zomaya, A.Y., Teh, Y.H., 2001. Observations on using genetic algorithms for dynamic load-balancing. IEEE Trans. Parall. Distr. Syst., 12(9):899-911.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Similar articles

- Go to

一种负载平衡的RAID-6存储方案

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference