Distributed SystemsWhat is a transactionConcept of distributed transactionVariety of Problems and SolutionsConcurrency SolutionInconsistent stateRecovery SolutionCommit / AbortTwo-Phase Commit ProtocolTwo-Phase Commit ProtocolArgusAssumptionsGuardiansActionsAction TreeLocks and nested transactionsImplementationArgus ConclusionQuickSilverQuickSilverOverviewTransaction ManagementTransaction ManagerTransactional IPCLog ManagerWeak Seriability: DFSPossible Usages of TransactionsLessons of QuickSilverLightweight Recoverable Virtual MemoryRVM: a simplified databaseConclusionTransactions in DistributedSystemsCS614 Spring 2002ANDR´E [email protected] UniversityTransactions in Distributed Systems – p.1/32Distributed SystemsWhy Distributed SystemsGeneralisation of a local systemNot everything can be done in a local systemCommon ProblemsState of system is difficult to defineEspecially with partial crashesHint: a database is a “local distributed” systemTransactions in Distributed Systems – p.2/32What is a transactionA transaction is a collection of operation thatrepresents a unit of consistency and recoveryA transaction starts by initialising things, thenreads and/or modifies objects. At the end, eitherCommit Changes are saved, resources arereleased; state is consistentAbort For an outsider, nothing happenedTransactions in Distributed Systems – p.3/32Concept of distributed transactionThe only difference is in the word Distributed.Some problems are the same as in databasesatomicityconcurrency (serialisation)recoveryThe solutions to those are conceptually thesameAdd network communication failuresAnd external process failuresTransactions in Distributed Systems – p.4/32Variety of Problems and SolutionsRecoverable Virtual Memory (RVM)Memory that survives crashesProgramming Language (Argus)To ease the development of distributedapplications (think of an object orientedlanguage, the objects being access bytransactions only)Distributed Operating System (QuickSilver)Transactions are used for all resourcesmanagementTransactions in Distributed Systems – p.5/32Concurrency SolutionUse of read and write locks to synchronisethe access / modification of system resourcesA two-phase lock mechanism to allow fullseriability. Locks are kept with the object.But different policies for different kind ofobjects. Two-phase are not necessaryneeded everywhere.Programmer should guard against deadlocksTransactions in Distributed Systems – p.6/32Inconsistent stateHaving atomicity on operations solve theproblem of inconsistent distributed stateAn operation can either commit or abort(failures are not tolerated everywhere)Nested transactions are trickier, notimplemented everywhere, need two-phasecommitTransactions in Distributed Systems – p.7/32Recovery SolutionDon’t save (on a stable storage) before beingrequested to commit, and then do save on astable storageKeep a log on a stable storage of the changesyou did to your dataFind a way to recover (consistent) state aftera failure / crash and / or abort (cleanly)leaving to the outer transaction to handle therest of story.Transactions in Distributed Systems – p.8/32Commit / AbortRule of everything or nothingEverything means local as well as remoteWhen there are nested transactions, commitand abort must propagate all the way down.There are two sorts of commits, the commit tothe top level transaction (which has to go tostable storage in some way), and the committo an outer transaction which could beaborted one day.System has to stay consistent!Transactions in Distributed Systems – p.9/32Two-Phase Commit [email protected]@[email protected]@[email protected]@[email protected]@G6abortedDifference between parent and top-level commitTransactions in Distributed Systems – p.10/32Two-Phase Commit ProtocolSub actions commit to the parent, in a way that can beundone (such as not saved on stable storage)Top level commits by sending a request to itssub-committed treeThey write in their log prepare and the object, andrelease the read locksUpon reception of all prepare OK Top level logs“Committed” and notify the subtree or send an abortChildren now log the commit, and store on stablestorage their objector else log abort and discard the object (undo), andrelease their locksTransactions in Distributed Systems – p.11/32ArgusA programming language and System forDistributed ComputingIntended for programs that keep online datafor long periods of timeGuardians provide encapsulation of objectsand resourcesActions allow atomicity of processesTransactions in Distributed Systems – p.12/32AssumptionsA failed node doesn’t send messagesMessages are always delivered, in order(retransmissions at higher level)Corruption of packets can be detectedTransactions in Distributed Systems – p.13/32GuardiansGuardians are objects that encapsulated resourcesNo other way of accessing the resource than using thededicatedhandlerThey resides in a single node, but could be movedfrom one node to anotherNodes can have 0, 1 or more guardiansResources are only accessed through handlersGuardians can create other guardiansGuardians have stable and volatile resourcesTransactions in Distributed Systems – p.14/32ActionsActions are total, atomic. They either abort or commit,but don’t leave an inconsistent stateThey can be nestedActions work on copies of their object, and keepversion numberWhen an action commits, it propagates its locks andlocal version of the guardian to the parent actionAs well as a list of participating guardians whichcommittedStrict two-phase locking (and locks held until a fatheraborts or top-level commits) (ensures seriabilility)Transactions in Distributed Systems – p.15/32Action [email protected]@[email protected]@[email protected]@[email protected]@G6abortedTransactions in Distributed Systems – p.16/32Locks and nested transactionsSynchronisation access to resources is donevia locksAn action can acquire a read lock if and onlyif all holders of write locks are ancestorsAn action can acquire a write lock if and onlyif all holders of read or write locks areancestorsTransactions in Distributed Systems – p.17/32ImplementationThere is a list of committed children which liesalong, as well as an abort list.Only commits and prepare are actually resentuntil getting answer. Release of locks forexample are not guaranteed to be received.Crashes and orphans processes are