Transaction Protocols

Posted on

Catalog

  • Concurrency Control
    • Two-phase Locking (2PL)
    • NO_WAIT
    • WAIT_DIE
    • Timestamp Ordering (TIMESTAMP)
    • Multi-version concurrency control (MVCC)
    • Optimistic concurrency control (OCC)
    • Deterministic (CALVIN)
  • Commitment Protocols
    • Two-phase Commit (2PC)

Classify from two views

  • Pessimistic v.s. Optimistic
  • Locked-based v.s. Timestamp-based

Comparison from another view

  • Pessimistic
    • Validate -> Read -> Compute -> Write
  • Optimistic
    • Read -> Compute -> Validate -> Write

2-PL

  • Basic procedures:
    • Expanding (Growing) Phase: lock are acquired
    • Shrinking (Contracting) Phase: lock are released
  • Centralized 2PL: only one scheduler
  • Distributed 2PL: at each site, scheduler handle lock requests at that site

Timestamp Ordering based algorithm

  • In a distributed environment, TS requires globally unique and monotonically increasing
  • A global counter is not easy to maintain and local clock are unsuitable. So, a unique site identifier is needed (e.g., {local time, site indentifier})
  • Based TO:
    • rts(x): largest TO of any read on x, wts(x): largest TO of any write on x
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      for Ri(x):
        if ts(Ti) < wts(x):
        then reject Ri(x)
        else accept Ri(x)
         rts(x) <- ts(Ti)
      for Wi(x):
        if ts(Ti) < rts(x) and ts(Ti) < wts(x):
        then reject Wi(x)
        else accept Wi(x)
         wts(x) <- ts(Ti)

Pitfall

  • Lock vs. Latch
    • Locking mechanism can protect transaction ACID
    • Latching mechanism can protect data structure safe
  • TO (Timestamp ordering) algorithm always will cause a deadlock situation (several transactions wait for each other)
    • However, a intervention from outside is needed
    • Wait-for Graph (has a cycle => deadlock)