容错计算英文版课件：21 Degradation Allowance

1、Nov. 20121Part VI Degradations: Behavioral LapsesAbout This PresentationThis presentation is intended to support the use of the textbook Dependable Computing: A Multilevel Approach (traditional print or on-line open publication, TBD). It is updated regularly by the author as part of his teaching of

2、the graduate course ECE 257A, Fault-Tolerant Computing, at Univ. of California, Santa Barbara. Instructors can use these slides freely in classroom teaching or for other educational purposes. Unauthorized uses, including distribution for profit, are strictly prohibited. Behrooz ParhamiEditionRelease

3、dRevisedRevisedRevisedRevisedFirstSep. 2006Oct. 2007Nov. 2009Nov. 2012Nov. 20122Part VI Degradations: Behavioral Lapses21 Degradation AllowanceNov. 20123Part VI Degradations: Behavioral LapsesOur computers are down,so we have to doeverything manually.“Redundancy is such an ugly word. Lets talkabout

4、your employment crunch.”Nov. 20124Part VI Degradations: Behavioral Lapses Robust Parallel Processing Resilient AlgorithmsNov. 20125Part VI Degradations: Behavioral Lapses21.1 Graceful DegradationDegradation allowanceDiagnose malfunctions and provide capability for the system to work without the modu

5、les which are malfunctioningDegradation managementAdapt: Prioritize tasks and redistribute loadMonitor: Keep tack of system operation in degraded modeReverse: Return system to the intact (or less degraded) state ASAPReturn: Go back to normal operationTerminology: n. Graceful degradation adj.Graceful

6、ly degrading/degradable = fail-softStrategies for failure prevention 1. Quick malfunction diagnosis2. Effective isolation of malfunctioning elements3. On-line repair (preferably via hot-pluggable modules)4. Avoidance of catastrophic malfunctionsNov. 20126Part VI Degradations: Behavioral LapsesArea u

7、nder performance curve represents work accomplishedPerformability of a Fail-Soft SystemOn-line repair: Done by removal/replacement of affected modules in a way that does not disrupt the operation of the remaining system partsCrashedOff-line repairOn-line repairOff-line repair: Involves shutting down

8、 the entire system while affected modules are removed and replacements are plugged inIntactTimeDegradedPartially failedFail-soft operationPerformanceNov. 20127Part VI Degradations: Behavioral Lapses21.2 Diagnosis, Isolation, and RepairDiagnose the malfunctionRemove the malfunctioning unit Update sys

9、tem (OS) tables Physical isolation? Initiate repair, if applicableCreate new working configuration Exclude processor, channel, controller, I/O device (e.g., sensor) Avoid bad tracks on disk, garbled files, noisy communication links Remove parts of the memory via virtual address mapping Bypass a cach

10、e or use only half of it (more restricted mapping?)UnitGuard 1 BusGuard 2Recover processes and associated data Recover state information from removed unit Initialize any new resource brought on-line Reactivate processes (via rollback or restart)Additional steps needed to return repaired units to ope

11、rating statusNov. 20128Part VI Degradations: Behavioral Lapses21.3 Stable StorageStorage that wont lose its contents (unlike registers and SRAM/DRAM)Combined stability & reliability can be provided with RAID-like methodsPossible implementation method: Battery backup for a time duration long enough t

12、o save contents of disk cache or other volatile memoryFlash memoryNov. 20129Part VI Degradations: Behavioral LapsesMalfunction-Stop ModulesMalfunction tolerance would be much easier if modules simply stopped functioning, rather than engage in arbitrary behaviorUnpredictable (Byzantine) malfunctions

13、are notoriously hard to handleAssuming the availability of a reliable stable storage along with its controlling s-process and (approximately) synchronized clocks, a k-malfunction-stop module can be implemented from k + 1 unitsOperation of s-process to decide whether the module has stopped:R := bag o

14、f received requests with appropriate timestampsif |R| = k+1 all requests identical and from different sources stopthen if request is a write then perform the write operation in stable storage else if request is a read, send value to all processeselse set variable stop in stable storage to TRUENov. 2

15、01210Part VI Degradations: Behavioral Lapses21.4 Process and Data RecoveryUse of logs with process restartImpossible when the system operates in real time and performs actions that cannot be undoneSuch actions must be compensated for as part of degradation managementNov. 201211Part VI Degradations:

16、Behavioral Lapses21.5 Checkpointing and RollbackEarly computers had a short MTTFIt was impossible to complete any computation that ran for several hoursIf MTTF is shorter than the running time, many restarts may be neededLong-running comp.TimeCheckpoint #1MTTFCheckpoint #2Checkpoint #3Checkpointing

