On Fast Searching of Log Area in FAST FTL using Counting Bloom Filters
Woon-Hak Kang, Sangwon Lee · 2011
NAND flash memory storage devices has been widely adopted in many applications, due to its good characteristics. Unlike hard disk drive, however, flash memory does not allow in-place update so that a block should be erased before a page of the block is overwritten. Several FTL algorithms have been proposed during the past decade, among them, FAST scheme is popular for its random write performance because of its full associativity between logical data pages and physical flash pages in log blocks (called log area). However, on every read/write/merge operations, FAST should check whether the most recent version of a page exists in log blocks. But, even though the mapping table resides in SRAM, this full scan of the mapping table for checking the existence of the up-to-date page in the log block is not any more trivial as the size of flash-based storage grows exponentially and thus the number of log blocks should accordingly increase for reasonable random write performance. As a scalable search scheme for log area, this paper applies the counting bloom filters to efficiently check whether the recent copy of a page exist in the log area of FAST scheme. To be specific, with a very small footprint of memory, which is very common in resource-limited flash memory controllers, the counting bloom filter can quickly determine a recent version of the given data page does not reside in log area when it does not have its recent copy in log area. The performance evaluation shows that our scheme can improve the search cost of log area by more than 80% with only exploit 30% of memory compare to bitmap scheme.