OPEN ACCESS
Large-scale storage systems face significant challenges in reliability and adaptability, thus it needs reliable, adaptive and effective data layout algorithms. Existing studies only partially meet these goals. This paper first puts forward a reliable copy data layout algorithm (RCDL) and an effective adaptive data layout algorithm (ADL), and on this basis, by combining the two algorithms, this paper proposes a multi-copy adaptive data layout algorithm MCADL, which can achieve better reliability, adaptability and effectiveness. The RCDL distributes the same copies to different storage devices to avoid the same replica on adjacent storage devices, thus obtaining higher redundancy and fault tolerance. The ADL algorithm combines the clustering algorithm with the consistent hash method, and introduces a small amount of virtual storage devices, greatly reducing the consumption of storage space. Data are distributed fairly according to the weights of the storage devices, so it is adaptive to system expansion and reduction. In order to utilize the respective advantages of RCDL and ADL, MCADL divides data into hot and cold data according to the data access frequency. RCDL layout is used for hot data and ADL layout is used for cold data. Theoretical and experimental results show that MCADL can obtain higher redundancy and fault tolerance and can fairly distribute data and add and remove adaptive storage devices according to the weights of storage devices, migrate optimal data amount when the scale of the storage system changes, and can quickly locate data, consuming less storage space.
Large-scale network storage, Data layout
[1] F. Dabek, M.F. Kaashoek, D. Karger, R. Morris, I. Stoica, Wide–area cooperative storage with CFS, 2001, In Proceedings of the 18th ACM Symposium on Operating Systems Principles, pp. 202–215.
[2] A. Rowstron, P. Druschel, Storage management and caching in PAST, a large–scale, persistent peer–to–peer storage utility, 2001, In Proceedings of the 18th ACM Symposium on Operating Systems Principles.
[3] S. Ghemawat, H. Gobioff, S.T. Leung, The google file system, 2003, In Proceedings of the 19th ACM Symposium on Operating Systems Principles, New York: ACM Press, pp. 19–22.
[4] J. Kubiatowicz, D. Bindel, Y. Chen, OceanStore: An architecture for global–scale persistent storage, 2000, ASPLOS.
[5] R. Renesse, Efficient reliable Internet storage, 2004, In Proceedings of the dependable distributed data management workshop.
[6] R.J. Honicky, E.L. Miller, A fast algorithm for online placement and reorganization of replicated data, 2003, In Proceedings of the 17th International Parallel & Distributed Processing Symposium, pp. 57-66.
[7] R.J. Honicky, E.L. Miller, Replication under scalable hash: a family of algorithms for scalable decentralized data distribution, 2004, In Proceedings of the 18th International Parallel and Distributed Processing Symposium. pp. 96-105.
[8] S.A. Weil, S.A. Brandt, E.L. Miller, C. Maltzahn, CRUSH: controlled, scalable and decentralized placement of replicated data, 2006, In Proceedings of Super Computing.
[9] A. Brinkmann, S. Effert, F.M. Heide, C. Scheideler, Dynamic and redundant data placement, 2007, In Proceedings of the 27th International Conference on Distributed Computing Systems. pp. 29-38.
[10] S. Weil, A. Leung, S.A. Brandt, C. Maltzahn, RADOS: A fast, scalable, and reliable storage service for petabyte–scale storage clusters, 2007, In Proceedings of the ACM petascale data storage workshop.
[11] A. Frieze, M. Jerrum, Improved approximation algorithms for MAX k–CUT and MAX BISECTION, 1997, Algorithmica.
[12] A. Brinkmann, K. Salzwedel, C. Scheideler, Compact, adaptive placement schemes for non–uniform distribution requirements, 2002, In Proceedings. of the 14th ACM Symposium on Parallel Algorithms and Architectures, Winnipeg, Manitoba, Canada, pp. 53-62.
[13] D. Karger, E. Lehman, T. Leighton, M. Levine, Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web, 1997, In Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 654-663.