Handout 27 1Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 — Principles of Computer SystemsHandout 27 April 30, 1997____________________________________________________________________________Distributed TransactionsIn this handout we study the problem of doing a transaction (that is, an atomic action) thatinvolves actions at several different transaction systems, which we call the ‘servers’. The mostobvious application is “distributed transactions”: separate databases running on differentcomputers. For example, we might want to transfer money from an account at Citibank to anaccount at Wells Fargo. Each bank runs its own transaction system, but we still want the entiretransfer to be atomic. More generally, however, it is good to be able to build up a systemrecursively out of smaller parts, rather than designing the whole thing as a single unit. Thedifferent parts can have different implementations, and the big system can be built even though itwasn’t thought of when the smaller ones were designed.SpecificationsWe have to solve two problems: composing the separate servers so that they can do a joint actionatomically, and dealing with partial failures. Composition doesn’t require any changes in the specof the servers; two servers that implement the SequentialTr spec in handout 18 can jointlycommit a transaction if some third agent keeps track of the transaction and tells them both tocommit. Partial failures do require changes in the server spec. In addition, they require, or at leaststrongly suggest, changes in the client spec. We consider the latter first.The client specIn the implementations we have in mind, the client may be invoking Do actions at several servers.If one of them fails, the transaction will eventually abort rather than committing. In the meantime,however, the client may be able to complete Do actions at other servers, since we don’t want eachserver to have to verify that no other server has failed before performing a Do. In fact, the clientmay itself be running on several machines, and may be invoking several Do’s concurrently. So thespec should say that the transaction can’t commit after a failure, and can abort any time after afailure, but need not abort until the client tries to commit. Furthermore, after a failure some Doactions may report crashed, and others, including some later ones, may succeed.We express this by adding another value failed to the phase. A crash sets the phase to failed,which enables an internal CrashAbort action that aborts the transaction. In the meantime a Docan either succeed or raise crashed.MODULE DistSeqTr [V,% Value of an actionS WITH { s0: ()->S },% StateA WITH { meaning: A->S->(V, S) }% Action] EXPORT Begin, Do, Commit, Abort, Crash =VAR ss := S.s0()% Stable Statevs := S.s0()% Volatile Stateph : ENUM[idle, run, failed] := idle% PHase (volatile)APROC Begin() = << Abort(); ph := run >>% aborts any current trans.APROC Do(a) -> V RAISES {crashed} = <<IF ph # idle => VAR v | (v, vs) := a.meaning(vs); RET v[] ph # run => RAISE crashedFI >>APROC Commit() RAISES {crashed} =<< IF ph = run => ss := vs; ph := idle [*] Abort(); RAISE crashed FI >>PROC Abort () = << vs := ss, ph := idle >>PROC Crash () = << ph := failed >>THREAD CrashAbort() = DO << ph = failed => Abort() >> ODEND DistSeqTrIn a real system Begin starts a new transaction and returns its transaction identifier t, which is anargument to every other routine. Transactions can commit or abort independently (subject to theconstraints of concurrency control). We omit this complication. Dealing with it requiresrepresenting each transaction’s state change independently in the spec. If the concurrency spec is‘any can commit’, Do(t) sees vs = ss + actions(t), and Commit(t) does ss := ss +actions(t).Partial failuresWhen several servers are involved in a transaction, they must agree about whether the transactioncommits. Thus each transaction commit requires consensus among the servers.The code that implements transactions usually keeps the state of a transaction in volatile storage,and only guarantees to make it stable at commit time. This is important for efficiency, since stablestorage writes are expensive. To do this with several servers requires a server action to make atransaction’s state stable without committing it; this action is traditionally called Prepare. Wecan invoke Prepare on each server, and if they all succeed, we can commit the transaction.Without Prepare we might commit the transaction, only to learn that some server has failed andlost the transaction state.The old LogRecovery or LogAndCache code in handout 18 does a Prepare implicitly, by forcingthe log to stable storage before writing the commit record. It doesn’t need a separate Prepareaction because it has direct and exclusive access to the state, so that the sequential flow of Commitensures that the state is stable before the transaction commits. For the same reason, it doesn’t needseparate actions to clean up the stable state; the sequential flow of Commit and Crash takes careof everything.Once a server is prepared, it must maintain the transaction state until it finds out whether thetransaction committed or aborted. We study a design in which a separate ‘coordinator’ module isresponsible for keeping track of all the servers and telling them to commit or abort. Real systemssometimes allow the servers to query the coordinator, but we omit this minor variation.We give the spec for a server. Since we want to be able to compose servers repeatedly, we give itas a modification of the DistSeqTr client spec. The change is the addition of the stable ‘preparedstate’ ps, and a separate Prepare action between the last Do and Commit. A transaction isprepared if ps # nil. Note that Crash has no effect on a prepared transaction. Abort works onany transaction, prepared or not.Handout 27 2MODULE TrServer [V,% Value of an actionS WITH { s0: ()->S },% StateA WITH { meaning: A->S->(V, S) }% Action] EXPORT Begin, Do, Commit, Abort, Prepare, Crash =VAR ss := S.s0()% Stable Stateps : (S + Null) := nil% Prepared State (stable)vs := S.s0()% Volatile Stateph : ENUM[idle, run, failed] := idle% PHase (volatile)% INVARIANT ps # nil ==> ph = idleAPROC Begin() = << Abort(); ph := run >>% aborts any current trans.APROC Do(a) -> V RAISES {crashed} = <<IF ph # idle => VAR v | (v, vs) := a.meaning(vs); RET v[] ph # run => RAISE crashedFI >>APROC