SPACE: A lightweight collaborative caching for clusters | Peer-to-Peer Networking and Applications Skip to main content

Advertisement

Springer Nature Link
Log in

SPACE: A lightweight collaborative caching for clusters

  • Published:
Peer-to-Peer Networking and Applications Aims and scope Submit manuscript

Abstract

In this paper, we introduce Systematic P2P Aided Cache Enhancement or SPACE, a new collaboration scheme among clients in a computer cluster of a high performance computing facility to share their caches with each other. The collaboration is achieved in a distributed manner, and is designed based on peer-to-peer computing model. The objective is to provide (1) a decentralized solution, and (2) a near optimal performance with reasonably low overhead. Simulation results are given to demonstrate the performance of the proposed scheme. In addition, the results show that SPACE evenly distributes work loads among participators, and entirely eliminates any requirement of a central cache manager.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. In the rest of the paper, we use the terms client and peer interchangeably.

  2. Precedence is measured according to an identification which may be the peer ID, IP address, etc.

  3. g(P) and f(P) are used for gossip and fetch events at peer P, and a ↦b means a happens before b.

  4. The true/false status may be represented with a single bit.

  5. Refer to [16] for details about the math behind Bloom filters.

  6. Note that total percentage of requests served at the remote peers and at the server denotes the local cache miss ratio. The percentage of read requests served at the server denotes the pseudo global cache miss ratio.

