HaParallel: Hit Ratio-Aware Parallel Aggressive Eviction Cache Management Algorithm for SSDs

Solid-state drives (SSDs) can be classified into two types: with and without built-in cache. In terms of performance, SSDs featuring cache exhibit a substantial performance advantage over their non-cache counterparts. The main focus of this paper is the management of built-in cache in SSDs. From a large number of previous studies, we observe that cache hit ratios remain relatively modest for the majority of workloads. First, based on this observation, we adopt an aggressive eviction policy, diverging from traditional eviction algorithms that follow an on-demand eviction policy. Next, considering the temporal locality and parallelism of cached data, we introduce multi-level linked lists to organize cached data. In this way, a smaller computational load can be used to increase the probability of triggering advanced commands. Finally, drawing inspiration from congestion control algorithm in computer networking, we design a cache hit ratio-aware unit. This unit can employ varying degrees of aggressive eviction policies based on its own state. The aim is to maximize the execution of advanced commands while limiting the impact of the aggressive eviction policy on the hit ratio. Our experimental simulations on real workloads show a substantial improvement in average response time compared to LRU, VBBMS, and Req-block, with our method achieving reductions of 19.7%, 19.4%, and 29.9%, respectively.