NAND flash memory is the ubiquitous non-volatile memory today. It is widely utilized for secondary storage of embedded systems. It is also starting to replace magnetic hard disks of general-purpose computing systems in the form of solid state drives (SSDs).
The management of flash memory is performed by a firmware called the flash translation layer (FTL). The FTL provides the traditional block-device interfaces to file systems, and is responsible for all functions of flash management. The performance of flash is most influenced by two characteristics of NAND flash: its units of access and out-of- place updating. Read and write operations of NAND flash are conducted in the unit of a page, which is 2KB or more.
Based on the concepts of page and block, there are two basic ways to perform this translation, namely, page-level mapping and block-level mapping. Read and write requests are serviced with the aid of an internal SRAM, DRAM, or non-volatile RAM cache that is equipped in flash devices.
The byte-addressable RAM cache plays an important role in flash storage system. NAND flash can take advantage of RAM’s access flexibility by maintaining entries of the address mapping table. All the mapping entries may be grouped and stored in the translation pages of flash memory (as opposed to data pages that store real data).
On the other hand, the access latency of RAM is much shorter than NAND flash. So caching mapping information or data in RAM can significantly improve the overall performance. Many schemes have been proposed on how to utilize the RAM cache. The emphasis has either been on keeping information for address mapping, or on buffering recently accessed data pages.
Recently, there are proposals on how to jointly use the RAM space for both mapping caching and data buffering. In this paper, we propose a novel RAM management scheme that is simple but efficient. We call it TreeFTL. The main ideas of TreeFTL are as follows:
1) TreeFTL does not cache single mapping entries like previous schemes. It maintains translation pages and data pages in RAM through a tree-like structure.
2) A lightweight strategy is devised for LRU eviction. It se- lects victims at a coarse granularity, and our experiments show that the gain it brings in is significant.
TreeFTL achieves the dynamic partitioning for address mapping and data buffering inherently using the tree structure. TreeFTL maintains a three-level tree structure in RAM. The first level and second level are used for mapping, while the third level is for caching data pages. TreeFTL dynamically adapts to the runtime workload by adjusting the tree structure.
One of TreeFTL’s key features is its lightweight LRU victim selection which can significantly reduce spatial and temporal overheads. The victim selection is done at a coarse level, but this trade-off in precision results in the significant reduction in processing time. Experimental results show that TreeFTL can outperform previous schemes on various workloads.
Experiments show that compared to the two latest schemes for RAM management in flash storage system, TreeFTL can reduce service time by 46.6% and 49.0% on average, respectively, with a 64MB RAM cache. As for the future work, we plan to integrate TreeFTL with the garbage collection module of flash management for higher performance.
To read this external content in full, download the complete paper from the online archives at the National University of Singapore.