Efficient SSD Cache for Cloud Block Storage via Leveraging Block Reuse Distances

Solid State Drives (SSDs) are popularly used for caching in large scale cloud storage systems nowadays. Traditionally, most cache algorithms make replacement upon each miss when cache space is full. However, we observe that in a typical Cloud Block Storage (CBS) system, there is a great percentage o...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2020-11, Vol.31 (11), p.2496-2509
Main Authors: Zhou, Ke, Zhang, Yu, Huang, Ping, Wang, Hua, Ji, Yongguang, Cheng, Bin, Liu, Ying
Format: Article
Language:English
Subjects:
Algorithms
cache algorithm
Caching
Cloud block storage
Cloud computing
Data storage
Distributed databases
Evictions
Indexes
Inserts
Reliability
reuse distance
Routing
Servers
Solid state devices
SSD
Storage systems
Virtual machine monitors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Solid State Drives (SSDs) are popularly used for caching in large scale cloud storage systems nowadays. Traditionally, most cache algorithms make replacement upon each miss when cache space is full. However, we observe that in a typical Cloud Block Storage (CBS) system, 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 article, 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. LEA mainly employs two lists, Lazy Eviction List (LEL) and Block Identity List (BIL), which keep track of two types of victim blocks respectively based on their cache duration when replacements occur, to improve cache efficiency. When a cache miss happens, if the victim 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 greatly reduces the number of SSD writes.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2020.2994075