Article

BPLRU: a buffer management scheme for improving random writes in flash storage

Authors:

Seongjun AhnAuthors Info & Claims

FAST'08: Proceedings of the 6th USENIX Conference on File and Storage Technologies

Article No.: 16, Pages 1 - 14

Published: 26 February 2008 Publication History

Abstract

Flash memory has become the most important storage media in mobile devices, and is beginning to replace hard disks in desktop systems. However, its relatively poor random write performance may cause problems in the desktop environment, which has much more complicated requirements than mobile devices. While a RAM buffer has been quite successful in hard disks to mask the low efficiency of random writes, managing such a buffer to fully exploit the characteristics of flash storage has still not been resolved. In this paper, we propose a new write buffer management scheme called Block Padding Least Recently Used, which significantly improves the random write performance of flash storage. We evaluate the scheme using trace-driven simulations and experiments with a prototype implementation. It shows about 44% enhanced performance for the workload of MS Office 2003 installation.

References

[1]

{1} Jens Axboe. Block IO Tracing. http://www.kernel. org/git/?p=linux/kernel/git/axboe/blktrace. git;a=blob;f=README.

[2]

{2} Amir Ban. Flash File System, 1993. United States Patent, No. 5,404,485.

[3]

{3} Fred Douglis, Ramon Caceres, M. Frans Kaashoek, Kai Li, Brian Marsh, and Joshua A. Tauber. Storage alternatives for mobile computers. In Operating Systems Design and Implementation, pages 25-37, 1994.

Digital Library

[4]

{4} Douglas Dumitru. Understanding Flash SSD Performance. Draft, http://www.storagesearch.com/ easyco-flashperformance-art.pdf, 2007.

[5]

{5} Futuremark Corporation. PCMARK'05. http://www. futuremark.com/products/pcmark05/.

[6]

{6} Intel Corporation. Understanding the Flash Translation Layer (FTL) Specification. White Paper, http://www. embeddedfreebsd.org/Documents/Intel-FTL.pdf, 1998.

[7]

{7} Iometer Project, iometer- {user-devel}@lists.sourceforge.net. Iometer Users Guide. http://www.iometer.org.

[8]

{8} Song Jiang, Xiaoning Ding, Feng Chen, Enhua Tan, and Xiaodong Zhang. DULO: an effective buffer cache management scheme to exploit both temporal and spatial locality. In FAST'05: Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies, pages 8-8, Berkeley, CA, USA, 2005. USENIX Association.

Digital Library

[9]

{9} Song Jiang and Xiaodong Zhang. LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance. In SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 31-42, New York, NY, USA, 2002. ACM.

Digital Library

[10]

{10} Heeseung Jo, Jeong-Uk Kang, Seon-Yeong Park, Jin-Soo Kim, and Joonwon Lee. FAB: flash-aware buffer management policy for portable media players. Consumer Electronics, IEEE Transactions on, 52(2):485-493, 2006.

Digital Library

[11]

{11} John, Hendrik Breitkreuz, Monk, and Bjoern. eMule. http://sourceforge.net/projects/emule.

[12]

{12} Hoyoung Jung, Kyunghoon Yoon, Hyoki Shim, Sungmin Park, Sooyong Kang, and Jaehyuk Cha. LIRS-WSR: Integration of LIRS and writes sequence reordering for flash memory. Lecture Notes in Computer Science, 4705:224-237, 2007.

Digital Library

[13]

{13} Jeong-Uk Kang, Heeseung Jo, Jin-Soo Kim, and Joonwon Lee. A superblock-based flash translation layer for NAND flash memory. In EMSOFT '06: Proceedings of the 6th ACM & IEEE International Conference on Embedded Software, pages 161-170, New York, NY, USA, 2006. ACM.

Digital Library

[14]

{14} Atsuo Kawaguchi, Shingo Nishioka, and Hiroshi Motoda. A flash-memory based file system. In USENIX Winter, pages 155-164, 1995.

Digital Library

[15]

{15} Bumsoo Kim and Guiyoung Lee. Method of driving remapping in flash memory and flash memory architecture suitable therefore, 2002. United States Patent, No. 6,381,176.

[16]

{16} Hyojun Kim, Jin-Hyuk Kim, ShinHo Choi, HyunRyong Jung, and JaeGyu Jung. A page padding method for fragmented flash storage. Lecture Notes in Computer Science, 4705:164-177, 2007.

Digital Library

[17]

{17} Jesung Kim, Jong Min Kim, S. H. Noh, Sang Lyul Min, and Yookun Cho. A space-efficient flash translation layer for CompactFlash Systems. IEEE Transactions on Consumer Electronics, 48(2):366-375, 2002.

Digital Library

[18]

{18} M-Systems. Two Technologies Compared: NOR vs. NAND. White Paper, http://www.dataio.com/pdf/ NAND/MSystems/MSystems_NOR_vs_NAND.pdf, 2003.

[19]

{19} Nimrod Megiddo and Dharmendra S. Modha. ARC: a self-tuning, low overhead replacement cache. In FAST '03: Proceedings of the 2nd USENIX Conference on File and Storage Technologies, pages 115-130, Berkeley, CA, USA, 2003. USENIX Association.

Digital Library

[20]

{20} Microsoft. Windows Driver Kit: Driver Development Tools, TraceView. http://msdn2.microsoft.com/ en-us/library/ms797981.aspx.

[21]