17、entails some overheadToo few checkpoints would lead to a lot of wasted workToo many checkpoints would lead to a lot of overheadCheckpoints are placed at convenient points along the computation path (not necessarily at equal intervals)Nov. 201212Part VI Degradations: Behavioral LapsesWhy Checkpointin

18、g HelpsA computations running time is T = 2 MTTF = 2/l. What is the probability that we can finish the computation in time 2T:a. Assuming no checkpointingb. Assuming checkpointing at regular intervals of T/2Ignore all overheads.Long-running comp.TimeMTTFChkpt #1Chkpt #2Chkpt #3T = 2 MTTF2TSC.135 335

19、= e2SH.367 879= e1C.367 87925% success probability47% success probabilityNov. 201213Part VI Degradations: Behavioral LapsesRecovery via RollbackRollback or restart creates no problem for tasks that do I/O at the endInteractive processes must be handled with more care e.g., bank ATM transaction to wi

20、thdraw money or transfer funds (check balance, reduce balance, dispense cash or increase balance)Roll back process 2 to the last checkpoint (#2)Restart process 6Process 1Process 3Process 2Process 4Process 6Process 5TimeCheckpoint #1Checkpoint #2Detected malfunctionAffected processesNov. 201214Part V

21、I Degradations: Behavioral LapsesCheckpointing for DataConsider data objects stored on a primary site and k backup sites (with appropriate design, such a scheme will be k-malfunction-tolerant)Each access request is sent to the primary siteRead request honored immediately by the primary siteOne way t

22、o deal with a write request: Update requests sent to backup sites Request is honored after all messages ackedIf one or more backup sites malfunction, service is not disruptedIf the primary site malfunctions, a new primary site is “elected” (distributed election algorithms exist that can tolerate mal

23、functions)Time in state: fn of k fn of k kAvailability 0 0.922 1 0.987 2 0.996 4 0.997 8 0.997Analysis by Huang and Jalote: Normal state (primary OK, data available) Recovery state (primary site is changing) Checkpoint state (primary doing back-up) Idle (no site is OK)Alternative:Primary site does f

24、requent back-upsNov. 201215Part VI Degradations: Behavioral LapsesAsynchronous Distributed CheckpointingFor noninteracting processes, asynchronous checkpoints not a problemProcess 1Process 3Process 2Process 4Process 5TimeIChkpt 1.1Detected malfunctionAffected processProcess 6IChkpt 1.2IChkpt 1.3IChk

25、pt. 2.1IChkpt 3.1IChkpt 3.2IChkpt 5.1IChkpt 5.2IChkpt 4.1 e3.2e1.1e5.1e3.1e3.3e5.3e1.2e5.2When one process is rolled back, other processes may have to be rolled back also, and this has the potential of creating a domino effectIdentifying a consistent set of checkpoints (recovery line) is nontrivialR

26、ecovery lineNov. 201216Part VI Degradations: Behavioral Lapses21.6 Optimal Checkpoint InsertionThere is a clear tradeoff in checkpoint insertionToo few checkpoints lead to long rollbacks in the event of a malfunctionToo many checkpoints lead to excessive time overheadAs in many other engineering pro

27、blems, there is a happy medium# of checkpointsCheckpointingoverheadExpected workfor recovering froma malfunctionNov. 201217Part VI Degradations: Behavioral LapsesOptimal Checkpointing for Long ComputationsT = Total computation time without checkpointingq = Number of computation segments; there will

28、be q 1 checkpointsTcp = Time needed to capture a checkpoint snapshotl = Malfunction rateEndChkpt #1Start. . .Chkpt #2T0T/q2T/q1 lT/q 1 lT/q . . .Discrete Markov model: Expected length of stay in each state1/(1 lT/q ), where time step is T/qComputation time with checkpointing Ttotal = T/(1 lT/q) + (q

29、 1)Tcp = T + lT2/(q lT) + (q 1)TcpdTtotal/dq = lT2/(q lT)2 + Tcp = 0 qopt = T(l + l/Tcp)Example: T = 200 hr, l = 0.01 / hr, Tcp = 1/8 hrqopt = 200(0.01 + (0.01/0.25)1/2) = 42; Ttotal 215 hr optWarning: Model is accurate only when T/q 0 Bowl-like curve for Ttotal, with a minimum Example: 4 6 8 10 20

