Recovery protocols for shared memory database systems

ABSTRACT

Significant performance advantages can be gained by implementing a database system on a cache-coherent shared memory multiprocessor. However, problems arise when failures occur. A single node (where a node refers to a processor/memory pair) crash may require a reboot of the entire shared memory system. Fortunately, shared memory multiprocessors that isolate individual node failures are currently being developed. Even with these, because of the side effects of the cache coherency protocol, a transaction executing strictly on a single node may become dependent on the validity of the memory of many nodes thereby inducing unnecessary transaction aborts. This happens when database objects, such as records, and database support structures, such as index structures and shared lock tables, are stored in shared memory.In this paper, we propose crash recovery protocols for shared memory database systems which avoid the unnecessary transaction aborts induced by the effects of using shared physical memory. Our recovery protocols guarantee that if one or more nodes crash, all the effects of active transactions running on the crashed nodes will be undone, and no effects of transactions running on nodes which did not crash will be undone. In order to show the practicality of our protocols, we discuss how existing features of cache-coherent multiprocessors can be utilized to implement these recovery protocols. Specifically, we demonstrate that (1) for many types of database objects and support structures, volatile (in-memory) logging is sufficient to avoid unnecessary transaction aborts, and (2) a very low overhead implementation of this strategy can be achieved with existing multiprocessor features.

REFERENCES

• 1: Panel Discussion on Shared Nothing, Shared Disk, and Shared Memory Database Systems. Proceedings of the 1994 ACM SIGMOD international Conference on Management of Data, 23, May 1994.
• 2: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Anupam Bhide, An Analysis of Three Transaction Processing Architectures, Proceedings of the 14th International Conference on Very Large Data Bases, p.339-350, August 29-September 01, 1988
• 5: Anupam Bhide , Michael Stonebraker, A Performance Comparison of Two Architectures for Fast Transaction Processing, Proceedings of the Fourth International Conference on Data Engineering, p.536-545, February 01-05, 1988
• 6: J. Chapin. Personal Communication. 1995.
• 7: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 8: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 9: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 10: D. Johnson and W. Zwaenepoel. Sender-Based Message Logging. Proceedings of the 17th International Symposium on Fault-Tolerant Computing, pages 14-19, 1987.
• 11: Nancy P. Kronenberg , Henry M. Levy , William D. Strecker, VAXcluster: a closely-coupled distributed system, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.130-146, May 1986 [doi>10.1145/214419.214421]
• 12: J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States
• 13: David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993 [doi>10.1145/158439.158907]
• 14: Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582155]
• 15: David Lomet , Betty Salzberg, Access method concurrency with recovery, ACM SIGMOD Record, v.21 n.2, p.351-360, June 1, 1992
• 16: C. Mohan , Don Haderle, Algorithms for flexible space management in transaction systems supporting fine-granularity locking, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.131-144, May 1994, Cambridge, United Kingdom
• 17: 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]
• 18: C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, ACM SIGMOD Record, v.21 n.2, p.371-380, June 1, 1992
• 19: C. Mohan , Inderpal Narang, Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment, Proceedings of the 17th International Conference on Very Large Data Bases, p.193-207, September 03-06, 1991
• 20: Lory D. Molesky , Krithi Ramamritham, Efficient Locking for Shared Memory Database Systems, University of Massachusetts, Amherst, MA, 1994
• 21: E. Rahm. Concurrency and Coherency Control in Database Sharing Systems. Technical Report, University of KaisersIautern, Germany, December 1991.
• 22: E. Rahm. Use of Global Extended Memory for Distributed Transaction Processing. Proceedings of the 4th Int. Workshop on High Performance Transaction Systems, AsiIomar, CA., September 1991.
• 23: T. Rengarajan, P. Spiro, and W. Wright. High Availability Mechanisms of VAX DBMS Software. Digital Technical Journal, (8):88-98, February 1989.
• 24: Kendall Square Research. KSR1 Principles of Operation. KSR Research. Waltham, Mass., 1992.
• 25: W. Snaman and D. Thiel. The VAX/VMS Distributed Lock Manager. Digital Technical Journal, (5):29-44, September 1987.
• 26: R. Strom, D. Bacon, and S. Yemini. Volatile Logging in n- Fault-Tolerant Distributed Systems. Proceedings of the 18th International Symposium on Fault-Tolerant Computing, pages 44-49, 1988.
• 27: Shreekant S. Thakkar , Mark Sweiger, Performance of an OLTP application on symmetry multiprocessor system, Proceedings of the 17th annual international symposium on Computer Architecture, p.228-238, May 28-31, 1990, Seattle, Washington, United States
• 28: P. S. Yu , A. Dan, Performance Evaluation of Transaction Processing Coupling Architectures for Handling System Dynamics, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.139-153, February 1994 [doi>10.1109/71.265942]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart

General Terms:
Algorithms, Design, Performance, Verification