错误容忍的随机模型
Stochastic Models for Fault Tolerance
Restart, Rejuvenation and Checkpointing
Katinka Wolter
英文版




Contents
Part I Introduction
1 Basic Concepts and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 The Timeout Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 System and Fault Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Preventive Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Note on Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Task Completion Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1 Bounded Downtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 System Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.2 Cumulative Uptime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.3 Probability of Task Completion . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Bounded Accumulated Downtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 System Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Cumulative Uptime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Probability of Task Completion . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Bounded Number of Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.1 System Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.2 Cumulative Uptime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.3 Probability of Task Completion . . . . . . . . . . . . . . . . . . . . . . . 29
Part II Restart
3 Applicability Analysis of Restart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1 Applications of Restart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Randomised Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.2 Optimal Restart Time for a Randomised Algorithm . . . . . . 37
3.1.3 Failure Detectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.4 Congestion Control in TCP. . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 Criteria for Successful Restarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.1 When Does Restart Improve the Expected Completion
Time? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2 When Does Restart Improve the Probability of Meeting a
Deadline? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Moments of Completion Time Under Restart . . . . . . . . . . . . . . . . . . . . . . 51
4.1 The Information Captured by theMoments of a Distribution . . . . . . 52
4.2 Models for Moments of Completion Time . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Unbounded Number of Restarts . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.2 Finite Number of Restarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Optimal Restart Times for the Moments of Completion Time . . . . . . 62
4.3.1 Expected Completion Time . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.2 Optimal Restart Times for Higher Moments . . . . . . . . . . . . . 69
4.4 Case Study: Optimising Expected Completion Time in Web
Services ReliableMessaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.1 Metrics for the Fairness-Timeliness tradeoff . . . . . . . . . . . . . 82
4.4.2 Oracles for Restart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.3 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5 HTTP Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5.1 60s Disruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5.2 Packet Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.5.3 Mail Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5 Meeting Deadlines Through Restart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1 A Model for the Probability of Meeting a Deadline Under Restart . . 95
5.2 Algorithms for Optimal Restart Times . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3 An Engineering Rule to Approximate the Optimal Restart Time . . . 100
5.4 Towards Online Restart for Self-Management of Systems . . . . . . . . . 106
5.4.1 Estimating the Hazard Rate . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.4.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Part III Software Rejuvenation
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6 Practical Aspects of Preventive Maintenance and Software
Rejuvenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.1 Preventive Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2 Software Rejuvenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7 Stochastic Models for Preventive Maintenance and Software
Rejuvenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.1 A Markovian Software Rejuvenation Model . . . . . . . . . . . . . . . . . . . . 133
7.2 Aging in the Modelling of Software Rejuvenation . . . . . . . . . . . . . . . 137
7.2.1 Behaviour in State A under Policy I . . . . . . . . . . . . . . . . . . . 141
7.2.2 Behaviour in State A under Policy II . . . . . . . . . . . . . . . . . . . 142
7.3 A Petri Net Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.4 A Non-Markovian Preventive Maintenance Model . . . . . . . . . . . . . . . 151
7.5 Stochastic Processes for Shock and Inspection-Based Modelling . . . 153
7.5.1 The Inspection Model with Alert Threshold Policy . . . . . . . 154
7.5.2 The Shock Model with a Risk Policy . . . . . . . . . . . . . . . . . . 159
7.6 Inspection-Based Modelling using the Möbius Modelling Tool . . . . 162
7.7 Comparative Summary of the Stochastic Models . . . . . . . . . . . . . . . . 164
7.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Part IV Checkpointing
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8 Checkpointing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.1 Checkpointing Single-Unit Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.2 Checkpointing in Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . 174
9 Stochastic Models for Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
9.1 Checkpointing at Program Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
9.1.1 Equidistant Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
9.1.2 Checkpointing Real-Time Tasks . . . . . . . . . . . . . . . . . . . . . . 189
9.1.3 Random Checkpointing Intervals . . . . . . . . . . . . . . . . . . . . . . 194
9.1.4 Algorithms for Optimum Checkpoint Selection . . . . . . . . . . 197
9.2 Checkpointing at System Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
9.2.1 Analytic Models for Checkpointing Transaction-Based
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.2.2 Checkpointing Policies for Transaction-Based Systems . . . 214
9.2.3 A Queueing Model for Checkpointing Transaction-Based
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
9.3 A Trade-Off Metric for Optimal Checkpoint Selection . . . . . . . . . . . 232
9.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
10 Summary, Conclusion and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
A Properties in Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
A.1 Cumulative FirstMoment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
A.2 The Gamma Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
B Important Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
B.1 Discrete Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
B.1.1 The Binomial Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
B.1.2 TheMultinomial Distribution. . . . . . . . . . . . . . . . . . . . . . . . . 243
B.1.3 The Geometric Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . 244
B.1.4 The Poisson Distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
B.2 Continuous Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 244
B.2.1 The Exponential Distribution . . . . . . . . . . . . . . . . . . . . . . . . . 244
B.2.2 The Erlang Distribution and the Hypo-exponential
Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
B.2.3 The Hyperexponential Distribution . . . . . . . . . . . . . . . . . . . . 247
B.2.4 The Mixed Hyper/Hypo-exponential Distribution . . . . . . . . 247
B.2.5 TheWeibull Distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
B.2.6 The Lognormal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . 249
C Estimating the Hazard Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
C.1 Cumulative Hazard Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
C.2 Epanechnikov Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
C.3 Bandwidth Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
D The Laplace and the Laplace-Stieltjes Transform . . . . . . . . . . . . . . . . . . 253
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267