{21} Chanik Park, Jeong-Uk Kang, Seon-Yeong Park, and Jin-Soo Kim. Energy-aware demand paging on NAND flash-based embedded storages. In ISLPED '04: Proceedings of the 2004 International Symposium on Low Power Electronics and Design, pages 338-343, New York, NY, USA, 2004. ACM.

Digital Library

[22]

{22} Seon-Yeong Park, Dawoon Jung, Jeong-Uk Kang, Jin-Soo Kim, and Joonwon Lee. CFLRU: a replacement algorithm for flash memory. In CASES '06: Proceedings of the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, pages 234-241, New York, NY, USA, 2006. ACM.

Digital Library

[23]

{23} Mendel Rosenblum and John K. Ousterhout. The design and implementation of a log-structured file system. ACM Transactions on Computer Systems, 10(1):26-52, 1992.

Digital Library

[24]

{24} Mark Russinovich. DiskMon for Windows v2.01. http://www.microsoft.com/technet/ sysinternals/utilities/diskmon.mspx, 2006.

[25]

{25} Samsung Electronics. K9XXG08UXM 1G x8 Bit / 2G x 8 Bit NAND Flash Memory. http://www.samsung. com/global/business/semiconductor/products/ flash/Products_NANDFlash.html, 2005.

[26]

{26} SSFDC Forum. SmartMedia Specification. http://www. ssfdc.or.jp.

Cited By

Kim JJung MKim JSolihin YHeinrich M(2023)Decoupled SSD: Rethinking SSD Architecture through Network-based Flash ControllersProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589096(1-13)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589096
An MIm SJung DLee S(2022)Your read is our priority in flash storageProceedings of the VLDB Endowment10.14778/3538598.353861215:9(1911-1923)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.14778/3538598.3538612
Lin HSha ZLi JCai ZGerofi BShi YLiao J(2022)DRAM Cache Management with Request Granularity for NAND-based SSDsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545081(1-10)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545081
Show More Cited By

Recommendations

FRASH: hierarchical file system for FRAM and flash
ICCSA'07: Proceedings of the 2007 international conference on Computational science and its applications - Volume Part I

In this work, we develop novel file system, FRASH, for byte-addressable NVRAM (FRAM[1]) and NAND Flash device. Byte addressable NVRAM and NAND Flash is typified by the DRAM-like fast access latency and high storage density, respectively. Hierarchical ...
HiNFS: A Persistent Memory File System with Both Buffering and Direct-Access
Special Issue on NVM and Storage

Persistent memory provides data persistence at main memory with emerging non-volatile main memories (NVMMs). Recent persistent memory file systems aggressively use direct access, which directly copy data between user buffer and the storage layer, to ...
PFFS: a scalable flash memory file system for the hybrid architecture of phase-change RAM and NAND flash
SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

In this paper, we present the scalable and efficient flash file system using the combination of NAND and Phase-change RAM (PRAM). Until now, several flash file systems have been developed considering the physical characteristics of NAND flash. However, ...

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings

FAST'08: Proceedings of the 6th USENIX Conference on File and Storage Technologies

February 2008

323 pages

Editors:
Mary Baker
Hewlett-Packard Labs
,
Erik Riedel
Seagate Research

Sponsors

USENIX Assoc: USENIX Assoc

Publisher

USENIX Association

United States

Publication History

Published: 26 February 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
33
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim JJung MKim JSolihin YHeinrich M(2023)Decoupled SSD: Rethinking SSD Architecture through Network-based Flash ControllersProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589096(1-13)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589096
An MIm SJung DLee S(2022)Your read is our priority in flash storageProceedings of the VLDB Endowment10.14778/3538598.353861215:9(1911-1923)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.14778/3538598.3538612
Lin HSha ZLi JCai ZGerofi BShi YLiao J(2022)DRAM Cache Management with Request Granularity for NAND-based SSDsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545081(1-10)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545081
Park HLee EKim JNoh SGunawi HMa X(2021)Lightweight data lifetime classification using migration counts to improve performance and lifetime of flash-based SSDsProceedings of the 12th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3476886.3477520(25-33)Online publication date: 24-Aug-2021
https://dl.acm.org/doi/10.1145/3476886.3477520
Bonnet PBouganim LKoltsidas IViglas S(2020)System co-design and data management for flash devicesProceedings of the VLDB Endowment10.14778/3402755.34028074:12(1504-1505)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402755.3402807
Kim JLim KJung YLee SMin CNoh SDan TDahlia M(2019)Alleviating garbage collection interference through spatial separation in all flash arraysProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358875(799-812)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358875
Wu CZhang LLi QFu ZZhu WZhang Y(2019)Enabling Flexible Resource Allocation in Mobile Deep Learning SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286535930:2(346-360)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2865359
Chen XLi YZhang T(2019)Reducing Flash Memory Write Traffic by Exploiting a Few MBs of Capacitor-Powered Write Buffer Inside Solid-State Drives (SSDs)IEEE Transactions on Computers10.1109/TC.2018.287168368:3(426-439)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1109/TC.2018.2871683
Yeon JJeong MLee SLee EAgrawal NRangaswami R(2018)RFLUSHProceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189778(201-209)Online publication date: 12-Feb-2018
https://dl.acm.org/doi/10.5555/3189759.3189778
Sun HHuang JQin XXie C(2018)DLSpaceACM Transactions on Embedded Computing Systems10.1145/328474917:6(1-33)Online publication date: 8-Dec-2018
https://dl.acm.org/doi/10.1145/3284749
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten