Garbage collection of multi-version indexed data on flash memory

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.