• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

SkeenNonblockingCommit

Page history last edited by PBworks 16 years, 11 months ago

Paper

  •  commit protocol: preserving atomicity across multiple sites
  • termination protocol: invoked when the occurence of site failures render the continued execution of the commit protocol impossible
  • recovery protocols: used by failed sites to resume transaction processing
  • global state: state of all local sites and outstanding network messages
  • committable: if all sites have voted yes on the transaction
  • concurrency set: given state of site i, you can derive the states of other sites
  • nonblocking protocols always have more than one committable state?
  • central site model
    • there is a single coordinator
    • all other participants are slaves
    • slaves only communicate with coordinator
    • coordinator sends same messages to all slaves, they respond
    • synchronous within one state transition
  • decentralized
    • each site is equal
    • every site uses same protocol
    • every sites communicates with every other
  • non blocking if
    • there exists no state such that it's concurrency set contains both and abort and commit
    • there existsno noncommittable state whose concurrency set contains a commit
  •  

 

Lecture

 

  • problem: multi-site T: substransaction on each site, sites can reply DONE, user says COMMIT, how does everyone see the same thing?
  • Mohan model: xact manager: does 2PC during normal operation, recover process when things go wrong
  • recover from: in doubt transactions (after a subordinate crash), termination protocol (COMMIT/ABORT for coordinator)
  • classic 2PC:
    • user -> coord: COMMIT
    • coord -> subord: PREPARE
    • subord -> coord: send YES or NO vote after forcing that decision to disk
    • cord -> log: force the decision given votes. This commits the transaction
    • cord -> subord: decision to subord (COMMIT/ABORT)
    • subord -> cord: ACK
    • cord -> disk: end You can forget about the transaction
  • failurehandling in basic 2PC
    • coordinator hands T to recover process if a subord fails while in a prepared state
    • subord hands T to recovery process if coord fails after saying PREPARE
    • crash recovery also hands in-flight T to recovery process
    • recovery process periodicly tries to finish
      • ask coord the outcome of Ts
      • notify non-ACK'd subords about the outcome
      • if no info found, you can send abort
  • goals for commit protocol:
    • atomicity in with failures
    • "forget" T fairly quickly
    • minimizing logging (esp. forces)
    • maximize opportunity for independent decision making (unilateral aborts)
    • good behavior for read-only T
    • tree of processes
  •  hierarchical tree:
    • coor -> sub -> leaf: PREPARE
    • leaf -> sub: READ
    • sub -> coord: YES
    • coord: force write commit
    • coord -> sub: COMMIT
    • sub: force write commit
    • sub -> coord: ACK
    • no info = ABORT
  • coordinator logs:
    • commit (forced)
    • end
  • subordinates log:
    • prepare with leafs (force)
    • decision after respponses (force)
    • commit (force)
    • end if it has any update leafs
  • read only participants:
    • no logging at all
    • not do RO T (including subs and coord)
  • aborts are streamlined
    • no-info assumtion
    • abort records are not forced, don't need participant list
    • abort msgs aren't ACKed
    • if there's a failure in abort case, don't need to hand off T
  • read paper for PC - because of the problems with read only, not used in practice
  •  other topology: centralized, tree, linear,
  • 3PC (skeen)
    • coord -> sub: PREPARE
    • sub: force write PREPARE
    • sub -> coord: VOTE YES
    • coord: forcce write ALL_PREPARED
    • coord -> sub: ALL_PREPARED
    • sub: force write ALL_PREPARED
    • sub -> coord: ACK
    • coord: force write COMMIT (commits T)
    • coord -> sub: COMMIT
    • sub: force write commit  (TODO is this needed?)
    • sub -> coord: ACK2
    • coord: end
  • termination - pick
    • move to my current state
    • commit/abort (chosen based on my state)
    • if you're in the all-prepared state => you can move into commit
    • else you can abort
    •  
  • backup coordinator (subordinate), used in skeen to recover from coord failure
  •  

Comments (0)

You don't have permission to comment on this page.