Anefficient data layout scheme for better I/O balancing inRAID-6 storage systems

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

RAID-6 / Data availability / High performance / I/O balancing

References

[1] Bachmat, E., Ofek, Y., Zakai, A., , 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., , 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., , 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., , 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 XORbased 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., , 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., , 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., , 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., , 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., , 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., , 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., , 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., , 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., , 2012b. 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, 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. [