Commit Algorithms

Please download to get full document.

View again

of 9
6 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
Commit Algorithms Commit Algorithms Fault Tolerance Causes of failure: ã ã ã process failure machine failure network failure transparent: mask (i.e., completely recover from) all failures, or predictable: exhibit a well defined failure behavior Goals: ã ã Elements: ã ã Atomic Transactions commitment (commit protocols) ã generals paradox (message loss) ã blocking vs. non-blocking protocols (non-failed sites must wait (can continue) while failed sites recover) ã independent recovery (failed
Document Share
Documents Related
Document Tags
Document Transcript
  Commit Algorithms  Commit Algorithms CS5204  – Operating Systems 2 Fault Tolerance Causes of failure: ã process failure ã machine failure ã network failure Goals : ã transparent: mask (i.e., completely recover from) all failures, or ã predictable: exhibit a well defined failure behavior Elements : ã Atomic Transactions ã commitment (commit protocols) ã generals paradox (message loss) ã blocking vs. non-blocking protocols (non-failed sites must wait (cancontinue) while failed sites recover) ã independent recovery (failed sites can recover using onlylocal information)  Commit Algorithms CS5204  – Operating Systems 3 Transaction Model Transaction ã A sequence of actions (typically read/write), each of which is executed at one ormore sites, the combined effect of which is guaranteed to be atomic. Atomic Transactions ã Atomicity: either all or none of the effects of the transaction are made permanent. ã Consistency: the effect of concurrent transactions is equivalent to some serialexecution. ã Isolation : transactions cannot observe each other’s partial effects.   ã Durability: once accepted, the effects of a transaction are permanent (until changedagain, of course). Environment Each node is assumed to have: ã data stored in a partially/full replicated manner ã stable storage (information that survives failures) ã logs (a record of the intended changes to the data: write ahead, UNDO/REDO) ã locks (to prevent access to data being used by a transaction in progress)  Commit Algorithms CS5204  – Operating Systems 4 2-phase Commit Protocol q 1   c 1   a 1   w 1   Commit_Request msgsent to all cohortsAll cohortsagreedSend Commit msgto all cohorts 3,4  One or more cohort(s)replied abort 1  Abort msg sentto all cohorts 2,4   Coordinator q i   a i   c i   w i   Abort msgreceivedfrom CoordinatorCommit_Requestmsg receivedAbort msg sentto CoordinatorCommit_Requestmsg receivedAgreed msg sentto Coordinator 1   Cohort i (i=2,3, …, n)   Commit msgreceived fromCoordinator 2  1. First, write UNDO/REDO logs on stable storage.2. Writes COMPLETE record; releases locks1. Assume ABORT if there is a timeout2. First, writes ABORT record to stable storage.3. First, writes COMMIT record to stable storage.4. Write COMPLETE record when all msgs confirmed.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks