Reliable Distributed SystemsReliability and transactionsTypes of reliabilityReplicating a transactional serverReplication with 2PCObservationReplication and AvailabilityUsual responses?Quorum exampleThings to noticeNext issue?Availability of 2PCWhat can be done?A quandry?Other optionsServer replicationPrimary/backupSlide 18Slide 19Issues?Split brain: reminderSlide 22Slide 23Implication?Real systemsHow does hardware help?ReconciliationSummaryReplication and High AvailabilitySteps to a solutionNon-blocking CommitDefinition of problemNon-trivialityTypical protocolCommit protocol illustratedSlide 36Slide 37Failure issuesFailure model impacts costs!Commit with simpler failure modelSlide 41Example of a hard scenarioSlide 43Slide 44Skeen: Three-phase commitSlide 46Three phase commit protocol illustratedObservations about 3PCAssumptions about failuresProblems with 3PCSituation in practical systems?Process groupsFailure detectionArchitectureSlide 55Slide 56IssuesGMP designReading ahead?Reliable Distributed SystemsFault Tolerance (Recoverability High Availability)Reliability and transactionsTransactions are well matched to database model and recoverability goalsTransactions don’t work well for non-database applications (general purpose O/S applications) or availability goals (systems that must keep running if applications fail)When building high availability systems, encounter replication issueTypes of reliabilityRecoverabilityServer can restart without intervention in a sensible stateTransactions do give us thisHigh availabilitySystem remains operational during failureChallenge is to replicate critical data needed for continued operationReplicating a transactional serverTwo broad approachesJust use distributed transactions to update multiple copies of each replicated data itemWe already know how to do this, with 2PCEach server has “equal status”Somehow treat replication as a special situationLeads to a primary server approach with a “warm standby”Replication with 2PCOur goal will be “1-copy serializability”Defined to mean that the multi-copy system behaves indistinguishably from a single-copy systemConsiderable form and theoretical work has been done on thisAs a practical matterReplicate each data itemTransaction managerReads any single copy Updates all copiesObservationNotice that transaction manager must know where the copies resideIn fact there are two modelsStatic replication set: basically, the set is fixed, although some members may be downDynamic: the set changes while the system runs, but only has operational members listed within itToday stick to the static caseReplication and AvailabilityA series of potential issuesHow can we update an object during periods when one of its replicas may be inaccessible?How can 2PC protocol be made fault-tolerant?A topic we’ll study in more depthBut the bottom line is: we can’t!Usual responses?Quorum methods:Each replicated object has an update and a read quorumDesigned so Qu+Qr > # replicas and Qu+Qu > # replicasIdea is that any read or update will overlap with the last updateQuorum exampleX is replicated at {a,b,c,d,e}Possible values?Qu = 1, Qr = 5 (violates QU+Qu > 5)Qu = 2, Qr = 4 (same issue)Qu = 3, Qr = 3Qu = 4, Qr = 2Qu = 5, Qr = 1 (violates availability)Probably prefer Qu=4, Qr=2Things to noticeEven reading a data item requires that multiple copies be accessed!This could be much slower than normal local access performanceAlso, notice that we won’t know if we succeeded in reaching the update quorum until we get responsesImplies that any quorum replication scheme needs a 2PC protocol to commitNext issue?Now we know that we can solve the availability problem for reads and updates if we have enough copiesWhat about for 2PC?Need to tolerate crashes before or during runs of the protocolA well-known problemAvailability of 2PCIt is easy to see that 2PC is not able to guarantee availabilitySuppose that manager talks to 3 processesAnd suppose 1 process and manager failThe other 2 are “stuck” and can’t terminate the protocolWhat can be done?We’ll revisit this issue soonBasically,Can extend to a 3PC protocol that will tolerate failures if we have a reliable way to detect themBut network problems can be indistinguishable from failuresHence there is no commit protocol that can tolerate failuresAnyhow, cost of 3PC is very highA quandry?We set out to replicate data for increased availabilityAnd concluded thatQuorum scheme works for updatesBut commit is requiredAnd represents a vulnerabilityOther options?Other optionsWe mentioned primary-backup schemesThese are a second way to solve the problemBased on the log at the data managerServer replicationSuppose the primary sends the log to the backup serverIt replays the log and applies committed transactions to its replicated stateIf primary crashes, the backup soon catches up and can take overPrimary/backupprimary backupClients initially connected to primary, which keeps backup up to date. Backup tracks loglogPrimary/backupprimary backupPrimary crashes. Backup sees the channel break, applies committed updates. But it may have missedthe last few updates!Primary/backupprimary backupClients detect the failure and reconnect to backup. Butsome clients may have “gone away”. Backup state couldbe slightly stale. New transactions might suffer from thisIssues?Under what conditions should backup take overRevisits the consistency problem seen earlier with clients and serversCould end up with a “split brain”Also notice that still needs 2PC to ensure that primary and backup stay in same states!Split brain: reminderprimary backupClients initially connected to primary, which keeps backup up to date. Backup follows loglogSplit brain: reminderTransient problem causes some links to break but not all.Backup thinks it is now primary, primary thinks backup is downprimarybackupSplit brain: reminderSome clients still connected to primary, but one has switchedto backup and one is completely disconnected from bothprimarybackupImplication?A strict interpretation of ACID leads to conclusions thatThere are no ACID replication schemes that provide high availabilityMost real systems solve by weakening ACIDReal systemsThey use primary-backup with
View Full Document