Total views : 203

Balancing Spatial Locality with Parallelism in Solid State Disks

Affiliations

  • Department of Ecommerce, Semyung University, Jecheon, Chungbuk, 27136, Korea
  • Department of Software Science, Dankook University, Yongin, Gyeonggi, 16890, Korea
  • Korea Institute of Ocean Science and Technology, Ansan, Gyeonggi, 15627, Korea

Abstract


Objectives: Modern flash memory based storage systems, such as Solid State Disks (SSDs), are actively utilizing the channel/way interleaving to exploit parallelism among multiple NAND chips. Methods/Statistical Analysis: However, the flip side of the interleaving is that it disperses data with spatial locality across different NAND blocks, which eventually causes a high garbage collection overhead. To overcome this problem, we propose a spatial locality-aware allocation policy, called SLAP. It uses the notion of stream, which is defined as a set of data having consecutive Logical Page Numbers (LPN). Findings: By allocating a stream into a NAND block separately, it can preserve the spatial locality. In addition, by handling multiple streams simultaneously, it can obtain the parallelism among NAND chips. Also, we discuss that SLAP can balance between locality-preserving and parallelism by providing a spectrum from a traditional parallelism-oriented allocation to a strict locality-preserving one. We have implemented SLAP on a page-level mapping Flash Translation Layer (FTL) that is being used as a default FTL in many commercial SSDs. Improvements/Applications: Trace-driven simulation based experimental results have shown that SLAP can improve performance by up to 35.3% with an average of 13.1%, compared with the traditional allocation policy for the three workload considered.

Keywords

Allocation Policy, Locality, NAND, Parallelism, SSDs.

Full Text:

 |  (PDF views: 203)

