An Adaptive Read-Write Partitioning Flash Translation Layer Algorithm

Yingbiao Yao, Mingbo Yan, Xiaochong Kong, Xiaorong Xu, Wei Feng, Xin XuIEEE Access 2019 · DOI

Abstract

The classic demand-based flash translation layer (DFTL) algorithm is well-known for solving the contradiction between mapping flexibility and mapping cache size by dynamically loading mapping entries. However, DFTL fails to utilize the spatial locality and hot-cold characteristics of requests and employs an inefficient mapping entry eviction scheme. This paper proposes an adaptive read-write partitioning flash translation layer algorithm (ARWFTL). ARWFTL divides the cache mapping table (CMT) into read and write partitions that adaptively resize based on workload characteristics and flash latency. It introduces a priority eviction window and a clustering-based write-back scheme to minimize flash writes, alongside a hot data window to separate hot and cold data. Experimental results show that ARWFTL reduces translation page write counts by 92.8% and average response time by 31.4% compared to DFTL.

Introduction

In Solid-State Drives (SSDs), the Flash Translation Layer (FTL) manages the mapping between logical and physical addresses. As SSD capacities grow, mapping tables exceed RAM limits, necessitating demand-based loading (DFTL). However, standard DFTL suffers from three major flaws: inefficient eviction of "dirty" entries, workload blindness (treating reads and writes identically), and "hot-cold entanglement," where frequently updated data is mixed with static data, complicating garbage collection.

The ARWFTL Architecture

The proposed ARWFTL algorithm addresses these inefficiencies through three primary mechanisms:

  1. Adaptive Partitioning: The Cache Mapping Table (CMT) is split into a Read CMT (R-CMT) and a Write CMT (W-CMT). The system dynamically adjusts the size of these partitions based on the "unit yield"—a metric balancing hit rates against the latency costs of flash operations.
  2. CFC-LRU Eviction: The "Clean entry First and Clustering-based LRU" strategy prioritizes evicting clean entries. When dirty entries must be evicted, the system clusters multiple entries from the same translation page into a single flash write, maximizing efficiency.
  3. Hot Data Windowing: The head of the W-CMT serves as a "hot data window." Data identified here is stored in separate physical blocks, preventing entanglement with cold data and streamlining future garbage collection.
Architecture of the ARWFTL algorithm showing read/write partitioning and eviction strategies.

Experimental Evaluation

The researchers evaluated ARWFTL using the FlashSim simulator across four real-world traces: Fin1, Fin2, Sys, and PC. These workloads represent a variety of access patterns, from write-heavy financial transactions to read-heavy office usage.

Read request ratios for Fin1 and Fin2 workloads, highlighting the need for adaptive partitioning.

As shown in the workload analysis, the ratio of read requests varies significantly over time and between different applications, justifying the need for an adaptive partitioning approach that can react to shifting demands in real-time.

Key Results and Insights

Compared to the baseline DFTL, ARWFTL achieved massive improvements across all critical metrics:

  • Translation Page Writes: Reduced by 92.8%, directly extending the physical life of the NAND flash.
  • Average Response Time: Improved by 31.4%, leading to a significantly snappier user experience.
  • Garbage Collection Efficiency: Valid page migrations dropped by 47.7%, and block erase counts fell by 31.7%.

The core insight of this research is treating the cache as an asymmetric resource. Since flash writes are the primary bottleneck for both performance and longevity, prioritizing write optimization within the cache yields the highest returns.

Conclusion

ARWFTL significantly enhances SSD performance and lifespan by intelligently managing mapping cache partitions and data placement. While the current hot-data recognition is intentionally simple to minimize CPU overhead on SSD controllers, future work could explore more granular data temperature tiers or integration with modern multi-stream SSD host hints.

Summary updated

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.
BibTeX
@inproceedings{yao2019adaptive,
  author = {Yingbiao Yao and Mingbo Yan and Xiaochong Kong and Xiaorong Xu and Wei Feng and Xin Xu},
  title = {{An Adaptive Read-Write Partitioning Flash Translation Layer Algorithm}},
  booktitle = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2958609},
}
Figure