Research Of Cache Replacement Algorithms For Flash-based Hybrid Storage System

With the fast improvement of flash-based solid state disk(SSD) technology, SSD has been put in a position to diverse storage systems widely. It has strengths of higher performance, lower energy and lower noise than magnetic hard disk drive(HDD). However, due to its relatively high price and low capacity, SSD is widely used in hybrid storage systems in either extending or caching HDD mode.Considering synthetically the characteristics of SSD and HDD, the thesis proposes a performance-effective Regional popularity-Aware Cache replacement algorithm(RAC) to improve the performance of flash-based hybrid storage system. Instead of a single block, the popularity of a region which is constituted by many adjacent disk blocks is recorded and used to determine replacing a bock or not. It is more suitable to apply RAC directly to SSD-based disk cache than traditional cache algorithms for the following reasons. Firstly, temporal locality of second-level cache is much poorer than first-level cache. Secondly, the distribution of I/O accesses to a block is not uniform and crosses at different cycles. Thirdly, accesses to back-end disk exhibit a high degree of spatial locality and popular regions remain constant at different cycles. In addition, the statistics of popular blocks for traditional cache algorithms need a long period of time for computing access frequency, during which there may be frequent and ineffective replacements among popular and unpopular blocks. This not only degrades performance but also leads to more write operations to SSD. In this way of RAC, the spatial locality of disk access is completely leveraged and sequential I/O blocks are gathered in SSD cache. Besides, the process of accumulation of the popularity is also accelerated. Furthermore, it improves hit ratio and reduces the number of unnecessary cache replacement on SSD, prolonging its lifetime.First of all, RAC was implemented and evaluated by many workloads in cachesim, then we implemented a hybrid storage system based on RAC in flashcache and did some system test. Compared to traditional cache algorithms, it improves I/O throughput by up to 52.7% and reduces replacements of SSD up to 98.5%.