Garbage collection of multi-version indexed data on flash memory
Authors: 
Kam-Yiu Lam, Chun Jiang Zhu, Yuan-Hao Chang, 
Jen-Wei Hsieh, Po-Chun Huang, Chung Keung Poon, Jiantao WangAuthors Info & Claims
Pages 630 - 643
Abstract
Maintaining a multi-version index on flash memory could generate a lot of updates and invalid pages. It is important to have an efficient garbage collection mechanism to ensure the flash memory has sufficient number of free blocks for storing new data versions and their index structures. In this paper, we study the important performance issues in using the purging-range query to reclaim the blocks, which are storing old data versions and invalid index entries, to be free blocks. To reduce the cost for processing the purging-range query, we propose the physical block labeling (PBL) scheme to provide a better estimation on the purging version number to be used for purging old data versions. To further enhance the performance of the garbage collection process, and at the same time to maximize the deadspans of data versions and balance the wear levels of the blocks, we propose two schemes called, the sequential placement (SQ) and frequency-based placement (FBP), for placing new data versions into free pages. As illustrated in the performance studies, both SQ and FBP can effectively balance the wear levels of the blocks. The deadspans of data versions are longer under FBP than both SQ and RR, and the page reallocation cost is also lower under FBP especially when the size of flash memory allocated for the database is limited. The experimental results also illustrate that PBL can effectively minimize the number of invocations of the purging-range query to be one to reclaim the required number of blocks in each garbage collection.
References
[1]
YAFFS Specification, Technical Report, Aleph One Limited, 2001.
[2]
Samsung Elec., 256M x 8 Bit NAND Flash Memory(K9F2G08UXA), 2006. <http://arm9download.cncncn.com/datasheet/k9f2g08x0arev13.pdf>
[3]
D. Agrawal, D. Ganesan, R. Sitaraman, Y. Diao, S. Singh, Lazy-adaptive tree: an optimized index structure for flash devices, Proc. VLDB Endowment, 2 (2009) 361-372.
[4]
J. Ahn, D. Kang, D. Jung, J. Kim, S. Maeng, µ ¿ -tree: an ordered index structure for NAND flash memory with adaptive page layout scheme, IEEE Transact. Comput., 62 (2013) 784-797.
[5]
A. Ban. Flash file system. M-Systems, 1995. US Patent 5,404,485.
[6]
B. Becker, S. Gschwind, T. Ohler, B. Seeger, P. Widmayer, An asymptotically optimal multiversion B-tree, VLDB J., 5 (1996) 264-275.
[7]
L. Biveinis, S. Šaltenis, C.S. Jensen. Main-memory operation buffering for efficient R-tree update, in: VLDB, 2007, pp. 591-602.
[8]
L.-P. Chang, On efficient wear leveling for large-scale flash-memory storage systems, in: Proceedings of the ACM Symposium on Applied Computing, 2007, pp. 1126-1130.
[9]
L.-P. Chang, T.-W. Kuo, Efficient management for large-scale flash-memory storage systems with resource conservation, ACM Transact. Storage, 1 (2005) 381-418.
[10]
M.-L. Chiang, R.-C. Chang, Cleaning policies in mobile computers using flash memory, J. Syst. Softw., 48 (1999) 213-231.
[11]
H. Cho, D. Shin, Y. Eom, KAST: K-Associative Sector Translation for NAND flash memory in real-time systems, in: Design, Automation, Test in Europe, 2009, pp. 507-512.
[12]
B. Debnath, S. Sengupta, J. Li, FlashStore: high throughput persistent key-value store, Proc. VLDB Endowment, 3 (2010) 1414-1425.
[13]
E. Gal, S. Toledo, Algorithms and data structures for flash memories, ACM Comput. Surv., 37 (2005) 138-163.
[14]
A. Gupta, Y. Kim, B. Urgaonkar, DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings, in: ASPLOS, 2009, pp. 229-240.
[15]
L. Han, Y. Ryu, K. Yim, CATA: a garbage collection scheme for flash memory file systems, Ubiquitous Intell. Comput., 4159 (2006) 103-112.
[16]
D. Kang, D. Jung, J. Kang, J. Kim, µ -tree: an ordered index structure for NAND Flash Memory, in: Proceedings of the International Conference on Embedded Software, 2007, pp. 144-153.
[17]
A. Kawaguchi, S. Nishioka, H. Motoda, A flash memory based file system, in: Proceedings of the USENIX Technical Conference, 1995, pp. 155-164.
[18]
J. Kim, J. Kim, S. Noh, S. Min, Y. Cho, A space-efficient flash translation layer for CompactFlash systems, IEEE Transact. Consum. Electron., 48 (2002) 366-375.
[19]
O. Kwon, K. Koh, J. Lee, H. Bahn, FeGC: an efficient garbage collection scheme for flash memory based storage systems, J. Syst. Softw., 84 (2011) 1507-1523.
[20]
E. Lee, S. Seshia. Introduction to Embedded Systems-A Cyber-Physical Systems Approach, 2011.
[21]
E.-M. Lee, S.-W. Lee, S. Park, Optimizing index scans on flash memory SSDs, SIGMOD Record, 40 (2011) 5-10.
[22]
K. Lee, H. Kim, K. Woo, Y. Chung, M. Kim, Design and implementation of MLC NAND flash-based DBMS for mobile devices, J. Syst. Softw., 82 (2009) 1447-1458.
[23]
S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Lee, S. Park, H.-J. Song, A log buffer-based flash translation layer using fully-associative sector translation, IEEE Transact. Embedded Comput. Syst., 6 (2007).
[24]
H. Li, D. Liang, L. Xie, G. Zhang, K. Ramamritham. TL-tree: flash-optimized storage for time-series sensing data on sensor platforms, in: Proceedings of the Annual ACM Symposium on Applied Computing, 2012, pp. 1565-1572.
[25]
M. Murugan, D. Du. Rejuvenator: A static wear leveling algorithm for NAND flash memory with minimized overhead, in: Proceedings of the IEEE Symposium on Mass Storage Systems and Technologies, 2011, pp. 1-12.
[26]
G. Na, S. Lee, B. Moon. Dynamic in-page logging for flash-aware B-tree index, in: Proceedings of the ACM Conference on Information and Knowledge Management, 2009, pp. 1485-1488.
[27]
D. Naranjo-Hernandez, L. Roa, J. Reina-Tosina, M. Estudillo-Valderrama, SoM: a smart sensor for human activity monitoring and assisted healthy ageing, IEEE Transact. Biomed. Eng., 59 (2012) 3177-3184.
[28]
S. Nath, P. Gibbons. Online maintenance of very large random samples on flash storage, in: VLDB, 2008, pp. 970-983.
[29]
A. Nori, Mobile and embedded databases, IEEE Data Eng. Bull., 30 (2007) 3-12.
[30]
Z. Qin, Y. Wang, D. Liu, Z. Shao, Y. Guan. MNFTL: an efficient flash translation layer for MLC NAND flash memory storage systems, in: IEEE/ACM Design Automation Conference, 2011, pp. 17-22.
[31]
K. Ramamritham, Real-time databases, Distrib. Parallel Databases, 1 (1993) 199-266.
[32]
M. Rosenblum, J.K. Ousterhout, The design and implementation of a log-structured file system, ACM Transact. Comput. Syst., 10 (1992) 26-52.
[33]
Y.N. Silva, X. Xiong, W.G. Aref, The RUM-tree: supporting frequent updates in R-trees using memos, VLDB J., 18 (2009) 719-738.
[34]
J. Wang, K.-Y. Lam, Y.-H. Chang, J.-W. Hsieh, P.-C. Huang. Block-based Multi-version B+-Tree for Flash-based Embedded Database Systems. To appear in IEEE Transactions Computers, 2014.
[35]
C.-H. Wu, T.-W. Kuo. An adaptive two-level management for the flash translation layer in embedded systems, in: IEEE/ACM International Conference on Computer-Aided Design, 2006, pp. 601-606.
[36]
G. Xu, Y. Liu, X. Zhang, L.M. Garbage, Collection policy to improve durability for flash memory, IEEE Transact. Consum. Electron., 58 (2012) 1232-1236.
[37]
S. Yin, P. Pucheral, X. Meng. A sequential indexing scheme for flash-based embedded systems, in: Proceedings of International Conference on Extending Database Technology, 2009, pp. 588-599.
[38]
D. Zeinalipour-Yazti, S. Lin, V. Kalogeraki, D. Gunopulos, W. Najjar. Microhash: an efficient index structure for flash-based sensor devices, in: Proceedings of the USENIX Conference on File and Storage Technologies, 2005, pp. 31-44.
Recommendations
Garbage collection for multi-version index on flash memory
DATE '14: Proceedings of the conference on Design, Automation & Test in EuropeIn this paper, we study the important performance issues in using the purging-range query to reclaim old data versions to be free blocks in a flash-based multi-version database. To reduce the overheads for using the purging-range query in garbage ...
An efficient garbage collection policy for flash memory based swap systems
ICCSA'07: Proceedings of the 2007 international conference on Computational science and its applications - Volume Part IMobile computing devices use flash memory as a secondary storage because it has many attractive features such as small size, fast access speeds, shock resistance, and light weight. Mobile computing devices exploit a swap system to extend a limited main ...
An efficient garbage collection for flash memory-based virtual memory systems
As more consumer electronics adopt monolithic kernels, NAND flash memory is used for the swap space in virtual memory systems. While flash memory has the advantages of low-power consumption, shock-resistance and non-volatility, it requires garbage ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier North-Holland, Inc.
United States
Publication History
Published: 01 November 2014
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025