Transaction Processing: Concepts and Techniques

Citation

Gray, J., & Reuter, A. (1992). Transaction Processing: Concepts and Techniques. Morgan Kaufmann.

Chapter Summary

The book has nineteen numbered chapters grouped in eight Parts: the basics of transaction processing, the basics of fault tolerance, transaction-oriented computing, concurrency control, recovery, a transactional file system as a sample resource manager, system surveys, and addenda (references, data structures and interfaces, glossary). A foreword by Bruce Lindsay and a preface open the book. Chapters 1–15 each close with exercises and answers, and most of them also with historical notes.

Part One: The Basics of Transaction Processing (Chapters 1–2)

Chapter 1, Introduction, gives a historical perspective and asks what a transaction processing system is, looking at it from the viewpoints of the end user, the administrator or operator, the application designer and the resource manager, and listing the core services and a feature list covering application development, repository, TP monitor, data communications, database, operations, and education and testing. Chapter 2, Basic Computer Science Terminology, supplies the vocabulary used later: hardware (memories, processors, communications, architectures), address spaces, processes, threads, messages and sessions, clients and servers, naming, authentication and authorization, files and SQL, software performance, and transaction processing standards such as LU6.2 and OSI-TP with X/Open DTP.

Part Two: The Basics of Fault Tolerance (Chapter 3)

Chapter 3, Fault Tolerance, covers definitions (fault, failure, availability, reliability), empirical studies of outages, typical module failure rates, hardware approaches such as N-plex and failfast modules, and why software is the main problem. It goes on to transactions and software fault tolerance, a process–message–storage model for highly available storage, processes and messages, general principles, and a cautionary tale titled "System Delusion".

Part Three: Transaction-Oriented Computing (Chapters 4–6)

Chapter 4, Transaction Models, proceeds from atomic actions and flat transactions through spheres of control, a notation for describing models, savepoints, chained transactions, nested transactions, distributed and multi-level transactions, open nested and long-lived transactions (including sagas), and "exotics". Chapter 5 is an overview of transaction processing monitors: their role, structure, transactional remote procedure calls and examples of the programming style. Chapter 6, Transaction Processing Monitors, goes inside: the resource manager interface, the monitor's data structures, a guided tour along the transactional RPC path, request and response queues, load balancing, authentication and restart processing.

Part Four: Concurrency Control (Chapters 7–8)

Chapter 7, Isolation Concepts, is a long chapter: a dependency model of isolation, isolation theorems, degrees of isolation and SQL, phantoms and predicate locks, granular locks and key-range locking, locking heuristics, nested-transaction locking, scheduling and deadlock, and exotics such as escrow and optimistic locking. Chapter 8, Lock Implementation, turns to atomic machine instructions, semaphores, the lock manager (names, queues, data structures, internal logic, escalation, restart), deadlock detection and locking for parallel transactions.

Part Five: Recovery (Chapters 9–12)

Chapter 9, Log Manager, treats log tables, sequence numbers, the public interface, implementation details such as group commit and careful writes, restart logic and log archiving. Chapter 10, Transaction Manager Concepts, covers the application and resource-manager interfaces, the DO-UNDO-REDO protocol, value, logical and physiological logging, write-ahead logging rules, compensation records, and two-phase commit. Chapter 11, Transaction Manager Structure, walks through normal processing, checkpoints, system restart, resource manager failure and archive recovery. Chapter 12, Advanced Transaction Manager Topics, treats heterogeneous commit coordinators, non-blocking commit, transfer-of-commit, optimizations of two-phase commit and disaster recovery at a remote site.

Part Six: Transactional File System: A Sample Resource Manager (Chapters 13–15)

Chapter 13, File and Buffer Management, covers the file system as a basis for durable storage, media and file management, and buffer management. Chapter 14, The Tuple-Oriented File System, covers mapping tuples into pages, physical tuple representation and file organizations (entry-sequenced, key-sequenced, hash, cluster and partitioned files). Chapter 15, Access Paths, covers hashing and B-trees, including their synchronization and recovery, with sample implementations of B-tree operations, and extendible hashing, grid files and holey brick B-trees.

Part Seven: System Surveys (Chapter 16)

