Monday, January 4, 2016

Transactions and Concurrency

Transactions

Motivation

  • Provide atomic operations at servers that maintain shared data for clients
  • Provide recoverability from server crashes

Properties (ACID)

  • Atomicity
  • Consistency
  • Isolation
  • Durability

Concurrency Control

Motivation

  • Without concurrency control, we have lost updates, inconsistent retrievals, dirty reads, etc. 
  • Concurrency control schemes are designed to allow two or more transactions to be executed correctly while maintaining serial equivalence
    • Serial Equivalence is correctness criterion
      • Schedule produced by concurrency control scheme should be equivalent to a serial schedule in which transactions are executed one after the other.

Scheme

  • Locking
  • Optimistic concurrency control
  • Time-stamp based concurrency control


Use of Locks in Strict Two-Phase Locking

When an operation accesses an object within a transaction
  • (1) If the object is not already locked, it is locked and the operation proceeds
  • (2) If the object has a conflicting lock set by another transaction, the transaction must wait until it is unlocked
  • (3) If the object has a non-conflicting lock set by another transaction, the lock is shared and the operation proceeds
  • (4) If the object has already been locked in the same transaction, the lock will be promoted if necessary and the operation proceeds
    • When promotion is prevented by a conflicting lock, rule 2 is used


Strict Two-Phase Locking





Deadlock

Example


Resolution of Deadlock

  • Timeout


Optimistic Concurrency Control

Drawback of locking

  • Overhead of lock maintainance
  • Deadlocks
  • Reduced concurrency

Optimistic Concurrency Control

  • In most applications, likelihood of conflicting  accesses by concurrent transaction is low
  • Transactions proceed as though there are no conflicts
  • Three phases
    • Working Phase
      • Transactions read and write private copies of objects
    • Validation phase
      • Each transaction is assigned a transaction number when it enters its phase
    • Update phase

Validation of Transaction




Timestamp Based Concurrency Control

  • Each transaction is assigned a unique timestamp at the moment it starts
    • In distributed transactions, Lamport's timestamps can be used.
  • Every data item has a timestamp
    • Read timestamp = timestamp of transaction that last read the time
    • Write timestamp = timestamp of transaction that most recently changed an item


Timestamp ordering write rule



Concurrency Control for Distributed Transactions

  • Locking
    • Distributed deadlocks possible
  • Timestamp ordering
    • Lamport time stamps

The Two-Phase Commit Protocol





Three Phase Commit

  • Problem with two-phase commit
    • If coordinator crashes, participants cannot reach a decision, stay blocked until coordinator recovers
  • Three-phase commit
    • There is no single state from which it is possible to make a transaction directly to another COMMIT or ABORT state
    • There is not state in which it is not possible to make a final decision, and from which a transaction to COMMIT can be made.

No comments:

Post a Comment