B-tree concurrency control and recovery in page-server database systems

ABSTRACT

We develop new algorithms for the management of transactions in a page-shipping client-server database system in which the physical database is organized as a sparse B-tree index. Our starvation-free fine-grained locking protocol combines adaptive callbacks with key-range locking and guarantees repeatable-read-level isolation (i.e., serializability) for transactions containing any number of record insertions, record deletions, and key-range scans. Partial and total rollbacks of client transactions are performed by the client. Each structure modification such as a page split or merge is defined as an atomic action that affects only two levels of the B-tree and is logged using a single redo-only log record, so that the modification never needs to be undone during transaction rollback or restart recovery. The steal-and-no-force buffering policy is applied by the server when flushing updated pages onto disk and by the clients when shipping updated data pages to the server, while pages involved in a structure modification are forced to the server when the modification is finished. The server performs the restart recovery from client and system failures using an ARIES/CSA-based recovery protocol. Our algorithms avoid accessing stale data but allow a data page to be updated by one client transaction and read by many other client transactions simultaneously, and updates may migrate from a data page to another in structure modifications caused by other transactions while the updating transaction is still active.

REFERENCES

• 1: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.23-34, May 22-25, 1995, San Jose, California, United States
• 2: Basu, J., Keller, A., and Pöss, M. 1997. Centralized versus distributed index schemes in OODBMS---a performance analysis. In Proceedings of the 1st East-European Symposium on Advances in Databases and Information Systems (ADBIS'97). 162--169.
• 3: Bayer, R. and Schkolnick, M. 1977. Concurrency of operations on B-trees. Acta Informatica 9, 1--21.
• 4: 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
• 5: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: 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
• 7: 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
• 8: Michael J. Carey , Miron Livny, Conflict detection tradeoffs for replicated data, ACM Transactions on Database Systems (TODS), v.16 n.4, p.703-746, Dec. 1991 [doi>10.1145/115302.115289]
• 9: O. Deux, The O2 system, Communications of the ACM, v.34 n.10, p.34-48, Oct. 1991 [doi>10.1145/125223.125238]
• 10: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Vélez, A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.107-121, August 13-16, 1990
• 11: Franklin, M. J. and Carey, M. J. 1994. Client-server caching revisited. In Distributed Object Management, Papers from the 1992 International Workshop on Distributed Object Management. Morgan Kaufmann, San Francisco, CA, 57--78.
• 12: Michael J. Franklin , Michael J. Carey , Miron Livny, Global Memory Management in Client-Server Database Architectures, Proceedings of the 18th International Conference on Very Large Data Bases, p.596-609, August 23-27, 1992
• 13: 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
• 14: 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]
• 15: Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.149-160, June 04-06, 1996, Montreal, Quebec, Canada
• 16: 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
• 17: Vibby Gottemukkala , Edward Omiecinski , Umakishore Ramachandran, Relaxed Index Consistency for a Client-Server Database, Proceedings of the Twelfth International Conference on Data Engineering, p.352-361, February 26-March 01, 1996
• 18: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 19: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 20: Jaluta, I. 2002. B-tree concurrency control and recovery in a client-server database management system. Ph.D. dissertation, Department of Computer Science and Engineering, Helsinki University of Technology. Helsinki, Finland. Go online to http://lib.hut.fi/ Diss/2002/isbn9512257068/.
• 21: Ibrahim Jaluta , Seppo Sippu , Eljas Soisalon-Soininen, Concurrency control and recovery for balanced B-link trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.257-277, April 2005 [doi>10.1007/s00778-004-0140-6]
• 22: 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]
• 23: B. Liskov , A. Adya , M. Castro , S. Ghemawat , R. Gruber , U. Maheshwari , A. C. Myers , M. Day , L. Shrira, Safe and efficient sharing of persistent objects in Thor, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.318-329, June 04-06, 1996, Montreal, Quebec, Canada
• 24: David B. Lomet, MLR: a recovery method for multi-level systems, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.185-194, June 02-05, 1992, San Diego, California, United States
• 25: Lomet, D. 1998. Advanced recovery techniques in practice. In Recovery Mechanisms in Database Systems, V. Kumar and M. Hsu, Eds. Prentice Hall PTR, Englewood Cliffs, NJ, 697--710.
• 26: David Lomet , Betty Salzberg, Access method concurrency with recovery, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.351-360, June 02-05, 1992, San Diego, California, United States
• 27: David Lomet , Betty Salzberg, Concurrency and recovery for index trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.224-240, August 1997 [doi>10.1007/s007780050042]
• 28: C. Mohan, ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes, Proceedings of the 16th International Conference on Very Large Data Bases, p.392-405, August 13-16, 1990
• 29: C. Mohan, Commit_LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.406-418, August 13-16, 1990
• 30: Mohan, C. 1992. Less optimism about optimistic concurrency control. In RIDE-TQP'92, Proceedings of the 2nd International Workshop on Research Issues on Data Engineering: Transaction and Query Processing. 199--204.
• 31: C. Mohan, Concurrency control and recovery methods for B+-tree indexes: ARIES/KVL and ARIES/IM, Performance of concurrency control mechanisms in centralized database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 32: 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]
• 33: C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States
• 34: 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
• 35: 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
• 36: Mohan, C., Narang, I., and Silen, S. 1991. Solutions to hot spot problems in a shared disks transaction environment. In Proceedings of the 4th International Workshop on High Performance Transaction Systems.
• 37: Mond, Y. and Raz, Y. 1985. Concurrency control in B+-tree databases using preparatory operations. In Proceedings of the 11th International Conference on Very Large Data Bases. 331--334.
• 38: M. Tamer Özsu , Kaladhar Voruganti , Ronald C. Unrau, An Asynchronous Avoidance-Based Cache Consistency Algorithm for Client Caching DBMSs, Proceedings of the 24rd International Conference on Very Large Data Bases, p.440-451, August 24-27, 1998
• 39: E. Panagos , A. Biliris, Synchronization and recovery in a client-server storage system, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.209-223, August 1997 [doi>10.1007/s007780050041]
• 40: Euthimios Panagos , Alexandros Biliris , H. V. Jagadish , Rajeev Rastogi, Fine-granularity Locking and Client-Based Logging for Distributed Architectures, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.388-402, March 25-29, 1996
• 41: Seppo Sippu , Eljas Soisalon-Soininen, A Theory of Transactions on Recoverable Search Trees, Proceedings of the 8th International Conference on Database Theory, p.83-98, January 04-06, 2001
• 42: Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Eugene Inseok Chong , Mahesh Jagannath , Aravind Yalamanchi , Ramkumar Krishnan , Anh-Tuan Tran , Samuel DeFazio , Jayanta Banerjee, Oracle8i Index-Organized Table and Its Application to New Domains, Proceedings of the 26th International Conference on Very Large Data Bases, p.285-296, September 10-14, 2000
• 43: Kaladhar Voruganti , M. Tamer Özsu , Ronald C. Unrau, An Adaptive Hybrid Server Architecture for Client Caching ODBMSs, Proceedings of the 25th International Conference on Very Large Data Bases, p.150-161, September 07-10, 1999
• 44: Kaladhar Voruganti , M. Tamer Özsu , Ronald C. Unrau, An Adaptive Data-Shipping Architecture for Client Caching Data Management Systems, Distributed and Parallel Databases, v.15 n.2, p.137-177, March 2004 [doi>10.1023/B:DAPD.0000013069.97679.62]
• 45: Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States
• 46: Seth J. White , David J. DeWitt, QuickStore: a high performance mapped object store, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.395-406, May 24-27, 1994, Minneapolis, Minnesota, United States
• 47: W. Kevin Wilkinson , Marie-Anne Neimat, Maintaining Consistency of Client-Cached Data, Proceedings of the 16th International Conference on Very Large Data Bases, p.122-133, August 13-16, 1990
• 48: Markos Zaharioudakis , Michael J. Carey, Highly concurrent cache consistency for indices in client-server database systems, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.50-61, May 11-15, 1997, Tucson, Arizona, United States
• 49: Markos Zaharioudakis , Michael J. Carey , Michael J. Franklin, Adaptive, fine-grained sharing in a client-server OODBMS: a callback-based approach, ACM Transactions on Database Systems (TODS), v.22 n.4, p.570-627, Dec. 1997 [doi>10.1145/278245.278249]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart
      H.2.4 Systems
          Subjects: Transaction processing; Concurrency

General Terms:
Algorithms, Design

Keywords:
ARIES, ARIES/CSA, B-tree, cache consistency, callback locking, client-server database system, data shipping, key-range locking, page server, partial rollback, physiological logging, sparse B-tree, structure modification