30、30 40 50 0 400 300 267 250 222 214 211 208 1/8 400 301 267 251 225 218 215 214 1/3 401 302 269 253 229 224 224 224 1 403 305 274 259 241 243 250 257 10 430 350 337 340 412 504 601 698 100 700 800 967 1150 2122 3114 4111 5108 1000340053007267 925019222292143921149208 TcpqTtotalRollbackCheckpointingNo

31、v. 201219Part VI Degradations: Behavioral LapsesOptimal Checkpointing in Transaction ProcessingPcp = Checkpointing periodTcp = Checkpointing time overhead (for capturing a database snapshot)Trb = Expected rollback time upon malfunction detectionRelative checkpointing overhead O = (Tcp + Trb) / Pcp A

32、ssume that rollback time, given malfunction at time x, is a + bx(b is typically small, because only updates need to be reprocessed)r(x): Expected rollback time due to malfunction in the time interval 0, xr(x+dx) = r(x) + (a + bx)ldx dr(x)/dx = (a + bx)l r(x) = lx(a + bx/2)Trb = r(Pcp) = lPcp(a + bPc

33、p/2)xx + dxPcp0Checkpoint i 1 Checkpoint iO = (Tcp+Trb)/Pcp = Tcp/Pcp + l(a + bPcp/2) is minimized for: Pcp = 2Tcp/(lb)Nov. 201220Part VI Degradations: Behavioral LapsesExamples for Optimal Database CheckpointingO = (Tcp+Trb)/Pcp = Tcp/Pcp + l(a + bPcp/2) is minimized for: Pcp = 2Tcp/(lb)Tcp = Time

34、needed to capture a checkpoint snapshot = 16 minl = Malfunction rate = 0.0005 / min (MTTF = 2000 min 33.3 hr)b = 0.1Pcp = 2Tcp/(lb) = 800 min 13.3 hr optSuppose that by using faster memory for saving the checkpoint snapshots (e.g., disk, rather than tape) we reduce Tcp to 1 minPcp = 2Tcp/(lb) = 200

35、min 3.3 hr optNov. 201221Part VI Degradations: Behavioral Lapses22 Degradation ManagementNov. 201222Part VI Degradations: Behavioral Lapses“Budget cuts.”Nov. 201223Part VI Degradations: Behavioral Lapses Robust Parallel Processing Resilient AlgorithmsNov. 201224Part VI Degradations: Behavioral Lapse

36、s22.1 Data Distribution MethodsReliable data storage requires that the availability and integrity of data not be dependent on the health of any one siteData ReplicationData dispersionNov. 201225Part VI Degradations: Behavioral LapsesData ReplicationResilient objects using the primary site approachAc

37、tive replicas: the state-machine approachRequest is sent to all replicas All replicas are equivalent and any one of them can service the requestEnsure that all replicas are in same state (e.g., via atomic broadcast)Maintaining replica consistency very difficult under Byzantine faultsWill discuss Byz

38、antine agreement laterRead and write quorumsExample: 9 replicas, arranged in 2D gridRows constitute write quorumsColumns constitute read quorumsA read quorum contains the latest updatePossible read quorumMost up-to-datereplicasNov. 201226Part VI Degradations: Behavioral LapsesData DispersionInstead

39、of replicating data objects completely, one can divide each one into k pieces, encode the pieces, and distribute the encoded pieces such that any q of the pieces suffice to reconstruct the dataNov. 201227Part VI Degradations: Behavioral Lapses22.2 Multiphase Commit ProtocolsThe two generals problem:

40、 Two generals lead divisions of an army camped on the mountains on the two sides of an enemy-occupied valleyThe two divisions can only communicate via messengersWe need a scheme for the generals to agree on a common attack time, given that attack by only one division would be disastrousMessengers ar

41、e totally reliable, but may need an arbitrary amount of time to cross the valley (they may even be captured and never arrive)G2G1G1 decides on T, sends a messenger to tell G2Tomorrow at noon Got it!Got your ack!G2 acknowledges receipt of the attack time TG2, unsure whether G1 got the ack (without wh

42、ich he would not attack), will need an ack of the ack!This can go on forever, without either being sureNov. 201228Part VI Degradations: Behavioral LapsesMaintaining System ConsistencyAtomic action: Either the entire action is completed or none of it is doneOne key tool is the ability to ensure atomi

43、city despite malfunctionsSimilar to a computer guaranteeing sequential execution of instructions, even though it may perform some steps in parallel or out of orderWhere atomicity is useful:Upon a write operation, ensure that all data replicas are updatedElectronic funds transfer (reduce one balance,

44、 increase the other one)In centralized systems atomicity can be ensured via locking mechanisms Acquire (read or write) lock for desired data object and operation Perform operation Release lockA key challenge of locks is to avoid deadlock (circular waiting for locks)Nov. 201229Part VI Degradations: B

