Efficient disk replacement and data migration algorithms for large disk subsystems

ABSTRACT

Random data placement, which is efficient and scalable for large-scale storage systems, has recently emerged as an alternative to traditional data striping. In this report, we study the disk replacement problem (DRP) to find a sequence of disk additions and removals for a storage system, while migrating the data and respecting the following constraints: (1) the data is initially balanced across the existing distributed disk configuration, (2) the data must again be balanced across the new configuration, and (3) the data migration cost must be minimized. In practice, migrating data from old disks to new devices is complicated by the fact that the total number of disks connected to the storage system is often limited by a fixed number of available slots and not all the old and new disks can be connected at the same time. This article presents solutions for both cases where the number of disk slots is either unconstrained or constrained.

REFERENCES

• 1: Eric Anderson , Joseph Hall , Jason D. Hartline , Michael Hobbs , Anna R. Karlin , Jared Saia , Ram Swaminathan , John Wilkes, An Experimental Study of Data Migration Algorithms, Proceedings of the 5th International Workshop on Algorithm Engineering, p.145-158, August 28-31, 2001
• 2: André Brinkmann , Kay Salzwedel , Christian Scheideler, Efficient, distributed data placement strategies for storage area networks (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.119-128, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341815]
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: SCADDAR: An Efficient Randomized Technique to Reorganize Continuous Media Blocks, Proceedings of the 18th International Conference on Data Engineering, p.473, February 26-March 01, 2002
• 5: Joseph Hall , Jason Hartline , Anna R. Karlin , Jared Saia , John Wilkes, On algorithms for efficient data migration, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.620-629, January 07-09, 2001, Washington, D.C., United States
• 6: Samir Khuller , Yoo-Ah Kim , Yung-Chun (Justin) Wan, Algorithms for data migration with cloning, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.27-36, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773156]
• 7: Richard Muntz , Jose Renato Santos , Steve Berson, RIO: a real-time multimedia object server, ACM SIGMETRICS Performance Evaluation Review, v.25 n.2, p.29-35, Sept. 1997 [doi>10.1145/262391.262398]
• 8: Jose Renato Santos , Richard R. Muntz , Berthier Ribeiro-Neto, Comparing random data allocation and data striping in multimedia servers, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.44-55, June 18-21, 2000, Santa Clara, California, United States
• 9: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 10: Wilkes, J., Golding, R., Staelin, C., and Sullivan, T. 2001. The HP AutoRAID hierarchical storage system. In High Performance Mass Storage and Parallel I/O: Technologies and Applications, H. Jin, T. Cortes, and R. Buyya eds. IEEE Computer Society Press and John Wiley, New York, NY, 90--106.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems

General Terms:
Algorithms, Management

Keywords:
Disk replacement, data migration, randomized striping, storage resource management