Beomjoo Seo
Roger Zimmermann
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.
- Anderson, E., Hall, J., Hartline, J., Hobbs, M., Karlin, A. R., Saia, J., Swaminathan, R., and Wilkes, J. 2001. An experimental study of data migration algorithms. In 5th International Workshop of Algorithm Engineering (WAE'01), Aarhus, Denmark.]] Google Scholar
- Brinkmann, A., Salzwedel, K., and Scheideler, C. 2000. Efficient, distributed data placement strategies for storage area networks. In the ACM Symposium on Parallel Algorithms and Architecture. 119--128.]] Google Scholar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms 2nd ed. The MIT Press.]] Google Scholar
- Goel, A., Shahabi, C., Yao, S.-Y. D., and Zimmermann, R. 2002. SCADDAR: An efficient randomized technique to reorganize continuous media blocks. In the 18th International Conference on Data Engineering (ICDE'02). San Jose, CA. 1850--1854.]] Google Scholar
- Hall, J., Hartline, J., Karlin, A. R., Saia, J., and Wilkes, J. 2001. On algorithms for efficient data migration. In the 12th annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Washington DC.]] Google Scholar
- Khuller, S., Kim, Y.-A., and Wan, Y.-C. J. 2003. Algorithms for data migration with cloning. In Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 27--36.]] Google Scholar
- Muntz, R., Santos, J., and Berson, S. 1997. RIO: A real-time multimedia object server. ACM Sigmetrics Perf. Eval. Rev. 25.]] Google Scholar
- Santos, J. R., Muntz, R. R., and Ribeiro-Neto, B. 2000. Comparing random data allocation and data striping in multimedia servers. In Proceedings of the SIGMETRICS Conference. Santa Clara, CA.]] Google Scholar
- Sleator, D. D. and Tarjan, R. E. 1985. Self-adjusting binary search trees. J. ACM 32, 3, 652--686.]] Google Scholar
- 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.]]Google Scholar
Index Terms
- Efficient disk replacement and data migration algorithms for large disk subsystems
Recommendations
Reliability and security of RAID storage systems and D2D archives using SATA disk drives
Information storage reliability and security is addressed by using personal computer disk drives in enterprise-class nearline and archival storage systems. The low cost of these serial ATA (SATA) PC drives is a tradeoff against drive reliability design ...
DCD—disk caching disk: a new approach for boosting I/O performance
ISCA '96: Proceedings of the 23rd annual international symposium on Computer architectureThis paper presents a novel disk storage architecture called DCD, Disk Caching Disk, for the purpose of optimizing I/O performance. The main idea of the DCD is to use a small log disk, referred to as cache-disk, as a secondary disk cache to optimize ...
Exploiting the performance gains of modern disk drives by enhancing data locality
Due to the widening performance gap between RAM and disk drives, a large number of I/O optimization methods have been proposed and designed to alleviate the impact of this gap. One of the most effective approaches of improving disk access performance is ...
Comments