search for books and compare prices
Tables of Contents for Recovery Mechanisms in Database Systems
Chapter/Section Title
Page #
Page Count
Foreword
xxv
2
Preface
xxvii
1
Acknowledgement
xxviii
1 IMS/360 and IMS/VS Recovery: Historical Recollections
1
5
1.1 Introduction
1
5
1.1.1 Basic Recovery Algorithms
2
1
1.1.2 Write-Ahead Logging
3
1
1.1.3 Duplex Logging
4
1
1.1.4 Dynamic Transaction Backout (Undo)
4
1
1.1.5 Conclusions
5
1
2 Introduction to Database Recovery
6
10
2.1 Introduction
6
1
2.2 ACID Properties of Transactions
7
2
2.3 Principles of Database Recovery
9
1
2.4 Methods for Writing Updates to a Database
10
1
2.5 Implementing Transaction Commit and Abort
11
2
2.6 Commit Processing and System Recovery
13
3
3 Principles of Transaction-Oriented Database Recovery
16
40
3.1 Introduction
16
1
3.2 Database Recovery: What It Is Expected to Do
17
6
3.2.1 What Is a Transaction?
17
3
3.2.2 Which Failures Have to Be Anticipated
20
2
3.2.3 Summary of Recovery Actions
22
1
3.3 The Mapping hierarchy of a DBMS
23
7
3.3.1 The Mapping Process: Objects and Operations
23
2
3.3.2 The Storage Hierarchy: Implementation Environment
25
1
3.3.3 Different Views of a Database
26
1
3.3.4 Mapping Concepts for Updates
27
3
3.4 Crash Recovery
30
19
3.4.1 State of the Database after a Crash
30
1
3.4.2 Types of Log Information to Support Recovery Actions
31
2
3.4.3 Classification of Log Data
33
4
3.4.4 Examples of Recovery Techniques
37
6
3.4.5 Examples of Logging and Recovery Concepts
43
4
3.4.6 Evaluation of Logging and Recovery Concepts
47
2
3.5 Archive Recovery
49
3
3.6 Conclusion
52
4
4 Recovery-Enhanced, Reliability, Dependability, and Performability
56
15
4.1 Introduction
57
2
4.2 How Systems Respond to Failure
59
1
4.3 Reliability
60
4
4.3.1 System Reliability
61
1
4.3.2 Service Reliability
61
3
4.4 Availability
64
2
4.4.1 System and Service Availability
64
2
4.5 Dependability
66
1
4.6 Performability
67
1
4.7 Discussion
68
3
5 The Impact of Recovery on Concurrency Control
71
30
5.1 Introduction
71
2
5.2 Computational Model
73
2
5.3 Atomicity
75
5
5.3.1 I/O Automata
75
1
5.3.2 Specifications
75
2
5.3.3 Global Atomicity
77
1
5.3.4 Local Atomicity
78
2
5.4 CC and Recovery Algorithms
80
2
5.5 Recovery
82
2
5.6 Commutativity
84
3
5.6.1 Equieffectiveness
85
1
5.6.2 Forward Commutativity
85
1
5.6.3 Backward Commutativity
86
1
5.6.4 Discussion
87
1
5.7 Interaction of Recovery and Concurrency Control
87
2
5.8 Restricted Locking Algorithms
89
7
5.8.1 Read/Write Locking
90
1
5.8.2 Invocation-Based Locking
91
5
5.9 Conclusions
96
5
6 Redo Recovery After System Crashes
101
24
6.1 Introduction
101
8
6.1.1 The Basics of Redo Recovery
102
1
6.1.2 The Problem
103
2
6.1.3 The Solution
105
3
6.1.4 The Consequences
108
1
6.2 Database Model
109
3
6.3 Conditions for Recoverability
112
4
6.3.1 Must Redo and Can Redo
112
2
6.3.2 Installation Graph
114
1
6.3.3 Explainable States
115
1
6.3.4 Minimal Uninstalled Updates
115
1
6.4 General Recovery Method
116
1
6.5 General Cache Management
117
3
6.6 Practical Recovery Methods
120
5
6.6.1 Existing Methods
120
1
6.6.2 A New Method: Tree Operations
121
1
6.6.3 Recycling Pages
122
1
6.6.4 Future Directions
122
3
7 MLR: A Recovery Method for Multilevel Systems
125
20
7.1 Introduction
125
2
7.1.1 Precursor Multilevel Methods
125
1
7.1.2 Explicit Multilevel Systems
126
1
7.1.3 Our Effort
127
1
7.2 Multilevel Systems
127
3
7.2.1 High-level Compensation
127
1
7.2.2 Concurrency Control
128
1
7.2.3 Layers in a Multilevel System
129
1
7.3 Recovery Fundamentals
130
3
7.3.1 Recovery Predicates
130
1
7.3.2 Higher-level Undo Recovery
131
1
7.3.3 Level Lo Recovery
131
2
7.4 Logging for MLR
133
5
7.4.1 Forward Operations
133
1
7.4.2 Interrupted Transaction Undo
134
1
7.4.3 Completed Subtransaction Undo
135
2
7.4.4 Another CLR Logging Strategy
137
1
7.5 MLR Rollback
138
2
7.5.1 Rollback in Normal Operation
138
1
7.5.2 Rollback for Crash Recovery
139
1
7.6 Discussion
140
5
7.6.1 Characterization of MLR
140
1
7.6.2 General Multilevel Systems
141
1
7.6.3 Layered Abstraction Systems
142
3
8 ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging
145
74
8.1 Introduction
146
10
8.1.1 Logging, Failures, and Recovery Methods
146
5
8.1.2 Latches and Locks
151
2
8.1.3 Fine-Granularity Locking
153
1
8.1.4 Buffer Management
154
1
8.1.5 Organization
155
1
8.2 Goals
156
4
8.3 Overview of ARIES
160
4
8.4 Data Structures
164
2
8.4.1 Log Records
164
1
8.4.2 Page Structure
165
1
8.4.3 Transaction Table
165
1
8.4.4 Dirty-Pages Table
165
1
8.5 Normal Processing
166
7
8.5.1 Updates
166
3
8.5.2 Total or Partial Rollbacks
169
2
8.5.3 Transaction Termination
171
1
8.5.4 Checkpoints
171
2
8.6 Restart Processing
173
8
8.6.1 Analysis Pass
173
2
8.6.2 Redo Pass
175
3
8.6.3 Undo Pass
178
1
8.6.4 Selective or Deferred Restart
179
2
8.7 Checkpoints During Restart
181
2
8.8 Media Recovery
183
2
8.9 Nested Top Actions
185
2
8.10 Recovery Paradigms
187
9
8.10.1 Selective Redo
187
3
8.10.2 Rollback State
190
3
8.10.3 Space Management
193
2
8.10.4 Multiple LSNs
195
1
8.11 Other WAL-Based Methods
196
5
8.12 Attributes of ARIES
201
5
8.13 Summary
206
13
8.13.1 Implementations and Extensions
208
11
9 Performance of Recovery Algorithms for Centralized Database Management Systems
219
40
9.1 Introduction
219
1
9.2 Recovery Algorithms
220
4
9.2.1 The U-R Algorithm
221
1
9.2.2 The U-NR Algorithm
222
1
9.2.3 The NU-R Algorithm
222
1
9.2.4 The NU-NR Algorithm
223
1
9.3 Checkpointing
224
1
9.4 Expected Behavior of Recovery Algorithms
224
2
9.5 Simulation Model and Parameters
226
12
9.5.1 Failure Criteria
227
1
9.5.2 Common Forward Processing
228
1
9.5.3 Common Recovery Processing Features
229
1
9.5.4 Simulation Models
230
8
9.6 Simulation Results and Discussion
238
17
9.7 Conclusions
255
4
10 Stochastic Models for Performance Analysis of Database Recovery Control
259
36
10.1 Introduction
259
2
10.2 Analytical Modeling of Database Recovery
261
4
10.2.1 Recovery Concepts
261
1
10.2.2 Buffer Management in Normal Operation
262
1
10.2.3 Checkpointing Schemes
262
1
10.2.4 Final Destination of Recovery Actions
262
1
10.2.5 Operational Parameters
263
1
10.2.6 Analytical Modeling of Database Recovery
263
2
10.3 Recovery at Buffer Level: Model 1
265
2
10.4 Recovery at Buffer and Disk Levels: Model 2
267
2
10.5 Physical Logs, Linear Recovery Periods, and Deterministic Checkpoints
269
2
10.5.1 Model 1
269
1
10.5.2 Model 2
270
1
10.6 Transaction Processing in Normal Operation: Model 3
271
2
10.6.1 Input Parameters
271
1
10.6.2 Output of the Model
272
1
10.7 Numerical Results
273
13
10.7.1 Recovery at Buffer versus Recovery at Buffer and Disk
275
2
10.7.2 Checkpointing Strategies
277
3
10.7.3 Recovery-Oriented Activities During Normal Operation
280
4
10.7.4 Comparison with Previous Models and Summary of Results
284
2
10.8 Concluding Remarks and Future Research
286
1
10.9 Appendix A -- Analysis of the Database Recovery Model 2
287
4
10.10 Appendix B: Disk Subsystem Operational Parameters
291
4
11 Analytical Modeling and Comparison of Buffer Coherency and Dirty-Page Propagation Policies under Different Recovery Complexities
295
40
11.1 Introduction
296
3
11.1.1 Primary Focus
298
1
11.1.2 Related Performance Study
299
1
11.2 Buffer Coherency Policies
299
5
11.2.1 Buffer Coherency Performance Issues
300
1
11.2.2 Schemes with Simple Recovery
301
1
11.2.3 Schemes with Medium Recovery
302
1
11.2.4 Schemes with Complex Recovery
303
1
11.3 Performance Model
304
15
11.3.1 Data Sharing Environment and Model Assumptions
304
1
11.3.2 Buffer Model
305
8
11.3.3 Estimation of Local and Remote Buffer Hit Probabilities
313
2
11.3.4 Integrated System Model
315
4
11.4 Performance Comparison
319
12
11.4.1 Validation of the Buffer Analyses
319
3
11.4.2 Comparison of Response Time and Maximum Throughput
322
9
11.5 Summary and Conclusions
331
4
12 Recovery Analysis of Data Sharing Systems under Deferred Dirty Page Propagation Policies
335
35
12.1 Introduction
336
2
12.1.1 Related Work
338
1
12.2 Preliminary
338
6
12.2.1 Database Recovery in A Single Node Environment
339
1
12.2.2 Data Sharing Architecture
340
2
12.2.3 Dirty Page Propagation Polices and Recovery under Data Sharing
342
2
12.3 Performance Model
344
9
12.3.1 Overview on Methodology
345
2
12.3.2 Model Assumption
347
1
12.3.3 Estimation of Log Application Count
348
4
12.3.4 Estimation of Data I/O Count
352
1
12.4 Performance Comparisons
353
9
12.4.1 Validation of Analytical Models
354
3
12.4.2 Comparison of Recovery Times
357
3
12.4.3 Recovery Time Vs. Performance Trade-off
360
2
12.5 Summary
362
8
13 Recovery and Performance of Atomic Commit Processing in Distributed Database Systems
370
47
13.1 Introduction
370
3
13.2 Distributed Database System Model
373
2
13.3 The Basic Two-Phase Commit Protocol
375
3
13.3.1 Recovery in 2PC Protocol
377
1
13.4 Enhancing the Performance of The 2PC Protocol
378
7
13.4.1 The Presumed Abort Protocol
378
2
13.4.2 The Presumed Commit Protocol
380
3
13.4.3 The New Presumed Commit Protocol
383
1
13.4.4 Efficiency of Presumed Abort and Presumed Commit variants
384
1
13.5 Other Two-Phase Commit Variants
385
5
13.5.1 Network Topology Specific 2PCs
386
1
13.5.2 Transaction Type Specific 2PCs
387
3
13.6 Atomic Commit Protocol Optimizations
390
4
13.6.1 Read-Only
390
1
13.6.2 Last Agent
391
1
13.6.3 Group Commit
392
1
13.6.4 Sharing the Log
392
1
13.6.5 Flattening the transaction tree
393
1
13.6.6 Optimistic
393
1
13.7 Reducing the Blocking Effects of 2PC Protocol
394
3
13.7.1 Non-blocking Atomic Commit Protocols
394
2
13.7.2 IBM's Presumed Nothing Protocol
396
1
13.8 Simulation-Based Performance Evaluation
397
13
13.8.1 Simulation System Model
398
2
13.8.2 Transactions and Their Execution Model
400
1
13.8.3 Workload Model
400
1
13.8.4 Performance of Atomic Commit Protocols
401
7
13.8.5 Summary of results
408
2
13.9 Conclusions
410
7
14 Crash Recovery in Client-Server EXODUS
417
27
14.1 Introduction
417
2
14.2 The Client-Server Environment
419
3
14.2.1 Architecture Overview
419
1
14.2.2 Logging Subsystem
420
2
14.3 Overview of ARIES
422
3
14.3.1 Normal Operation
423
1
14.3.2 Analysis
423
1
14.3.3 Redo
424
1
14.3.4 Undo
424
1
14.4 Recovery in ESM-CS
425
9
14.4.1 ARIES and the Page-Server Environment
425
1
14.4.2 Log Record Counters (LRCs)
426
1
14.4.3 Conditional Undo
427
2
14.4.4 Performing Correct Analysis during Restart
429
4
14.4.5 Summary of the Algorithm
433
1
14.5 Performance
434
5
14.5.1 Logging Experiments
434
4
14.5.2 Transaction Rollback and Recovery Performance
438
1
14.6 Related Work
439
1
14.7 Conclusions
440
4
15 A Formal Approach to Recovery by Compensating Transsactions
444
22
15.1 Introduction
444
2
15.2 Overview of Compensation
446
1
15.3 A Transaction Model
447
5
15.3.1 Transaction and Programs
447
3
15.3.2 Histories and Correctness
450
2
15.4 Compensating Transactions
452
4
15.4.1 Specification Constraints
452
2
15.4.2 Types of Compensation
454
2
15.5 Examples and Applications
456
2
15.5.1 A Generic Example
456
1
15.5.2 Storage Management Examples
457
1
15.6 Approximating Soundness
458
3
15.7 Implementation Issues
461
1
15.8 Related Work
462
1
15.9 Conclusions
463
3
16 Coordinating Multitransaction Activities with Nested Sagas
466
16
16.1 Introduction
466
3
16.2 Basic Services
469
5
16.3 Nested Sagas
474
4
16.4 Discussion
478
1
16.5 Conclusions
479
3
17 Recovery Options in Directory-Based Software Coherency Schemes
482
23
17.1 Introduction
483
2
17.2 Overview of Owner-Based Directory Coherency Protocols
485
3
17.3 Failure and Transaction Model
488
1
17.4 Recovery Issues in Coherent Shared Memory Systems
489
1
17.5 Recovery Issues in Directory Based Coherency Protocols
490
1
17.5.1 Owner Crashes
490
1
17.5.2 Loaner Crashes
491
1
17.6 Recovery in Directory Based Coherency
491
9
17.6.1 Recovering Directory Structures
492
2
17.6.2 Run-Time Recovery Extensions for DBC
494
1
17.6.3 Recovering Data in Directory-Based Coherency
495
5
17.7 Related Work
500
1
17.8 Summary
501
4
18 ObjectFlow and Recovery in Workflow Systems
505
23
18.1 Introduction
505
4
18.1.1 Introduction to Workflow Computing
506
2
18.1.2 Evolution of Workflow Systems
508
1
18.2 The Flow Model
509
8
18.2.1 Flow Definition Model
509
3
18.2.2 Noncyclic Flows
512
4
18.2.3 Cyclic Flows, or Conditional Rollback
516
1
18.3 Nested and Dynamic Subflows
517
3
18.3.1 Primitive Versus Compound Nodes
517
1
18.3.2 Applications, Data Flow, and Data Recovery
518
1
18.3.3 Execution Control
519
1
18.3.4 Role Resolution
520
1
18.4 Structure and Implementation of Object Flow
520
5
18.4.1 Structure of a Workflow System
521
1
18.4.2 Workflow Execution Framework
522
1
18.4.3 API and Distributability
523
1
18.4.4 Atomic State Transitions and System Recovery
523
2
18.5 Conclusion and Future Work
525
3
19 The Case for Safe RAM
528
20
19.1 Introduction
528
1
19.2 Feasibility and cost of Safe RAM
529
5
19.2.1 Realization with Conventional Technology
530
1
19.2.2 Physical Realizations
531
1
19.2.3 Assumptions About Technology
532
1
19.2.4 Cost of Safe RAM
533
1
19.3 History of Reliable Updates Techniques
534
2
19.4 Modeling
536
4
19.4.1 Size of Safe
536
1
19.4.2 Performance Model
537
3
19.5 When Is Safe RAM Cost-Effective?
540
5
19.5.1 Comparison Methodology
540
1
19.5.2 The Comparison
541
4
19.6 Some Related Issues
545
1
19.7 Summary
546
2
20 Recovering from Main-Memory Lapses
548
26
20.1 Introduction
548
2
20.2 System Structure
550
5
20.2.1 System Model
550
2
20.2.2 Commit Processing
552
2
20.2.3 Abort Processing
554
1
20.3 Checkpointing and Recovery
555
4
20.3.1 Checkpointing
555
2
20.3.2 Recovery
557
2
20.4 Correctness
559
2
20.5 Segmenting the Database
561
1
20.6 Logical Logging
562
5
20.6.1 Model of Logical Logging
563
1
20.6.2 Logical Logging and Rollback
564
1
20.6.3 Checkpointing and Recovery
565
1
20.6.4 Correctness
566
1
20.7 Extensions
567
1
20.7.1 Database Bigger Than Memory
567
1
20.7.2 Partitioning the Redo Log
567
1
20.7.3 Miscellaneous
568
1
20.8 Discussion
568
1
20.9 Related Work
569
2
20.10 Conclusion
571
3
21 Fuzzy Checkpointing Alternatives for Main-Memory Databases
574
43
21.1 Introduction
575
2
21.2 MMDB Architecture
577
1
21.3 Dynamic Segmenting Fuzzy Checkpointing
578
20
21.3.1 Segmenting Main-Memory Databases
580
2
21.3.2 Dynamic Segmented Fuzzy Checkpointing
582
4
21.3.3 Further Improvement of DSFC
586
3
21.3.4 Performance of DSFC
589
9
21.4 Partitioning Checkpointing
598
15
21.4.1 MMDB Architecture for Partition Checkpointing
599
2
21.4.2 Partition Checkpointing Algorithms
601
1
21.4.3 Recovery Algorithm
602
2
21.4.4 Scheduling Algorithms for Local Checkpoints
604
2
21.4.5 Performance Analysis for Partition Checkpointing
606
1
21.4.6 Partition Checkpointing Overhead
607
1
21.4.7 Savings to Identify Transaction Status
608
1
21.4.8 Recovery Savings Due to Reduced Log Processing
609
2
21.4.9 Total Savings for Partition Checkpointing
611
2
21.5 Comparision and Extension
613
1
21.6 Conclusions
614
3
22 Performance Measurement of Main-Memory Database Recovery Algorithms Based on Update-in-Place and Shadow Approaches
617
21
22.1 Introduction
618
3
22.1.1 A Review of earlier works on MDBS Recovery
619
2
22.2 Algorithms Investigated
621
2
22.2.1 Lehman's Algorithm
621
1
22.2.2 Eich's Algorithm
622
1
22.3 Basic Assumptions and Simulation Models
623
4
22.3.1 Basic Assumptions
623
1
22.3.2 Simulation Model of Lehman's Algorithm
624
1
22.3.3 Simulation model of Eich's algorithm
625
2
22.4 Simulation Results and Discussion
627
8
22.4.1 No-Failure Case
627
3
22.4.2 Failure Case
630
2
22.4.3 CPU Utilization
632
2
22.4.4 The Behavior of the System After a Crash
634
1
22.4.5 Modification to Eich's Algorithm
635
1
22.5 Conclusion
635
4
23 Recoverable Mobile Environment: Design and Trade-Off Analysis
638
23
23.1 Introduction
639
3
23.2 Related Work
642
1
23.3 Recovery Strategies
642
4
23.3.1 State Saving
642
2
23.3.2 Handoff
644
2
23.4 Performance Analysis
646
12
23.4.1 Terms and Notations
646
2
23.4.2 Modeling and Metrics
648
1
23.4.3 No-Logging Pessimistic (NP) Scheme
649
1
23.4.4 No-Logging Lazy (NL) Scheme
650
1
23.4.5 No-Logging Trickle (NT) Scheme
650
1
23.4.6 Logging-Pessimistic (LP) Scheme
651
1
23.4.7 Logging-Lazy (LL) Scheme
652
1
23.4.8 Logging-Trickle (LT) Scheme
652
1
23.4.9 Results
652
5
23.4.10 Discussion
657
1
23.5 Conclusions
658
3
24 Fault Tolerance and Recovery in Mobile Computing Systems
661
36
24.1 Introduction
661
1
24.2 Distributed systems with mobile hosts
662
2
24.3 System architecture
664
1
24.4 Mobile applications
665
1
24.5 Fault-tolerance in mobile database platforms
666
8
24.5.1 Transaction Execution in Mobile Database Systems
666
2
24.5.2 Impact of mobility on transaction correctness
668
1
24.5.3 Transaction Correctness in Mobile Computing Systems
669
3
24.5.4 Recovery in Mobile Databases
672
2
24.6 Classes of solutions
674
8
24.6.1 The "Data-Broadcasting" Approach
675
1
24.6.2 The "proxy" approach
676
2
24.6.3 The "Disconnected" Approach
678
2
24.6.4 The "Distributed" Approach
680
2
24.7 Comparison
682
4
24.7.1 Qualitative Analysis
682
4
24.7.2 Fault tolerance and Recovery Issues
686
1
24.8 Performance evaluation of recovery techniques
686
6
24.9 Conclusions
692
5
25 Advanced Recovery Techniques in Practice
697
14
25.1 Introduction
697
3
25.1.1 Requirements for Log-Based Recovery
698
1
25.1.2 Why Recovery Is Difficult
698
1
25.1.3 The Choice of Log Operations
699
1
25.2 Standard Logged Operations
700
2
25.2.1 Physical Operations
700
1
25.2.2 Logical Operations
700
1
25.2.3 "Physiological" Operations
701
1
25.3 Multilevel Undo Recovery
702
4
25.3.1 Multilevel Transactions
702
1
25.3.2 B-Tree Need for Multilevel Recovery
702
1
25.3.3 Ordering Problems for B-Tree Restructuring
703
1
25.3.4 Solutions
704
2
25.4 More Powerful Redo Operations
706
3
25.4.1 Physiological Half-Split Operations
706
1
25.4.2 Multi-Page Half-Split Operations
707
1
25.4.3 Consequences for Cache Management
708
1
25.5 Discussion
709
2
26 Logging and Recovery in Commercial Systems
711
10
26.1 Introduction
711
1
26.2 IMS
711
4
26.2.1 Logging and its interaction with the system
712
1
26.2.2 Commit Behavior
713
1
26.2.3 Checkpoints
713
1
26.2.4 Relationship to Recovery and Restart
714
1
26.3 IMS Fast Path Feature
715
1
26.3.1 Logging and Its Interaction with the System
715
1
26.3.2 Commit Behavior
715
1
26.3.3 Checkpoints
716
1
26.3.4 Relationship to Recovery and Restart
716
1
26.4 Oracle
716
3
26.4.1 Logging and Its Interaction with the System
717
1
26.4.2 Commit Behavior
718
1
26.4.3 Checkpoints
718
1
26.4.4 Relationship to Recovery and Restart
718
1
26.5 Conclusions
719
2
27 The Recovery Manager of the System R Database Manager
721
28
27.1 Introduction
721
5
27.1.1 Application Interface to System R
721
2
27.1.2 Structure of System R
723
2
27.1.3 Model of Failures
725
1
27.2 Description of System R Recovery Manager
726
4
27.2.1 What Is a Transaction?
726
2
27.2.2 Transaction Save Points
728
2
27.2.3 Summary
730
1
27.3 Implementation of System R Recovery
730
11
27.3.1 Files, Versions, and Shadows
730
2
27.3.2 Logs and the DO, UNDO, and REDO Protocol
732
2
27.3.3 Commit Processing
734
1
27.3.4 Transaction UNDO
735
1
27.3.5 Transaction Save Points
735
1
27.3.6 System Configuration, Startup, and Shutdown
736
1
27.3.7 System Checkpoint
736
1
27.3.8 System Restart
737
2
27.3.9 Media Failure
739
1
27.3.10 Managing the Log
740
1
27.3.11 Recovery and Locking
741
1
27.4 Evaluation
741
8
27.4.1 Implementation Cost
741
1
27.4.2 Execution Cost
742
1
27.4.3 I/O Cost
742
1
27.4.4 Success Rate
742
1
27.4.5 Complexity
743
1
27.4.6 Disk-Based Log
743
1
27.4.7 Save Points
743
1
27.4.8 Shadows
744
2
27.4.9 Message Recovery, an Oversight
746
1
27.4.10 New Features
746
3
28 Implementing Crash Recovery in QuickStore: A Performance Study
749
31
28.1 Introduction
749
1
28.2 Challenges for recovery
750
1
28.3 Recovery strategies
751
9
28.3.1 Recovery in ESM
751
1
28.3.2 The Page-Differencing Approach
752
3
28.3.3 The Subpage-Differencing Approach
755
1
28.3.4 Enabling Recovery for Subpage-Differencing
756
1
28.3.5 The Whole-Page logging approach
757
1
28.3.6 Actions Performed at Clients
757
2
28.3.7 The Redo-at-Server Approach
759
1
28.3.8 Implementation Discussion
760
1
28.4 Performance experiments
760
3
28.4.1 OO7 Benchmark Database
760
2
28.4.2 OO7 Benchmark Operations
762
1
28.4.3 Software Versions
763
1
28.4.4 Hardware Used
763
1
28.5 Performance results
763
12
28.5.1 Unconstrained Cache Results
764
4
28.5.2 Constrained Cache Results
768
3
28.5.3 Big Database Results
771
4
28.6 Related work
775
2
28.7 Conclusions
777
3
29 Disk Array Striping
780
27
29.1 Introduction
781
2
29.2 Background and Previous Work
783
2
29.2.1 Nonredundant Disk Arrays (RAID Level O)
783
1
29.2.2 Block-Interleaved, Parity Disk Arrays (RAID Level 5)
784
1
29.3 Experimental Design
785
3
29.3.1 The Disk Model
785
1
29.3.2 The Workload
786
2
29.3.3 The RAID Simulator
788
1
29.3.4 Metrics
788
1
29.4 Choosing the Striping Unit
788
10
29.4.1 Knowing Concurrency
792
4
29.4.2 Not Knowing Concurrency
796
2
29.5 Varying the Number of Disks
798
1
29.6 Verification Using Traces
799
4
29.7 Conclusions
803
4
30 RAID5 Disk Arrays and Their Performance Evaluation
807
40
30.1 Introduction
808
2
30.2 RAID5 Disk Arrays
810
7
30.3 Overview of Analytical and Simulation Studies
817
3
30.4 Modeling Assumptions and Parameters
820
5
30.5 Analytic Results
825
6
30.5.1 Analysis of M/G/1 Queueing Systems
825
2
30.5.2 Analysis of the Vacationing Server Model for M/G/1
827
2
30.5.3 Analysis of Fork-Join Requests
829
2
30.6 Analysis of RAID5 in Normal and Degraded Modes
831
2
30.7 Analysis of RAID5 in the Rebuild Mode
833
4
30.8 Conclusions from Numerical Studies
837
2
30.9 Conclusions and Future Work
839
8
31 A Performance Comparison of RAID5 and Log-Structured Arrays
847
34
31.1 Introduction
848
1
31.2 RAID-5 Performance Analysis
849
3
31.2.1 Analysis of Cached RAIDs
850
2
31.3 Parameters Used in Performance Comparisons
852
2
31.3.1 Disk, Controller, and Channel Parameters
852
1
31.3.2 Workload Parameters
853
1
31.4 Importance of Destage Assumptions in Cached RAID Performance
854
1
31.5 Compression in RAID Subsystems
855
12
31.5.1 Overview of LSA
856
3
31.5.2 Seek Affinity and Skew in LSA
859
1
31.5.3 A Performance Model of LSA
860
1
31.5.4 Calculating the Garbage-Collection Rate
861
3
31.5.5 LSA Performance Results
864
2
31.5.6 Effect of Compression Ratio.
866
1
31.5.7 RAID5 with Compression in Cache
866
1
31.6 RAID5 Versus LSA
867
7
31.6.1 Comparison on an IMS-like Workload
869
4
31.6.2 Comparison on a Workload with Flat Skew
873
1
31.7 Conclusions
874
7
Selected Biography
881