Concurrency Control Techniques

Concurrency Control Techniques

Introduction

  • Concurrency control protocols: Set of rules to guarantee serializability.
  • Two-phase locking protocols: Lock data items to prevent concurrent access.
  • Timestamp: Unique identifier for each transaction.
  • Multiversion currency control protocols: Use multiple versions of a data item.
  • Validation or certification of a transaction.

21.1 Two-Phase Locking Techniques for Concurrency Control

  • Lock: Variable associated with a data item describing status for operations that can be applied.
  • One lock for each item in the database.
  • Binary locks:
    • Two states (values).
    • Locked (1): Item cannot be accessed.
    • Unlocked (0): Item can be accessed when requested.
  • Transaction requests access by issuing a lock_item(X) operation.
  • Lock table specifies items that have locks.
  • Lock manager subsystem:
    • Keeps track of and controls access to locks.
  • Rules enforced by lock manager module:
    • At most one transaction can hold the lock on an item at a given time.
    • Binary locking too restrictive for database items.
  • Shared/exclusive or read/write locks
    • Read operations on the same item are not conflicting
    • Must have exclusive lock to write
  • Three locking operations
    • read_lock(X)
    • write_lock(X)
    • unlock(X)
  • Lock conversion
    • Transaction that already holds a lock allowed to convert the lock from one state to another
    • Upgrading
      • Issue a read_lock operation then a write_lock operation
    • Downgrading
      • Issue a read_lock operation after a write_lock operation

Guaranteeing Serializability by Two-Phase Locking

  • Two-phase locking protocol
    • All locking operations precede the first unlock operation in the transaction
  • Phases
    • Expanding (growing) phase
      • New locks can be acquired but none can be released
      • Lock conversion upgrades must be done during this phase
    • Shrinking phase
      • Existing locks can be released but none can be acquired
      • Downgrades must be done during this phase
  • If every transaction in a schedule follows the two-phase locking protocol, schedule guaranteed to be serializable
  • Two-phase locking may limit the amount of concurrency that can occur in a schedule
  • Some serializable schedules will be prohibited by two-phase locking protocol

Variations of Two-Phase Locking

  • Basic 2PL
    • Technique described on previous slides
  • Conservative (static) 2PL
    • Requires a transaction to lock all the items it accesses before the transaction begins
    • Predeclare read-set and write-set
    • Deadlock-free protocol
  • Strict 2PL
    • Transaction does not release exclusive locks until after it commits or aborts
  • Rigorous 2PL
    • Transaction does not release any locks until after it commits or aborts
  • Concurrency control subsystem responsible for generating read_lock and write_lock requests
  • Locking generally considered to have high overhead

Dealing with Deadlock and Starvation

  • Deadlock
    • Occurs when each transaction T in a set is waiting for some item locked by some other transaction T’
    • Both transactions stuck in a waiting queue
  • Deadlock prevention protocols
    • Every transaction locks all items it needs in advance
    • Ordering all items in the database
    • Transaction that needs several items will lock them in that order
    • Both approaches impractical
    • Protocols based on a timestamp
      • Wait-die
      • Wound-wait
  • No waiting algorithm
    • If transaction unable to obtain a lock, immediately aborted and restarted later
  • Cautious waiting algorithm
    • Deadlock-free
  • Deadlock detection
    • System checks to see if a state of deadlock exists
    • Wait-for graph
  • Victim selection
    • Deciding which transaction to abort in case of deadlock
  • Timeouts
    • If system waits longer than a predefined time, it aborts the transaction
  • Starvation
    • Occurs if a transaction cannot proceed for an indefinite period of time while other transactions continue normally
    • Solution: first-come-first-served queue

21.2 Concurrency Control Based on Timestamp Ordering

  • Timestamp
    • Unique identifier assigned by the DBMS to identify a transaction
    • Assigned in the order submitted
    • Transaction start time
  • Concurrency control techniques based on timestamps do not use locks
    • Deadlocks cannot occur
  • Generating timestamps
    • Counter incremented each time its value is assigned to a transaction
    • Current date/time value of the system clock
    • Ensure no two timestamps are generated during the same tick of the clock
  • General approach
    • Enforce equivalent serial order on the transactions based on their timestamps
  • Timestamp ordering (TO)
    • Allows interleaving of transaction operations
    • Must ensure timestamp order is followed for each pair of conflicting operations
    • Each database item assigned two timestamp values
      • read_TS(X)
      • write_TS(X)
  • Basic TO algorithm
    • If conflicting operations detected, later operation rejected by aborting transaction that issued it
    • Schedules produced guaranteed to be conflict serializable
    • Starvation may occur
  • Strict TO algorithm
    • Ensures schedules are both strict and conflict serializable
  • Thomas’s write rule
    • Modification of basic TO algorithm
    • Does not enforce conflict serializability
    • Rejects fewer write operations by modifying checks for write_item(X) operation

