Concepts and Techniques To order this title, and for more information, click here
By Jim Gray Andreas Reuter
Description 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.
Contents
Transaction Processing: Concepts and Techniques by Jim Gray and Andreas Reuter
FOREWORD BY BRUCE LINDSAY PREFACE
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 Exercises Answers
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 Exercises Answers
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 Exercises Answers
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 Exercises Answers
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 Exercises Answers
6 TRANSACTION PROCESSING MONITORS
6.1 Introduction 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 Exercises
Answers
PART FOUR - Concurrency Control
7 ISOLATION CONCEPTS
7.1 Overview 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 Exercises Answers
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 Exercises Answers
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 Exercises Answers
10 TRANSACTION MANAGER
CONCEPTS
10.1 Introduction 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 Exercises Answers
11 TRANSACTION MANAGER STRUCTURE
11.1 Introduction 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 Exercises Answers
12 ADVANCED
TRANSACTION MANAGER TOPICS
12.1 Introduction 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 Exercises Answers
PART
SIX - Transactional File System: A Sample Resource Manager
13 FILE AND BUFFER MANAGEMENT
13.1 Introduction
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 Exercises Answers
14 THE TUPLE-ORIENTED FILE SYSTEM
14.1
Introduction 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 Exercises Answers
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 Exercises Answers
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.2 ADABAS TPF 16.7.3 Encina 16.7.4
Tuxedo
16.8 Summary
Books and book related electronic products are priced in euro (EUR), and Great Britain Pounds (GBP) and US dollars (USD). EUR prices apply in Europe. GBP prices apply to the UK. USD prices apply to the Americas, Asia Pacific and the rest of the world.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company