Purchase textbook

Transaction Processing,

Edition 1 Concepts and Techniques

Editors: By Jim Gray and Andreas Reuter

Publication Date: 30 Sep 1992

0 Reviews

Ways Of Reading

This e-publication is accessible to the full extent that the file format and types of content allow, on a specific reading device, by default, without necessarily including any additions such as textual descriptions of images or enhanced navigation.

Navigation

The contents of the PDF have been tagged to permit access by assistive technologies as per PDF-UA-1 standard.
Page breaks included from the original print source

Additional Accessibility Information

All (or substantially all) textual matter is arranged in a single logical reading order (including text that is visually presented as separate from the main text flow, e.g., in boxouts, captions, tables, footnotes, endnotes, citations, etc.). Non-textual content is also linked from within this logical reading order. (Purely decorative non-text content can be ignored).
The language of the text has been specified (e.g., via the HTML or XML lang attribute) to optimise text-to-speech (and other alternative renderings), both at the whole document level and, where appropriate, for individual words, phrases or passages in a different language.

Conformance

The publication was certified on 20250625
Accessibility addendum
For detailed accessibility information, see Elsevier’s website at https://www.elsevier.com/about/accessibility
For queries regarding accessibility information, contact [email protected]

Note

This product relies on 3rd party tooling which may impact the accessibility features visible in inspection copies. All accessibility features mentioned would be present in the purchased version of the title.

The key to client/server computing.Transaction processing techniques are deeply ingrained in the fields ofdatabases and operating systems and are used to monitor, control and updateinformation 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 howto build high-performance distributed systems and high-availabilityapplications with finite budgets and risk.

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

About the author

By Jim Gray and Andreas Reuter