21.3 Multiversion Concurrency Control Techniques

  • Several versions of an item are kept by a system
  • Some read operations that would be rejected in other techniques can be accepted by reading an older version of the item
  • Maintains serializability
  • More storage is needed
  • Multiversion currency control scheme types
    • Based on timestamp ordering
    • Based on two-phase locking
    • Validation and snapshot isolation techniques
  • Multiversion technique based on timestamp ordering
    • Two timestamps associated with each version are kept
      • read_TS(Xi)
      • write_TS(Xi)
  • Multiversion two-phase locking using certify locks
    • Three locking modes: read, write, and certify

21.4 Validation (Optimistic) Techniques and Snapshot Isolation Concurrency Control

  • Optimistic techniques
    • Also called validation or certification techniques
    • No checking is done while the transaction is executing
    • Updates not applied directly to the database until finished transaction is validated
    • All updates applied to local copies of data items
    • Validation phase checks whether any of transaction’s updates violate serializability
    • Transaction committed or aborted based on result
  • Concurrency Control Based on Snapshot Isolation
    • Transaction sees data items based on committed values of the items in the database snapshot
    • Does not see updates that occur after transaction starts
    • Read operations do not require read locks
    • Write operations require write locks
    • Temporary version store keeps track of older versions of updated items
    • Variation: serializable snapshot isolation (SSI)

21.5 Granularity of Data Items and Multiple Granularity Locking

  • Size of data items known as granularity
    • Fine (small)
    • Coarse (large)
  • Larger the data item size, lower the degree of concurrency permitted
    • Example: entire disk block locked
  • Smaller the data item size, more locks required
    • Higher overhead
  • Best item size depends on transaction type
  • Multiple Granularity Level Locking
    • Lock can be requested at any level
    • Intention locks are needed
    • Transaction indicates along the path from the root to the desired node, what type of lock (shared or exclusive) it will require from one of the node’s descendants
    • Intention lock types
      • Intention-shared (IS)
        • Shared locks will be requested on a descendant node
      • Intention-exclusive (IX)
        • Exclusive locks will be requested
      • Shared-intension-exclusive (SIX)
        • Current node is locked in shared mode but one or more exclusive locks will be requested on a descendant node
    • Multiple granularity locking (MGL) protocol rules

21.6 Using Locks for Concurrency Control in Indexes

  • Two-phase locking can be applied to B-tree and B+ -tree indexes
  • Nodes of an index correspond to disk pages
  • Holding locks on index pages could cause transaction blocking
  • Other approaches must be used
    • Conservative approach
      • Lock the root node in exclusive mode and then access the appropriate child node of the root
    • Optimistic approach
      • Request and hold shared locks on nodes leading to the leaf node, with exclusive lock on the leaf
    • B-link tree approach
      • Sibling nodes on the same level are linked at every level
      • Allows shared locks when requesting a page
      • Requires lock be released before accessing the child node

21.7 Other Concurrency Control Issues

  • Insertion
    • When new data item is inserted, it cannot be accessed until after operation is completed
  • Deletion operation on the existing data item
    • Write lock must be obtained before deletion
  • Phantom problem
    • Can occur when a new record being inserted satisfies a condition that a set of records accessed by another transaction must satisfy
    • Record causing conflict not recognized by concurrency control protocol
  • Interactive transactions
    • User can input a value of a data item to a transaction T based on some value written to the screen by transaction T′, which may not have committed
    • Solution approach: postpone output of transactions to the screen until committed
  • Latches
    • Locks held for a short duration
    • Do not follow usual concurrency control protocol

21.8 Summary

  • Concurrency control techniques
    • Two-phase locking
    • Timestamp-based ordering
    • Multiversion protocols
    • Snapshot isolation
  • Data item granularity
  • Locking protocols for indexes
  • Phantom problem and interactive transaction issues