Sampling-ba sed garbage collection metadata management scheme for flash-based storage

Biplob Debnath, Srinivasan Krishnan, Weijun Xiao, David J. Lilja, David H.C. Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Existing garbage collection algorithms for the flash-based storage use score-based heuristics to select victim blocks for reclaiming free space and wear leveling. The score for a block is estimated using metadata information such as age, block utilization, and erase count. To quickly find a victim block, these algorithms maintain a priority queue in the SRAM of the storage controller. This priority queue takes O(K) space, where K stands for flash storage capacity in total number of blocks. As the flash capacity scales to larger size, K also scales to larger value. However, due to higher price per byte, SRAM will not scale proportionately. In this case, due to SRAM scarcity, it will be challenging to implement a larger priority queue in the limited SRAM of a large-capacity flash storage. In addition to space issue, with any update in the metadata information, the priority queue needs to be continuously updated, which takes O(lg(K)) operations. This computation overhead also increases with the increase of flash capacity. In this paper, we have taken a novel approach to solve the garbage collection metadata management problem of a large-capacity flash storage. We propose a sampling-based approach to approximate existing garbage collection algorithms in the limited SRAM space. Since these algorithms are heuristic-based, our sampling-based algorithm will perform as good as unsampled (original) algorithm, if we choose good samples to make garbage collection decisions. We propose a very simple policy to choose samples. Our experimental results show that small number of samples are good enough to emulate existing garbage collection algorithms.

Original languageEnglish (US)
Title of host publication2011 IEEE 27th Symposium on Mass Storage Systems and Technologies, MSST 2011
DOIs
StatePublished - Aug 3 2011
Event2011 IEEE 27th Symposium on Mass Storage Systems and Technologies, MSST 2011 - Denver, CO, United States
Duration: May 23 2011May 27 2011

Publication series

NameIEEE Symposium on Mass Storage Systems and Technologies
ISSN (Print)2160-1968

Other

Other2011 IEEE 27th Symposium on Mass Storage Systems and Technologies, MSST 2011
Country/TerritoryUnited States
CityDenver, CO
Period5/23/115/27/11

Fingerprint

Dive into the research topics of 'Sampling-ba sed garbage collection metadata management scheme for flash-based storage'. Together they form a unique fingerprint.

Cite this