Optimal File-Bundle Caching Algorithms for Data-Grids

ABSTRACT

The file-bundle caching problem arises frequently in scientific applications where jobs process several files concurrently. Consider a host system in a data-grid that maintains a disk cache for servicing jobs of file requests where a job is serviced only if all its requested files are present in the disk cache. Files must now be admitted into the cache and replaced in sets of file-bundles. We show that traditional caching algorithms based on file popularity measures do not perform well since they may hold in cache non-relevant combinations of files. We present and analyze a new caching algorithm for maximizing the throughput of jobs and minimizing data replacement costs at such data-grid hosts. We tested the new algorithm using a disk cache simulation model under a wide range of conditions of file request distributions, varying cache size, file size distribution, etc. The results show significant improvement over traditional caching algorithms.

REFERENCES

• 1: Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
• 2: [2] A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets. J. Network and Computer Applications, 23(3):187- 200, 2000.
• 3: [3] ESG:. The Earth System Grid, http://www.scd.ucar.edu/css/esg/.
• 4: [4] U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001.
• 5: [5] U. Hahn, W. Dilling, and D. Kaletta. Adaptive replacement algorithm for disk caches in hsm systems. In 16 Int'l. Symp on Mass Storage Syst., pages 128-140, San Diego, California, Mar. 15-18 1999.
• 6: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 7: Ekow Otoo , Doron Rotem , Arie Shoshani, Impact of Admission and Cache Replacement Policies on Response Times of Jobs on Data Grids, Proceedings of the International Workshop on Challenges of Large Applications in Distributed Environments, p.113, June 21-21, 2003
• 8: Ekow Otoo , Arie Shoshani, Accurate Modeling of Cache Replacement Policies in a Data Grid, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.10, April 07-10, 2003
• 9: M. Tamer Özsu , Patrick Valduriez, Principles of distributed database systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 10: [10] PPDG:. The Particle Physics Data Grid, http://www.ppdg.net/.
• 11: Arcot Rajasekar , Michael Wan , Reagan Moore, MySRB & SRB: Components of a Data Grid, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p.301, July 24-26, 2002
• 12: [12] A. Shoshani, A. Sim, and J. Gu. Storage resource managers: Middleware components for grid storage. In 10th NASA Goddard Conference on Mass Storage Syst. and Tech., Apr. 15-18 2002.
• 13: Mitchell D. Theys , Howard Jay Siegel , Noah B. Beck , Min Ta , n , Inc. Cisco Systems , Michael Jurczyk, A Mathematical Model, Heuristic, and Simulation Study for a Basic Data Staging Problem in a Heterogeneous Networking Environment, Proceedings of the Seventh Heterogeneous Computing Workshop, p.115, March 30-30, 1998
• 14: [14] J. Wang. A survey of web caching schemes for the internet. In ACM SIGCOMM'99, Cambridge, Massachusetts, Aug. 1999.
• 15: Kesheng Wu , Wendy Koegler , Jacqueline Chen , Arie Shoshani, Using bitmap index for interactive exploration of large datasets, Proceedings of the 15th international conference on Scientific and statistical database management, p.65-74, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214955]
• 16: Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States