R&D: Advanced Adaptive Least Recently Used Buffer Management Algorithm for SSD

IEEE Access has published an article written by Yingbiao Yao, Xiaochong Kong, Jie Zhou, Xiaorong Xu, Wei Feng, and Zhaoting Liu, School of Communication Engineering, Hangzhou Dianzi University, Hangzhou, China.

Structure of AALRU consists of two parts: the data page buffer (a read buffer and a write buffer) and the adaptive threshold adjustment scheme. The adaptive threshold adjustment scheme includes the read-write buffer ratio threshold τ and the page padding trigger threshold.
Click to enlarge

Abstract: “The traditional solid-state drive buffer management algorithm generally adopts fixed structures and parameters, leading to their poor adaptability. For example, after the underlying flash translation layer (FTL) or the upper workload is changed, the traditional algorithm’s performance fluctuates significantly. Focusing on this problem, based on the cross-layer aware method, we propose an Advanced Adaptive Least Recently Used buffer management algorithm (AALRU). The core idea of the AALRU is that by sensing the characteristics of the upper workload and the status of the underlying FTL, the AALRU adaptively adjusts its structure, parameters, and write-back strategy to optimize the buffer’s performance. First, the AALRU divides the buffer into two parts: read buffer and write buffer, and their proportion is adjusted by sensing the read-write characteristics of the workload and the underlying read-write latency. Second, the AALRU employs different granularities to manage the buffer. On one hand, for data loading and migrating, the AALRU adopts page-level granularity, which can avoid the problem of hot and cold data page entanglement in block management, and thus improve the buffer hit ratio. On the other hand, for data writing back to the FTL, the AALRU adopts block-level granularity, which can enhance the continuity of write requests and thus reduce the underlying FTL’s garbage collection overhead. Finally, when the clustered data are written back, by sensing the underlying FTL’s garbage collection status, the AALRU adaptively adjusts the page-padding trigger threshold to reconstruct the continuity of the write-back data, which can mitigate the underlying FTL’s garbage collection overhead. The experimental results show that the AALRU has the best adaptability to different FTLs and test workloads, and it can achieve optimal or near-optimal results.“