Transaction Processing: Concepts and Techniquesby Jim Gray and Andreas ReuterFOREWORD BY BRUCE LINDSAYPREFACEPART ONE - The Basics of Transaction Processing1 INTRODUCTION1.1 Historical Perspective1.2 What Is a Transaction Processing System?1.2.1 The End User's View of a Transaction Processing System1.2.2 The Administrator/Operator's View of a TP System1.2.3 Application Designer's View of a TP System1.2.4 The Resource Manager's View of a TP System1.2.5 TP System Core Services1.3 A Transaction Processing System Feature List1.3.1 Application Development Features1.3.2 Repository Features1.3.3 TP Monitor Features1.3.4 Data Communications Features1.3.5 Database Features1.3.6. Operations Features1.3.7 Education and Testing Features1.3.8 Features Summary1.4 Summary1.5 Historical NotesExercisesAnswers2 BASIC COMPUTER SCIENCE TERMINOLOGY2.1 Introduction2.1.1 Units2.2 Basic Hardware2.2.1 Memories2.2.2 Processors2.2.3 Communications Hardware2.2.4 Hardware Architectures2.3 Basic Software - Address Spaces, Processes, Sessions2.3.1 Address Spaces2.3.2 Processes, Protection Domains, and Threads2.3.3 Messages and Sessions2.4 Generic System Issues2.4.1 Clients and Servers2.4.2 Naming2.4.3 Authentication2.4.4 Authorization2.4.5 Scheduling and Performance2.4.6 Summary2.5 Files2.5.1 File Operations2.5.2 File Organizations2.5.3 Distributed Files2.5.4 SQL2.6 Software Performance2.7 Transaction Processing Standards2.7.1 Portability versus Interoperability Standards2.7.2 APIs and FAPs2.7.3 LU6.2, a de facto Standard2.7.4 OSI-TP with X/Open DTP, a de jure Standard2.8 SummaryExercisesAnswersPART TWO - The Basics of Fault Tolerance3 FAULT TOLERANCE3.1 Introduction3.1.1 A Crash Course in Simple Probability3.1.2 An External View of Fault Tolerance3.2 Definitions3.2.1. Fault, Failure, Availability, Reliability3.2.2 Taxonomy of Fault Avoidance and Fault Tolerance3.2.3 Repair, Failfast, Modularity, Recursive Design3.3 Empirical Studies3.3.1 Outages Are Rare Events3.3.2 Studies of Conventional Systems3.3.3 A Study of Fault-Tolerant System3.4 Typical Module Failure Rates3.5 Hardware Approaches to Fault Tolerance3.5.1 The Basic N-Plex Idea: How to Build Failfast Modules3.5.2 Failfast versus Failvote Voters in an N-Plex3.5.3 N-Plex plus Repair Results in High Availability3.5.4 The Voter's Problem3.5.5 Summary3.6 Software Is the Problem3.6.1 N-Version Programming and Software Fault Tolerance3.6.2 Transactions and Software Fault Tolerance3.6.3 Summary3.7 Fault Modeal and Software Fault Masking3.7.1 An Overview of the Model3.7.2 Building Highly Available Storage3.7.3 Highly Available Processes3.7.4 Reliable Messages via Sessions and Process Pairs3.7.5 Summary of the Process-Message-Storage Model3.8 General Principles3.9 A Cautionary Tale - System Delusion3.10 Summary3.11 Historical NotesExercisesAnswersPART THREE - Transaction-Oriented Computing4 TRANSACTION MODELS4.1 Introduction4.1.1 About this Chapter4.2 Atomic Actions and Flat Transaction4.2.1 Disk Writes as Atomic Actions4.2.2 A Classification of Action Types4.2.3 Flat Transactions4.2.4 Limitations of Flat Transactions4.3 Spheres of Control4.3.1 Definition of Spheres of Control4.3.2 Dynamic Behavior of Spheres of Control4.3.3 Summary4.4 A Notation for Explaining Transaction Models4.4.1 What is Required to Describe Transaction Models?4.4.2 Elements of the Notation4.4.3 Defining Transaction Models by a Set of Simple Rules4.5 Flat Transactions with Savepoints4.5.1 About Savepoints4.5.2 Developing the Rules for the Savepoint Model4.5.3 Persistent Savepoints4.6 Chained Transactions4.7 Nested Transactions4.7.1 Definition of the Nexting Structure4.7.2 Using Nested Transactions4.7.3 Emulating Nested Transactions by Savepoints4.8 Distributed Transactions4.9 Multi-Level Transactions4.9.1 The Role of a Compensating Transaction4.9.2 The Use of Multi-Level Transactions4.10 Open Nested Transactions4.11 Long-Lived transactions4.11.1 Transaction Processing Context4.11.2 The Mini-Batch4.11.3 Sagas4.12 Exotics4.13 Summary4.14 Historical NotesExercisesAnswers5 TRANSACTION PROCESSING MONITORS - An Overview5.1 Introduction5.2 The Role of TP Monitors in Transaction Systems5.2.1 The Transaction -Oriented Computing Style5.2.2 The Transaction Processing Services5.2.3 TP System Process Structure5.2.4 Summary5.3 The Structure of a TP Monitor5.3.1 The TP Monitor Components5.3.2 Components of the Transaction Services5.3.3 TP Monitor Support for the Resource Manager Interfaces5.4 Transactional Remote Procedure Calls: The Basic Idea5.4.1 Who Participates in Remote Procedure Calls?5.4.2 Address Space Structure Required for RPC Handling5.4.3 The Dynamics of Remote Procedure Calls5.4.4 Summary5.5 Examples of the Transaction-Oriented Programming Style5.5.1 The Basic Processing Loop5.5.2 Attaching Resource Managers to Transactions: The Simple Cases5.5.3 Attaching Resource Managers To Transactions: The Sophisticated Case5.5.4 Using Persistent Savepoints5.6 Terminological Wrap-Up5.7 Historical NotesExercisesAnswers6 TRANSACTION PROCESSING MONITORS6.1 Introduction6.2 Transactional Remote Procedures Calls6.2.1 The Resource Manager Interface6.2.2 What the Resource Manager Has to Do in Support of Transactions6.2.3 Interfaces between resource Managers and the TP Monitor6.2.4 Resource Manager Calls versus Resource Manager Sessions6.2.5 Summary6.3. Functional Principles of the TP Monitor6.3.1 The Central Data Structures of the TPOS6.3.2 Data Structures Owned by the TP Monitor6.3.3. A Guided Tour Along the TRPC Path6.3.4 Aborts Racing TRPCs6.3.5 Summary6.4 Managing Request and Response Queues6.4.1 Short-Term Queues for Mapping Resource Manager Invocations6.4.2 Durable Request Queues for Asynchronous Transaction Processing6.4.3 Summary6.5 Other Tasks of the TP Monitor6.5.1 Load Balancing6.5.2 Authentication and Authorization 6.5.3 Restart Processing6.6 Summary6.7 Historical NotesExercisesAnswersPART FOUR - Concurrency Control7 ISOLATION CONCEPTS7.1 Overview7.2 Introduction to Isolation7.3 The Dependency Model of Isolation7.3.1 Static versus Dynamic Allocation7.3.2 Transaction Dependencies7.3.3 The Three Bad Dependencies7.3.4 The Case for a Formal Model of Isolation7.4 Isolation: The Application Programmer's View7.5 Isolation Theorems7.5.1 Actions and Transactions7.5.2 Well-Formed and Two-Phased Transactions7.5.3 Transaction Histories7.5.4 Legal Histories and Lock Compatibility7.5.5 Versions, Dependencies, and the Dependency Graph7.5.6 Equivalent and Isolated Histories: BEFORE, AFTER, and Wormholes7.5.7 Wormholes Are Not Isolated7.5.8 Summary of Definitions7.5.9 Summary of the Isolation Theorems7.6 Degrees of Isolation7.6.1 Degrees of Isolation Theorem7.6.2 SQL and Degrees of Isolation7.6.3 Pros and Cons of Low Degrees of Isolation7.6.4 Exotic SQL Isolation - Read-Past and Notify Locks7.7 Phantoms and Predicate Locks7.7.1 The Problem with Predicate Locks7.8 Granular Locks7.8.1 Three Locking and Intent Lock Modes7.8.2 Update Mode Locks7.8.3 Granular Locking Summary7.8.4 Key-Range Locking7.8.5 Dynamic Key-Range Locks: Previous-Key and Next-Key Locking7.8.6 Key-Range Locks Need DAG Locking7.8.7 The DAG Locking Protocol7.8.8 Formal Definition of Granular Locks on a DAG7.9 Locking Heuristics7.10 Nested Transaction Locking7.11 Scheduling and Deadlock7.11.1 The Convoy Phenomenon7.11.2 Deadlock Avoidance versus Toleration7.11.3 The Wait-for Graph and Deadlock Detector7.11.4 Distributed Deadlock7.11.5 Probability of Deadlock7.12 Exotics7.12.1 Field Calls7.12.2 Escrow Locking and Other Field Call Refinements7.12.3 Optimistic and Timestamp Locking7.12.4 Time Domain Addressing7.13 Summary7.14 Historical NotesExercisesAnswers8 LOCK IMPLEMENTATION8.1 About This Chapter8.1.2 The Need for Parallelism within the Lock Manager8.1.3 The Resource Manager and Lock Manager Address Space8.2 Atomic Machine Instructions8.3 Semaphores8.3.1 Exclusive Semaphores8.3.2 Crabbing: Traversing Shared Data Structures8.3.3 Shared Semaphores8.3.4 Allocating Shared Storage8.3.5 Semaphores and Exceptions8.4 Lock Manager8.4.1 Lock Names8.4.2 Lock Queues and Scheduling8.4.3 Lock Duration and Lock Counts8.4.4 Lock Manager Interface and Data Structures8.4.5 Lock Manager Internal Logic8.4.6 Lock Escalation and Generic Unlock, Notify Locks8.4.7 Transaction Savepoints, Commit, and Rollback8.4.8 Locking at System Restart8.4.9 Phoenix Transactions8.4.10 Lock Manager Configuration and Complexity8.4.11 Lock Manager Summary8.5 Deadlock Detection8.6 Locking for Parallel and Parallel Nested Transactions8.7 Summary8.8 Historical NotesExercisesAnswersPART FIVE- Recovery9 LOG MANAGER9.1 Introduction9.1.1 Uses of the Log9.1.2 Log Manager Overview9.1.3 The Log Manager's Relationship to Other Services9.1.4 Why Have a Log Manager?9.2 Log Tables9.2.1 Mapping the Log Table onto Files9.2.2 Log Sequence Numbers9.3 Public Interface to the Log9.3.1 Authorization to Access the Log Table9.3.2 Reading the Log Table9.3.4 Summary9.4 Implementation Details of Log Reads and Writes9.4.1 Reading the Log9.4.2 Log Anchor9.4.3 Transaction Related Anchors9.4.4 Log Insert9.4.5 Allocate and Flush Log Daemons9.4.6 Careful Writes: Serial of Ping-Pong9.4.7 Group Commit, Batching, Boxcarring9.4.8 WADS Writes9.4.9 Multiple Logs per Transaction Manager9.4.10 Summary9.5 Log Restart Logic9.5.1 Saving the Transaction Manager Anchor9.5.2 Preparing for Restart: Careful Writes of the Log Anchor9.5.3 Finding the Anchor and Log End at Restart9.6 Archiving the Log9.6.1 How Much of the Log Table Should Be Online?9.6.2 Low-Water Marks for Rollback, Restart, Archive9.6.3 Dynamic Logs: Copy Aside versus Copy Forward9.6.4 Archiving the Log Without Impacting Concurrent Transactions9.6.5 Electronic Vaulting and Change Accumulation9.6.6 Dealing with Log Manager-Archive Circularity9.7 Logging in a Client-Server Architecture9.8 Summary9.9 Historical NotesExercisesAnswers10 TRANSACTION MANAGER CONCEPTS10.1 Introduction10.2 Transaction Manager Interfaces10.2.1 The Application Interface to Transactions10.2.2 The Resource Manager Interface to Transactions10.2.3 Transaction Manager Functions10.3 Transactional Resource10.3.1 The DO-UNDO-REDO Protocol10.3.2 The Log Table and Log Records10.3.3. Communication Session Recovery10.3.4 Value Logging10.3.5 Logical Logging10.3.6 Physiological Logging10.3.7 Physiological Logging Rules: FIX, WAL, and Force-Log-at-Commit10.3.8 Compensation Log Records10.3.9 Idempotence of Physiological REDO10.3.10 Summary10.4 Two-Phase Commit: Making Computations Atomic10.4.1 Two-Phase Commit in a Centralized System10.4.2 Distributed Transactions and Two-Phase Commit10.5 Summary10.6 Historical NotesExercisesAnswers11 TRANSACTION MANAGER STRUCTURE11.1 Introduction11.2 Normal Processing11.2.1 Transaction Identifiers11.2.2 Transaction Manager Data Structures11.2.3 MyTrid( ), Status_Transaction( ), Leave_Transaction( ), Resume_Transaction( )11.2.4 Savepoint Log Records11.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 Checkpoint11.3.1 Sharp Checkpoints11.3.2 Fuzzy Checkpoints11.3.3 Transaction Manager Checkpoint11.4 System Restart11.4.1 Transaction States at Restart11.4.2 Transaction Manager Restart Logic11.4.3 Resource Manager Restart Logic, Identify( )11.4.4 Summary of the Restart Design11.4.5 Independent Resource Managers11.4.6 The Two-Checkpoint Approach: A Different Strategy11.4.7 Why Restart Works11.4.8 Distributed Transaction Resolution: Two Phase Commit at Restart11.4.9 Accelerating Restart11.4.10 Other Restart Issues11.5 Resource Manager Failure and Restart11.6 Archive Recovery11.7 Configuring the Transaction Manager11.7.1 Transaction Manager Size and Complexity11.8 SummaryExercisesAnswers12 ADVANCED TRANSACTION MANAGER TOPICS12.1 Introduction12.2 Heterogeneous Commit Coordinators12.2.1 Closes versus Open Transaction Managers12.2.2 Interoperating with a Closed Transaction Manager12.2.3 Writing A Gateway to an Open Transaction Manager12.2.4 Summary of Transaction Gateways12.3 Highly Available (Non-Blocking) Commit Coordinators12.3.1 Heuristic Decisions Resolve Blocked Transaction Commit12.4 Transfer-of-Commit12.5 Optimizations of Two-Phase Commit12.5.1 Read-Only Commit Optimization12.5.2 Lazy Commit Optimization12.5.3 Linear Commit Optimization12.6 Disaster Recovery at a Remote Site12.6.1 System Pair Takeover12.6.2 Session Switching at Takeover12.6.3 Configuration Options: 1-Safe, 2-Safe, and Very Safe12.6.4 Catch-up After Failure12.6.5 Summary of System Pair Designs12.7 Summary12.8 Historical NotesExercisesAnswersPART SIX - Transactional File System: A Sample Resource Manager13 FILE AND BUFFER MANAGEMENT13.1 Introduction13.2 The File System as a Basis for Transactional Durable Storage13.2.1 External Storage versus Main Memory13.2.3 Levels of Abstraction in a Transactional File and Database Manager13.3 Media and File Management13.3.1 Objects and Operations of the Basic File System13.3.2 Managing Disk Space13.3.3 Catalog Management for Low-Level File Systems13.4 Buffer Management13.4.1 Functional Principles of the Database Buffer13.4.2 Implementation Issues of a Buffer Manager13.4.3 Logging and Recovery from the Buffer's Perspective13.4.4 Optimizing Buffer Manager Performance13.5 Exotics13.5.1 Side Files13.5.2 Single-Level Storage13.6 Summary13.7 Historical NotesExercisesAnswers14 THE TUPLE-ORIENTED FILE SYSTEM14.1 Introduction14.2 Mapping Tuples into Pages14.2.1 Internal Organization of Pages14.2.2 Free Space Administration in a File14.2.3 Tuple Identification14.3 Physical Tuple Management14.3.1 Physical Representation of Attribute Values14.3.2 Physical Representation of Short Tuples14.3.3 Special Aspects of Representing Attribute Values in Tuples14.3.4 Physical Representation of Long Tuples14.3.5 Physical Representation of Complex Tuples and Very Long Attributes14.4 File Organization14.4.1 Administrative Operations14.4.2 An Abstract View of Different File Organizations via Scans14.4.3 Entry-Sequenced Files14.4.4 System-Sequenced Files14.4.5 Relative Files14.4.6 Key-Sequenced Files and Hash Files14.4.7 Summary14.5 Exotics14.5.1 Cluster Files14.5.2 Partitioned Files14.5.3 Using Transactions to Maintain the File System14.5.4 The Tuple-Oriented File System in Current Database Systems14.6 SummaryExercisesAnswers15 ACCESS PATHS15.1 Introduction15.2 Overview of Techniques to Implement Associative Access Paths15.2.1 Summary15.3 Associative Access By Hashing15.3.1 Folding the Key Value into a Numerical Data Type15.3.2 Criteria for a Good Hash Function15.3.3 Overflow Handling in Hash Files15.3.4 Local Administration of Pages in Hash File15.3.5 Summary of Associative Access Based of Hashing15.4 B-Trees15.4.1 B-Trees: The Basic Idea15.4.2 Performance Aspects of B-Trees15.4.3 Synchronization on B-Trees: The Page-Oriented View15.4.4 Synchronization on B-Trees: The Tuple-Oriented View15.4.5 Recovering Operations on B-Trees15.5. Sample Implementation of Some Operations on B-Trees15.5.1 Declarations of Data Structures Assumed in All Programs15.5.2 Implementation of the readkey Operation on a B-Tree15.5.3 Key-Range Locking in a B-Tree15.5.4 Implementation of the Insert Operation for a B-Tree: The Simple Case15.5.5 Implementing B-Tree Insert: The Split Case15.5.6 Summary15.6 Exotics15.6.1 Extendible Hashing15.6.2 The Grid File15.6.3 Holey Brick B-Trees15.7 Summary15.8 Historical NotesExercisesAnswersPART SEVEN - System Surveys16 SURVEY OF TP SYSTEMS16.1 Introduction16.2 IMS16.2.1 Hardware and Operating System Environment16.2.2 Workflow Model16.2.3 Program Isolation16.2.4 Main Storage Databases and Field Calls 16.2.5 Data Sharing16.2.6 Improved Availability and duplexed systems16.2.7 DB216.2.8 Recent Evolution of IMS16.3 CICS and LU6.216.3.1 CICS Overview16.3.2 CICS Services16.3.3. CICS Workflow16.3.4 CICS Distributed Transaction Processing16.3.5 LU6.216.4 Guardian 9016.4.1 Guardian: The Operating System and Hardware16.4.2 Pathway, Terminal Context, and Server Class Management16.4.3 Transaction Management16.4.4 Other Interesting Features16.5 DECdta16.5.1 ACMS's Three-Ball Workflow Model of Transaction Processing16.5.2 ACMS Services16.5.3 ACMS Summary16.5.4 VMS Transaction Management Support16.5.5 Summary of DECdta16.5.6 Reliable Transaction Router (RTR)16.6 X/Open DTP, OSI-TP, CCR16.6.1 The Local Case16.6.2 The Distributed Case: Services and Servers16.6.3 Summary16.7 Other Systems16.7.1 Universal Transaction Manager (UTM)16.7.2 ADABAS TPF16.7.3 Encina16.7.4 Tuxedo16.8 SummaryPART EIGHT - Addenda17 REFERENCES18 DATA STRUCTURES AND INTERFACES19 GLOSSARYINDEX

Transaction Processing,

Editors: By Jim Gray and Andreas Reuter

Description

About the author

Related Titles