Cited By
View all- Zhang GHuang ZMa XYang SWang ZZheng WAgrawal NRangaswami R(2018)RAID+Proceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189786(279-293)Online publication date: 12-Feb-2018
CRAID: online RAID upgrades using dynamic hot data reorganization
Authors: 
A. Miranda, T. CortesAuthors Info & Claims
Abstract
Current algorithms used to upgrade RAID arrays typically require large amounts of data to be migrated, even those that move only the minimum amount of data required to keep a balanced data load. This paper presents CRAID, a self-optimizing RAID array that performs an online block reorganization of frequently used, long-term accessed data in order to reduce this migration even further. To achieve this objective, CRAID tracks frequently used, long-term data blocks and copies them to a dedicated partition spread across all the disks in the array. When new disks are added, CRAID only needs to extend this process to the new devices to redistribute this partition, thus greatly reducing the overhead of the upgrade process. In addition, the reorganized access patterns within this partition improve the array's performance, amortizing the copy overhead and allowing CRAID to offer a performance competitive with traditional RAIDs.
We describe CRAID's motivation and design and we evaluate it by replaying seven real-world workloads including a file server, a web server and a user share. Our experiments show that CRAID can successfully detect hot data variations and begin using new disks as soon as they are added to the array. Also, the usage of a dedicated partition improves the sequentiality of relevant data access, which amortizes the cost of reorganizations. Finally, we prove that a full-HDD CRAID array with a small distributed partition (<1.28% per disk) can compete in performance with an ideally restriped RAID-5 and a hybrid RAID-5 with a small SSD cache.
References
[1]
AGRAWAL, N ., PRABHAKARAN, V., WOBBER, T., DAVIS, J., MANASSE, M., AND PANIGRAHY, R. Design tradeoffs for SSD performance. In USENIX 2008 Annual Technical Conference on Annual Technical Conference (2008), pp. 57-70.
[2]
AKYÜREK, S., AND SALEM, K. Adaptive block rearrangement. ACM Transactions on Computer Systems (TOCS) 13, 2 (1995), 89-121.
[3]
ARLITT, M., CHERKASOVA, L., DILLEY, J., FRIEDRICH, R., AND JIN, T. Evaluating content management techniques for web proxy caches. ACM SIGMETRICS Performance Evaluation Review 27, 4 (2000), 3-11.
[4]
ARTIAGA, E., AND MIRANDA, A. PRACE-2IP Deliverable D12.4. Performance Optimized Lustre. INFRA- 2011-2.3.5 - Second Implementation Phase of the European High Performance Computing (HPC) service PRACE (2012).
[5]
BHADKAMKAR, M., GUERRA, J., USECHE, L., BURNETT, S., LIPTAK, J., RANGASWAMI, R., AND HRISTIDIS, V. BORG: block-reORGanization for self-optimizing storage systems. In Proccedings of the 7th conference on File and storage technologies (2009), USENIX Association, pp. 183-196.
[6]
BRINKMANN, A., SALZWEDEL, K., AND SCHEIDELER, C. Efficient, Distributed Data Placement Strategies for Storage Area Networks. In Proceedings of the 12th ACM Symposium on Parallel Algorithms and Architectures (SPAA) (2000), pp. 119-128.
[7]
BROWN, N. Online RAID-5 resizing. drivers/md/raid5. c in the source code of Linux Kernel 2.6. 18, 2006.
[8]
BUCY, J., SCHINDLER, J., SCHLOSSER, S., AND GANGER, G. The DiskSim Simulation Environment Version 4.0 Reference Manual (CMU-PDL-08-101). Parallel Data Laboratory (2008), 26.
[9]
CAO, P., AND IRANI, S. Cost-aware WWW proxy caching algorithms. In Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems (1997), vol. 193.
[10]
CHEN, P., LEE, E., GIBSON, G., KATZ, R., AND PATTERSON, D. RAID: High-performance, reliable secondary storage. ACM Computing Surveys (CSUR) 26, 2 (1994), 145-185.
[11]
CHEN, P. M., AND LEE, E . K. Striping in a RAID level 5 disk array, vol. 23. ACM, 1995.
[12]
ELLARD, D., LEDLIE, J., MALKANI, P., AND SELTZER, M. Passive NFS tracing of email and research workloads. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (2003), USENIX Association, pp. 203-216.
[13]
GOEL, A., SHAHABI, C., YAO, S., AND ZIMMERMANN, R. SCADDAR: An efficient randomized technique to reorganize continuous media blocks. In Data Engineering, 2002. Proceedings. 18th International Conference on (2002), IEEE, pp. 473-482.
[14]
GÓMEZ, M., AND SANTON JA, V. Characterizing temporal locality in I/O workload. In Proc. of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems (2002).
[15]
GONZALEZ, J., AND CORTES, T. Increasing the capacity of RAID5 by online gradual assimilation. In Proceedings of the international workshop on Storage network architecture and parallel I/Os (2004), ACM, pp. 17- 24.
[16]
HE, X., YANG, Q., AND ZHANG, M. A caching strategy to improve iSCSI performance. In Local Computer Networks, 2002. Proceedings. LCN 2002. 27th Annual IEEE Conference on (2002), IEEE, pp. 278-285.
[17]
HETZLER, S. R., ET AL. Data storage array scaling method and system with minimal data movement. US Patent 8,239,622.
[18]
HIDROBO, F., AND CORTES, T. Autonomic storage system based on automatic learning. In High Performance Computing-HiPC 2004. Springer, 2005, pp. 399-409.
[19]
HONICKY, R., AND MILLER, E. L. Replication under scalable hashing: A family of algorithms for scalable decentralized data distribution. In Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International (2004), IEEE, p. 96.
[20]
HSU, W., SMITH, A., AND YOUNG, H. The automatic improvement of locality in storage systems. ACM Transactions on Computer Systems (TOCS) 23, 4 (2005), 424-473.
[21]
JIN, S., AND BESTAVROS, A. GreedyDual* Web caching algorithm: exploiting the two sources of temporal locality in Web request streams. Computer Communications 24, 2 (2001), 174-183.
[22]
LEE, S., AND BAHN, H. Data allocation in MEMS-based mobile storage devices. Consumer Electronics, IEEE Transactions on 52, 2 (2006), 472-476.
[23]
LEGG, C. Method of increasing the storage capacity of a level five RAID disk array by adding, in a single step, a new parity block and N-1 new data blocks which respectively reside in a new columns, where N is at least two, Dec. 7 1999. US Patent 6,000,010.
[24]
LEUNG, A., PASUPATHY, S., GOODSON, G., AND MILLER, E. Measurement and analysis of large-scale network file system workloads. In USENIX 2008 Annual Technical Conference on Annual Technical Conference (2008), pp. 213-226.
[25]
LI, D., AND WANG, J. EERAID: energy efficient redundant and inexpensive disk array. In Proceedings of the 11th workshop on ACM SIGOPS European workshop (2004), ACM, p. 29.
[26]
LI, Z., CHEN, Z., SRINI VASAN, S., AND ZHOU, Y. C-miner: Mining block correlations in storage systems. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (2004), vol. 186, USENIX Association.
[27]
LYMAN, P. How much information? 2003. http://www.sims.berkeley.edu/research/ projects/how-much-info-2003/ (2003).
[28]
MEGIDDO, N., AND MODHA, D. ARC: A self-tuning, low overhead replacement cache. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (2003), pp. 115-130.
[29]
MIRANDA, A., AND CORTES, T. Analyzing Long-Term Access Locality to Find Ways to Improve Distributed Storage Systems. In Parallel, Distributed and Network-Based Processing (PDP), 2012 20th Euromicro International Conference on (2012), IEEE, pp. 544-553.
[30]
MIRANDA, A., EFFERT, S., KANG, Y., MILLER, E. L., BRINKMANN, A., AND CORTES, T. Reliable and randomized data distribution strategies for large scale storage systems. In High Performance Computing (HiPC), 2011 18th International Conference on (2011), IEEE, pp. 1-10.
[31]
NARAYANAN, D., DONNELLY, A., AND ROWSTRON, A. Write off-loading: Practical power management for enterprise storage. ACM Transactions on Storage (TOS) 4, 3 (2008), 10.
[32]
NARAYANAN, D., THERESKA, E., DONNELLY, A., ELNIKETY, S., AND ROWSTRON, A. Migrating server storage to SSDs: analysis of tradeoffs. In Proceedings of the 4th ACM European conference on Computer systems (2009), ACM, pp. 145-158.
[33]
NIGHTINGALE, T., HU, Y., AND YANG, Q. The design and implementation of DCD device driver for UNIX. In Proceedings of the 1999 USENIX Technical Conference (1999), pp. 295-308.
[34]
PARK, J., CHUN, H., BAHN, H., AND KOH, K. G-MST: A dynamic group-based scheduling algorithm for MEMS-based mobile storage devices. Consumer Electronics, IEEE Transactions on 55, 2 (2009), 570-575.
[35]
PATTERSON, D., ET AL. A simple way to estimate the cost of downtime. In Proc. 16th Systems Administration Conf.-- LISA (2002), pp. 185-8.
[36]
PATTERSON, D., GIBSON, G., AND KATZ, R. A case for redundant arrays of inexpensive disks (RAID), vol. 17. ACM, 1988.
[37]
RUEMMLER, C., AND WILKES, J. Disk shuffling. Tech. rep., Technical Report HPL-91-156, Hewlett Packard Laboratories, 1991.
[38]
RUEMMLER, C., AND WILKES, J. UNIX disk access patterns. In Proceedings of the Winter 1993 USENIX Technical Conference (1993), pp. 405-420.
[39]
Segate Cheetah 15K.5 FC product manual. http://www. seagate.com/staticfiles/support/disc/manuals/ enterprise/cheetah/15K.5/FC/100384772f.pdf Last retrieved Sept. 9, 2013.
[40]
SEO, B., AND ZIMMERMANN, R. Efficient disk replacement and data migration algorithms for large disk subsystems. ACM Transactions on Storage (TOS) 1, 3 (2005), 316-345.
[41]
VERMA, A., KOLLER, R., USECHE, L., AND RANGASWAMI, R. SRCMap: energy proportional storage using dynamic consolidation. In Proceedings of the 8th USENIX conference on File and storage technologies (2010), USENIX Association, pp. 20-20.
[42]
VONGSATHORN, P., AND CARSON, S. A system for adaptive disk rearrangement. Software: Practice and Experience 20, 3 (1990), 225-242.
[43]
WEIL, S. A., BRANDT, S. A., MILLER, E. L., AND MALTZAHN, C. Crush: Controlled, scalable, decentralized placement of replicated data. In Proceedings of the 2006 ACM/IEEE conference on Supercomputing (2006), ACM, p. 122.
[44]
WILKES, J., GOLDING, R., STAELIN, C., AND SULLIVAN, T. The HP AutoRAID hierarchical storage system. ACM Transactions on Computer Systems (TOCS) 14, 1 (1996), 108-136.
[45]
WONG, C. Minimizing expected head movement in one-dimensional and two-dimensional mass storage systems. ACM Computing Surveys (CSUR) 12, 2 (1980), 167-178.
[46]
WONG, T., GANGER, G., WILKES, J., ET AL. My Cache Or Yours?: Making Storage More Exclusive. School of Computer Science, Carnegie Mellon University, 2000.
[47]
WU, C., AND HE, X. Gsr: A global stripe-based redistribution approach to accelerate raid-5 scaling. In Parallel Processing (ICPP), 2012 41st International Conference on (2012), IEEE, pp. 460-469.
[48]
YANG, Q., AND HU, Y. DCD--disk caching disk: A new approach for boosting I/O performance. In Computer Architecture, 1996 23rd Annual International Symposium on (1996), IEEE, pp. 169-169.
[49]
ZHANG, G., SHU, J., XUE, W., AND ZHENG, W. SLAS: An efficient approach to scaling round-robin striped volumes. ACM Transactions on Storage (TOS) 3, 1 (2007), 3.
[50]
ZHENG, W., AND ZHANG, G. FastScale: accelerate RAID scaling by minimizing data migration. In Proceedings of the 9th USENIX Conference on File and Storage Technologies (FAST) (2011).
[51]
ZHU, Q., CHEN, Z., TAN, L., ZHOU, Y., KEETON, K., AND WILKES, J. Hibernator: helping disk arrays sleep through the winter. In ACM SIGOPS Operating Systems Review (2005), vol. 39, ACM, pp. 177-190.
- CRAID: online RAID upgrades using dynamic hot data reorganization
Recommendations
HPDA: A hybrid parity-based disk array for enhanced performance and reliability
Flash-based Solid State Drive (SSD) has been productively shipped and deployed in large scale storage systems. However, a single flash-based SSD cannot satisfy the capacity, performance and reliability requirements of the modern storage systems that ...
Higher reliability redundant disk arrays: Organization, operation, and coding
Parity is a popular form of data protection in redundant arrays of inexpensive/independent disks (RAID). RAID5 dedicates one out of N disks to parity to mask single disk failures, that is, the contents of a block on a failed disk can be reconstructed by ...
LDM: Log Disk Mirroring with Improved Performance and Reliability for SSD-Based Disk Arrays
With the explosive growth in data volume, the I/O bottleneck has become an increasingly daunting challenge for big data analytics. Economic forces, driven by the desire to introduce flash-based Solid-State Drives (SSDs) into the high-end storage market, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- VMware
- NetApp
- NSF
- EMC2: EMC2
- Symantec: Symantec
In-Cooperation
Publisher
USENIX Association
United States
Publication History
Published: 17 February 2014
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
Cited By
View all- Zhang GHuang ZMa XYang SWang ZZheng WAgrawal NRangaswami R(2018)RAID+Proceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189786(279-293)Online publication date: 12-Feb-2018