On Transactional Concurrency Control

On Transactional Concurrency Control

by Goetz Graefe, H. V. Jagadish
Released June 2019
Publisher(s): Morgan & Claypool Publishers
ISBN: 9781681735498

Explore a preview version of On Transactional Concurrency Control right now.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from 200+ publishers.

Start your free trial

Book description

This book contains a number of chapters on transactional database concurrency control.

A two-sentence summary of the volume's entire sequence of chapters is this: traditional locking techniques can be improved in multiple dimensions, notably in lock scopes (sizes), lock modes (increment, decrement, and more), lock durations (late acquisition, early release), and lock acquisition sequence (to avoid deadlocks). Even if some of these improvements can be transferred to optimistic concurrency control, notably a fine granularity of concurrency control with serializable transaction isolation including phantom protection, pessimistic concurrency control is categorically superior to optimistic concurrency control, i.e., independent of application, workload, deployment, hardware, and software implementation.

Table of contents

  1. On Transactional Concurrency Control
    1. Published Papers
      1. A Survey of B-Tree Locking Techniques (ACM TODS 2010)
      2. Hierarchical Locking in B-Tree Indexes (BTW Keynote 2007)
      3. Transaction Support for Indexed Views (ACM SIGMOD 2004)
      4. Controlled Lock Violation (ACM SIGMOD 2013)
      5. Orthogonal Key-Value Locking (BTW 2015 and Extended Draft 2019)
    2. Optimistic Concurrency Control
      1. Orthogonal Key-Value Validation
      2. Serializable Timestamp Validation
      3. Repairing Optimistic Concurrency Control
    3. Locking
      1. Avoiding Index Navigation Deadlocks
      2. Two-Phase Commit
      3. Deferred Lock Enforcement
    4. The End of Optimistic Concurrency Control (1/2)
    5. The End of Optimistic Concurrency Control (2/2)
  2. Published Papers
    1. A Survey of B-Tree Locking Techniques
      1. Introduction
        1. Historical Background
        2. Overview
      2. Preliminaries
      3. Two Forms of B-Tree Locking
        1. Locks and Latches
        2. Recovery and B-Tree Locking
        3. Lock-Free B-Trees
        4. Summary
      4. Protecting a B-Tree's Physical Structure
        1. Issues
        2. Lock Coupling
        3. Blink-Trees
        4. Load Balancing and Reorganization
        5. Summary
      5. Protecting a B-Tree's Logical Contents (1/3)
      6. Protecting a B-Tree's Logical Contents (2/3)
      7. Protecting a B-Tree's Logical Contents (3/3)
        1. Key Range Locking
        2. Key Range Locking and Ghost Records
        3. Key Range Locking as Hierarchical Locking
        4. Locking in Nonunique Indexes
        5. Increment Lock Modes
        6. Summary
      8. Future Directions
      9. Summary and Conclusions
      10. References
    2. Hierarchical Locking in B-Tree Indexes
      1. Introduction
        1. Problem Overview
        2. Solution Overview
      2. Related Work
        1. Related Work on Multi-Granularity Locking
        2. Related Work on Key Range Locking
      3. Assumptions
      4. Traditional Locking Hierarchies
        1. Locks on Keys and Ranges
        2. Key Insertion Using Ghost Records
        3. Splitting and Merging Key Ranges
        4. Summary
      5. Locks on Separator Keys (1/2)
      6. Locks on Separator Keys (2/2)
        1. Techniques
        2. Advantages
        3. Disadvantages
        4. Opportunities
        5. Summary
      7. Locks on Key Prefixes
        1. Techniques
        2. Advantages
        3. Disadvantages
        4. Opportunities
        5. Summary
      8. Summary and Conclusions
      9. References
    3. Concurrent Queries and Updates in Summary Views and Their Indexes
      1. Introduction
        1. Serializable View Maintenance
        2. Contributions
        3. Overview
      2. Prior Work (1/4)
      3. Prior Work (2/4)
      4. Prior Work (3/4)
      5. Prior Work (4/4)
        1. Deltas for Materialized Views
        2. Concurrency Control for Materialized Views
        3. Multi-Level Transactions and Aries
        4. Concurrent Update Techniques
        5. Snapshot Isolation and Multi-Version Concurrency Control
        6. Derived Lock Modes
        7. Lock Escalation and De-Escalation
        8. Transaction Save Points
        9. Local Commit Processing
        10. Two-Phase Commit
        11. Managing Individual Records and Keys
        12. Online Index Operations
        13. Duplicate Records and Keys
        14. Incremental View Maintenance
        15. Expanded ``Group by'' Clauses
      6. Multi-Version Snapshot Isolation
      7. Concurrent Updates and Linear Version History (1/2)
      8. Concurrent Updates and Linear Version History (2/2)
        1. Multiple Records per Summary Row
        2. Multiple Delta Records per Summary Row
        3. Deferred Actions and Virtual Log Records
        4. Commit-Time-Only Locks
        5. Commit Processing
        6. Transaction Abort
        7. Transaction Save Points
        8. Two-Phase Commit
      9. Logging and Recovery (1/2)
      10. Logging and Recovery (2/2)
        1. Transaction Abort
        2. Partial Rollback for Save Points
        3. Transaction Commit
        4. System and Media Recovery
        5. Failures and Transaction Abort During Commit Processing
        6. Two-Phase Commit
        7. Optimistic Concurrency Control
      11. Multi-Granularity Locking
        1. Derived Lock Types
        2. Interpretation of the Lock Table
        3. Commit Processing with Intention Locks
      12. Update and Upgrade Locks
      13. Insert and Delete
        1. Escrow Locks and Key Range Locking
        2. Record Creation by System Transactions
        3. Locking and Logging in System Transactions
      14. Online Index Operations
      15. Correctness
      16. Performance
      17. Summary and Conclusions
      18. References
    4. Controlled Lock Violation
      1. Introduction
      2. Related Prior Work (1/2)
      3. Related Prior Work (2/2)
        1. Main Memory Databases
        2. Early Lock Release in Shore-MT
        3. Early Lock Release in Foster B-Trees
        4. Other Cases of Early Lock Release
        5. Distributed Commit
      4. Controlled Lock Violation (1/2)
      5. Controlled Lock Violation (2/2)
        1. Principles
        2. Approach
        3. Implementation Techniques
        4. Comparison with Early Lock Release
        5. Combined Locks
        6. Weak Transaction Isolation Levels
        7. Summary
      6. Distributed Transactions
        1. Implementation of Commit Dependencies
        2. Performance Effects
        3. Summary
      7. Canned Transactions
      8. Performance Evaluation
        1. Implementation
        2. Results
      9. Discussion
      10. Summary and Conclusions
      11. Acknowledgements
      12. References
    5. Orthogonal Key-Value Locking
      1. Introduction
        1. Motivation
        2. Concurrency Control and Lock Scopes
        3. Design Goals
        4. Outline
      2. Prior Designs (1/2)
      3. Prior Designs (2/2)
        1. History of Locking in B-Trees
        2. ARIES/KVL ``Key-Value Locking''
        3. ARIES/IM ``Index Management''
        4. SQL Server Key-Range Locking
        5. Orthogonal Key-Range Locking
        6. Summary of Prior Designs
      4. Orthogonal Key-Value Locking (1/3)
      5. Orthogonal Key-Value Locking (2/3)
      6. Orthogonal Key-Value Locking (3/3)
        1. Design Goals
        2. Orthogonality
        3. Partitioned Lists
        4. Partitioned Gaps
        5. Lock Manager Implementation
        6. Unique Secondary Indexes
        7. Primary Indexes
        8. Master-Detail Clustering
        9. Summary of Orthogonal Key-Value Locking
      7. Case Studies (1/3)
      8. Case Studies (2/3)
      9. Case Studies (3/3)
        1. Empty Queries–Phantom Protection
        2. Successful Equality Queries
        3. Phantom Protection with Ghost Records
        4. Range Queries
        5. Non-Key Updates
        6. Deletions
        7. Insertions
        8. Key Updates
        9. Non-Unique Primary Indexes
        10. Summary of the Case Studies
      10. Future Opportunities (1/2)
      11. Future Opportunities (2/2)
        1. Column-Level Locking
        2. Orthogonal Row Locking
        3. Orthogonal Locking in Tables and Indexes
        4. Orthogonal Schema Locking
        5. Summary of Future Opportunities
      12. Conclusions
      13. References
  3. Optimistic Concurrency Control
    1. Orthogonal Key-Value Validation
      1. Introduction
      2. Related Prior Work (1/3)
      3. Related Prior Work (2/3)
      4. Related Prior Work (3/3)
        1. Two-Phase Locking
        2. Transaction Isolation Levels
        3. Ghost Records
        4. System Transactions
        5. Orthogonal Key-Value Locking
        6. A Brief Comparison of Locking Techniques
        7. Optimistic Concurrency Control
        8. Summary of Related Prior Work
      5. Orthogonal Key-Value Validation (1/2)
      6. Orthogonal Key-Value Validation (2/2)
        1. Read- and Write-Sets
        2. Ghost Records and System Transactions
        3. User Transactions
        4. Phantom Protection
        5. Integrity Constraints
        6. Transaction Isolation Levels
        7. Hierarchical and Multi-Granularity Concurrency Control
        8. Beyond B-Tree Indexes
        9. Summary of the Design
      7. Case Studies (1/2)
      8. Case Studies (2/2)
        1. Queries with Empty Results–Phantom Protection
        2. Successful Equality Queries
        3. Range Queries
        4. Non-Key Updates
        5. Deletions
        6. Insertions
        7. Key Updates
        8. Summary of the Case Studies
      9. Alternative Approaches
      10. Conclusions
      11. References
    2. Serializable Timestamp Validation
      1. Introduction
      2. Related Prior Work (1/2)
      3. Related Prior Work (2/2)
        1. Ghost Records and System Transactions
        2. Multi-Version Storage and Snapshot Isolation
        3. Traditional Locking
        4. Orthogonal Key-Value Locking
        5. A Quick Comparison
        6. Optimistic Concurrency Control
        7. Timestamp Validation
        8. Summary of Related Prior Work
      4. Phantom Protection with Timestamp Validation (1/2)
      5. Phantom Protection with Timestamp Validation (2/2)
        1. Basic Designs
        2. Technology Transfers from Traditional Locking Techniques
        3. Orthogonal Key-Value Timestamp Validation
        4. Summary of Timestamp Validation with Phantom Protection
      6. Management of Timestamps
        1. Compressing Timestamps
        2. Caching Timestamps
        3. Timestamp Validation in Databases Without Timestamps
        4. Client-Server Database Storage
        5. Summary of Timestamp Management
      7. Hierarchical Timestamps
      8. Conclusions
      9. References
    3. Repairing Optimistic Concurrency Control
      1. Introduction
      2. Related Prior Work (1/2)
      3. Related Prior Work (2/2)
        1. Traditional Optimistic Concurrency Control
        2. Locking Techniques
        3. Two-Phase Commit
        4. Controlled Lock Violation
        5. Summary of Related Prior Work
      4. Concurrent Validation
        1. The Need for Concurrent Validation
        2. Simple and Efficient Concurrent Validation
        3. Summary of Concurrent Validation
      5. Premature Publication
        1. The Danger of Premature Publication
        2. Optimistic Transactions Without Premature Publication
        3. Summary of Premature Publication
      6. Distributed Transactions
        1. Two-Phase Commit
        2. Three-Phase Commit and Controlled Lock Violation
        3. Summary of Distributed Transactions
      7. Conclusions
      8. References
  4. Locking
    1. Avoiding Index-Navigation Deadlocks
      1. Introduction
      2. Related Prior Work (1/2)
      3. Related Prior Work (2/2)
        1. Ghost Records and System Transactions
        2. ARIES/KVL ``Key-Value Locking''
        3. ARIES/IM ``Index Management''
        4. Orthogonal Key-Value Locking
        5. A Brief Comparison of Locking Techniques
        6. Summary of Related Prior Work
      4. Recommended Locking Sequences
        1. New Techniques
        2. Examples
        3. Effects
      5. Conclusions
      6. References
    2. A Problem in Two-Phase Commit
      1. References
    3. Deferred Lock Enforcement
      1. Introduction
      2. Related Prior Work (1/2)
      3. Related Prior Work (2/2)
        1. Multi-Version Storage
        2. Transaction-Private Update Buffers
        3. Update Locks and Intention Locks
        4. Orthogonal Key-Value Locking
        5. Early Lock Release and Controlled Lock Violation
        6. Summary of Related Prior Work
      4. Deferred Lock Acquisition
        1. Transaction-Private Update Buffers
        2. Lock Timing and Semantics
        3. Integration with Multi-Version Storage
        4. Summary of Deferred Lock Acquisition
      5. Deferred Lock Enforcement (1/2)
      6. Deferred Lock Enforcement (2/2)
        1. Lock Semantics and Transitions
        2. Integration with Controlled Lock Violation
        3. Integration with Multi-Version Storage
        4. Transaction Commit Logic
        5. Summary of Deferred Lock Enforcement
      7. Deferred Lock Enforcement and Other Techniques (1/3)
      8. Deferred Lock Enforcement and Other Techniques (2/3)
      9. Deferred Lock Enforcement and Other Techniques (3/3)
        1. System Transactions
        2. Weak Transaction Isolation Levels
        3. Integration with Hierarchical Locking
        4. Lock Escalation and De-Escalation
        5. Increment/Decrement Locks
        6. Deadlocks
        7. Transaction Rollback
        8. Instant Recovery
        9. Optimistic Concurrency Control
        10. Summary of Deferred Lock Enforcement with Other Techniques
      10. Distributed Operations
        1. Transaction Commit Logic
        2. Log Shipping and Replication
        3. Summary of Distributed Operations
      11. Summary and Conclusions
      12. References
  5. The End of Optimistic Concurrency Control
    1. The End of Optimistic Concurrency Control
      1. Introduction
      2. Earlier Comparisons
      3. Common Misconceptions
      4. Locking in Optimistic Concurrency Control
      5. Advantage: Locking
      6. Another Quick Look at Optimistic Concurrency Control
      7. Recommendations
      8. Conclusions
      9. References
    2. Author's Biography

Product information

  • Title: On Transactional Concurrency Control
  • Author(s): Goetz Graefe, H. V. Jagadish
  • Release date: June 2019
  • Publisher(s): Morgan & Claypool Publishers
  • ISBN: 9781681735498