Shifted declustering: a placement-ideal layout scheme for multi-way replication storage architecture

ABSTRACT

Recent years have seen a growing interest in the deployment of sophisticated replication based storage architecture in data-intensive computing. Existing placement-ideal data layout solutions place an emphasis on declustered parity based storage. However, there exist major differences between parity and replication architectures, especially in data layouts. We retrofit the desirable properties of optimal parallelism in parity architectures for replication architectures, and propose a novel placement-ideal data layout ---- shifted declustering for replication based storage. Shifted declustering layout obtains optimal parallelism in a wide range of configurations, and obtains optimal high performance and load balancing in both fault-free and degraded modes. Our theoretical proofs and comprehensive simulation results show that shifted declustering is superiour in performance and load balancing to traditional replication layout schemes such as standard mirroring, chained declustering, group rotational declustering and existing parity layout schemes PRIME and RELPR in reference [4].

REFERENCES

• 1: The disksim simulation environment (v3.0). http://www.pdl.cmu.edu/DiskSim/, 2007.
• 2: Powervault md 1000 disk expansion enclosure details. http://www.dell.com/content/products/productdetails.aspx/pvaul md1000, 2007.
• 3: Seagate, samsung begin to ship 1tb desktop hard drives. http://www.dailytech.com/Article.aspx?newsid=7740, 2007.
• 4: G. A. Alvarez, W. A. Burkhard, L. J. Stockmeyer, and F. Cristian. Declustered disk array architectures with optimal and near-optimal parallelism. In ISCA, pages 109--120, 1998.
• 5: R. E. Bryant. Data-intensive supercomputing: The case for DISC. Technical Report CMU-CS-07-128, Carnegie Mellon University, May 2007.
• 6: M.-S. Chen, H.-I. Hsiao, C.--S. Li, and P. S. Yu. Using rotational mirrored declustering for replica placement in a disk--array--based video server. Multimedia Syst., 5(6):371--379, 1997.
• 7: S. Chen and D. Towsley. A performance evaluation of RAID architectures. IEEE Trans. Comput., 45(10):1116--1130, 1996.
• 8: G. Copeland and T. Keller. A comparison of high-availability media recovery techniques. In SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data, pages 98--109, New York, NY, USA, 1989. ACM.
• 9: G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon's highly available key-value store. In SOSP '07: Proceedings of twenty--first ACM SIGOPS symposium on Operating systems principles, pages 205--220, New York, NY, USA, 2007. ACM.
• 10: S. Ghemawat, H. Gobioff, and S.--T. Leung. The google file system. In SOSP, pages 29--43, 2003.
• 11: M. Holland and G. A. Gibson. Parity declustering for continuous operation in redundant disk arrays. In ASPLOS, pages 23--35, 1992.
• 12: H.-I. Hsiao and D. J. DeWitt. Chained declustering: A new availability strategy for multiprocessor database machines. In Proceedings of the Sixth International Conference on Data Engineering, pages 456--465, Washington, DC, USA, 1990. IEEE Computer Society.
• 13: J. L. Griffin, S. W. Schlosser, G. R. Ganger, and D. F. Nagle. Modeling and scheduling of mems-based storage devices. Technical Report CMU-CS-00-100, Carnegie Mellon University, 1999.
• 14: F. J. MacWilliams and J. J. A. Sloane. The Theory of Error-Correcting Codes. Amsterdam, North-Holland, 1977.
• 15: J. Marshall Hall. Combinatorial theory (2nd ed.). John Wiley & Sons, Inc., New York, NY, USA, 1998.
• 16: D. A. Patterson, G. Gibson, and R. H. Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID). In Proceedings of the 1988 ACM Conference on Management of Data (SIGMOD), pages 109--116, Chicago, IL, June 1988.
• 17: W. W. Peterson and E. Weldon. Error-Correcting Codes. MIT Press, 1972.
• 18: Y. Saito, S. Frolund, A. Veitch, A. Merchant, and S. Spence. Fab: building distributed enterprise disk arrays from commodity components. SIGPLAN Not., 39(11):48--58, 2004.
• 19: W. W. Wilcke, R. R. Garner, C. Fleiner, R. F. Freitas, and R. A. Golding. IBM intelligent bricks project: petabytes and beyond. IBM journal of research and development, 2006.
• 20: J. M. Wing. Computer science meets science and engineering. HEC FSIO R&D Workshop, NSF, August 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Parallel I/O

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Design, Performance, Reliability

Keywords:
data layout, multi-way replication, optimal parallelism