An Adaptive Read-Write Partitioning Flash Translation Layer Algorithm

Abstract

The classic demand-based flash translation layer (DFTL) algorithm is well-known since it can solve the contradiction between mapping flexibility and the size of mapping cache by dynamically loading mapping entries. However, DFTL failed to utilize the spatial locality and hot-cold characteristics of the request and had an inefficient mapping entry eviction scheme. This paper proposes an adaptive read-write partitioning flash translation layer algorithm (ARWFTL). First, the cache mapping table (CMT) is divided into the read CMT and the write CMT. The size of the two can be adaptively adjusted by sensing the characteristics of the upper workload and the read-write latency of the underlying flash page. Second, a priority eviction window is set at the tail of the write CMT to evict the clean mapping entry firstly. When there is no clean mapping entry in the priority eviction window, the tail mapping entry and other mapping entries that belong to the same translation page are clustered to write back into the translation page. Then, other written back mapping entries are set to be clean and the tail mapping entry is evicted. Third, a hot data window is set at the head of the write CMT to recognize the hot and cold data of write requests. Then, the hot and cold data are stored in different data blocks of flash to avoid hot and cold data entanglement and reduce valid page migrations in garbage collection. Experimental results show that, compared with DFTL, ARWFTL can reduce the translation page write counts, the valid page migration counts, the block erase counts, and the average response time by 92.8%, 47.7%, 31.7%, and 31.4%, respectively. In addition, ARWFTL is also superior to the other recent DFTL-based improved algorithms, and even exceeds the pure page-level FTL in some indicators.

Keywords

• Solid-state drive
• flash translation layer
• adaptive read-write partition
• cache mapping table