B-tree concurrency control and recovery in a client-server database management system

Abstract

In this thesis, we consider the management of transactions in a data-shipping client-server database system in which the physical database is organized as a sparse B±tree or B-link-tree index. Client transactions perform their operations on cached copies of index and data pages. A client transaction can contain any number of operations of the form "fetch the first (or next) matching record", "insert a record", or "delete a record", where database records are identified by their primary keys. Efficient implementation of these operations on B±tree and B-link trees are developed for page-server systems. Our algorithms guarantee recoverability of the logical database operations as well as the tree-structure modifications on the physical B±tree or B-link tree. Record updates and structure modifications are logged using physiological log records, which are generated by clients and shipped to the server. During normal processing client transaction aborts and rollbacks are performed by the clients themselves. The server applies the write-ahead logging (WAL) protocol, and the steal and no-force buffering policies for data and index pages. The server performs the restart recovery after a system failure using an ARIES-based recovery protocol.

Tree-structure modifications such as page splits and merges are defined as small atomic actions, where each action affects only two levels of a B±tree, or a single level of a B-link tree, while retaining the structural consistency and balance of the tree. In the case of a B-link tree, our balance conditions guarantee that all pages always contain at least m (a chosen minimum load factor) records and that the length of the search path of a database record is never greater than twice the tree height. Deletions are handled uniformly with insertions, so that underflows are disposed of by merging a page into its sibling page or redistributing the records between two sibling pages. Each structure modification is logged using a single physiological redo-only log record. Hence, structure modifications need never be undone during transaction rollback or restart recovery.

Our algorithms allow for inter-transaction caching of data and index pages, so that a page can reside in a client cache even when no transaction is currently active at the client. Cache consistency is guaranteed by a replica-management protocol based on callback locking. In one set of our algorithms, both the concurrency-control and replica-management protocols operate at the page level. These algorithms are most suitable for object-oriented database and CAD/CAM applications, where long-lasting editing sessions are typical. Another set of our algorithms is designed for general database applications where concurrency and transaction throughput are the major issues. In these algorithms, transaction isolation is guaranteed by the key-range locking protocol, and replica management operates in adaptive manner, so that only the needed record may be called back. A leaf (data) page may now contain uncommitted updates by several client transactions, and uncommitted updates by one transaction on a leaf page may migrate to another page in structure modifications. Moreover, a record in a leaf page cached at one client can be updated by one transaction while other records in copies of the same page cached at other clients can simultaneously be fetched by other transactions.