COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Transaction Processing - 1st Edition - ISBN: 9781558601901, 9780080519555

Transaction Processing

1st Edition

Concepts and Techniques

Authors: Jim Gray Andreas Reuter
Hardcover ISBN: 9781558601901
eBook ISBN: 9780080519555
Imprint: Morgan Kaufmann
Published Date: 30th September 1992
Page Count: 1070
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

Transaction Processing: Concepts and Techniques
by Jim Gray and Andreas Reuter

PART ONE - The Basics of Transaction Processing
1 INTRODUCTION 1.1 Historical Perspective
1.2 What Is a Transaction Processing System? 1.2.1 The End User's View of a Transaction Processing System
1.2.2 The Administrator/Operator's View of a TP System
1.2.3 Application Designer's View of a TP System
1.2.4 The Resource Manager's View of a TP System
1.2.5 TP System Core Services 1.3 A Transaction Processing System Feature List 1.3.1 Application Development Features
1.3.2 Repository Features
1.3.3 TP Monitor Features
1.3.4 Data Communications Features
1.3.5 Database Features
1.3.6. Operations Features
1.3.7 Education and Testing Features
1.3.8 Features Summary 1.4 Summary
1.5 Historical Notes
2 BASIC COMPUTER SCIENCE TERMINOLOGY 2.1 Introduction 2.1.1 Units 2.2 Basic Hardware 2.2.1 Memories
2.2.2 Processors
2.2.3 Communications Hardware
2.2.4 Hardware Architectures 2.3 Basic Software - Address Spaces, Processes, Sessions 2.3.1 Address Spaces
2.3.2 Processes, Protection Domains, and Threads
2.3.3 Messages and Sessions 2.4 Generic System Issues 2.4.1 Clients and Servers
2.4.2 Naming
2.4.3 Authentication
2.4.4 Authorization
2.4.5 Scheduling and Performance
2.4.6 Summary 2.5 Files 2.5.1 File Operations
2.5.2 File Organizations
2.5.3 Distributed Files
2.5.4 SQL 2.6 Software Performance
2.7 Transaction Processing Standards 2.7.1 Portability versus Interoperability Standards
2.7.2 APIs and FAPs
2.7.3 LU6.2, a de facto Standard
2.7.4 OSI-TP with X/Open DTP, a de jure Standard 2.8 Summary
PART TWO - The Basics of Fault Tolerance
3 FAULT TOLERANCE 3.1 Introduction 3.1.1 A Crash Course in Simple Probability
3.1.2 An External View of Fault Tolerance 3.2 Definitions 3.2.1. Fault, Failure, Availability, Reliability
3.2.2 Taxonomy of Fault Avoidance and Fault Tolerance
3.2.3 Repair, Failfast, Modularity, Recursive Design 3.3 Empirical Studies 3.3.1 Outages Are Rare Events
3.3.2 Studies of Conventional Systems
3.3.3 A Study of Fault-Tolerant System 3.4 Typical Module Failure Rates
3.5 Hardware Approaches to Fault Tolerance 3.5.1 The Basic N-Plex Idea: How to Build Failfast Modules
3.5.2 Failfast versus Failvote Voters in an N-Plex
3.5.3 N-Plex plus Repair Results in High Availability
3.5.4 The Voter's Problem
3.5.5 Summary 3.6 Software Is the Problem 3.6.1 N-Version Programming and Software Fault Tolerance
3.6.2 Transactions and Software Fault Tolerance
3.6.3 Summary 3.7 Fault Modeal and Software Fault Masking 3.7.1 An Overview of the Model
3.7.2 Building Highly Available Storage
3.7.3 Highly Available Processes
3.7.4 Reliable Messages via Sessions and Process Pairs
3.7.5 Summary of the Process-Message-Storage Model 3.8 General Principles
3.9 A Cautionary Tale - System Delusion
3.10 Summary
3.11 Historical Notes
PART THREE - Transaction-Oriented Computing
4 TRANSACTION MODELS 4.1 Introduction 4.1.1 About this Chapter 4.2 Atomic Actions and Flat Transaction 4.2.1 Disk Writes as Atomic Actions
4.2.2 A Classification of Action Types
4.2.3 Flat Transactions
4.2.4 Limitations of Flat Transactions 4.3 Spheres of Control 4.3.1 Definition of Spheres of Control
4.3.2 Dynamic Behavior of Spheres of Control
4.3.3 Summary 4.4 A Notation for Explaining Transaction Models 4.4.1 What is Required to Describe Transaction Models?
4.4.2 Elements of the Notation
4.4.3 Defining Transaction Models by a Set of Simple Rules 4.5 Flat Transactions with Savepoints 4.5.1 About Savepoints
4.5.2 Developing the Rules for the Savepoint Model
4.5.3 Persistent Savepoints 4.6 Chained Transactions
4.7 Nested Transactions 4.7.1 Definition of the Nexting Structure
4.7.2 Using Nested Transactions
4.7.3 Emulating Nested Transactions by Savepoints 4.8 Distributed Transactions
4.9 Multi-Level Transactions 4.9.1 The Role of a Compensating Transaction
4.9.2 The Use of Multi-Level Transactions 4.10 Open Nested Transactions
4.11 Long-Lived transactions 4.11.1 Transaction Processing Context
4.11.2 The Mini-Batch
4.11.3 Sagas 4.12 Exotics
4.13 Summary
4.14 Historical Notes
5 TRANSACTION PROCESSING MONITORS - An Overview 5.1 Introduction
5.2 The Role of TP Monitors in Transaction Systems 5.2.1 The Transaction -Oriented Computing Style
5.2.2 The Transaction Processing Services
5.2.3 TP System Process Structure
5.2.4 Summary 5.3 The Structure of a TP Monitor 5.3.1 The TP Monitor Components
5.3.2 Components of the Transaction Services
5.3.3 TP Monitor Support for the Resource Manager Interfaces 5.4 Transactional Remote Procedure Calls: The Basic Idea 5.4.1 Who Participates in Remote Procedure Calls?
5.4.2 Address Space Structure Required for RPC Handling
5.4.3 The Dynamics of Remote Procedure Calls
5.4.4 Summary 5.5 Examples of the Transaction-Oriented Programming Style 5.5.1 The Basic Processing Loop
5.5.2 Attaching Resource Managers to Transactions: The Simple Cases
5.5.3 Attaching Resource Managers To Transactions: The Sophisticated Case
5.5.4 Using Persistent Savepoints 5.6 Terminological Wrap-Up
5.7 Historical Notes
6.2 Transactional Remote Procedures Calls 6.2.1 The Resource Manager Interface
6.2.2 What the Resource Manager Has to Do in Support of Transactions
6.2.3 Interfaces between resource Managers and the TP Monitor
6.2.4 Resource Manager Calls versus Resource Manager Sessions
6.2.5 Summary 6.3. Functional Principles of the TP Monitor 6.3.1 The Central Data Structures of the TPOS
6.3.2 Data Structures Owned by the TP Monitor
6.3.3. A Guided Tour Along the TRPC Path
6.3.4 Aborts Racing TRPCs
6.3.5 Summary 6.4 Managing Request and Response Queues 6.4.1 Short-Term Queues for Mapping Resource Manager Invocations
6.4.2 Durable Request Queues for Asynchronous Transaction Processing
6.4.3 Summary 6.5 Other Tasks of the TP Monitor 6.5.1 Load Balancing
6.5.2 Authentication and Authorization
6.5.3 Restart Processing 6.6 Summary
6.7 Historical Notes
PART FOUR - Concurrency Control
7.2 Introduction to Isolation
7.3 The Dependency Model of Isolation 7.3.1 Static versus Dynamic Allocation
7.3.2 Transaction Dependencies
7.3.3 The Three Bad Dependencies
7.3.4 The Case for a Formal Model of Isolation 7.4 Isolation: The Application Programmer's View
7.5 Isolation Theorems 7.5.1 Actions and Transactions
7.5.2 Well-Formed and Two-Phased Transactions
7.5.3 Transaction Histories
7.5.4 Legal Histories and Lock Compatibility
7.5.5 Versions, Dependencies, and the Dependency Graph
7.5.6 Equivalent and Isolated Histories: BEFORE, AFTER, and Wormholes
7.5.7 Wormholes Are Not Isolated
7.5.8 Summary of Definitions
7.5.9 Summary of the Isolation Theorems 7.6 Degrees of Isolation 7.6.1 Degrees of Isolation Theorem
7.6.2 SQL and Degrees of Isolation
7.6.3 Pros and Cons of Low Degrees of Isolation
7.6.4 Exotic SQL Isolation - Read-Past and Notify Locks 7.7 Phantoms and Predicate Locks 7.7.1 The Problem with Predicate Locks 7.8 Granular Locks 7.8.1 Three Locking and Intent Lock Modes
7.8.2 Update Mode Locks
7.8.3 Granular Locking Summary
7.8.4 Key-Range Locking
7.8.5 Dynamic Key-Range Locks: Previous-Key and Next-Key Locking
7.8.6 Key-Range Locks Need DAG Locking
7.8.7 The DAG Locking Protocol
7.8.8 Formal Definition of Granular Locks on a DAG 7.9 Locking Heuristics
7.10 Nested Transaction Locking
7.11 Scheduling and Deadlock 7.11.1 The Convoy Phenomenon
7.11.2 Deadlock Avoidance versus Toleration
7.11.3 The Wait-for Graph and Deadlock Detector
7.11.4 Distributed Deadlock
7.11.5 Probability of Deadlock 7.12 Exotics 7.12.1 Field Calls
7.12.2 Escrow Locking and Other Field Call Refinements
7.12.3 Optimistic and Timestamp Locking
7.12.4 Time Domain Addressing 7.13 Summary
7.14 Historical Notes
8 LOCK IMPLEMENTATION 8.1 About This Chapter 8.1.2 The Need for Parallelism within the Lock Manager
8.1.3 The Resource Manager and Lock Manager Address Space 8.2 Atomic Machine Instructions
8.3 Semaphores 8.3.1 Exclusive Semaphores
8.3.2 Crabbing: Traversing Shared Data Structures
8.3.3 Shared Semaphores
8.3.4 Allocating Shared Storage
8.3.5 Semaphores and Exceptions 8.4 Lock Manager 8.4.1 Lock Names
8.4.2 Lock Queues and Scheduling
8.4.3 Lock Duration and Lock Counts
8.4.4 Lock Manager Interface and Data Structures
8.4.5 Lock Manager Internal Logic
8.4.6 Lock Escalation and Generic Unlock, Notify Locks
8.4.7 Transaction Savepoints, Commit, and Rollback
8.4.8 Locking at System Restart
8.4.9 Phoenix Transactions
8.4.10 Lock Manager Configuration and Complexity
8.4.11 Lock Manager Summary 8.5 Deadlock Detection
8.6 Locking for Parallel and Parallel Nested Transactions
8.7 Summary
8.8 Historical Notes
PART FIVE- Recovery
9 LOG MANAGER 9.1 Introduction 9.1.1 Uses of the Log
9.1.2 Log Manager Overview
9.1.3 The Log Manager's Relationship to Other Services
9.1.4 Why Have a Log Manager? 9.2 Log Tables 9.2.1 Mapping the Log Table onto Files
9.2.2 Log Sequence Numbers 9.3 Public Interface to the Log 9.3.1 Authorization to Access the Log Table
9.3.2 Reading the Log Table
9.3.4 Summary 9.4 Implementation Details of Log Reads and Writes 9.4.1 Reading the Log
9.4.2 Log Anchor
9.4.3 Transaction Related Anchors
9.4.4 Log Insert
9.4.5 Allocate and Flush Log Daemons
9.4.6 Careful Writes: Serial of Ping-Pong
9.4.7 Group Commit, Batching, Boxcarring
9.4.8 WADS Writes
9.4.9 Multiple Logs per Transaction Manager
9.4.10 Summary 9.5 Log Restart Logic 9.5.1 Saving the Transaction Manager Anchor
9.5.2 Preparing for Restart: Careful Writes of the Log Anchor
9.5.3 Finding the Anchor and Log End at Restart 9.6 Archiving the Log 9.6.1 How Much of the Log Table Should Be Online?
9.6.2 Low-Water Marks for Rollback, Restart, Archive
9.6.3 Dynamic Logs: Copy Aside versus Copy Forward
9.6.4 Archiving the Log Without Impacting Concurrent Transactions
9.6.5 Electronic Vaulting and Change Accumulation
9.6.6 Dealing with Log Manager-Archive Circularity 9.7 Logging in a Client-Server Architecture
9.8 Summary
9.9 Historical Notes
10.2 Transaction Manager Interfaces 10.2.1 The Application Interface to Transactions
10.2.2 The Resource Manager Interface to Transactions
10.2.3 Transaction Manager Functions 10.3 Transactional Resource 10.3.1 The DO-UNDO-REDO Protocol
10.3.2 The Log Table and Log Records
10.3.3. Communication Session Recovery
10.3.4 Value Logging
10.3.5 Logical Logging
10.3.6 Physiological Logging
10.3.7 Physiological Logging Rules: FIX, WAL, and Force-Log-at-Commit
10.3.8 Compensation Log Records
10.3.9 Idempotence of Physiological REDO
10.3.10 Summary 10.4 Two-Phase Commit: Making Computations Atomic 10.4.1 Two-Phase Commit in a Centralized System
10.4.2 Distributed Transactions and Two-Phase Commit 10.5 Summary
10.6 Historical Notes
11.2 Normal Processing 11.2.1 Transaction Identifiers
11.2.2 Transaction Manager Data Structures
11.2.3 MyTrid( ), Status_Transaction( ), Leave_Transaction( ), Resume_Transaction( )
11.2.4 Savepoint Log Records
11.2.5 Begin Work( )
11.2.6 Local Commit_Work( ).
11.2.7 Remote Commit_Work( ): Prepare( ) and Commit( )
11.2.8 Save_Work( ) and Read_Context( )
11.2.9 Rollback_Work( ) 11.3 Checkpoint 11.3.1 Sharp Checkpoints
11.3.2 Fuzzy Checkpoints
11.3.3 Transaction Manager Checkpoint 11.4 System Restart 11.4.1 Transaction States at Restart
11.4.2 Transaction Manager Restart Logic
11.4.3 Resource Manager Restart Logic, Identify( )
11.4.4 Summary of the Restart Design
11.4.5 Independent Resource Managers
11.4.6 The Two-Checkpoint Approach: A Different Strategy
11.4.7 Why Restart Works
11.4.8 Distributed Transaction Resolution: Two Phase Commit at Restart
11.4.9 Accelerating Restart
11.4.10 Other Restart Issues 11.5 Resource Manager Failure and Restart
11.6 Archive Recovery
11.7 Configuring the Transaction Manager 11.7.1 Transaction Manager Size and Complexity 11.8 Summary
12.2 Heterogeneous Commit Coordinators 12.2.1 Closes versus Open Transaction Managers
12.2.2 Interoperating with a Closed Transaction Manager
12.2.3 Writing A Gateway to an Open Transaction Manager
12.2.4 Summary of Transaction Gateways 12.3 Highly Available (Non-Blocking) Commit Coordinators 12.3.1 Heuristic Decisions Resolve Blocked Transaction Commit 12.4 Transfer-of-Commit
12.5 Optimizations of Two-Phase Commit 12.5.1 Read-Only Commit Optimization
12.5.2 Lazy Commit Optimization
12.5.3 Linear Commit Optimization 12.6 Disaster Recovery at a Remote Site 12.6.1 System Pair Takeover
12.6.2 Session Switching at Takeover
12.6.3 Configuration Options: 1-Safe, 2-Safe, and Very Safe
12.6.4 Catch-up After Failure
12.6.5 Summary of System Pair Designs 12.7 Summary
12.8 Historical Notes
PART SIX - Transactional File System: A Sample Resource Manager
13.2 The File System as a Basis for Transactional Durable Storage 13.2.1 External Storage versus Main Memory
13.2.3 Levels of Abstraction in a Transactional File and Database Manager 13.3 Media and File Management 13.3.1 Objects and Operations of the Basic File System
13.3.2 Managing Disk Space
13.3.3 Catalog Management for Low-Level File Systems 13.4 Buffer Management 13.4.1 Functional Principles of the Database Buffer
13.4.2 Implementation Issues of a Buffer Manager
13.4.3 Logging and Recovery from the Buffer's Perspective
13.4.4 Optimizing Buffer Manager Performance 13.5 Exotics 13.5.1 Side Files
13.5.2 Single-Level Storage 13.6 Summary
13.7 Historical Notes
14.2 Mapping Tuples into Pages 14.2.1 Internal Organization of Pages
14.2.2 Free Space Administration in a File
14.2.3 Tuple Identification 14.3 Physical Tuple Management 14.3.1 Physical Representation of Attribute Values
14.3.2 Physical Representation of Short Tuples
14.3.3 Special Aspects of Representing Attribute Values in Tuples
14.3.4 Physical Representation of Long Tuples
14.3.5 Physical Representation of Complex Tuples and Very Long Attributes 14.4 File Organization 14.4.1 Administrative Operations
14.4.2 An Abstract View of Different File Organizations via Scans
14.4.3 Entry-Sequenced Files
14.4.4 System-Sequenced Files
14.4.5 Relative Files
14.4.6 Key-Sequenced Files and Hash Files
14.4.7 Summary 14.5 Exotics 14.5.1 Cluster Files
14.5.2 Partitioned Files
14.5.3 Using Transactions to Maintain the File System
14.5.4 The Tuple-Oriented File System in Current Database Systems 14.6 Summary
15 ACCESS PATHS 15.1 Introduction
15.2 Overview of Techniques to Implement Associative Access Paths 15.2.1 Summary 15.3 Associative Access By Hashing 15.3.1 Folding the Key Value into a Numerical Data Type
15.3.2 Criteria for a Good Hash Function
15.3.3 Overflow Handling in Hash Files
15.3.4 Local Administration of Pages in Hash File
15.3.5 Summary of Associative Access Based of Hashing 15.4 B-Trees 15.4.1 B-Trees: The Basic Idea
15.4.2 Performance Aspects of B-Trees
15.4.3 Synchronization on B-Trees: The Page-Oriented View
15.4.4 Synchronization on B-Trees: The Tuple-Oriented View
15.4.5 Recovering Operations on B-Trees 15.5. Sample Implementation of Some Operations on B-Trees 15.5.1 Declarations of Data Structures Assumed in All Programs 15.5.2 Implementation of the readkey Operation on a B-Tree
15.5.3 Key-Range Locking in a B-Tree
15.5.4 Implementation of the Insert Operation for a B-Tree: The Simple Case
15.5.5 Implementing B-Tree Insert: The Split Case
15.5.6 Summary 15.6 Exotics 15.6.1 Extendible Hashing
15.6.2 The Grid File
15.6.3 Holey Brick B-Trees 15.7 Summary
15.8 Historical Notes
PART SEVEN - System Surveys
16 SURVEY OF TP SYSTEMS 16.1 Introduction
16.2 IMS 16.2.1 Hardware and Operating System Environment
16.2.2 Workflow Model
16.2.3 Program Isolation
16.2.4 Main Storage Databases and Field Calls
16.2.5 Data Sharing
16.2.6 Improved Availability and duplexed systems
16.2.7 DB2
16.2.8 Recent Evolution of IMS 16.3 CICS and LU6.2 16.3.1 CICS Overview
16.3.2 CICS Services
16.3.3. CICS Workflow
16.3.4 CICS Distributed Transaction Processing
16.3.5 LU6.2 16.4 Guardian 90 16.4.1 Guardian: The Operating System and Hardware
16.4.2 Pathway, Terminal Context, and Server Class Management
16.4.3 Transaction Management
16.4.4 Other Interesting Features 16.5 DECdta 16.5.1 ACMS's Three-Ball Workflow Model of Transaction Processing
16.5.2 ACMS Services
16.5.3 ACMS Summary
16.5.4 VMS Transaction Management Support
16.5.5 Summary of DECdta
16.5.6 Reliable Transaction Router (RTR) 16.6 X/Open DTP, OSI-TP, CCR 16.6.1 The Local Case
16.6.2 The Distributed Case: Services and Servers
16.6.3 Summary 16.7 Other Systems 16.7.1 Universal Transaction Manager (UTM)
16.7.3 Encina
16.7.4 Tuxedo 16.8 Summary
PART EIGHT - Addenda


The key to client/server computing.

Transaction processing techniques are deeply ingrained in the fields of databases and operating systems and are used to monitor, control and update information in modern computer systems. This book will show you how large, distributed, heterogeneous computer systems can be made to work reliably. Using transactions as a unifying conceptual framework, the authors show how to build high-performance distributed systems and high-availability applications with finite budgets and risk.

The authors provide detailed explanations of why various problems occur as well as practical, usable techniques for their solution. Throughout the book, examples and techniques are drawn from the most successful commercial and research systems. Extensive use of compilable C code fragments demonstrates the many transaction processing algorithms presented in the book. The book will be valuable to anyone interested in implementing distributed systems or client/server architectures.


No. of pages:
© Morgan Kaufmann 1993
30th September 1992
Morgan Kaufmann
Hardcover ISBN:
eBook ISBN:


Intel Recommended Reading List for Developers, 1st Half 2013 – Books for Software Developers, Intel

Intel Recommended Reading List for Developers, 2nd Half 2013 – Books for Software Developers, Intel

Intel Recommended Reading List for Developers, 1st Half 2014 – Books for Software Developers, Intel

Ratings and Reviews

About the Authors

Jim Gray

Andreas Reuter