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.