References

  1. Adve SV, Gharachorloo K (1996) Shared memory consistency models: a tutorial. Comput 29(12):66–76

    Article  Google Scholar 

  2. Akon M, Goswami D, Li HF, Shen XS, Singh A (2008) A novel software-built parallel machines and their interconnections. J Interconnection Netw 9:1–29

    Article  Google Scholar 

  3. Akon MM, Goswami D, Li HF (2004) SuperPAS: a parallel architectural skeleton model supporting extensibility and skeleton composition. In: International symposium on parallel and distributed processing and applications, pp 985–996

  4. Akon MM, Goswami D, Li HF (2005) A model for designing and implementing parallel applications using extensible architectural skeletons. In: International conference on parallel computing technologies, pp 367–380

  5. Akon MM, Singh A, Goswami D, Li HF (2005) Extensible parallel architectural skeletons. In: IEEE international conference on high performance computing, pp 290–301

  6. Akon MM, Singh A, Shen X, Goswami D, Li HF (2005) Developing high-performance parallel applications using EPAS. In: International symposium on parallel and distributed processing and applications, pp 431–441

  7. Bansal S, Modha D (2004) CAR: clock with adaptive replacement. In: USENIX conference on file and storage technologies, pp 187–200

  8. Bowman CM, Danzig PB, Hardy DR, Manber U, Schwartz MF (1995) The Harvest information discovery and access system. Comput Netw ISDN Syst 28(1–2):119–125

    Article  Google Scholar 

  9. Breslau L, Cao P, Fan L, Phillips G, Shenker S (1999) Web caching and zipf-like distributions: evidence and implications. In: INFOCOM, pp 126–134

  10. Cao P, Irani S (1997) Cost-aware WWW proxy caching algorithms. In: Usenix symposium on internet technologies and systems, pp 193–206

  11. Chen Y, Dehne F, Eavis T, Rau-Chapli A (2004) Parallel ROLAP data cube construction on shared-nothing multiprocessors. Distributed and Parallel Databases 15(3):219–236

    Article  Google Scholar 

  12. Chi HC, Zhang Q (2005) Deadline-aware network coding for video on demand service over P2P networks. HKUST 7(22–23):755–763

    Google Scholar 

  13. Chi HC, Zhang Q, Shen X (2007) Efficient search and scheduling in P2P-based media-on-demand streaming service. IEEE J Sel Areas Commun 25(1):119–130

    Article  Google Scholar 

  14. Cuenca-Acuna FM, Nguyen TD (2001) Cooperative caching middleware for cluster-based servers. In: 10th IEEE international symposium on high performance distributed computing, pp 303–315

  15. Dahlin M, Wang R, Anderson TE, Patterson DA (1994) Cooperative caching: using remote client memory to improve file system performance. In: Operating systems design and implementation, pp 267–280

  16. Fan L, Cao P, Almeida J, Broder AZ (2000) Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Trans Netw 8(3):281–293

    Article  Google Scholar 

  17. Ghemawat S, Gobioff H, Leung ST (2003) The Google file system. In: ACM symposium on operating systems principles, pp 29–43

  18. Globisch G (1995) PARMESH—a parallel mesh generator. Parallel Comput 21(3):509–524

    Article  MATH  MathSciNet  Google Scholar 

  19. Goil S, Choudhary AN (1997) High performance OLAP and data mining on parallel computers. Data Mining and Knowledge Discovery 1(4):391–417

    Article  Google Scholar 

  20. Hennessy JL, Patterson DA (2002) Computer architecture: a quantitative approach, 3rd edn. Morgan Kaufmann, San Francisco

    MATH  Google Scholar 

  21. Howard JH, Kazar ML, Menees SG, Nichols DA, Satyanarayanan M, Sidebotham RN, West MJ (1998) Scale and performance in a distributed file system. ACM Trans Comput Syst 6(1):51–81

    Article  Google Scholar 

  22. Hu A (2001) Video-on-demand broadcasting protocols: a comprehensive study. In: IEEE INFOCOM, pp 508–517

  23. IBM (2007) IBM general parallel file system. http://www.ibm.com/systems/clusters/software/gpfs.html

  24. Kampe M, Stenstrom P, Dubois M (2004) Self-correcting LRU replacement policies. In: CF ’04: proceedings of the 1st conference on computing frontiers, Ischia, pp 181–191

  25. Korupolu MR, Dahlin M (2002) Coordinated placement and replacement for large-scale distributed caches. IEEE Trans Knowl Data Eng 14(6):1317–1329

    Article  Google Scholar 

  26. Kothari A, Agrawal D, Gupta A, Suri S (2003) Range addressable network: a P2P cache architecture for data ranges. In: Third international conference on peer-to-peer computing, Sweden, pp 14–23

  27. Linga P, Gupta I, Birman K (2003) A churn-resistant peer-to-peer web caching system. In: ACM workshop on survivable and self-regenerative systems, pp 1–10

  28. Nelson MN, Welch BB, Ousterhout JK (1998) Caching in the Sprite network file system. ACM Trans Comput Syst 6(1):134–154

    Article  Google Scholar 

  29. Pagh A, Pagh R, Rao SS (2005) An optimal bloom filter replacement. In: Annual ACM-SIAM symposium on discrete algorithms, pp 823–829

  30. Patterson DA, Gibson G, Katz RH (1988) A case for redundant arrays of inexpensive disks (raid). In: International conference on management of data (SIGMOD), pp 109–116

  31. Radenski A, Norris B, Chen W (2000) A generic all-pairs cluster-computing pipeline and its applications. In: Parallel computing: fundamentals & applications, pp 366–374

  32. Ratnasamy S, Francis P, Handley M, Karp R, Shenker S (2001) A scalable content-addressable network. In: ACM SIGCOMM, pp 161–172

  33. Red Hat, Inc (2007) Red hat global file system. http://www.redhat.com/software/rha/gfs/

  34. Rousskov A, Wessels D (1998) Cache digests. Comput Netw ISDN Syst 30(22–23):2155–2168

    Article  Google Scholar 

  35. Sandberg R, Goldberg D, Kleiman S, Walsh D, Lyon B (1985) Design and implementation of the sun network filesystem. In: Proc. summer 1985 USENIX conf, pp 119–130

  36. Sarkar P, Hartman J (1996) Efficient cooperative caching using hints. In: OSDI ’96: proceedings of the second USENIX symposium on operating systems design and implementation, Seattle, pp 35–46

  37. Sarkar P, Hartman JH (2000) Hint-based cooperative caching. ACM Trans Comput Syst 18(4):387–419

    Article  Google Scholar 

  38. Satyanarayanan M, Kistler JJ, Kumar P, Okasaki ME, Siegel EH, Steere DC (1990) Coda: a highly available file system for a distributed workstation environment. IEEE Trans Comput 39(4):447–459

    Article  Google Scholar 

  39. Skobeltsyn G, Aberer K (2006) Distributed cache table: efficient query-driven processing of multiterm queries in P2P networks. Tech rep LSIRRE-PORT-2006-010, EPFL, Lausanne, Switzerland

  40. Tanenbaum AS, Woodhull AS (2006) Operating systems design and implementation, 3rd edn. Prentice Hall, Englewood Cliffs

    Google Scholar 

  41. Tewari R, Dahlin M, Vin HM, Kay JS (1999) Design considerations for distributed caching on the internet. In: International conference on distributed computing systems, pp 273–284

  42. Wang C, Xiao L, Liu Y, Zheng P (2006) DiCAS: an efficient distributed caching mechanism for P2P systems. IEEE Trans Parallel Distrib Syst 17(10):1097– 1109

    Article  Google Scholar 

  43. Wang M, Ailamaki A, Faloutsos C (2002) Capturing the spatio-temporal behavior of real traffic data. Perform Eval 49(1–4):147–163

    Article  MATH  Google Scholar 

  44. University of Waterloo (2007) Abacus cluster. http://abacus.uwaterloo.ca/

  45. Wong WA, Baer JL (2000) Modified LRU policies for improving second-level cache behavior. In: High-performance computer architecture, pp 49–60

  46. Zhang L, Michel S, Nguyen K, Rosenstein A, Floyd S, Jacobson V (1998) Adaptive web caching: towards a new global caching architecture. In: 3rd international WWW caching workshop, pp 2169–2177

Download references

Acknowledgement

Financial support of this research has been provided by the Natural Sciences and Engineering Research Council (NSERC) of Canada.

Author information

Authors and Affiliations

  1. Department of ECE, University of Waterloo, Waterloo, Ontario, Canada

    Mursalin Akon, Towhidul Islam, Xuemin Shen & Ajit Singh

Authors
  1. Mursalin Akon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Towhidul Islam
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xuemin Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ajit Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xuemin Shen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Akon, M., Islam, T., Shen, X. et al. SPACE: A lightweight collaborative caching for clusters. Peer-to-Peer Netw. Appl. 3, 83–99 (2010). https://doi.org/10.1007/s12083-009-0047-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12083-009-0047-5

Keywords

Search

Navigation