``Cost-aware caching algorithms for distributed storage servers"  
 
Shuang Liang, Ke Chen, Song Jiang, and Xiaodong Zhang

Proceedings of the 21st International Symposium on Distributed Computing 
(DISC'07), Lemesos, Cyprus, September 24-26, 2007.  

Abstract

We study replacement algorithms for non-uniform access caches that are used 
in distributed storage systems. Considering access latencies as major costs 
of data management in such a system, we show that the total cost of any 
replacement algorithm is bounded by the total costs of evicted blocks plus 
the total cost of the optimal off-line algorithm (OPT). We propose two 
off-line heuristics: MIN-d and MIN-cod, as well as an on-line algorithm: 
HD-cod, which can berun efficiently and perform well at the same time. 

Our simulation results with Storage Performance council(SPC)'s storage 
server traces show that: (1) for off-line workloads, MIN-cod performs 
as well as OPT in some cases, all is at most three times worse in all 
test case; (2) for on-line workloads, HD-cod performs closely to the 
best algorithms in all cases, and is the single algorithm that performs 
well in all test cases, including the optimal on-line algorithm (Landlord). 
Our study suggests that the essential issue to be considered be the trade-off 
between the costs of victim blocks and the total number of evictions in 
order to effectively optimize both efficiency and performance of distributed 
storage cache replacement algorithms. 
 

Back to the HPCS Main Page at the Ohio State University.