References


  • Kim Y, Oral S, Shipman G, Lee J, Dillow D, Wang F.Harmonia: A Globally Coordinated Garbage Collector for Arrays of Solid-State Drives, In: Proceeding of the IEEE 27th Symposium on Mass Storage Systems and Technologies, Denever, CO, 2011 May, 1−12.
  • Albrecht C, Merchant A, Stokely M, Waliji M, Labelle F, Coehlo N, Shi X, Schrock CE. Janus: Optimal Flash Provisioning for Cloud Storage Workloads, In: Proceedings of the USENIX Annual Technical Conference, Berkeley; 2013. p. 91−102.
  • Monfared V, Hassan M, Daneshmand S, Taheran F, Kaewtrakulpong P. Effects of Geometric Factors and Material Properties on Stress behavior in Rotating Disk, Indian Journal of Science and Technology. 2014; 7(1):1−6.
  • Yoo B, Won Y, Choi J, Yoon S, Cho S, Kang S. SSD Characterization: From Energy Consumption’s Perspective, In: Proceedings of the 3rd USENIX Conference on Hot Topics in Storage and File Systems, Berkeley, CA, USA, 2011, 3−3.
  • MICRON. P420m Architecture. Date Accessed: 2016.Available at: http://www.micron.com/products/solid-statestorage.
  • Agrawal N, Prabhakaran V, Wobber T, Davis JD, Manasse M, Panigrahy R. Design Tradeoffs for SSD Performance, In: Proceedings of the USENIX Annual Technical Conference, Berkeley, CA, USA, 2008, 57−70.
  • Zhao K, Zhao W, Sun H, Zhang T, Zhang X, Zheng N.LDPC-in-SSD: Making advanced Error Correction Codes Work Effectively in Solid State Drives, In: Proceedings of the 11th USENIX Conference on File and Storage Technologies; 2013. p. 243−56.
  • Kim J, Lee J, Choi J, Lee D, Noh S. Improving SSD Reliability with RAID via Elastic Striping and Anywhere Parity, In: Proceedings of the 43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Budapest; 2013. p. 1−12.
  • Jimenez X, Novo D, Ienne P. Wear Unleveling: Improving NAND Flash Lifetime by Balancing Page Endurance, In: Proceedings of the 12th USENIX Conference on File and Storage Technologies; 2014. p. 47−59.
  • Chen F, Luo L, Zhang X. CAFTL: A Content-Aware Flash Translation Layer Enhancing the Lifespan of Flash Memory Based Solid State Drives, In: Proceedings of the 9th USENIX Conference on File and Storage Technologies; 2011. p. 6−6.
  • Oh Y, Choi J, Lee D, Noh SH. Caching Less for Better Performance: Balancing Cache Size and Update Cost of Flash Memory Cache in Hybrid Storage Systems, In: Proceedings of the 10th USENIX Conference on File and Storage Technologies; 2012. p. 25.
  • Bucy JS, Schindler J, Schlosser SW, Ganger GR. The DiskSim Simulation Environment Version 4.0 Reference Manual, Technical report, CMU-PDL-08-101, Carnegie Mellon University, 2008.
  • SSD Extension for DiskSim Simulation Environment. Date Accessed: 06/03/2009. Available at: http://research.microsoft.com/en-us/downloads.
  • Gal E, Toledo S. Algorithms and Data Structures for Flash Memories, ACM Computing Surveys. 2005; 37(2):138−63.
  • Kim J, Kim JM, Noh S, Min SL, Cho Y. A Space-Efficient Flash Translation Layer for Compact Flash Systems, IEEE Transactions on Consumer Electronics. 2002; 48(2):366−75.
  • Lee S, Shin D, Kim YJ, Kim J. LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems, SIGOPS Operating System Review. 2008; 42(6):36−42.
  • Gupta A, Kim Y, Urgaonkar B. DFTL: A Flash Translation Layer Employing Demand-Based Selective Caching of Page-Level Address Mappings, In: Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems; 2009. p.229−40.
  • Jiang S, Zhang L, Yuan X, Hu H, Chen Y. S-FTL: An Efficient Address Translation for Flash Memory by Exploiting Spatial Locality, In: Proceedings of the IEEE 27th Symposium on Mass Storage Systems and Technologies, Denver, CO, 2011, 1−12.
  • Kwon H, Kim E, Choi J, Lee D, Noh SH. Janus-FTL: Finding the Optimal Point on the Spectrum Between Page and Block Mapping Schemes, In: Proceedings of the 10th ACM International Conference on Embedded Software, Scottsdale, Arizona, USA, 2010, 169−78.
  • Ma D, Feng J, Li G. Lazy FTL: A Page-Level Flash Translation Layer Optimized for NAND Flash Memory, In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Athens, Greece, 2011, 1−12.
  • Yoo J, Won Y, Hwang J, Kang S, Choi J, Yoon S, Cha J. VSSIM: Virtual Machine Based SSD Simulator, In: Proceedings of the IEEE 29th Symposium on Mass Storage Systems and Technologies, Long Beach, CA, 2013, 1−14.
  • Kim J, Lee C, Lee S, Son I, Choi J, Yoon S, Lee HU, Kang S, Won Y, Cha J. Deduplication in SSDs: Model and quantitative analysis, In: Proceedings of the IEEE 28th Symposium on Mass Storage Systems and Technologies, San Diego, CA, 2012, 1−12.
  • Muniswamy-Reddy KK, Holland DA. Causality-Based Versioning, In: Proceedings of the 7th Conference on File and Storage Technologies; 2009. p. 15−28.
  • Kim H, Ahn S. BPLRU: A Buffer Management Scheme for Improving Random writes in Flash Storage, In: Proceedings of the 6th USENIX Conference on File and Storage Technologies; 2008. p. 1−31.
  • Megiddo N, Modha DS. ARC: A Self-Tuning, Low Overhead Replacement Cache, In: Proceedings of the 2nd USENIX Conference on File and Storage Technologies; 2003. p. 115−30.
  • Narayanan D, Donnelly A, Rowstron A, Donnelly A, Rowstron A. Write off-loading: Practical Power Management for Enterprise Storage, In: Proceedings of the USENIX Conference on File and Storage Technologies; 2008. p. 253−67.
  • ONeil EJ, ONeil PE, Weikum G. The LRU-K Page Replacement Algorithm for Database Disk Buffering, In: Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, 1993, 297−306.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.