A comparative evaluation of buffer replacement algorithms LIRS-WSR and AD-LRU for flash memory based systems

Abstract

Flash memory has characteristics of asymmetric I/O latencies for read, write and erase operations and out-of-place update. Thus, buffering policy for flash based systems has to consider these properties to improve the overall performance. Existing buffer replacement algorithms such as LRU, LIRS, ARC etc do not deal with differing I/O latency of flash memory. Therefore, these algorithms have been revised to make them suitable for buffering policy for flash based systems. Among different flash aware buffer replacement algorithms LIRS-WSR and AD-LRU are two new buffer replacement policies that can be suitable for flash based systems. LIRS-WSR enhances LIRS by reordering the writes of not-cold-dirty pages from the buffer cache to flash storage to focus on the reduction of number of write/erase operations as well as preventing serious degradation of buffer hit ratio. AD-LRU also focuses on improving overall performance of flash based systems by reducing number of write /erase operations and by retaining high buffer hit ratio. We evaluate these two different approaches with same objectives of improving buffering policy for flash based systems by using trace driven simulation. When workload has high reference locality, AD-LRU has significantly superior performance than LIRS-WSR in terms of both hit rate and write count. AD-LRU has higher hit rate up to 22% and minimizes write count up to 40% in comparison to LIRS-WSR. This is because of AD-LRU‟s good adaptive technique to handle changes in reference patterns. For uniformly distributed workloads, the difference in hit rates and write count of AD-LRU and LIRS-WSR is comparatively small. AD-LRU outperforms LIRS-WSR by increasing hit rate up to 5% and decreasing write count up to 3% in comparison to LIRS-WSR in its worst case.

Keywords: Flash memory, Buffer Replacement Algorithm, LIRS, LIRS-WSR, AD-LRU, Hit Rate, Write Count