Transaction Processing

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 fra...

(展开全部)

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.

Foreword
Preface
PART ONE - The Basics of Transaction Processing
1 Introduction
1.1 Historical Perspective
1.2 What Is a Transaction Processing System?
· · · · · · (更多)

Foreword
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 SummaryExercisesAnswers
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 DB 2
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
PART EIGHT - Addenda
17 References
18 Data Structures and Interfaces
19 Glossary
Index
· · · · · · (收起)