Chapter 16, Survey of TP Systems, describes IMS, CICS and LU6.2, Guardian 90, DECdta, X/Open DTP with OSI-TP and CCR, and other systems (UTM, ADABAS TPF, Encina and Tuxedo).

Part Eight: Addenda (Chapters 17–19)

References, Data Structures and Interfaces, and a Glossary, followed by the index.

Key Concepts

Parts One and Two: Basics and Fault Tolerance

• Transaction processing system: a system built around transactions, seen differently by users, administrators, application designers and resource managers.
• Availability and reliability: the definitions and failure-rate models that underlie fault-tolerant design.
• Failfast modules and N-plex: hardware structures that detect or mask faults.

Part Three: Transaction-Oriented Computing

• Flat, chained, nested and multi-level transactions: the transaction models, each defined by the rules it imposes on savepoints, scope and commit.
• Sagas and compensation: ways to handle long-lived work with compensating transactions.
• TP monitor and transactional RPC: the middleware that structures, schedules and attaches resource managers to transactions.

Parts Four and Five: Concurrency Control and Recovery

• Isolation and degrees of isolation: the dependency-based definition of isolation and the weaker levels used in practice.
• Granular and key-range locking: locking at several levels and over ranges of keys to prevent phantoms.
• Write-ahead log and physiological logging: the logging rules that make redo and undo work.
• Two-phase commit: the protocol that makes a distributed computation atomic.

Parts Six to Eight

• B-trees and hashing as access paths: the structures through which tuples are found, with their locking and recovery.
• System surveys: comparisons of IMS, CICS, Guardian 90, DECdta and X/Open DTP.

Critical Analysis

Strengths

• Transactions as one framework. The publisher's description says the authors use transactions as a unifying conceptual framework, and the structure bears this out: fault tolerance, transaction models, concurrency control and recovery are four parts of one argument.
• Implementation depth. Chapters 8, 9 and 11 look at the internals of a lock manager, log manager and transaction manager, and the publisher notes compilable C code fragments to demonstrate the algorithms.
• Teaching apparatus. Chapters 1–15 each end with exercises and answers, and most with historical notes (the table of contents lists them), giving the book's long argument a self-study structure.
• A worked sample resource manager. Part Six builds a transactional file system and B-tree access paths, showing how the earlier ideas meet a concrete storage layer.

Limitations

• Dated systems survey. Chapter 16 covers products and standards of the early 1990s, such as IMS, CICS, Guardian 90 and DECdta, with no later systems.
• Length and specialization. With sixteen chapters of main text and a detailed treatment of lock and log managers, the book is a monograph on one topic; courses will assign selected chapters.
• Foundations assumed. Chapter 2 supplies terminology, but the later parts presuppose a database course and some operating-systems background.

Where It Fits in the Course

The other books in this course cover the whole of a database system. Silberschatz, Korth and Sudarshan's Database System Concepts and Elmasri and Navathe's Fundamentals of Database Systems are broad textbooks that include transactions, concurrency and recovery as chapters; Ramakrishnan and Gehrke's Database Management Systems is also a general textbook. Coronel and Morris, and Hernandez, are gentler books on design and use. Gray and Reuter is the book to read when one chapter of those texts has raised more questions than it answers.

It is therefore a second-stage book: read the transactions chapters of a general text first, then use Parts Four and Five here for locking, logging, recovery and two-phase commit in full detail.

How to Use This Book

The book suits graduate students in databases and distributed systems, and engineers building or tuning storage engines, database internals or transaction monitors. Readers should already have taken a database course and know the basics of operating systems and concurrency.

A practical plan:

• Core: Chapter 1 and the first sections of Chapter 4 for the vocabulary of transactions; Chapter 7 (isolation) and Chapters 9–11 (logging, the transaction manager, restart, two-phase commit).
• For implementers: Chapter 8 on lock implementation, Chapter 12 on advanced commit topics, and Chapters 13–15 on file, buffer and B-tree management.
• Optional: Chapter 3 on fault tolerance, Chapters 5–6 on TP monitors, and Chapter 16 as a historical survey rather than a guide to current products.

Work through the exercises at the end of each chapter and check them against the answers, and treat the C fragments as models to adapt and run.