Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Distributed Transaction

Avatar for biaobiaoqi biaobiaoqi
August 26, 2013

Distributed Transaction

Learning note for Distributed System Concepts and Design 5th.

Avatar for biaobiaoqi

biaobiaoqi

August 26, 2013
Tweet

Other Decks in Technology

Transcript

  1. Outline •  Flat and Nested Distributed Transactions •  Atomic Commit

    Protocols •  Concurrency Control in Distributed Transaction •  Deadlock Detection
  2. Distributed  Transactions •  Flat Transaction •  Nested Transaction •  Distributed

    Transaction: a flat or nested transaction that accesses objects managed by multiple servers.
  3. Coordinator •  Roles o  Client, Coordinator, Participant •  Requests o 

    openTransaction, closeTransaction •  Join o  a new participant joins the transaction
  4. Atomic  Commit  Protocols •  Atomicity o  It requires that the

    servers participating in a distributed transaction either all commit it or all abort it. •  One-phase atomic commit protocol o  Coordinator to communicate the commit or abort request to all participants in the transaction and to keep on repeating the request until all have carried it out. o  It does not allow a server to make a decision to abort a transaction: •  Deadlock •  Optimistic concurrency control, validation phase failes •  Server crash
  5. 2  Phase  Commit  Protocol •  Goal: o  Designed to allow

    any participant to abort its part of a transaction. •  1st phase(voting phase) o  Coordinator sends a canCommit? Request to all participants. o  Each participant votes Yes/No(committed/aborted) to coordinator.(back up in permanent storage) •  2nd phase(completion phase) o  Coordinator collects votes and make decision. o  Participants votes YES wait for doCommit or doAbbort request. If it’s commit case, participants make haveCommited call as confirmation.
  6. 2PC  Failure  Model •  No Byzantine faults o  It’s assumed

    that an underlying protocol removes corrupt and duplicated messages •  Consensus cannot be reached in an asynchronous system if process sometimes fails. o  Process recovery from permanent storage and information held by other processes.
  7. Timeout  Action  in  2PC •  Uncertain state for participant o 

    After participant reply canCommit request, and waits for a long o  Causes •  Server crash or delayed messages. o  Resolution •  Participant sends getDecision request to coordinator, asking coordinator for decision on a transaction after some delay. •  Uncertain state for coordinator o  Coordinator waits for canCommit reply for a long time o  Causes •  Participants crash or delayed messages o  Resolution •  Coordinator sends doAbort request
  8. Performance  of  2PC •  Time costs o  If all goes

    well: 3N (haveCommited process are not counted) •  Blocking commit protocol o  à3-phase commit protocol •  Availability of single-node
  9. 2PC  for  Nested   Transactions •  Relationship o  Parent transaction

    :coordinator o  Child sub-transaction :automatically joins parent •  Dependencies: o  Parent aborts à child will be forced abort o  Child aborts à parent can even commit(determined by business logic) •  Provisionally commit != prepared to commit
  10. Example 1 2 T 11 T 12 T 22 T

    21 abort (at M) provisional commit (at N) provisional commit (at X) aborted (at Y) provisional commit (at N) provisional commit (at P) T T T
  11. Hierarchic  and  flat  2PC •  Hierarchic 2PC o  Multi-level nested

    protocol o  Parent sends canCommit to immediate children, and so on down the tree. o  Disadvantage •  Involves passing a series of messages down and up the tree •  Flat 2PC o  Coordinator of top-level transaction sends canCommit messages to all subtransacitons. o  Disadvantage •  Need to have the abort list in order to eliminate transactions whose parents have aborted.
  12. Concurrency  Control  in   Distributed  Transaction •  Concurrency Control o 

    Each sever applies local concurrency control; o  globally serialized is also needed. •  3 Kinds o  Locking o  Timestamp Ordering o  Optimistic Concurrency Control
  13. Locking •  Locks on an object are held locally. • 

    It cannot release any locks until it knows that the transaction has been committed or aborted at all the servers involved in the transaction. •  Distributed deadlock
  14. Timestamp  ordering •  Globally unique timestamps are needed. •  Same

    ordering of transactions can be achieved at all the servers. <local timestamp, server-id> is used, in which server-id is less significant. •  Timestamps can be kept roughly synchronized through all coordinators by the use of synchronized local physical clocks
  15. Optimistic  Concurrency  Control •  Optimistic o  The likelihood of two

    clients’ transactions accessing the same object is low. •  3 Phase o  Working Phase •  Tentative version. o  Validation Phase •  Often executed in critical section •  After closeTransaction request is received. •  If validation fails, abort some transaction. o  Update Phase: •  Often executed in critical section •  Tentative versions are made permanent. •  Validation takes place during the first phase of the two-phase commit protocol.
  16. Deadlock •  PAID: Prevent, Avoid, Ignore, Detect •  Deadlock detection:

    find cycles in wait-for graph •  Simple solution: centralized deadlock detection. o  Poor availability, Lack of fault tolerance o  No ability to scale o  Transmission of local wait-for graphs is high •  Phantom deadlocks •  Edge chasing/path pushing o  Global wait-for graph is not constructed o  Forwarding messages called probes to find cycles
  17. Edge-­‐‑chasing  Algorithm •  1.Initiation o  When a server notes transaction

    T starts waiting for transaction U, where U is waiting to access an object at another server, it sending a probe containing the edge <T à U> to the server of U. •  2.Detection o  Detection consists of receiving probes o  whether a deadlock has occurred o  whether to forward the probes. •  3.Resolution o  When a cycle is detected, a transaction in the cycle is aborted to break the deadlock.