Garbage collection for a client-server persistent object store

ABSTRACT

We describe an efficient server-based algorithm for garbage collecting persistent object stores in a client-server environmnet. The algorithm is incremental and runs concurrently with client transactions. Unlike previous algorithms, it does not hold any transactional locks on data and does non require callbacks to clients. It is fault-tolerant, but performs very little logging. The algorithm has been designed to be integrated into existing systems, and therefore it works with standard implementation techniques such as Two-Phase Locking and Write-Ahead-Logging. In addition, it supports client-server performance optimizations such as client caching and flexible management of client buffers. We describe an implementation of the algorithm in the EXODUS storage manager and present the results of a performance study of the implementation.

REFERENCES

• 1: Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998 [doi>10.1145/292469.292471]
• 2: AMSALEG, L. 1995. Conception et r alisation d'un glaneur de cellules adapt aux SGBDO client-serveur. Ph.D. Dissertation. Universit Paris 6 Pierre et Marie Curie, Paris, France.
• 3: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 4: Srinivas Ashwin , Prasan Roy , S. Seshadri , Abraham Silberschatz , S. Sudarshan, Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting, Proceedings of the 23rd International Conference on Very Large Data Bases, p.366-375, August 25-29, 1997
• 5: M. P. Atkinson , P. J. Bailey , K. J. Chisholm , P. W. Cockshott , R. Morrison, An approach to persistent programming, Readings in object-oriented database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 6: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 7: François Bancilhon , Claude Delobel , Paris Kanellakis, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 8: BENZAKEN, V. AND DELOBEL, C. 1990. Enhancing performance in a persistent object store: Clustering strategies in 02. In Proceedings of the 4th International Workshop on Persistent Object Systems (Martha's Vineyard, MA, Sept.). 403-412.
• 9: Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.1-10, May 22-25, 1995, San Jose, California, United States
• 10: BISHOP, P. 1977. Computer systems with a very large address space and garbage collection. Ph.D. Dissertation. MIT Laboratory for Computer Science, Cambridge, MA.
• 11: D. R. Brownbridge, Cyclic reference counting for combinator machines, Proc. of a conference on Functional programming languages and computer architecture, p.273-288, January 1985, Nancy, France
• 12: Margaret H. Butler, Storage reclamation in object oriented database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.410-425, May 27-29, 1987, San Francisco, California, United States
• 13: Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.12-21, May 25-28, 1993, Washington, D.C., United States
• 14: Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
• 15: Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States
• 16: Michael J. Carey , Michael J. Franklin , Markos Zaharioudakis, Fine-grained sharing in a page server OODBMS, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.359-370, May 24-27, 1994, Minneapolis, Minnesota, United States
• 17: COOK, J., KLAUSER, A., WOLF, A., AND ZORN, B. 1994a. Effectively controlling garbage collection rates in object databases. Tech. Rep. CU-CS-758-94. Department of Computer Science, University of Colorado at Boulder, Boulder, CO.
• 18: Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn, Partition selection policies in object database garbage collection, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.371-382, May 24-27, 1994, Minneapolis, Minnesota, United States
• 19: David Luke Detlefs , Jeannette Wing, Concurrent atomic garbage collection, 1990
• 20: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Velez, A study of three alternative workstation server architectures for object-oriented database systems, Proceedings of the sixteenth international conference on Very large databases, p.107-121, September 1990, Brisbane, Australia
• 21: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 22: Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
• 23: EXODUS PROJECT GROUP.1993. EXODUS storage manager architectural overview. Computer Science Department, Univ. of Wisconsin at Madison, Madison, WI. ftp://ftp.cs.wisc.edu/exodus/sm/doc/arch_overview.3.0.ps.
• 24: Paulo Ferreira , Marc Shapiro, Garbage Collection in the Larchant Persistent Distributed Shared Store, Proceedings of the 5th IEEE Workshop on Future Trends of Distributed Computing Systems, p.461, August 28-30, 1995
• 25: FRANKLIN, M. 1997. Concurrency control and recovery. In The Computer Science and Engineering Handbook, A. B. Tucker, Ed. CRC Press, Inc., Boca Raton, FL, 1058-1077.
• 26: Michael J. Franklin , Michael J. Carey , Miron Livny, Local Disk Caching for Client-Server Database Systems, Proceedings of the 19th International Conference on Very Large Data Bases, p.641-655, August 24-27, 1993
• 27: Michael J. Franklin , Michael J. Carey , Miron Livny, Transactional client-server cache consistency: alternatives and performance, ACM Transactions on Database Systems (TODS), v.22 n.3, p.315-363, Sept. 1997 [doi>10.1145/261124.261125]
• 28: Michael J. Franklin , Michael J. Zwilling , C. K. Tan , Michael J. Carey , David J. DeWitt, Crash recovery in client-server EXODUS, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.165-174, June 02-05, 1992, San Diego, California, United States
• 29: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 30: GRUBER, O. AND AMSALEG, L. 1994. Object grouping in EOS. In Distributed Object Management, T. zsu, U. Dayal, and P. Valduriez, Eds. Morgan Kaufmann, San Mateo, CA, 117-131.
• 31: Elliot K. Kolodner , William E. Weihl, Atomic incremental garbage collection and recovery for a large stable heap, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.177-186, May 25-28, 1993, Washington, D.C., United States
• 32: Elliot Kolodner , Barbara Liskov , William Weihl, Atomic garbage collection: managing a stable heap, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.15-25, June 1989, Portland, Oregon, United States
• 33: Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991 [doi>10.1145/125223.125244]
• 34: Fabrice Le Fessant , Ian Piumarta , Marc Shapiro, An implementation of complete, asynchronous, distributed garbage collection, ACM SIGPLAN Notices, v.33 n.5, p.152-161, May 1998
• 35: Umesh Maheshwari , Barbara H. Liskov, Fault-tolerant distributed garbage collection in a client-server object-oriented database, Proceedings of the third international conference on on Parallel and distributed information systems, p.239-248, October 1994, Autin, Texas, United States
• 36: Umesh Maheshwari , Barbara Liskov, Partitioned garbage collection of a large object store, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.313-323, May 11-15, 1997, Tucson, Arizona, United States
• 37: J. Harold McBeth, Letters to the editor: on the reference counter method, Communications of the ACM, v.6 n.9, p.575, Sept. 1963 [doi>10.1145/367593.367649]
• 38: C. Mohan , Inderpal Narang, ARIES/CSA: a method for database recovery in client-server architectures, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.55-66, May 24-27, 1994, Minneapolis, Minnesota, United States
• 39: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 40: James O'Toole , Scott Nettles , David Gifford, Concurrent compacting garbage collection of a persistent heap, ACM SIGOPS Operating Systems Review, v.27 n.5, p.161-174, Dec. 1993
• 41: SHAPIRO, M., GRUBER, O., AND PLAINFOSS , D. 1990. A garbage detection protocol for a realistic distributed object-support system. Tech. Rep. INRIA-1320. INRIA, Rennes, France.
• 42: Marcin Skubiszewski , Patrick Valduriez, Concurrent Garbage Collection in O2, Proceedings of the 23rd International Conference on Very Large Data Bases, p.356-365, August 25-29, 1997
• 43: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 44: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 45: Voon-Fee Yong , Jeffrey F. Naughton , Jie-Bing Yu, Storage Reclamation and Reorganization in Client-Server Persistent Object Stores, Proceedings of the Tenth International Conference on Data Engineering, p.120-131, February 14-18, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Object-oriented databases; Transaction processing

General Terms:
Algorithms, Measurement, Performance

Keywords:
client-server system, logging, persistent object-store, recovery