Best-Effort Cache Synchronization with Source Cooperation
Chris Olston and Jennifer Widom
Abstract
In environments where exact synchronization between source data
objects and cached copies is not achievable due to bandwidth or other
resource constraints, stale (out-of-date) copies are permitted.
It is desirable to minimize the overall divergence between
source objects and cached copies by selectively refreshing modified
objects. We call the online process of selecting which objects to
refresh in order to minimize divergence best-effort
synchronization. In most approaches to best-effort synchronization,
the cache coordinates the process and selects objects to refresh. In
this paper, we propose a best-effort synchronization scheduling policy
that exploits cooperation between data sources and the cache. We also
propose an implementation of our policy that incurs low communication
overhead even in environments with very large numbers of sources. Our
algorithm is adaptive to wide fluctuations in available resources and
data update rates. Through experimental simulation over synthetic and
real-world data, we demonstrate the effectiveness of our algorithm,
and we quantify the significant decrease in divergence achievable with
source cooperation.
Conference Paper (SIGMOD 2002): [PS], [PDF]. Citation: [BibTeX]
Extended Version: [PS], [PDF]
Algorithm Demo: [Java]
TRAPP Project Web Page: [HTML]