HaParallel：一种基于命中率感知的并行式激进驱逐缓存管理算法，适用于固态硬盘（SSDs）

《ACM Transactions on Storage》：HaParallel: Hit Ratio-Aware Parallel Aggressive Eviction Cache Management Algorithm for SSDs

SSD内置缓存管理研究提出主动驱逐策略、多级链表组织缓存数据及基于网络拥塞控制的命中率感知单元，实验显示平均响应时间比传统算法分别降低19.7%、19.4%、29.9%。

　　

摘要

固态硬盘（SSD）可以分为两种类型：带有内置缓存的和没有内置缓存的。在性能方面，带有缓存的SSD相比没有缓存的SSD具有显著的优势。本文的主要关注点是SSD中内置缓存的管理。通过大量先前的研究，我们发现对于大多数工作负载来说，缓存命中率仍然相对较低。首先，基于这一观察结果，我们采用了一种积极的驱逐策略，这种策略与传统基于按需驱逐的算法不同。其次，考虑到缓存数据的时间局部性和并行性，我们引入了多层链表来组织缓存数据。这样，可以通过较小的计算负载来提高触发高级命令的概率。最后，借鉴计算机网络中的拥塞控制算法，我们设计了一个能够感知缓存命中率的单元。该单元可以根据自身的状态采用不同程度的积极驱逐策略。目的是在限制积极驱逐策略对命中率影响的同时，最大化高级命令的执行频率。我们在实际工作负载上的实验模拟显示，与LRU、VBBMS和Req-block相比，我们的方法平均响应时间有了显著提升，分别减少了19.7%、19.4%和29.9%。