Bypass caching: Making scientific databases good network citizens

Scientific database federations are geographically dis-tributed and network bound. Thus, they could benefit from proxy caching. However, existing caching tech-niques are not suitable for their workloads, which compare and join large data sets. Existing techniques reduce paral-lelism by conducting distributed queries in a single cache and lose the data reduction benefits of performing selec-tions at each database. We develop the bypass-yield for-mulation of caching, which reduces network traffic in wide-area database federations, while preserving paral-lelism and data reduction. Bypass-yield caching is altruis-tic; caches minimize the overall network traffic generated by the federation, rather than focusing on local perfor-mance. We present an adaptive, workload-driven algo-rithm for managing a bypass-yield cache. We also develop on-line algorithms that make no assumptions about work-load: a k-competitive deterministic algorithm and a ran-domized algorithm with minimal space complexity. We verify the efficacy of bypass-yield caching by running work-load traces collected from the Sloan Digital Sky Survey through a prototype implementation. 1