45、ehavioral LapsesTwo-Phase Commit ProtocolTo avoid participants being stranded in the wait state (e.g., when the coordinator malfunctions), a time-out scheme may be implementedEnsuring atomicity of actions in a distributed environmentQuietWaitAbortCommitCoordinator- / Begin to allYes from all / Commi

46、t to allNo from some / Abort to allQuietWaitAbortCommitParticipantBegin / YesAbort / -Commit / -Begin / NoWhere the transaction is initiatedWhere some part of the transaction is performedExecute the termination protocolNov. 201230Part VI Degradations: Behavioral LapsesThree-Phase Commit ProtocolTwo-

47、phase commit is a blocking protocol, even with timeout transitionsQuietWaitAbortCommitCoordinator- / Begin to allYes from all / Prepare to allNo from some / Abort to allQuietWaitAbortParticipantBegin / YesAbort / -Prepare / AckBegin / NoPrepareAck from all / Commit to allCommitPrepareCommit / -Safe

48、from blocking, given the absence of a local state that is adjacent to both a commit and an abort stateNov. 201231Part VI Degradations: Behavioral Lapses22.3 Dependable CommunicationPoint-to-point message: encoding + acknowledgment + timeoutReliable broadcast: message guaranteed to be received by all

49、 nodesForwarding along branches of a broadcast tree, with possible repetition (duplicate messages recognized from their sequence numbers) Positive and negative acknowledgments piggybacked on subsequent broadcast messages (P broadcasts message m1, Q receives it and tacks a positive ack for m1 to mess

50、age m2 that it broadcasts, R did not receive m1 but finds out about it from Qs ack and requests retransmit)Atomic broadcast: reliable broadcast, plus the requirement that multiple broadcasts be received in the same order by all nodes (much more complicated to ensure common ordering of messages)Causa

51、l broadcast: if m2 is sent after m1, any message triggered by m2 must not cause actions before those of m1 have been completedNov. 201232Part VI Degradations: Behavioral Lapses22.4 Dependable CollaborationDistributed systems, built from COTS nodes (processors plus memory) and interconnects, have red

52、undancy and allow software-based malfunction tolerance implementationInterconnect malfunctions are dealt with by synthesizing reliable communication primitives (point-to-point, broadcast, multicast)Node malfunctions are modeled differently, with the more general models requiring greater redundancy t

53、o deal with ByzantineTimingOmissionCrashNode stops (does not undergo incorrect transitions)Node does not respond to some inputsNode responds either too early or too lateTotally arbitrary behaviorNov. 201233Part VI Degradations: Behavioral LapsesMalfunction Detectors in Distributed SystemsMalfunction

54、 detector: Distributed oracle related to malfunction detectionCreates and maintains a list of suspected processesDefined by two properties: completeness and accuracyAdvantages: Allows decoupling of the effort to detect malfunctions, e.g. site crashes, from that of the actual computation, leading to

55、more modular designImproves portability, because the same application can be used on a different platform if suitable malfunction detectors are available for itExample malfunction detectors: P (Perfect): strong completeness, strong accuracy (min required for IC)S: strong completeness, eventual weak

56、accuracy (min for consensus)Reference: M. Raynal, “A Short Introduction to Failure Detectors for Asynchronous Distributed Systems,” ACM SIGACT News, Vol. 36, No. 1, pp. 53-70, March 2005.Nov. 201234Part VI Degradations: Behavioral LapsesReliable Group Membership ServiceA group of processes may be co

57、operating for solving a problemThe groups membership may expand and contract owing to changing processing requirements or because of malfunctions and repairsReliable multicast: message guaranteed to be received by all members within the groupECE 254C: Advanced Computer Architecture Distributed Syste

58、ms(course devoted to distributed computing and its reliability issues)Nov. 201235Part VI Degradations: Behavioral Lapses22.5 Remapping and Load BalancingAfter remapping, various parts of the computation are performed by different modules compared with the original mappingIt is quite unlikely that th

59、e same incorrect answers are obtained in the remapped versionWhen pieces of a computation are performed on different modules, remapping may expose hidden malfunctionsLoad balancing is the act of redistributing the computational load in the face of lost/recovered resources and dynamically changing co

60、mputational requirementsNov. 201236Part VI Degradations: Behavioral LapsesCell 6Cell 1Cell 2Cell 3Cell 4Cell 5Recomputation with Shift in SpaceLinear array with an extra cell can redo the same pipelined computation with each step of the original computation shifted in spaceEach cell i + 1 compares t