Week 10: Distributed Transactions

Terms you should know

Paul Krzyzanowski

April 6, 2021

Commit Protocols

  • ACID semantics
  • Transaction Atomicity
  • Transaction Consistency
  • Transaction Isolation/Serializability
  • Transaction Durability
  • Write-ahead log
  • Rollback
  • Transaction manager
  • Transaction coordinator
  • Participants
  • Commit
  • Abort
  • Two-phase commit protocol
    • Role of phase 1
    • Role of phase 2
    • Recovery coordinator
    • Failure assumptions
  • Three-phase commit protocol
    • Purpose
    • Role of phases 1, 2, 3
    • Recovery coordinator possibility
    • Problems with the protocol
  • Brewer’s CAP theorm - what does it show?
  • Eventual consistency
    • Why would we want it?

Concurrency Control

  • Purpose of concurrency control
  • Schedule
  • Pessimistic vs. optimistic concurrency control
  • Two-phase locking protocol (2PL)
    • Role of phases
    • What does the protocol accomplish?
  • Strong strict two-phase locking (SS2PL)
    • How does it differ from two-phase locking?
    • What is the advantage over two-phase locking?
    • What is the disadvantage over two-phase locking?
  • Exclusive vs. shared locks
  • Two-version-based concurrency control
    • How does locking differ from SS2PL?
    • What is a commit lock?
  • Timestamp ordering
    • What does it require?
    • How does it work?
  • Multiversion concurrency control (MVCC)
    • Is it optimistic or pessimistic?
    • How are timestamps used?
    • How does it work?

Deadlock

  • What is deadlock?
  • Understand the four conditions for deadlock
  • Wait-for graph (WFG)
  • Centralized detection
  • What causes phantom (false) deadlock?
  • Chandy-Misra-Haas distributed deadlock detection
    • What is a probe?
    • What is edge chasing?
    • How do you know you have deadlock?
  • Wait-die and wound-wait algorithms
    • What is the goal of each?

Google Spanner

  • Consistency model
  • Commit protocol used
  • Spanserver role
  • Zonemaster role
  • Concurrency control mechanisms used
  • Snapshot reads
  • External consistency
  • TrueTime API
  • What is TT.now().earliest?
  • What is TT.now().latest?
  • What is the purpose of a commit wait?
  • How does the CAP theorem apply to Spanner?
Last modified April 7, 2021.
recycled pixels