A hybrid filesystem for hard disk drives in tandem with flash memory. (English) Zbl 1234.68050
Summary: The traditional hard disk drive (HDD) is often a bottleneck in the overall performance of modern computer systems. With the development of solid state drives (SSD) based on flash memory, new possibilities are available to improve secondary storage performance. In this work, we propose a new hybrid SSD-HDD storage system and a selection of algorithms designed to assign pages across an HDD and an SSD to optimise I/O performance. The hybrid system combines the advantages of the SSD’s fast random seek speed with the sequential access speed and large storage capacity of the HDD to produce significantly improved performance in a variety of situations. We further improve performance by allowing concurrent access across the two types of storage devices. We show the drive assignment problem is NP-complete and accordingly propose effective heuristic solutions. Extensive experiments using both synthetic and real data sets show our system with a small SSD can outperform a striped dual HDD and remain competitive with a dual SSD.
MSC:
| 68M99 | Computer system organization |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Agrawal N, Bolosky WJ, Douceur JR, Lorch JR (2007) A five-year study of file-system metadata. ACM Trans Storage 3(3). Article No. 9 |
| [2] | Arnan R, Bachmat E, Lam TK, Michel R (2007) Dynamic data reallocation in disk arrays. ACM Trans Storage 3(1): 2 · doi:10.1145/1227835.1227837 |
| [3] | Baker M, Asami S, Deprit E, Ousterhout JK, Seltzer MI (1992) Non-volatile memory for fast, reliable file systems. In: Architectural support for programming languages and operating systems (ASPLOS), pp 10–22 |
| [4] | Bouganim L, Jónsson Bó, Bonnet P (2009) uFLIP: understanding flash IOp atterns. In: Conference on innovative data systems research (CIDR) |
| [5] | Caulfield AM, Grupp LM, Swanson S (2009) Gordon: using flash memory to build fast, power-efficient clusters for data-intensive applications. In: Architectural support for programming languages and operating systems (ASPLOS), pp 217–228 |
| [6] | Chang L-P, Kuo T-W (2005) Efficient management for large-scale flash-memory storage systems with resource conservation. ACM Trans Storage 1(4): 381–418 · doi:10.1145/1111609.1111610 |
| [7] | Chang Y-H, Hsieh J-W, Kuo T-W (2007) Endurance enhancement of flash-memory storage systems: an efficient static wear leveling design. In: DAC ’07: proceedings of the 44th annual conference on design automation, New York, NY, USA. ACM, pp 212–217 |
| [8] | Choi H-J, Lim SH, Park KH (2009) JFTL: a flash translation layer based on a journal remapping for flash memory. ACM Trans Storage 4(4). Article No. 14 |
| [9] | Dramaliev I, Madhyastha T (2003) Optimizing probe-based storage. In: FAST 03: 2nd USENIX conference on file and storage technologies, pp 103–114 |
| [10] | Gabriel K.J. (1997) Microelectromechanical systems (MEMS). Aerospace conference. Proceedings IEEE 1997 3: 9–43 · doi:10.1109/AERO.1997.574849 |
| [11] | Gal E, Toledo S (2005) Algorithms and data structures for flash memories. ACM Comput Surv 37(2): 138–163 · doi:10.1145/1089733.1089735 |
| [12] | Garrison JA, Narasimha Reddy AL (2009) Umbrella file system: storage management across heterogeneous devices. ACM Trans Storage 5(1). Article No. 3 |
| [13] | getprice.com. Get Price 1TB Baracuda 7200.12 Price. http://www.getprice.com.au/Seagate-Barracuda-7200-12-3-5-1TB-HDD-SATAII-7200rpm-32MB-Cache-ST31000528AS-Gpnc_58–36904358.htm . Accessed June 2010 |
| [14] | Grossman DD, Silverman HF (1973) Placement of records on a secondary storage device to minimize access time. J ACM 20(3): 429–438 · Zbl 0265.68022 · doi:10.1145/321765.321775 |
| [15] | Gupta A, Kim Y, Urgaonkar B (2009) Dftl: a flash translation layer employing demand-based selective caching of page-level address mappings. In: Architectural support for programming languages and operating systems (ASPLOS), pp 229–240 |
| [16] | Hong B, Wang F, Brandt SA, Long DDE, Thomas SJ, Schwarz JE (2006) Using MEMS-based storage in computer systems–MEMS storage architectures. ACM Trans Storage 2(1): 1–21 · doi:10.1145/1138041.1138042 |
| [17] | Johnson DS, Garey MR (1979) Computers and intractability. A guide to the theory of NP-completeness. Mathematical programming, chap A6. W.H. Freeman and Company · Zbl 0411.68039 |
| [18] | Koltsidas I, Viglas S (2008) Flashing up the storage layer. In: 34th International conference on very large databases (VLDB) |
| [19] | Kang J-U, Jo H, Kim J-S, Lee J (2006) A superblock-based flash translation layer for NAND flash memory. In: EMSOFT ’06: Proceedings of the 6th ACM & IEEE international conference on embedded software, New York, NY, USA. ACM, pp 161–170 |
| [20] | Kim J, Kim JM, Soh SH, Min SL, Cho Y (2002) A space-efficient flash translation layer for compactflash systems. IEEE Trans Consumer Electron 48(2): 366–375 · doi:10.1109/TCE.2002.1010085 |
| [21] | Lee J, Kim S, Kwon H, Hyun C, Ahn S, Choi J, Lee D, Noh SH (2007) Block recycling schemes and their cost-based optimization in nand flash memory based storage system. In: EMSOFT ’07: Proceedings of the 7th ACM & IEEE international conference on embedded software, New York, NY, USA. ACM, pp 174–182 |
| [22] | Lee S-W, Park D-J, Chung T-S, Lee D-H, Park S, Song H-J (2007) A log buffer-based flash translation layer using fully-associative sector translation. ACM Trans Embedded Comput Syst 6(3): 18 · doi:10.1145/1275986.1275990 |
| [23] | Lee S, Kim C, Jung S, Song I-S, Cho YC (2001) MEMS for IT applications. In: Proceedings of 2001 international symposium on micromechatronics and human science, vol 1, pp 17–23 |
| [24] | Lee S, Shin D, Kim Y-J, Kim J (2008) LAST: locality-aware sector translation for NAND flash memory-based storage systems. SIGOPS Oper Syst Rev 42(6): 36–42 |
| [25] | Leventhal A (2008) Flash storage memory. Commun ACM 51(7): 47–51 · doi:10.1145/1364782.1364796 |
| [26] | Lim S-H, Lee C, Park K-H (2007) Hashing directory scheme for NAND flash file system. In: The 9th international conference on advanced communication technology vol 1, pp 273–276 |
| [27] | Lim S-H, Park K-H (2006) An efficient NAND flash file system for flash memory storage. IEEE Trans Comput 55: 906–912 · doi:10.1109/TC.2006.96 |
| [28] | Liu Y, Xie C-S, Li H-Y (2005) PMSH: a new algorithm for RAID data migration based on stripe unit heat. In: Proceedings of 2005 international conference on machine learning and cybernetics, vol 6, pp 3421–3427 |
| [29] | Matthews J, Trika SN, Hensgen D, Coulson R, Grimsrud K (2008) Intel turbo memory: nonvolatile disk caches in the storage hierarchy of mainstream computer systems. ACM Trans Storage 4(2). Article No. 4 |
| [30] | Miller EL, Brandt SA, Long DDE (2001) HeRMES: high-performance reliable MRAM-enabled storage. In: Hot topics in operating systems, pp 95–99 |
| [31] | Payer H, Sanvido M, Bandic Z, Kirsch C (2009) Combo drive: optimizing cost and performance in a heterogeneous storage device. In: Workshop on integrating solid-state memory into the storage hierarchy (WISH) |
| [32] | Rosenblum M, Ousterhout JK (1992) The design and implementation of a log-structured file system. ACM Trans Comput Syst 10(1): 26–52 · doi:10.1145/146941.146943 |
| [33] | Seagate. Seagate 1TB Barracuda 7200.12 Specifications. http://www.seagate.com/docs/pdf/datasheet/disc/ds_barracuda_7200_12.pdf . Accessed June 2010 |
| [34] | Soundararajan G, Prabhakaran V, Balakrishnan M, Wobber T (2010) Extending SSD lifetimes with disk-based write caches. In: Proceedings of the 8th USENIX conference on File and storage technologies, FAST’10, pp 8–8, Berkeley, CA, USA. USENIX Association |
| [35] | SuperTalent. Super Talent MasterDrive EX2 Specifications. http://www.supertalent.com/products/ssd_category_detail.php?type=MasterDrive . Accessed June 2010 |
| [36] | UMassRepository. Storage system workloads. http://traces.cs.umass.edu/index.php/Storage/Storage . Accessed June 2009 |
| [37] | Uysal M, Merchant A, Alvarez GA (2003) Using MEMS-based storage in disk arrays. In: FAST 03: 2nd USENIX conference on file and storage technologies, pp 89–101 |
| [38] | Kuenning GH., Reiher PL., Popek GJ. (2006) The conquest file system: better performance through a disk/persistent-ram hybrid design. ACM Trans Storage 2(3): 309–348 · doi:10.1145/1168910.1168914 |
| [39] | Wang W, Zhao Y, Bunt R (2004) HyLog: a high performance approach to managing disk layout. In: FAST 04: 3rd USENIX conference on file and storage technologies, pp 145–158 |
| [40] | www.mwave.com.au . OCZ Vertex 2 Price. http://www.mwave.com.au/sku-22140387-OCZ_Vertex_2_120GB_SATA_II_3_5%22_Solid_State_Drive_0_1ms_Seek_Time_Read_285M . Accessed August 2011 |
| [41] | www.mwave.com.au . OCZ Vertex 3 Price. http://www.mwave.com.au/sku-22140500-FREE_SHIPPING_OCZ_Vertex_3_2_5%22_Solid_State_Drive_240GB_SATA3_Read_550MB_s_ . Accessed August 2011 |
| [42] | www.ocztechnology.com . OCZ Vertex 2 Specifications. http://www.ocztechnology.com/ocz-vertex-2-sata-ii-2-5-ssd.html . Accessed August 2011 |
| [43] | www.ocztechnology.com . OCZ Vertex 3 Specifications. http://www.ocztechnology.com/ocz-vertex-3-sata-iii-2-5-ssd.html . Accessed August 2011 |
| [44] | Yu H, Agrawal D, El Abbadi A (2003) Towards optimal I/O scheduling for MEMS-based storage. In: 20th IEEE/11th NASA Goddard conference on mass storage systems & technologies |
| [45] | Zhang Z, Ghose K (2003) yFS: a journaling file system design for handling large data sets with reduced seeking. In: FAST 03: 2nd USENIX conference on file and storage technologies, pp 59–72 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
