LEA: A Lazy Eviction Algorithm for SSD Cache in Cloud Block Storage

Solid State Drives (SSDs) are popularly used for caching in large scale cloud storage systems nowadays. Traditionally, most cache algorithms make replacement at each miss when cache space is full. However, we observe that in a typical Cloud Block Storage (CBS), there is a great percentage of blocks with large reuse distances, which would result in large number of blocks being evicted out of the cache before they ever have a chance to be referenced while they are cached, significantly jeopardizing the cache efficiency. In this paper, we propose LEA, Lazy Eviction cache Algorithm, for cloud block storage to efficiently remedy the cache inefficiencies caused by cache blocks with large reuse distances. Specifically, LEA uses two lists, Lazy Eviction List (LEL) and Block Identity List (BIL). When a cache miss happens, if the candidate evicted-block has not resided in cache for longer than its reuse distance, LEA inserts the missed block identity into BIL. Otherwise, it inserts the missed block entry into LEL. We have evaluated LEA by using IO traces collected from Tencent, one of the largest network service providers in the world, and several open source traces. Experimental results show that LEA not only outperforms most of the state-of-the-art cache algorithms in hit ratio, but also reduces the number of SSD writes greatly.