TR-07-10.pdf

``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.